CIUDAD DE MÉXICO (apro).- Los juegos de mesa han sido por muchos años, una cama de prueba para los científicos. El ajedrez ha sido estudiado, por ejemplo, de forma exhaustiva y hoy contamos incluso con redes neuronales que juegan mejor que el Campeón Mundial de la especialidad. Estas mismas redes neuronales nos están incluso enseñando cómo ganar en otros juegos que desde siempre han sido una interrogante sobre si uno de los jugadores puede siempre ganar o bien, si haciendo las mejores jugadas, se llega a la nulidad, al empate.
En la Teoría de Juegos tenemos el Othello o Reversi, un juego de mesa que apareció como un programa de computadora desde las primeras versiones de Windows. Se trata de un tablero cuadriculado en donde hay discos blancos y negros. Cuando dos discos de un color se intersectan, ponen todos los discos de ese color. En el turno del adversario puede hacer lo equivalente.
Quien haya jugado Reversi recordará que el control de las esquinas es fundamental. En ocasiones, parece que un jugador tiene pocas fichas de su color, pero si domina las esquinas, eventualmente puede darle vuelta a la tortilla (literalmente), y ganar. Este pasatiempo es interesante de programar y hay un sinfín de versiones del mismo. Lo que es más difícil de encontrar es demostrar lo que hoy ya sabemos, que jugando de forma perfecta, el juego es un empate. Esto se hizo gracias al uso del algoritmo “poda alfa beta”.
a poda alfa beta se usa tradicionalmente en los juegos de suma-cero (donde la ventaja de uno es exactamente la desventaja del rival y por ende, la suma de la ventaja y desventaja siempre da cero), y de información perfecta, es decir, que todo lo que pasa en el tablero lo pueden ver los jugadores. No hay secretos, pues.
Por ejemplo, el gato es un juego que es un empate si ambos jugadores juegan de manera perfecta. El connect-4, que es similar al gato, es más difícil de resolver, pues en una malla de 6×7 hay 4,531,985,219,092 posiciones posibles. Sin embargo, en 1988 se resolvió y se encontró que el jugador que e pieza puede forzar el triunfo, aunque su rival juegue perfecto. Las damas se resolvieron en el 2007 y es un empate. Y ojo, este juego tiene unos 500 mil millones de posiciones que hay que analizar.
Pero regresando al Reversi, en un artículo de Hiroki Takizawa, titulado “El Othello está resuelto” (https://arxiv.org/abs/2310.19387), el cual puede generar una cantidad de posiciones de alrededor de 10 a la potencia 58, indica el investigador que el juego es un empate. Este es el juego con más posiciones posibles que ha sido resuelto.
Takizawa construyó la poda alfa beta a partir de un programa de código abierto de Othello, llamado Edax (https://github.com/abulmo/edax-reversi), en donde jugando perfectamente bien, se empata en 36 movimientos. Esto es el resultado óptimo, el cual el investigador obtuvo usando cómputo masivo de las computadoras de la empresa Preferred Networks, que en sus políticas permiten que sus trabajadores usen 20% del tiempo de su trabajo para explorar sus propias ideas. Así, la empresa le permitió usar un clúster de supercomputadoras MN-J, la cual estuvo catalogada como la computadora más poderosa del planeta (2020).
Referencias: https://www.i-programmer.info/news/112-theory/16745-othello-solved-its-a-draw.html