El clásico juego de estrategia del Othello, en algunos sitios también llamado Reversi o Yang, ya ha sido resuelto pese a lo inabarcable que parecía resultar computacionalmente. En total se había calculado que el Othello tenía unas 1058 posibles partidas y 1028 posiciones válidas. Siguiendo el algoritmo marcado por la solución, y jugando sin errores por ninguno de los jugadores, el resultado acaba en tablas.
El trabajo completo, publicado en arXiv, tiene un título tan sucinto como directo: Othello is Solved («El Othello está resuelto») y está firmado por Hiroki Takizawa. Para el desarrollo de la solución hubo que comprobar más posibles partidas que para el juego de las damas (que desde 2007 está resuelto) del que se estiman existen unas 1020 posiciones posibles. En el caso del Othello, como en el del ajedrez –que está mucho más lejos, del orden de 10120– no se conoce el valor exacto, pero se aproximó considerando partidas de unos 58 movimientos en total, con 10 posibles opciones para cada movimiento.
Una partida óptima sin fallos que conduce a las tablas
En realidad no hizo falta probar todas las posiciones; utilizando una base de datos de partidas conocidas y una lista de unas 2.600 posiciones clave, transposiciones y simetrías la cosa pudo simplificarse bastante, pues se demostró que todas ellas llevaban a las tablas. En el diagrama 2 se puede ver el orden de la partida óptima en el que cualquier desviación por parte de uno de los jugadores de los movimientos marcados lleva al otro a ganar o forzar las tablas. No es algo que se pueda abarcar «humanamente» pero sí en la memoria de un ordenador.
El autor ha publicado el código con el que se ha hecho todo trabajo para quien quiera juguetear, comprobar o ampliar.
§
Como nota personal, recuerdo haber programado un Othello en varias versiones en la época de los Commodore, en una versión que jugaba razonablemente bien y que era capaz de luchar por estrategias óptimas como son ocupar las esquinas, los laterales y algunas casillas clave. Me asombró (dentro de lo que cabe) ganándome alguna vez, y desde luego ganando a gente que sabía menos del juego que yo.
Se puede jugar al Othello online en muchas páginas web; la de eOthello no está mal y tiene un nivel aceptable, aunque se le puede ganar.
Relacionado:
