miércoles, 27 de marzo de 2013

ZERMELO SOBRE EL AJEDREZ

Ernst Zermelo (1871-1953), matemático alemán, fue uno de los creadores de la teoría axiomática de conjuntos. La axiomática conjuntista más usada hoy lleva el nombre de ZF por Zermelo y Fraenkel, o ZFC si se añade a ZF el axioma de elección, que Zermelo utilizó en un famoso artículo de 1908 para demostrar que todo conjunto puede ser bien ordenado; en ese mismo año, Zermelo propuso la primera versión de lo que evolucionaría gracias a Fraenkel y Skolem hasta convertirse en la teoría ZFC. Hoy se reconoce además que Zermelo había descubierto en Gotinga antes que Russell la conocida paradoja del conjunto de todos los conjuntos que no se pertenecen a sí mismos. En 1913 apareció el artículo de Zermelo sobre el ajedrez que traducimos, en el que suele considerarse que demuestra el llamado ‘teorema de Zermelo’ sobre teoría de juegos, considerado el primer teorema de esa disciplina matemática.

De las versiones del teorema, una de las más sencillas dice: en un juego finito, de información perfecta, en el que se enfrentan dos jugadores y en el que no interviene el azar, o bien un jugador tiene una estrategia ganadora o bien ambos tienen una estrategia que les permite forzar tablas. En efecto, Zermelo construye en el artículo dos conjuntos de continuaciones del juego a partir de una posición dada q: uno, que puede ser vacío, ofrece a las blancas una estrategia ganadora a partir de q; si ese conjunto es vacío, existe otro, quizá vacío, que permite a las blancas forzar tablas; si este segundo conjunto también es vacío, las negras tienen una estrategia ganadora a partir de q y las blancas no pueden más que demorar la derrota hasta un número máximo de movimientos. Como la misma situación se da para las negras, las alternativas posibles son que las blancas tengan una posición ganadora, que la tengan las negras o que ambos jugadores puedan forzar tablas.

Dadas las características del juego, el teorema es casi trivial. Tiene, sin embargo, el mérito de haber inaugurado la teoría de juegos, que habría de convertirse en una rama floreciente de las matemáticas gracias al trabajo de matemáticos como el famoso John Nash, Morgenstern o Von Neumann.

SOBRE UNA APLICACIÓN DE LA TEORÍA DE CONJUNTOS A LA TEORÍA DEL AJEDREZ

Ernst Zermelo

Las consideraciones siguientes son independientes de las reglas concretas del juego del ajedrez y valen en principio para cualquier juego intelectual no de azar semejante, en el que se enfrentan dos jugadores. Pero, por mor de concreción, preferimos ejemplificar aquí con el ajedrez, siendo éste el juego más conocido de este tipo. No se trata de exponer aquí un método para la práctica del juego sino de contestar a esta pregunta:

¿Puede determinarse de manera matemáticamente objetiva el valor que una posición posible en el juego tiene para uno de los jugadores y puede determinarse, o al menos definirse, cuál es el mejor movimiento posible para él sin recurrir a construcciones con matiz psicológico y subjetivo como la del ‘jugador perfecto’?

Que esto es posible al menos en algunos casos lo revelan esos problemas de ajedrez, es decir, ejemplos de posiciones, en los que cabe demostrar que el jugador que mueve puede forzar el mate en un número predeterminado de movimientos. Creo que merece la pena investigar si una tal valoración de la posición es teóricamente concebible y tiene sentido también en aquellos casos en los que el análisis de la situación encuentra un obstáculo, insalvable en la práctica, en el elevado número de las posibles continuaciones del juego. Y creo que esta averiguación es necesaria para sentar el fundamento de la teoría de los finales de juego y de las aperturas, tal como se encuentra expuesta en los libros de enseñanza del ajedrez. El método utilizado en las líneas que siguen para la solución de ese problema se ha tomado de la teoría de conjuntos y del cálculo lógico, y revela la utilidad de esas disciplinas matemáticas también en casos que involucran solamente totalidades finitas.

Como el número de escaques y de piezas es finito, es también finito el conjunto P de las posiciones posibles p0, p2, p3, …, pt, entre las que dos posiciones por lo demás iguales deben distinguirse también atendiendo a cuál es el jugador al que toca mover, a si uno de los bandos ha enrocado ya, a si algún peón ha coronado, etc. Sea entonces q una de esas posiciones; para q hay un conjunto Q de finales posibles fq, es decir, un conjunto de secuencias (q, q1, q2,…) de posiciones que, partiendo de q, suceden unas a otras de acuerdo con las reglas del juego, de tal manera que cualquier posición qn de entre esas sucede a la posición qn-1 a través de un movimiento permitido de las blancas o las negras. Cada uno de esos finales de juego fq termina en una posición de mate o de ahogado[1], o, al menos teóricamente, continúa indefinidamente y en este caso el resultado de la partida tendría que considerarse indeterminado o sería tablas (remis). El conjunto Q de todos esos posibles finales de juego fq que parten de q es un subconjunto, finito o infinito, pero bien definido, del conjunto Pa que contiene todas las secuencias enumerables de elementos p del conjunto P.

Algunos de esos finales de juego fq pueden conducir a la victoria de las blancas en no más de r movimientos (entendiendo por ‘movimiento’ el paso de una posición pn-1 a una posición pn, es decir una media jugada, no una jugada completa), aunque en general esto dependerá de cómo jueguen las negras. Pero ¿cómo debe ser una posición q para que las blancas puedan forzar el mate en no más de r movimientos, con independencia de cómo jueguen las negras? Afirmo que la condición suficiente y necesaria para eso es la existencia de un subconjunto no vacío Sr(q) del conjunto Q tal que:

1. Todos los elementos fq del conjunto Sr(q) terminan con la victoria de las blancas en no más de r movimientos, de tal manera que cada secuencia fq contiene como mucho r términos, lo que implica que Sr(q) es siempre finito.

2. Si fq = (q, q1, q2, …) es un elemento cualquiera de Sr(q) y si qn es un término cualquiera de fq, que se da tras un movimiento de las negras y que será un término par o impar de fq según quién juegue en q, y si, finalmente, q’n es una variante posible, porque las negras desde qn-1 podrían jugar tanto qn como q’n, entonces Sr(q) contiene al menos un elemento fq’n = (q, q1, …, qn-1, q’n, …), que tiene en común con fq los primeros n términos. De hecho, en ese y solo en ese caso, pueden las blancas empezar con un elemento cualquiera fq de Sr(q) y, si las negras juegan q’n en vez de qn, contestar con un correspondiente q’n+1[1] que asegure su victoria en no más de r movimientos.

Ciertamente, puede haber más de un conjunto Sr(q) pero la unión de cualquier par de ellos cumplirá las condiciones 1 y 2, y también lo hará la unión U(Sr(q)) de todos ellos, que está bien definida por r y q, y que será diferente de Ø, es decir, que tendrá al menos un elemento, con tal que de que realmente exista un Sr(q). En consecuencia, que U(Sr(q)) ≠ Ø es la condición necesaria y suficiente para que las blancas puedan asegurarse la victoria a partir de q en no más de r movimientos. Si r< r’, entonces U(Sr(q)) es subconjunto de U(Sr’(q)), puesto que todo conjunto Sr(q) satisface las condiciones impuestas a los conjuntos Sr’(q), de modo que debe estar incluido en U(Sr’(q)); y si m es el menor número para el que U(Sm(q)) ≠ Ø, entonces S*(q) = U(Sm(q)) es la intersección de todos los U(Sr(q)) y contiene todas aquellas continuaciones del juego a partir de q que permiten a las blancas ganar en un número mínimo de movimientos. Para esos valores mínimos m = mq hay un valor máximo T≤ t, que depende de q y donde t+1 el número de todas las posiciones posibles, de modo que la condición necesaria y suficiente para que exista algún Sr(q) no vacío y las blancas puedan asegurarse la victoria a partir de q es que U(ST(q)) ≠ Ø. Si desde una posición q es posible forzar la victoria, entonces, como vamos a mostrar, es posible hacerlo en no más de t movimientos. De hecho, todo final fq = (q, q1, q2, …, qn) con n > t contiene una posición qa = qb repetida y las blancas podrían haber jugado la primera vez que esa posición se dio tal como lo hacen en la segunda y así haber ganado en menos de n movimientos; por tanto, m ≤ t.

Si, en cambio, S(q) = Ø, entonces las blancas pueden como mucho, si juegan bien, conseguir tablas pero también podrían estar en una posición perdedora y entonces solamente podrían intentar demorar el mate todo lo posible. Si las blancas tienen la posibilidad de aguantar hasta el j-ésimo movimiento, entonces tiene que haber un subconjunto Zj(q) de Q tal que

1. En ninguno de los finales contenidos en Zj(q) pierden las blancas antes del j-ésimo movimiento.

2. Si fq es un elemento cualquiera de Zj(q) y en fq la posición qn puede ser reemplazada por la posición q’n como consecuencia de un movimiento permitido de las negras, entonces Zj(q) contiene al menos un elemento de la forma

fq’n = (q, q1, q2 …, qn-1, q’n, …),

que tiene en común con fq[3] los primeros n-1 elementos y después continúa con q’n. También los conjuntos Zj(q) son todos subconjuntos de su unión U(Zj(q)), que queda unívocamente determinada por j y q, y que tiene la misma propiedad que Zj, y para cada j < j’, es U(Zj(q)) subconjunto de U(Zj’(q)). Para los números j para los que U(Zj(q)) es diferente de Ø vale que o bien carecen de máximo o bien j ≤ J[4] ≤ T ≤ t, dado que el contrario, si puede asegurarse la victoria, debe poder hacerlo en no más de T movimientos. Así, las blancas pueden asegurarse tablas si y solo si U(ZT+1(q)) ≠ Ø. Si no pueden asegurarse tablas, entonces pueden, mediante Z*(q) = U(ZJ(q)), retrasar la derrota al menos durante J ≤ T movimientos. Como todos los conjuntos Sr(q) satisfacen las condiciones impuestas a los conjuntos Zj(q), el conjunto U(Sr(q)) es subconjunto de U(Zj(q)) y S(q) es subconjunto de Z(q). El resultado de nuestras consideraciones es, por tanto, el siguiente:

A cada posición posible del juego corresponden dos conjuntos bien definidos S(q) y Z(q), subconjuntos del conjunto Q de todos los finales de juego que empiezan con q, y de esos dos el primero es subconjunto del segundo. Si S(q) es distinto de Ø, entonces las blancas pueden forzar su victoria con independencia de cómo jueguen las negras y pueden hacerlo en no más de m movimientos por medio de un subconjunto Sm(q) de S(q) pero no pueden hacerlo con seguridad en menos movimientos. Si S(q) = Ø pero Z(q) ≠ Ø, entonces las blancas pueden al menos hacer tablas mediante los finales de juego contenidos en Z(q). Cuando Z(q) es vacío, las blancas, si el contrario juega bien, pueden solamente demorar la derrota hasta el J-ésimo movimiento mediante un conjunto bien definido Z*(q) de continuaciones del juego. En cualquier caso, solamente las partidas contenidas en S*(q) o Z*(q) pueden considerarse ‘correctas’ desde el punto de vista de las blancas; mediante cualquier otra continuación, las blancas, si están en posición ganadora, dejarían escapar o demorarían la victoria, si el contrario juega bien; y si no están en posición ganadora, harían posible o acelerarían su derrota. Para las negras valen observaciones enteramente análogas y las partidas que deberían contar como partidas jugadas correctamente hasta el final a partir de q son las que satisfacen simultáneamente las condiciones de cada bando, y éstas forman un subconjunto bien definido W(q) de Q.

Los números t y T son independientes de la posición y quedan determinados solo por las reglas del juego. A cada posición del juego corresponde un número m = mq o un número J = Jq, ninguno mayor que T, según sea que las blancas pueden forzar su victoria en m movimientos, pero no en menos, o que pueden hacerlo las negras en J pero no en menos movimientos. La teoría específica de este juego debería calcular esos números o al menos delimitar sus valores entre unos mínimos y unos máximos, lo que hasta ahora no se ha conseguido más que en los ‘problemas de mate en n jugadas’ o en los finales de partida propiamente dichos. La cuestión de si la posición inicial p0 es ya una posición ganadora para alguno de los bandos es por ahora un problema abierto. Si se le diera una solución rigurosa, entonces ciertamente el ajedrez perdería su condición de juego.

Zermelo, E. 1913. Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels, Proc. Fifth Congress Mathematicians, (Cambridge 1912), Cambridge University Press 1913, pp. 501-504.

Texto original según

http://www.socio.ethz.ch/publications/spieltheorie/klassiker/Zermelo_Uber_eine_Anwendung_der_Mengenlehre_auf_die_Theorie_des_Schachspiels.pdf

Traducción de Laureano Luna Cabañero.

[1] ‘Ahogado’ o ‘rey ahogado’ denota la situación en la que un jugador, cuyo rey no está en jaque, no puede hacer ninguna jugada permitida, lo que da lugar a tablas. N. del T.

[2] En el original no aparece el ‘+1’, lo que debe de ser una errata. N del T.

[3] En el original aparece ‘q’, lo que seguramente es una errata. N del T.

[4] Debe entenderse que J es el máximo de los números j como T es el máximo de los números t. N del T.

No hay comentarios:

Publicar un comentario