stringtranslate.com

Computadora Otelo

Computer Othello se refiere a la arquitectura de computadora que abarca hardware y software de computadora capaz de jugar el juego de Othello . Se incluyó notablemente en Microsoft Windows desde 1.0 hasta XP , donde se le conoce simplemente como Reversi.

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 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 "capa" . Esta búsqueda continúa hasta una cierta profundidad de búsqueda máxima 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 , sólo 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 la poda Alfa-beta , Negascout , MTD(f) y NegaC*. [2] El algoritmo alfabético es un método para acelerar la rutina de búsqueda Minimax eliminando 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 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 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 previas en árboles, 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 las evaluaciones en niveles más profundos y superficiales. [10] [11]

Técnicas de evaluación

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

Mesas cuadradas de disco

Diferentes cuadrados tienen diferentes valores: las esquinas son buenas y los cuadrados al lado de 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 valores diferentes para cada posición durante las diferentes etapas del juego; por ejemplo, las esquinas son más importantes en la apertura y en el inicio del juego que en el final. [12]

Basado en movilidad

La mayoría de los jugadores humanos se esfuerzan por maximizar la movilidad (cantidad de movimientos disponibles) y minimizar los discos fronterizos (discos adyacentes a casillas vacías). Se calcula la movilidad del jugador y la movilidad del oponente, y también se calcula 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 e intentan minimizar la cantidad de discos durante la mitad del juego, otra estrategia utilizada por los jugadores humanos. [12]

Coeficientes de patrón/basados ​​en patrones

La maximización de la movilidad y la minimización de las 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 determinar los 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 final de discos 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 ofrecer aperturas comunes que se consideran buenas formas de contrarrestar 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 que no se realizó en ningún juego 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 esos puestos. [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 busca la mejor desviación en todas las nuevas posiciones.

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 Otelo

Durante el juego, los jugadores alternan movimientos. El jugador humano usa fichas negras mientras que la computadora usa fichas blancas. El jugador humano comienza el juego. [1] Otelo se resuelve fuertemente en tableros de 4×4 y 6×6, con el segundo jugador (blanco) 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 simples de Othello 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 se ha resuelto en menos de 100 horas mediante muchos programas sencillos de Othello 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). [dieciséis]

Otelo 8×8

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

Algunos programas importantes han ampliado sus libros desde hace muchos años. Como resultado, muchas líneas en la práctica son empates o victorias para cualquiera de los lados. En cuanto a las tres aperturas principales: diagonal, perpendicular y paralela, parece que tanto la diagonal como la perpendicular conducen a dibujar líneas, mientras que la apertura paralela es una victoria para las negras. El árbol del dibujo también parece más grande después de la abertura diagonal que después de la abertura perpendicular. [20] [ verificación fallida ] La apertura paralela tiene grandes ventajas para el jugador negro, permitiendo a las negras ganar siempre en una jugada perfecta. [21] [ verificación fallida ]

Hitos en la computadora Otelo

Logistello contra Takeshi Murakami (cuarto juego)

Lista de los mejores programas de Othello/Reversi

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

Ver 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 TICCA, vol. 15, núm. 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 Otelo", 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 distribuido Minimax de ABDADA. Actas de la Conferencia de Ciencias de la Computación ACM de 1996, págs. 131-138. ACM, Nueva York, NY, reimpreso ICCA Journal vol. 19, n° 1
  6. ^ Mark Brockington (1997). KEYANO Unplugged - La construcción de un programa de Otelo. 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. ^ Buró, Michael (1997). "Experimentos con Multi-ProbCut y una nueva función de evaluación de alta calidad para Otelo". 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 | Libros guía. Nova Science Publishers, Inc.6080 Jericho Tpke. Suite 207 Commack, Nueva YorkEstados Unidos: Nova Science Publishers, Inc. págs. 11–59. ISBN 978-1-59033-021-0.{{cite book}}: Mantenimiento CS1: ubicación ( enlace )
  11. ^ Heinz, Ernst A. (2013). Búsqueda escalable en ajedrez informático: mejoras algorítmicas y experimentos a altas profundidades de búsqueda. Medios de ciencia y negocios de Springer. pag. 32.ISBN​ 978-3-322-90178-1.
  12. ^ abcdef Gunnar Andersson (2007). "Escribir un programa de Otelo". 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 el 2 de septiembre de 2008
  15. ^ Juego perfecto en 6x6 Othello desde dos posiciones iniciales alternativas Archivado el 1 de noviembre de 2009 en Wayback Machine el 17 de noviembre de 2004
  16. ^ F. Pittner (julio de 2006). "Página de inicio de Totelo". 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, Martín. Recreaciones Matemáticas. Científico americano, abril de 1977.
  23. ^ Duda, Richard O (octubre de 1977). "Otelo, un nuevo juego antiguo". BYTE . págs. 60–62.
  24. ^ Wright, Ed (noviembre-diciembre de 1977). "Otelo". Computación creativa . 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 humana en una computadora personal". BYTE . pag. 56 . Consultado el 18 de octubre de 2013 .
  26. ^ "Computer Othello - Videojuego de Nintendo".
  27. ^ abcdef "La historia de los juegos de computadora" (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 para Computadoras". BYTE . pag. dieciséis . Consultado el 18 de octubre de 2013 .
  29. ^ Michael Buro (20 de agosto de 1997). "Partido de Otelo del año". skatgame.net . Consultado el 12 de febrero de 2023 .
  30. ^ Yamana, Takuto. "Transcripciones de autojuego de Egaroucid". Otelo AI Egaroucid . Consultado el 5 de noviembre de 2023 .

enlaces externos

Busque otelo informático en Wikcionario, el diccionario gratuito.