stringtranslate.com

Computadora Otelo

El término Computer Othello hace referencia a la arquitectura informática que abarca el hardware y el software informáticos capaces de ejecutar el juego de Othello . Se incluyó en particular en Microsoft Windows desde la versión 1.0 hasta XP , donde simplemente se lo conoce como Reversi. [ cita requerida ]

Disponibilidad

Existen muchos programas 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 ejecutar juegos en los que los mejores jugadores humanos son derrotados fácilmente. 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 a la hora de explorarlas. [1]

Técnicas de búsqueda

Los programas informáticos 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 "jugada" . Esta búsqueda continúa hasta que se alcanza una determinada 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 la búsqueda de buenos movimientos. Estos se basan en la poda Alpha-beta , Negascout , MTD(f) y NegaC*. [2] El algoritmo alphabeta es un método para acelerar la rutina de búsqueda Minimax al podar los casos que no se utilizarán de todos modos. Este método aprovecha el hecho de que todos los demás niveles en el á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 ser el enfoque preferido.

Corte multiproblema

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 utilizando una regresión lineal entre las puntuaciones más profundas y las más superficiales. 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 anteriores 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 Othello , donde existe una fuerte correlación entre las puntuaciones de evaluación en niveles más profundos y más superficiales. [10] [11]

Técnicas de evaluación

Hay tres paradigmas diferentes para crear funciones de evaluación.

Mesas de disco cuadrado

Los distintos cuadrados tienen distintos valores: las esquinas son buenas y los cuadrados que están junto a ellas 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 valores diferentes para cada posición durante las distintas etapas del juego; por ejemplo, las esquinas son más importantes en la apertura y en el comienzo del juego intermedio que en el final. [12]

Basado en la movilidad

La mayoría de los jugadores humanos intentan maximizar la movilidad (número de movimientos disponibles) y minimizar los discos de borde (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 borde y esquina e intentan minimizar la cantidad de discos durante el comienzo del juego medio, 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 la frontera se pueden descomponer 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 del juego de todos los juegos. [12]

La opción más común para predecir la diferencia de discos final utiliza una medida de diferencia de discos ponderada donde el lado ganador obtiene una bonificación correspondiente a la cantidad de discos. [12]

Libro de apertura

Los libros de aperturas ayudan a los programas informáticos al proporcionar aperturas comunes que se consideran buenas formas de contrarrestar las aperturas deficientes. Todos los programas potentes utilizan libros de aperturas y actualizan sus libros automáticamente después de cada partida. Para recorrer todas las posiciones de todas las partidas de la base de datos de partidas y determinar la mejor jugada no realizada 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 no es necesario volver a buscar esas posiciones. [12] Esto requiere mucho 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 encontrar la mejor desviación.

Otras optimizaciones

Un hardware más rápido y procesadores adicionales pueden mejorar las capacidades del programa que reproduce Othello, como por ejemplo la búsqueda de capas más profundas.

Resolviendo Otelo

Durante el juego, los jugadores alternan movimientos. 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 4x4 y 6x6, y el segundo jugador (blanco) gana 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 Othello simples que utilizan el método Minimax, que 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

Othello 6x6 ha sido resuelto en menos de 100 horas por muchos programas Othello simples que utilizan el método Minimax, que genera todas las posiciones posibles (casi 3,6 billones). El resultado es que wEl equipo gana con un margen de +4 (16-20). [16]

Otelo 8 × 8

Se estima que el tamaño del árbol de juego Othello 8x8 es de 10 54 nodos y que el número de posiciones legales es inferior a 10 28. En octubre de 2023, una preimpresión afirma que el juego se ha resuelto y que el resultado óptimo es un empate. [17] [18] Los resultados de los cálculos también se comparten, lo que lo convierte en uno de los libros más grandes disponibles públicamente. [19]

Algunos programas de alto nivel han ampliado sus libros durante muchos años. Como resultado, muchas líneas son en la práctica empates o victorias para ambos bandos. Con respecto a las tres aperturas principales, diagonal, perpendicular y paralela, parece que tanto la apertura diagonal como la perpendicular conducen a líneas de empate, mientras que la apertura paralela es una victoria para las negras. El árbol de empate también parece más grande después de la apertura diagonal que después de la apertura perpendicular. [20] [ verificación fallida ] La apertura paralela tiene fuertes ventajas para el jugador negro, lo que le permite ganar siempre en una jugada perfecta. [21] [ verificación fallida ]

Hitos en la informática Othello

Logistello vs. Takeshi Murakami (4.º partido)

Lista de los mejores programas de Othello/Reversi

  1. NTest (Ntest) de Chris Welty
  2. Edax (Edax Archivado el 6 de abril de 2013 en Wayback Machine ) por Richard Delorme
  3. Logistello (Logistello) de Michael Buro

Véase también

Notas

  1. ^ ab "Dcs.gla.ac.uk" (PDF) . Archivado desde el original (PDF) el 3 de enero de 2011.
  2. ^ Jean-Christophe Weill (1992). La búsqueda NegaC*. Revista ICCA, vol. 15, n.º 1, págs. 3-7.
  3. ^ Armanto, Hendrawan; Santoso, Joan; Juan, Daniel; Kurniawan, Faris; Yudianto, Ricky; Gunawan, Steven (octubre de 2012). "Red neuronal evolutiva para el juego Otelo". Procedia - Ciencias sociales y del comportamiento . 57 : 419–425. doi : 10.1016/j.sbspro.2012.09.1206 .
  4. ^ 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 
  5. ^ Jean-Christophe Weill (1996). El algoritmo de búsqueda ABDADA Distributed Minimax. Actas de la Conferencia de Ciencias Informáticas de la ACM de 1996, págs. 131-138. ACM, Nueva York, NY, reimpreso en ICCA Journal, vol. 19, n.º 1
  6. ^ 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.
  7. ^ Rainer Feldmann, Peter Mysliwietz, Burkhard Monien (1991). Un programa de ajedrez totalmente distribuido. Avances en el ajedrez informático 6
  8. ^ 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.
  9. ^ 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 .
  10. ^ 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}}: Mantenimiento de CS1: ubicación ( enlace )
  11. ^ Heinz, Ernst A. (2013). Búsqueda escalable en ajedrez por ordenador: mejoras algorítmicas y experimentos a gran profundidad de búsqueda. Springer Science & Business Media. pág. 32. ISBN 978-3-322-90178-1.
  12. ^ abcdef Gunnar Andersson (2007). "Cómo escribir un programa Othello". radagast.se . Consultado el 12 de febrero de 2023 .
  13. ^ Cómo funciona Ntest ​​Archivado el 9 de noviembre de 2011 en Wayback Machine el 2 de marzo de 2005
  14. ^ ab Solución de Otelo 4 × 4 Archivado el 7 de julio de 2011 en Wayback Machine 2 de septiembre de 2008
  15. ^ Jugada perfecta en Othello 6x6 desde dos posiciones iniciales alternativas Archivado el 1 de noviembre de 2009 en Wayback Machine 17 de noviembre de 2004
  16. ^ F. Pittner (julio de 2006). «Página de inicio de Tothello». www.tothello.com . Consultado el 12 de febrero de 2023 .
  17. ^ "Otelo está resuelto" (PDF) . Consultado el 4 de noviembre de 2023 .
  18. ^ Takizawa, Hiroki. "guiones inversos". Github . Consultado el 4 de noviembre de 2023 .
  19. ^ "Análisis del juego de posiciones de Otelo" . Consultado el 4 de noviembre de 2023 .
  20. ^ "El programa Otelo más potente en términos de inteligencia artificial". Archivado desde el original el 9 de enero de 2007. Consultado el 5 de abril de 2010 .
  21. ^ "Proyecto SaioApp: el motor Othello más potente" . Consultado el 12 de febrero de 2023 .
  22. ^ Gardner, Martin. Recreaciones matemáticas. Scientific American, abril de 1977.
  23. ^ Duda, Richard O (octubre de 1977). "Othello, un nuevo juego antiguo". BYTE . págs. 60–62.
  24. ^ Wright, Ed (noviembre-diciembre de 1977). "Othello". Creative Computing . págs. 140-142 . Consultado el 18 de octubre de 2013 .
  25. ^ ab Frey, Peter W (julio de 1980). "Simulación de la toma de decisiones humanas en una computadora personal". BYTE . p. 56 . Consultado el 18 de octubre de 2013 .
  26. ^ "Computer Othello - Videojuego de Nintendo".
  27. ^ abcdef "La historia de los videojuegos" (PDF) . Archivado desde el original (PDF) el 24 de enero de 2011.
  28. ^ ab Frey, Peter W (julio de 1981). "El torneo Santa Cruz Open / Othello Tournament for Computers". BYTE . p. 16 . Consultado el 18 de octubre de 2013 .
  29. ^ Michael Buro (20 de agosto de 1997). "Othello match of the year". skatgame.net . Consultado el 12 de febrero de 2023 .
  30. ^ Yamana, Takuto. "Transcripciones de autojuego de Egaroucid". Otelo AI Egaroucida . Consultado el 5 de noviembre de 2023 .

Enlaces externos

Busque computadora othello en Wikcionario, el diccionario libre.