Hispanopedia WikiEl término "Othello informático" se refiere a la arquitectura informática que abarca el hardware y el software capaces de jugar al Othello . Una versión de Othello se incluyó en Microsoft Windows desde la versión 1.0 hasta la XP , donde se la conoce simplemente como Reversi.
Disponibilidad
Existen numerosos programas de Othello, como NTest , Saio, Edax , Cassio, Pointy Stone, Herakles, WZebra y Logistello , que se pueden descargar gratuitamente de Internet . Estos programas, al ejecutarse en cualquier ordenador moderno , permiten jugar partidas en las que los mejores jugadores humanos son fácilmente derrotados. Esto se debe a que, si bien las consecuencias de los movimientos son predecibles tanto para ordenadores como para humanos, los ordenadores son mejores explorándolas. [ 1 ]
Técnicas de búsqueda
Los programas informáticos de Othello buscan todas las jugadas legales posibles mediante un árbol de juego . En teoría, examinan todas las posiciones/nodos, donde cada movimiento de un jugador se denomina "jugada" . Esta búsqueda continúa hasta alcanzar una profundidad máxima determinada o hasta que el programa determine que se ha llegado a una posición final ("hoja").
Una implementación ingenua de este enfoque, conocida como Minimax o Negamax , solo puede buscar a una profundidad pequeña en un tiempo práctico, por lo que se han ideado varios métodos para aumentar considerablemente la velocidad de búsqueda de buenos movimientos. Estos se basan en la poda alfa-beta , Negascout , MTD(f) y NegaC*. [ 2 ] El algoritmo alphabeta es un método para acelerar la rutina de búsqueda Minimax podando los casos que no se utilizarán de todos modos. Este método aprovecha el hecho de que cada dos niveles en el árbol maximizarán y cada dos niveles minimizarán. [ 3 ]
También se utilizan varias heurísticas para reducir el tamaño del árbol buscado: buen ordenamiento de movimientos, tabla de transposición y búsqueda selectiva. [ 4 ]
Para acelerar la búsqueda en máquinas con múltiples procesadores o núcleos, se puede implementar una "búsqueda paralela" . Se han realizado varios experimentos con el juego Othello, como ABDADA [ 5 ] o APHID [ 6 ]. En programas recientes , YBWC [ 7 ] parece ser el enfoque preferido.
Corte multiprob
Multi-ProbCut es una heurística utilizada en la poda alfa-beta del árbol de búsqueda. [ 8 ] La heurística ProbCut estima las puntuaciones de evaluación en niveles más profundos del árbol de búsqueda mediante una regresión lineal entre las puntuaciones de niveles más profundos y superficiales. Multi-ProbCut extiende este enfoque a múltiples niveles del árbol de búsqueda. La regresión lineal se aprende a través de búsquedas previas en el árbol, lo que convierte a la heurística en una especie de control de búsqueda dinámico. [ 9 ] Es particularmente útil en juegos como Otelo, donde existe una fuerte correlación entre las puntuaciones de evaluación en niveles más profundos y superficiales. [ 10 ] [ 11 ]
Técnicas de evaluación
Existen tres paradigmas diferentes para crear funciones de evaluación.
Tablas de discos cuadrados
Las distintas casillas tienen valores diferentes: las esquinas son buenas y las casillas contiguas a las esquinas son malas. Sin tener en cuenta las simetrías, hay 10 posiciones diferentes en un tablero, y a cada una de ellas se le asigna un valor para cada una de las tres posibilidades: disco negro, disco blanco y vacío. Un enfoque más sofisticado consiste en asignar valores diferentes a cada posición durante las distintas fases del juego; por ejemplo, las esquinas son más importantes en la apertura y al principio del medio juego que en el final. [ 12 ]
Basado en la movilidad
La mayoría de los jugadores humanos se esfuerzan por maximizar la movilidad (número de movimientos disponibles) y minimizar los discos de frontera (discos adyacentes a casillas vacías). Se calcula la movilidad del jugador y del oponente, así como la movilidad potencial del jugador y del oponente. [ 13 ] Estas medidas se pueden encontrar muy rápidamente y aumentan significativamente la fuerza de juego. La mayoría de los programas conocen las configuraciones de bordes y esquinas e intentan minimizar el número de discos durante la fase inicial del juego, otra estrategia utilizada por los jugadores humanos. [ 12 ]
Coeficientes basados en patrones / coeficientes de patrón
La maximización de la movilidad y la minimización de la frontera se pueden descomponer en configuraciones locales que se pueden sumar; la implementación habitual consiste en evaluar cada configuración de fila, columna, diagonal y esquina por separado y sumar los valores, lo que implica evaluar muchos patrones diferentes. [ 12 ] El proceso de determinación de valores para todas las configuraciones se realiza tomando una gran base de datos de partidas jugadas entre jugadores fuertes y calculando estadísticas para cada configuración en cada etapa de la partida a partir de todas las partidas. [ 12 ]
La opción más común para predecir la diferencia final de discos utiliza una medida de diferencia de discos ponderada donde el lado ganador recibe una bonificación correspondiente al número de discos. [ 12 ]
Libro de apertura
Los libros de aperturas ayudan a los programas informáticos al proporcionar aperturas comunes que se consideran buenas maneras de contrarrestar aperturas débiles. Todos los programas fuertes utilizan libros de aperturas y los actualizan automáticamente después de cada partida. Para recorrer todas las posiciones de todas las partidas en la base de datos y determinar el mejor movimiento que no se haya jugado en ninguna partida de la base de datos, se utilizan tablas de transposición para registrar las posiciones que se han buscado previamente. Esto significa que esas posiciones no necesitan buscarse de nuevo. [ 12 ] Esto consume tiempo ya que se debe realizar una búsqueda profunda para cada posición, pero una vez hecho esto, actualizar el libro es fácil. Después de cada partida jugada, se buscan todas las posiciones nuevas para la mejor desviación.
Otras optimizaciones
Un hardware más rápido y procesadores adicionales pueden mejorar las capacidades del programa para jugar al Othello, como por ejemplo una búsqueda de jugadas más profunda.
Resolviendo Otelo
Durante el juego, los jugadores se turnan. El jugador humano usa fichas negras mientras que la computadora usa blancas. El jugador humano comienza el juego. [ 1 ] Othello se resuelve con fuerza en tableros de 4×4 y 6×6, con el segundo jugador (blancas) ganando en juego perfecto . [ 14 ] [ 15 ]
Otelo 4 × 4
Othello 4x4 tiene un árbol de juego muy pequeño y ha sido resuelto en menos de un segundo por muchos programas sencillos de Othello que utilizan el método Minimax, el cual genera todas las posiciones posibles (casi 10 millones). El resultado es que las blancas ganan con un margen de +8 (3–11). [ 14 ]
Otelo 6 × 6
El problema Othello 6x6 se ha resuelto en menos de 100 horas mediante muchos programas sencillos de Othello que utilizan el método Minimax, el cual genera todas las posiciones posibles (casi 3,6 billones). El resultado es que wEl blanco gana con un margen de +4 (16–20). [ 16 ]
Otelo 8 × 8
El tamaño del árbol del juego Othello 8x8 se estima en 10⁵⁴ nodos, y el número de posiciones legales se estima en menos de 10²⁸ . En octubre de 2023, una preimpresión afirmaba que el juego había sido resuelto, siendo el resultado óptimo el empate. [ 17 ] [ 18 ] Los resultados de los cálculos también se compartieron, lo que lo convierte en uno de los libros más extensos disponibles públicamente. [ 19 ]
Algunos programas de ajedrez de alto nivel han ampliado sus libros durante muchos años. Como resultado, muchas líneas son en la práctica tablas o victorias para cualquiera de los dos bandos. En cuanto a las tres aperturas principales (diagonal, perpendicular y paralela), parece que tanto la diagonal como la perpendicular conducen a tablas, mientras que la paralela resulta en victoria para las negras. El árbol de tablas también parece más grande después de la apertura diagonal que después de la perpendicular. [ 20 ] La apertura paralela ofrece grandes ventajas para las negras, permitiéndoles ganar siempre en una jugada perfecta. [ 21 ]
Hitos en la informática Otelo
- 1977 : Scientific American hizo la primera referencia publicada conocida a un programa Othello/Reversi, escrito por NJD Jacobs en BCPL . [ 22 ] BYTE publicó "Othello, a New Ancient Game" como un programa de entrada BASIC en octubre. [ 23 ]
- 1977 : Creative Computing publicó una versión de Otelo escrita por Ed Wright en FORTRAN . [ 24 ] [ 25 ]
- 1978 : Nintendo lanza el videojuego Computer Othello en las salas recreativas . [ 26 ]
- 1980 : El programa de Othello The Moor (escrito por Mike Reeve y David Levy ) ganó una partida en un encuentro de seis partidas contra el campeón mundial Hiroshi Inoue. [ 27 ] Peter W Frey de la Universidad Northwestern analizó estrategias de Othello para computadora y humanos en BYTE , y analizó su juego de Othello TRS-80 que, según Frey, derrotó fácilmente la versión de Wright que se ejecutaba en un CDC 6600. [ 25 ] Paul Rosenbloom de la Universidad Carnegie Mellon desarrolló IAGO , que terminó en tercer lugar en un torneo de computadoras de la Universidad Northwestern. [ 28 ] Cuando IAGO jugó contra The Moor, IAGO fue mejor capturando piezas permanentemente y limitando la movilidad de su oponente. [ 27 ]
- 1981 : IAGO, ejecutándose en un DEC KA10, terminó por delante de otros 19 participantes en el Torneo Abierto de Othello de Santa Cruz, en la Universidad de California, Santa Cruz , con el único récord invicto. El juego de Charles Heath, basado en TRS 80, terminó en segundo lugar. Los motores basados en CPU de microcomputadoras ganaron del segundo al séptimo lugar, por delante de varias computadoras centrales y minicomputadoras; Frey especuló que esto se debía a que el Othello computarizado no se beneficia de varias de las ventajas de las computadoras más grandes, como la aritmética de punto flotante más rápida . [ 28 ]
- A finales de la década de 1980 : Kai-Fu Lee y Sanjoy Mahajan crearon el programa Othello BILL , que era similar a IAGO pero incorporaba aprendizaje bayesiano. BILL superó consistentemente a IAGO. [ 27 ]
- 1992 : Michael Buro comenzó a trabajar en el programa de Othello, Logistello . Las técnicas de búsqueda, la función de evaluación y la base de conocimiento de patrones de Logistello eran mejores que las de programas anteriores. Logistello perfeccionó su juego jugando más de 100 000 partidas contra sí mismo. [ 27 ]
- 1997 : Logistello ganó todas las partidas en un encuentro de seis juegos contra el campeón mundial Takeshi Murakami. Si bien no había muchas dudas de que los programas de Othello eran más fuertes que los humanos, habían pasado 17 años desde el último encuentro entre una computadora y un campeón mundial vigente. Después del encuentro de 1997, ya no cabía duda: Logistello era significativamente mejor que cualquier jugador humano. [ 29 ] [ 27 ]
- 1998 : Michael Buro retiró Logistello. El interés por la investigación en Othello disminuyó un poco, pero algunos programas, incluidos Ntest, Saio, Edax, Cassio, Zebra y Herakles, continuaron desarrollándose. [ 27 ]
- 2004 : Ntest se convirtió en el programa más potente, significativamente más fuerte que Logistello.
- 2005 : Ntest, Saio, Edax, Cyrano y Zebra se volvieron significativamente más fuertes que Logistello. Ntest y Zebra se retiraron.
- 2011 : Saio , Edax y Cyrano se volvieron mucho más rápidos que Logistello y otros programas.
- 2022 : Egaroucid se presenta como un motor potente, inspirado en gran medida en Edax.
- 2023 : Otelo se resuelve utilizando Edax ligeramente modificado. Egaroucid publica datos de autojuego. [ 30 ]
Lista de los mejores programas de Otelo/Reversi
- NTest ( Ntest ) por Chris Welty
- Edax ( Edax archivado el 6 de abril de 2013 en Wayback Machine ) por Richard Delorme
- Logistello ( Logistello ) de Michael Buro
Véase también
Notas
- 1 2 "Dcs.gla.ac.uk" (PDF) . Archivado del original (PDF) el 3 de enero de 2011.
- ↑ Jean-Christophe Weill (1992). La búsqueda NegaC*. ICCA Journal, vol. 15, n.º 1, págs. 3-7.
- ^ Armanto, Hendrawan; Santoso, Joan; Juan, Daniel; Kurniawan, Faris; Yudianto, Ricky; Gunawan, Steven (octubre de 2012). "Red neuronal evolutiva para el juego Othello" . Procedia - Ciencias sociales y del comportamiento . 57 : 419– 425. doi : 10.1016/j.sbspro.2012.09.1206 .
- ↑ Buro, M., "Experimentos con Multi-ProbCut y una nueva función de evaluación de alta calidad para Othello" , Games in AI Research , HJ van den Herik, H. Iida (ed.), ISBN 90-621-6416-1, 2000
- ↑ Jean-Christophe Weill (1996). El algoritmo de búsqueda minimax distribuido ABDADA. Actas de la Conferencia de Ciencias de la Computación de la ACM de 1996, págs. 131-138. ACM, Nueva York, NY, reimpreso en ICCA Journal Vol. 19, No. 1
- ↑ Mark Brockington (1997). KEYANO Unplugged - La construcción de un programa Othello. Informe técnico TR-97-05, Departamento de Ciencias de la Computación, Universidad de Alberta.
- ↑ Rainer Feldmann, Peter Mysliwietz, Burkhard Monien (1991). Un programa de ajedrez totalmente distribuido. Avances en el ajedrez informático 6
- ↑ Buro, Michael (1997). "Experimentos con Multi-ProbCut y una nueva función de evaluación de alta calidad para Othello" . Games in AI Research . 34 (4): 77– 96.
- ↑ Bulitko, Vadim; Lustrek, Mitja; Schaeffer, Jonathan; Bjornsson, Yngvi; Sigmundarson, Sverrir (1 de junio de 2008). "Control dinámico en búsqueda heurística en tiempo real" . Revista de investigación en inteligencia artificial . 32 : 419– 452. doi : 10.1613/jair.2497 .
- ↑ Fürnkranz, Johannes (2001). Máquinas que aprenden a jugar | Guías . Nova Science Publishers, Inc. 6080 Jericho Tpke. Suite 207 Commack, NY Estados Unidos: Nova Science Publishers, Inc. pp. 11–59 . ISBN 978-1-59033-021-0.
{{cite book}}: CS1 mantenimiento: ubicación ( enlace ) - ↑ Heinz, Ernst A. (2013). Búsqueda escalable en ajedrez computacional: mejoras algorítmicas y experimentos con altas profundidades de búsqueda . Springer Science & Business Media. pág. 32. ISBN 978-3-322-90178-1.
- 1 2 3 4 5 6 Gunnar Andersson (2007). "Escribiendo un programa de Otelo" . radagast.se . Recuperado el 12 de febrero de 2023 .
- ↑ Cómo funciona Ntest Archivado el 9 de noviembre de 2011 en Wayback Machine el 2 de marzo de 2005
- 1 2 Solución de Otelo 4 × 4 Archivado el 7 de julio de 2011 en Wayback Machine el 2 de septiembre de 2008
- ↑ Jugada perfecta en Otelo 6x6 desde dos posiciones iniciales alternativas. Archivado el 1 de noviembre de 2009 en Wayback Machine el 17 de noviembre de 2004.
- ↑ F. Pittner (julio de 2006). "Página principal de Tothello" . www.tothello.com . Consultado el 12 de febrero de 2023 .
- ↑ "Otelo resuelto" (PDF) . Consultado el 4 de noviembre de 2023 .
- ^ Takizawa, Hiroki. "guiones inversos" . Github . Consultado el 4 de noviembre de 2023 .
- ↑ "Análisis del juego de posiciones de Otelo" . Consultado el 4 de noviembre de 2023 .
- ↑ "El programa Othello más potente en términos de inteligencia artificial" . Archivado del original el 9 de enero de 2007. Consultado el 5 de abril de 2010 .
- ↑ "Proyecto SaioApp: el motor Othello más potente" . Consultado el 12 de febrero de 2023 .
- ↑ Gardner, Martin. Recreaciones matemáticas. Scientific American, abril de 1977.
- ↑ Duda, Richard O (octubre de 1977). "Otelo, un nuevo juego antiguo" . BYTE . págs. 60–62 .
- ↑ Wright, Ed (noviembre-diciembre de 1977). "Otelo" . Creative Computing . págs. 140-142 . Recuperado el 18 de octubre de 2013 .
- 1 2 Frey, Peter W (julio de 1980). "Simulación de la toma de decisiones humanas en un ordenador personal" . BYTE . pág. 56. Consultado el 18 de octubre de 2013 .
- ↑ "Otelo para ordenador - Videojuego de Nintendo" .
- 1 2 3 4 5 6 "La historia de los videojuegos" (PDF) . Archivado del original (PDF) el 24 de enero de 2011.
- 1 2 Frey, Peter W (julio de 1981). "El torneo Santa Cruz Open / Othello para computadoras" . BYTE . pág. 16. Recuperado el 18 de octubre de 2013 .
- ↑ Michael Buro (20 de agosto de 1997). "Partido de Otelo del año" . skatgame.net . Consultado el 12 de febrero de 2023 .
- ^ Yamana, Takuto. "Transcripciones de autojuego de Egaroucid" . Otelo AI Egaroucid . Consultado el 5 de noviembre de 2023 .
Enlaces externos
- Otelo 4 × 4
- Otelo 6 × 6
- Programación de ajedrez
- Juega a Otelo online
- Software Reversi
- Juegos de estrategia abstracta
- Problemas completos de PSPACE
