Computer Othello se refiere a la arquitectura de la computadora que abarca el hardware y el software de computadora capaces de jugar el juego de Othello .
NTest - un fuerte programa othello |
Disponibilidad
Hay muchos programas de Othello como NTest , Saio, Edax , Cassio, Pointy Stone, Herakles, WZebra y Logistello que se pueden descargar de Internet de forma gratuita. Estos programas, cuando se ejecutan en cualquier computadora actualizada , pueden jugar juegos en los que los mejores jugadores humanos son fácilmente derrotados. Esto se debe a que, aunque las consecuencias de los movimientos son predecibles tanto para las computadoras como para los humanos, las computadoras son mejores para imaginarlas. [1]
Técnicas de búsqueda
Los programas informáticos de Othello buscan posibles movimientos legales utilizando un árbol de juego . En teoría, examinan todas las posiciones / nodos, donde cada movimiento de un jugador se denomina "capa" . Esta búsqueda continúa hasta una cierta profundidad máxima de búsqueda o el programa determina que se ha alcanzado una posición final de "hoja".
Una implementación ingenua de este enfoque, conocida como Minimax o Negamax , solo puede buscar a una pequeña profundidad en una cantidad de tiempo práctica, por lo que se han ideado varios métodos para aumentar en gran medida la velocidad de búsqueda de buenos movimientos. Estos se basan en poda alfa-beta , Negascout , MTD-f , NegaC *. [2] El algoritmo de alfabeta es un método para acelerar la rutina de búsqueda de Minimax al eliminar los casos que no se utilizarán de todos modos. Este método aprovecha el hecho de que todos los demás niveles del árbol se maximizarán y todos los demás niveles se minimizarán. [3]
También se utilizan varias heurísticas para reducir el tamaño del árbol buscado: buen orden 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 , el YBWC [7] parece el enfoque preferido.
Corte multi-prob
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 puntuaciones más profundas y menos profundas. Multi-ProbCut extiende este enfoque a múltiples niveles del árbol de búsqueda. La regresión lineal en sí se aprende a través de búsquedas de árbol anteriores, lo que hace que la heurística sea una especie de control de búsqueda dinámica. [9] Es particularmente útil en juegos como Othello, donde existe una fuerte correlación entre los puntajes de las evaluaciones en niveles más profundos y menos profundos. [10] [11]
Técnicas de evaluación
Hay tres paradigmas diferentes para crear funciones de evaluación.
Mesas de disco cuadrado
Los diferentes cuadrados tienen diferentes valores: las esquinas son buenas y los cuadrados junto a las esquinas son malos. 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 es tener diferentes valores para cada posición durante las diferentes etapas del juego; por ejemplo, las esquinas son más importantes en la apertura y en el medio juego temprano que en el final. [12]
Basado en movilidad
La mayoría de los jugadores humanos se esfuerzan por maximizar la movilidad (número de movimientos disponibles) y minimizar los discos fronterizos (discos adyacentes a casillas vacías). Se calculan la movilidad del jugador y la movilidad del oponente, y también se calculan la movilidad potencial del jugador y la movilidad potencial del oponente. [13] Estas medidas se pueden encontrar muy rápidamente y aumentan significativamente la fuerza de juego. La mayoría de los programas tienen conocimiento de las configuraciones de bordes y esquinas y tratan de minimizar la cantidad de discos durante el medio juego temprano, otra estrategia utilizada por los jugadores humanos. [12]
Coeficientes de patrones / basados en patrones
La maximización de la movilidad y la minimización de fronteras se pueden dividir en configuraciones locales que se pueden sumar; La implementación habitual es evaluar cada configuración de fila, columna, diagonal y esquina por separado y sumar los valores; se deben 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 juegos jugados entre jugadores fuertes y calculando estadísticas para cada configuración en cada etapa de juego de todos los juegos. [12]
La opción más común para predecir la diferencia de disco final usa una medida de diferencia de disco ponderada donde el lado ganador obtiene una bonificación correspondiente al número de discos. [12]
Libro de apertura
La apertura de libros ayuda a los programas de computadora al brindar aperturas comunes que se consideran buenas formas de contrarrestar las aperturas deficientes. Todos los programas potentes utilizan libros de apertura y actualizan sus libros automáticamente después de cada juego. Para revisar todas las posiciones de todos los juegos en la base de datos del juego y determinar el mejor movimiento no jugado en ningún juego de la base de datos, las tablas de transposición se utilizan para registrar las posiciones que se han buscado previamente. Esto significa que no es necesario volver a buscar esas posiciones. [12] Esto lleva mucho tiempo ya que se debe realizar una búsqueda profunda para cada puesto, pero una vez hecho esto, actualizar el libro es fácil. Después de cada juego jugado, se buscan todas las posiciones nuevas para obtener la mejor desviación.
Otras optimizaciones
Un hardware más rápido y procesadores adicionales pueden mejorar las capacidades del programa de reproducción de Othello, como una búsqueda de capas más profunda.
Resolviendo Othello
Durante el juego, los jugadores alternan movimientos. El jugador humano usa contadores negros mientras que la computadora usa blancos. El jugador humano comienza el juego. [1] Othello está fuertemente resuelto en tableros de 4 × 4 y 6 × 6, con el segundo jugador (blanco) ganando en juego perfecto . [14] [15] Sigue sin resolverse en un tablero estándar de 8 × 8, pero el análisis por computadora da miles de líneas de dibujo , o caminos hacia un dibujo, aunque tal línea no ha sido completamente probada. [dieciséis]
Otelo 4 × 4
Othello 4x4 tiene un árbol de juego muy pequeño y se ha resuelto en menos de un segundo mediante muchos programas Othello simples que utilizan el método Minimax, que genera todas las posiciones posibles (cerca de 10 millones). El resultado es que las blancas ganan con un margen de +8 (3-11). [14]
Otelo 6 × 6
Othello 6x6 se ha resuelto en menos de 100 horas mediante muchos programas Othello simples que utilizan el método Minimax, que genera todas las posiciones posibles (casi 3,6 billones). El resultado es que white gana con un margen de +4 (16-20). [17]
Otelo 8 × 8
El tamaño del árbol de juego Othello 8x8 se estima en 10 54 nodos, y el número de posiciones legales se estima en menos de 10 28 . El juego sigue sin resolverse. Posiblemente se podría encontrar una solución utilizando computación intensiva con los mejores programas en hardware paralelo rápido o mediante computación distribuida .
Algunos programas importantes han ampliado sus libros durante muchos años. Como resultado, muchas líneas son en la práctica empates o victorias para ambos lados. Con respecto a las tres aberturas principales de diagonal, perpendicular y paralela, parece que tanto las aberturas diagonales como las perpendiculares conducen a dibujar líneas, mientras que la abertura paralela es una victoria para el negro. El árbol de dibujo también parece más grande después de la abertura diagonal que después de la abertura perpendicular. [18] La apertura paralela tiene fuertes ventajas para el jugador negro, permitiéndole ganar siempre en una jugada perfecta. [19]
Hitos en computadora Othello
a | B | C | D | mi | F | gramo | h | ||
1 | 1 | ||||||||
2 | 2 | ||||||||
3 | 3 | ||||||||
4 | 4 | ||||||||
5 | 5 | ||||||||
6 | 6 | ||||||||
7 | 7 | ||||||||
8 | 8 | ||||||||
a | B | C | D | mi | F | gramo | h |
- 1977 : Scientific American hizo la primera referencia publicada conocida a un programa Othello / Reversi, escrito por NJD Jacobs en BCPL . [20] BYTE publicado "Otelo, un nuevo juego antiguo" como una base de tipo de programa en octubre. [21]
- 1977 : Creative Computing publicó una versión de Othello escrita por Ed Wright en FORTRAN . [22] [23]
- 1978 : Nintendo lanza el videojuego Computer Othello en salas de juego . [24]
- 1980 : El programa de Othello The Moor (escrito por Mike Reeve y David Levy ) ganó un juego en un partido de seis juegos contra el campeón mundial Hiroshi Inoue. [25] Peter W Frey de la Northwestern University discutió las estrategias de Othello humanas y de computadora en BYTE , y discutió su juego TRS-80 Othello que, según Frey, derrotó fácilmente a la versión de Wright que se ejecuta en un CDC 6600 . [23] Paul Rosenbloom de la Carnegie Mellon University desarrolló IAGO , que terminó en tercer lugar en un torneo informático de la Northwestern University. [26] Cuando IAGO jugó The Moor, IAGO era mejor capturando piezas de forma permanente y limitando la movilidad de su oponente. [25]
- 1981 : IAGO corriendo en un DEC KA10 terminó por delante de otros 19 concursantes en el Torneo Abierto de Otelo de Santa Cruz en la Universidad de California, Santa Cruz , con el único récord invicto. El juego basado en TRS 80 de Charles Heath terminó en segundo lugar. Los motores basados en CPU de microcomputadoras ganaron del segundo al séptimo lugar, por delante de varios mainframes y miniordenadores; Frey especuló que esto se debía a que la computadora Othello 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 . [26]
- 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 el aprendizaje bayesiano. BILL venció de manera confiable a IAGO. [25]
- 1992 : Michael Buro comienza a trabajar en el programa Logistello de Othello . Las técnicas de búsqueda, la función de evaluación y la base de conocimientos de patrones de Logistello eran mejores que las de los programas anteriores. Logistello perfeccionó su juego jugando más de 100.000 juegos contra sí mismo. [25]
- 1997 : Logistello ganó todos los juegos en un partido de seis juegos contra el campeón mundial Takeshi Murakami. Aunque 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 partido entre una computadora y un campeón mundial reinante. Después del partido de 1997, ya no había ninguna duda: Logistello era significativamente mejor que cualquier jugador humano. [27] [25]
- 1998 : Michael Buro retira Logistello. El interés de la investigación en Othello disminuyó un poco, pero algunos programas, incluidos Ntest, Saio, Edax, Cassio, Zebra y Herakles, continuaron desarrollándose. [25]
- 2004 : Ntest se convirtió en el programa más fuerte, 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.
Lista de los mejores programas de Othello / Reversi
- NTest ( Ntest ) por Chris Welty
- Edax ( Edax ) de Richard Delorme
- Logistello de Michael Buro
Ver también
- Computadora Go
- Shogi de la computadora
- Ajedrez de computadora
- Olimpiada informática
- Reversi
Notas
- ^ a b Dcs.gla.ac.uk Archivado el 3 de enero de 2011 en la Wayback Machine.
- ^ Jean-Christophe Weill (1992). La búsqueda NegaC *. Revista ICCA, vol. 15, núm. 1, págs. 3-7.
- ^ Armanto, Hendrawan; Santoso, Joan; Giovanni, 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 distribuida Minimax de ABDADA. Actas de la Conferencia de Ciencias de la Computación de ACM de 1996, págs. 131-138. ACM, Nueva York, NY, reimprimió ICCA Journal Vol. 19, N ° 1
- ^ Mark Brockington (1997). KEYANO Unplugged - La construcción de un programa Otelo. 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 completamente 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" . Juegos en la investigación de IA . 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 | Libros de guía . Nova Science Publishers, Inc. 6080 Jericho Tpke. Suite 207 Commack, NY Estados Unidos: Nova Science Publishers, Inc. págs. 11–59. ISBN 978-1-59033-021-0.Mantenimiento de CS1: ubicación ( enlace )
- ^ Heinz, Ernst A. (2013). Búsqueda escalable en ajedrez informático: mejoras algorítmicas y experimentos a grandes profundidades de búsqueda . Springer Science & Business Media. pag. 32. ISBN 978-3-322-90178-1.
- ^ a b c d e f Escribiendo un programa de Otelo 02 de abril de 2007
- ^ Cómo funciona Ntest Archivado 2011-11-09 en Wayback Machine el 2 de marzo de 2005
- ^ Un b Solución de Otelo 4 × 4 Archivado 2011-07-07 en la Wayback Machine 02 de septiembre de, 2008
- ^ Juego perfecto en 6x6 Othello desde dos posiciones iniciales alternativas Archivado el 1 de noviembre de 2009 en la Wayback Machine el 17 de noviembre de 2004
- ^ Libro de apertura de Edax 4.0 01 de noviembre de 2008
- ^ Un software gratuito para resolver othello 4x4 y 6x6
- ^ "Programa othello más fuerte en términos de inteligencia artificial" . Archivado desde el original el 9 de enero de 2007 . Consultado el 5 de abril de 2010 .
- ^ Libro de Saio
- ^ Gardner, Martin. Recreaciones matemáticas. Scientific American, abril de 1977.
- ^ Duda, Richard O (octubre de 1977). "Othello, un nuevo juego antiguo" . BYTE . págs. 60–62.
- ^ Wright, Ed (noviembre-diciembre de 1977). "Otelo" . Computación creativa . págs. 140-142 . Consultado el 18 de octubre de 2013 .
- ^ a b Frey, Peter W (julio de 1980). "Simulación de la toma de decisiones humanas en una computadora personal" . BYTE . pag. 56 . Consultado el 18 de octubre de 2013 .
- ^ https://www.arcade-museum.com/game_detail.php?game_id=7380
- ^ a b c d e f La historia de los juegos de computadora Archivado el 24 de enero de 2011 en la Wayback Machine.
- ^ a b Frey, Peter W (julio de 1981). "El Torneo Abierto de Santa Cruz / Otelo para Computadoras" . BYTE . pag. 16 . Consultado el 18 de octubre de 2013 .
- ↑ The Othello Match of the Year Takeshi Murakami vs.Logistello
enlaces externos
- 4 × 4 Otelo
- 6 × 6 Otelo
- Lista de programas de Othello
- Programación de ajedrez