El que pierde, gana

Para ganar en la versi¨®n lineal del Nim (en la que pierde el que se lleva el ¨²ltimo palillo), de cuyas variantes nos ocupamos la semana pasada, hay que dejarle al otro jugador 5 palillos, con lo que, coja los que coja, le dejaremos el ¨²ltimo. Y para poder dejarle 5, antes hay que dejarle 9, y antes 13, y antes 17¡­ O sea, quien se encuentre con 4n + 1 palillos pierde seguro (siempre que el otro haga las jugadas correctas, se entiende). Por lo tanto, si se parte de una fila de 20 palillos, gana el primer jugador retirando 3 y dejando 17.

Las variantes con varias filas de palillos son m¨¢s complicadas; pero solo aparentemente, pues en realidad existe una forma muy sencilla de averiguar si una posici¨®n es ganadora o perdedora, que fue descubierta a principios del siglo pasado por el matem¨¢tico estadounidense Charles L. Bouton (tambi¨¦n responsable de llamar Nim al juego), cuyo an¨¢lisis pionero se considera el origen de la teor¨ªa de juegos combinatorios (CGT, seg¨²n las siglas en ingl¨¦s), cuyo objeto de estudio son los juegos secuenciales con informaci¨®n perfecta (es decir, en los que los jugadores conocen en todo momento el estado del juego y todos los movimientos posibles).

Bouton demostr¨® que para determinar si una posici¨®n era ganadora o perdedora, bastaba con escribir el n¨²mero de palillos de cada fila en notaci¨®n binaria: si todas las columnas suman 0 o par, la posici¨®n es ganadora; de lo contrario, no.

Supongamos que partimos de tres filas con 5, 4 y 3 palillos respectivamente:

I I I I I

I I I I

I I I

Poniendo 5, 4 y 3 en n¨²meros binarios:

101

100

11

212

La primera columna suma 2, la segunda 1 y la tercera 2, y puesto que hay una suma impar, la situaci¨®n es perdedora. Y, efectivamente, el primer jugador consigue una posici¨®n ganadora quitando dos palillos de la tercera fila, y, si juega correctamente, tiene la victoria asegurada, haga lo que haga el otro.

El Nim es, por tanto, e independientemente de cu¨¢ntas filas y de cu¨¢ntos palillos haya en cada fila, un juego de estrategia segura. No todos los juegos secuenciales con informaci¨®n perfecta lo son (o al menos no podemos estar seguros de que lo sean), pues a partir de un cierto grado de complejidad escapan a nuestras posibilidades de c¨¢lculo. Es el caso del ajedrez: su combinatoria es tan enorme (del orden de los septillones) que, aunque algunos especialistas creen que la ¡°partida perfecta¡± acabar¨ªa en tablas, no podemos asegurarlo.

¡®Antichess¡¯

Y hablando del ajedrez y de otro juego secuencial con informaci¨®n perfecta ¡ªel Nim¡ª en el que, seg¨²n las variantes, lo que en una es ganar (llevarse el ¨²ltimo palillo) en la otra es perder, no se puede dejar de mencionar el antichess o ajedrez pierde-gana, una modalidad muy popular en la que el objetivo es perder todas las piezas o quedar ahogado. Como en la famosa novela de Graham Green, el que pierde, gana. Las reglas son las mismas que las del ajedrez convencional, con algunas excepciones:

*La captura es obligatoria (como en las damas). Si hay m¨¢s de una captura posible, el jugador puede elegir la que m¨¢s le convenga.

*El rey es una pieza m¨¢s que se puede capturar como cualquier otra, y, por tanto, no hay jaque, ni jaque mate, y tampoco enroque. Consiguientemente, un pe¨®n que corona tambi¨¦n puede convertirse en rey.

*Un jugador ahogado, es decir, que no puede efectuar ning¨²n movimiento l¨ªcito, gana la partida.

Huelga decir que las partidas de antichess son muy distintas de las de ajedrez convencional (?qu¨¦ aperturas te parecen buenas y cu¨¢les no?). Y los problemas tambi¨¦n, como comprobar¨¢s si intentas resolver el de la figura: negras juegan y ganan (es decir, pierden). Parece f¨¢cil perder-ganar con un solo pe¨®n, pero¡­