¿Se ha resuelto 'Othello'?
(arxiv.org)- Se ha demostrado computacionalmente que en Othello/Reversi de 8×8, cuando ambos lados juegan de forma perfecta, el resultado final es empate, por lo que según los investigadores ha alcanzado un estado de resolución débil
- El espacio de búsqueda era tan grande —se estima en unos 10^58 registros de partida posibles y unas 10^28 posiciones de tablero— que seguía siendo un problema mucho más difícil que casos resueltos previamente como checkers
- Este resultado obtuvo el valor teórico del juego de la posición inicial y una estrategia para alcanzar ese valor, pero no constituye una resolución fuerte que calcule todas las posiciones intermedias
- Los investigadores explican que utilizaron búsqueda heurística basada en software de Othello y alpha-beta search, y que la escala de búsqueda necesaria para una solución exacta fue menor de lo que se había predicho
- Los datos originales y programas para reproducir el resultado fueron publicados en GitHub, Zenodo y figshare, por lo que pueden usarse como un caso verificable de investigación sobre la resolución de juegos de estrategia pura
Resolución computacional de Othello
- Othello en tablero de 8×8 fue resuelto débilmente, y el valor teórico del juego de la posición inicial se calculó como empate
- Si ambos bandos juegan de manera óptima y sin errores, el resultado es un empate, y esta investigación lo demostró computacionalmente
- La Figure 1 presenta una línea de juego óptima y el resultado final
- Si en esa secuencia se produce una desviación en cualquier momento, el software de los investigadores garantiza como rival un empate o una victoria
- Este resultado coincide con el empate que expertos humanos de Othello habían anticipado, por lo que los investigadores consideran que el resultado en sí no es sorprendente
Alcance de la resolución y valor teórico del juego
- Resolver un juego de información perfecta significa determinar el resultado final cuando ambos lados realizan juego perfecto, es decir, el valor teórico del juego
- Los juegos resueltos suelen clasificarse en tres niveles
- Resolución ultra-débil (ultra-weakly solved): solo se conoce el valor teórico del juego de la posición inicial
- Resolución débil (weakly solved): se conoce el valor teórico del juego de la posición inicial y una estrategia para que ambos lados alcancen ese valor dentro de recursos computacionales razonables
- Resolución fuerte (strongly solved): se calcula el resultado de todas las posiciones posibles que pueden surgir durante la partida
- Esta investigación presenta un caso en que Othello fue resuelto débilmente, no una resolución fuerte que calcule todas las posiciones posibles
- Checkers también se presenta como un juego resuelto débilmente en ese mismo sentido
Por qué Othello permaneció sin resolverse durante tanto tiempo
- Othello es un juego popular de gran profundidad estratégica: fue inventado en la Inglaterra del siglo XIX, y su forma actual se difundió ampliamente en Japón durante el siglo XX antes de expandirse por todo el mundo
- El campeonato mundial se celebra cada año desde 1977, lo que muestra su popularidad global
- El espacio de búsqueda es enorme
- En promedio, alrededor de 10 movimientos por posición
- En promedio, unas 58 jugadas por partida completa
- Aproximadamente 10^58 registros de partida posibles
- Aproximadamente 10^28 posiciones de tablero posibles
- Se plantea que esta escala es mucho mayor que la de juegos difíciles ya resueltos hasta ahora, en particular checkers
- Debido a ese gran espacio de búsqueda, Othello había permanecido como un reto de largo plazo en ciencias de la computación
Método de búsqueda y eficiencia computacional
- Los investigadores utilizaron alpha-beta search con el objetivo de lograr una resolución débil
- Los algoritmos de resolución de juegos varían según el objetivo y la naturaleza del juego
- Para resolución débil se usa con frecuencia alpha-beta search
- Para resolución fuerte suele utilizarse retrograde analysis
- Para rompecabezas con secuencias de solución muy largas se han desarrollado métodos como df-pn search
- Alpha-beta search es un algoritmo que recorre secuencialmente el grafo del juego en profundidad, por lo que no es fácil aumentar mucho la eficiencia de búsqueda solo con paralelización simple
- Se han investigado varios métodos para búsqueda en paralelo
- En entornos de memoria compartida, YBWC y Lazy SMP son métodos populares
- En entornos de memoria distribuida, APHID y ABDADA se presentan como algoritmos relacionados
- En entornos de memoria distribuida, condiciones como el ancho de banda y la latencia entre nodos varían mucho, por lo que los desarrolladores pueden tener que elegir un algoritmo adecuado para su entorno o desarrollar uno nuevo
- Incluso usando clústeres de computación modernos, resolver Othello era una gran barrera, y el avance vino de modificar software moderno de Othello para mejorar la eficiencia de búsqueda
Otros juegos resueltos y posibilidades de uso
- Como el caso más reciente de un problema difícil resuelto antes de Othello, se menciona checkers
- También se enumeran como casos resueltos juegos no triviales como Connect Four, Qubic, Go-Moku, Nine Men’s Morris y Awari
- La dificultad de resolver un juego suele depender en gran medida del número de posiciones o situaciones dentro del juego
- Resolver un juego no solo sirve para revelar el resultado final, sino que también puede aprovecharse para la generación de rompecabezas basada en ese juego
- Los investigadores ofrecen los datos originales y programas para reproducibilidad en GitHub, Zenodo y figshare
1 comentarios
Opiniones en Hacker News
Dice que “eligieron 2,587 posiciones de entre 2,958,551, plantearon una hipótesis sobre el resultado, y si todas esas hipótesis son correctas, eso demuestra que la posición inicial es un empate”, pero no da una explicación más detallada.
Suena menos a que el juego se haya resuelto por completo, y más a que el autor buscó con bastante empeño una secuencia ganadora pero no la encontró.
Dice: “Hay muchas formas de elegir un subconjunto que pueda demostrar que la posición inicial es un empate, pero con el Algorithm 1 obtuvimos un subconjunto pequeño”.
El Algorithm 1 se describe como algo que recibe las puntuaciones previstas de todas las posiciones con 50 casillas vacías y devuelve un subconjunto tal que, si todas las posiciones de ese subconjunto se resuelven y sus soluciones coinciden con las predicciones, entonces la posición inicial también queda resuelta como consecuencia.
En general, la exposición del paper no es intuitiva. Puede que el autor tenga razón, pero creo que habría que sentarse bien a seguir la lógica; mi primera impresión es escéptica.
Hay demostraciones de este tipo en otros casos. Por ejemplo, el teorema de los cuatro colores también se redujo a un número finito de configuraciones y luego se coloreó a mano.
El script de https://github.com/eukaryo/reversi-scripts/blob/main/reversi... juega de forma perfecta bajo el supuesto de que todo eso es correcto. Otros scripts del repositorio usan datos calculados a partir de soluciones de posiciones con 36 casillas vacías, y eso parece factible incluso en una máquina común.
En esencia, parece una estructura que consulta una tabla de menos de 300 GB con todas las posiciones de 37 a 64 casillas vacías alcanzables desde la solución débil, y resuelve con
-solvede edax las posiciones con 36 casillas vacías o menos.Othello es un buen juego para mostrar cuán fuerte puede volverse algo usando solo heurísticas básicas.
A medida que avanza la partida, hay casillas donde nunca debes jugar, y otras donde, si puedes, definitivamente debes jugar.
Con solo implementar esas reglas ya se obtiene un rival bastante decente, y es interesante ver lo rápido que la gente atribuye “inteligencia” incluso a cosas muy simples.
Decía que enfrentaron una app que usaba heurísticas simples parecidas contra otra app con una estrategia igual de simple pero terriblemente mala de “voltear la mayor cantidad posible”.
El algoritmo heurístico ganó por paliza; recuerdo algo como 60 a 4, o incluso peor.
Cuando quedaban 19 casillas vacías, resolvía por completo el resto de la partida, y era bastante impresionante.
Othello era un juego que incluso venía en consolitas LCD de 10 dólares con dos pilas AA.
Si te interesan los juegos, el Campeonato Mundial de Othello, que también es popular entre investigadores de ciencias de la computación e inteligencia artificial, se está realizando ahora en Roma, Italia.
Las partidas se transmiten en vivo en liveothello.com y en YouTube @WorldOthello.
Me pregunto si Othello, como las damas, es un juego en el que la mayoría de las partidas de alto nivel terminan en empate.
Genial.
Hace unos 15 años resolví un juego más simple que jugaba con mi hermano. Era un juego africano con unos 10 hoyos a cada lado del tablero y piedras dentro.
Escribí un motor alfa-beta y encontró una estrategia que siempre ganaba, ridícula pero adaptada a la forma en que jugábamos. Después de eso empecé a ganar todas las partidas de golpe, y mi hermano nunca volvió a querer jugar conmigo. Fue el duelo típico entre un científico de la computación y un optometrista.
Hay mucho que aprender viendo jugar Mancala a personas africanas mayores. Juegan rapidísimo, y también se siente un poco como póker, donde el engaño forma parte del juego.
Si repartes las piedras lo suficientemente rápido, puedes saltarte un recipiente o dejar caer una piedra extra para sacar ventaja.
Yo no soy tan hábil y juego con mi familia, así que no hago trampa. Aun así, se vuelve un juego muy distinto. Es como la diferencia entre señoras británicas jugando Mahjong lentamente mientras toman té y jugarlo apostando dinero en un casino chino.
Si ganas demasiado o pierdes demasiado, dejas de disfrutar el juego.
Pero no sé qué relevancia tiene aquí la profesión de optometrista.
¿Esto es real? Me parece un poco raro que haya un solo autor y que esté afiliado a una startup de deep learning de la que nunca había oído hablar.
Supongo que estará en proceso de revisión por pares, ¿no?
Además, Othello no está exactamente al nivel de la hipótesis de Riemann. Probablemente se había investigado menos, y quizá todavía quedaba alguna fruta baja al alcance.
Othello es uno de esos juegos realmente buenos para jugar con niños pequeños.
Las reglas son simples, hay patrones que vale la pena aprender y también está la diversión de voltear muchas piezas de golpe. Sobre todo, es igual de divertido no solo para niños, sino también para adultos.
Pude disfrutarlo bastante sin abrumar a un niño de 6 años y sin que se sintiera como un simple juego de pura suerte.
https://mancala.fandom.com/wiki/Hus
En teoría no hay azar, pero en la práctica las reacciones en cadena impiden calcular tan lejos.
El tablero se puede hacer fácilmente en casa.
Si quieren probar el juego, subí uno que hice con mis hijos: https://jawj.github.io/fliptiles
El jugador de “AI” es muy débil.
Aprendí un juego nuevo.
La computadora sacó 33 puntos y yo 31.
Si creen que Othello es trivial, prueben Zebra.
Sitio web del autor original: http://radagast.se/othello/
Código fuente en GitHub: https://github.com/hoshir/zebra
Lo que me gusta de Othello es la contradicción entre acción y territorio.
Durante la partida, el acto de hacer una jugada en mi turno, en cierto sentido, me perjudica, pero aun así estoy obligado a jugar.
Por eso, hasta que el espacio se reduzca demasiado y llegue el momento en que haya que recuperar una influencia clara, conviene ocupar territorio manteniéndose pequeño y hacia el interior.
Relacionado con esto, también está jugar Reversi 6x6 de forma perfecta.
https://mame.github.io/6x6-reversi-oracle/
Fuente: https://twitter.com/mametter/status/1476379841004183556
No sabía hasta ahora que el 8x8 todavía no estaba resuelto.