Ir al contenido

Otelo en computadoras

De Wikipedia, la enciclopedia libre

Otelo en Computadoras se refiere a un sistema computacional que incluye hardware y software capaz de jugar Otelo.

NTest - uno de los programas otelo más fuertes

Viabilidad

[editar]

Existen muchos programas de Otelo como NTest, Saio, Edax, Cassio, Pointy Stone, Herakles, WZebra y Logistello que pueden ser descargados gratuitamente de Internet y que ejecutados en una Computadora personal actual pueden derrotar fácilmente a los mejores jugadores humanos. Los mejores programas pueden prever hasta 30 movimientos antes de cada jugada (dado un tiempo razonable) en una computadora personal común.

Estrategias de Búsqueda

[editar]

Los programas de Otelo buscan los posibles movimientos legales en un Árbol de Juego.. En teoría examina todas las posiciones/nodos, donde cada movimiento de un jugador es llamado una jugada ("ply"). Esta búsqueda continúa hasta que se alcance cierta profundidad máxima o hasta que el programa determine que una posición final “hoja” ha sido alcanzada. Una implementación muy simple de esta aproximación, conocida como Minimax o Negamax, solo puede buscar a una profundidad pequeña en un tiempo razonable, por tanto se han elaborado varios métodos para acelerar la búsqueda de buenos movimientos. Estos se basan en Poda alfa-beta, Negascout, MTD-f, NegaC*.[1]​ Para reducir el tamaño del árbol de búsqueda también se utilizan varias heurísticas como: ordenamiento de los tableros hijos, tablas de transposición, y búsqueda selectiva.[2]​ Para acelerar la búsqueda en máquinas con múltiples procesadores o núcleos, se puede implementar una “búsqueda en paralelo”. Se han realizado varios experimentos con el juego Otelo, como pueden ser[3]​ o APHID.[4]​ En programas recientes, el YBWC[5]​ parece ser la aproximación preferida.

Técnicas de Evaluación

[editar]

Existen 3 paradigmas diferentes para crear funciones de evaluación.

Tablas de Posiciones (Disk-Square tables)

[editar]

Las casillas tienen diferentes valores. Por ejemplo, las esquinas son buenas y las casillas adyacentes a las esquinas son malas. Sin tener en cuenta la simetría, existen 10 posiciones diferentes en el 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. Una aproximación más sofisticada es asignar diferentes valores a cada posición durante las diferentes etapas del juego; por ejemplo, las esquinas son más importantes en la apertura y en el principio del medio-juego que en el final.[6]​

Basadas en movilidad (Mobility-based)

[editar]

La mayoría de los jugadores humanos se esfuerzan por maximizar la movilidad (número de movimientos posibles) y minimizar los discos frontera (discos adyacentes a una casilla vacía). Tanto la movilidad del jugador como la del oponente, así como la movilidad potencial son fácilmente calculadas, y estas incrementan considerablemente la robustez en juego del jugador. La mayoría de los programas tienen conocimientos sobre configuraciones de bordes y esquinas, y tratan de minimizar el número de discos durante el principio del medio-juego, estrategia también usada por jugadores humanos.[6]​

Basadas en Patrones (Pattern-based / Pattern coefficients)

[editar]

La maximización de la movilidad y la minimización de la frontera se pueden separar en configuraciones locales que pueden unificarse luego; la implementación usual es evaluar cada configuración de fila, columna, diagonal y esquina por separado y luego unificar los valores, muchos patrones diferentes deben ser evaluados.[6]​ El proceso de asignar valores a cada configuración se realiza manteniendo una extensa base de datos de juegos entre jugadores expertos y calculando estadísticas de cada configuración en cada una de las etapas de cada juego almacenado.[6]​ La opción más común para predecir la diferencia de discos final, utiliza una medida ponderada de la diferencia de discos donde el ganador recibe un plus correspondiente a un número de discos.[6]​

Libro de aperturas

[editar]

Los libros de aperturas ayudan a los programas proveyéndolos de aperturas consideradas buenas para contrarrestar a aperturas pobres. Todos los programas fuertes usan libros de aperturas y los actualizan automáticamente después de cada juego. Consiste en revisar todas las posiciones de todos los juegos en la base de datos y determinar la mejor jugada no utilizada en ninguno de los juegos de la base de datos. Las tablas de transposición se utilizan para almacenar las posiciones previamente revisadas para evitar revisarlas nuevamente.[6]​ Esto consume tiempo puesto que se debe realizar una búsqueda en profundidad por cada posición, pero una vez hecho, actualizar el libro sobre la marcha es sencillo. Después de cada juego todas las nuevas posiciones son revisadas en busca de la mejor desviación.

Otras optimizaciones

[editar]

Mejor hardware y procesadores adicionales pueden mejorar las habilidades de los programas que juegan Otelo, como mismo las búsquedas más profundas conllevan a programas más fuertes.

Resolviendo Othello

[editar]

Completamente resuelto para tableros de 4x4 y 6x6, con jugadores infalibles el segundo jugador (blancas) siempre gana.[7]​[8]​ Aunque no ha sido resuelto matemáticamente, está prácticamente resuelto para el tablero de 8x8 (el estándar). Aunque el análisis computacional muestra miles de formas de quedar en tablas, ninguna de ellas ha sido completamente demostrada.[9]​

Otelo 4 x 4

[editar]

Otelo 4x4 tiene un árbol de juego considerablemente pequeño y ha sido resueltos en menos de un segundo por varios de los programas más simples de Otelo que utilizan Minimax, y que generan todas las posibles posiciones (casi 10 millones). Los juegos perfectos siempre terminan con en segundo jugador (blancas) ganando por 8.[7]​

Otelo 6 x 6

[editar]

Ha sido resuelto en menos de 100 horas por los programas más simples que utiliza minimax, generando las casi 3.6 millones de posiciones posibles. Los juegos perfectos siempre terminan con el segundo jugador (blancas) ganando por 4.[10]​

Otelo 8 x 8

[editar]

El tamaño del árbol de juego se estima sea de 1054 nodos y el número de posiciones legales menos de 1028. Aunque no ha sido matemáticamente resuelto aún, se podría encontrar una solución utilizando cómputo intensivo con los mejores programas en hardware paralelizado, o a través de cómputo distribuido. Algunos de los mejores programas llevan años expandiendo sus libros en un conjunto de computadoras. Como resultado, muchas líneas son en la práctica tablas, o gana alguno de los jugadores. Sobre los 3 aperturas principales: diagonal, perpendicular y paralela; al parecer las aperturas perpendicular y diagonal conllevan a tablas, mientras que la paralela conlleva a una victoria de las negras. La apertura en paralelo da una fuerte ventaja a las negras para ganar siempre.[11]​ Aunque aún no ha sido probado, prácticamente el juego acaba en tablas si ambos jugadores juegan perfecto. En juegos estándares, usando sus libros de aperturas, los mejores programas pierden en menos de 1% de las ocasiones.

Otelo 10 x 10

[editar]

Tiene un medio-juego más largo y el primer jugador (negras) tiene más posibilidades de ganar. El análisis computacional muestra que es muy probable que el juego termine en tablas si ambos jugadores juegan perfectamente, sin embargo es considerablemente poco profundo y se necesitan más cálculos. La complejidad del árbol de juego es muy alta, se estima que sea de 1090, con un estimado de posiciones legales de 1044.[cita requerida]

Cronología de Otelo en Computadoras

[editar]

1978: Nintendo lanza el Videojuego Computer Othello en arcade.

1980: El programa Otelo Moor (escrito por by Mike Reeve y David Levy) ganó uno de los 6 juegos de un Torneo contra el campeón mundial Hiroshi Inoue.

Early 1980s: Paul Rosenbloom desarrolló el programa Otelo IAGO. Cuando IAGO de enfrentó a The Moor, IAGO result major capturando piezas permanentemente, y limitando la movilidad del oponente

Late 1980s: Kai-Fu Lee y Sanjoy Mahajan crearon el programa Otelo BILL, que era similar a IAGO pero incorporaba aprendizaje Bayesiano. BILL indiscutiblemente derrotó a IAGO.

1992: Michael Buro comenzó a trabajar en el programa Otelo Logistello. Las técnicas de búsqueda, función de evaluación, y la base de conocimiento de patrones de Logistello eran mejores que la de los programas anteriores. Logistello perfeccionó su juego jugando 100,000 juegos contra sí mismo.

1997: Logistello ganó todos los juegos de un torneo de 6 contra el campeón mundial Takeshi Murakami. Aunque no existía mucha duda de que los programas Otelo eran mejores que los humanos, habían pasado 17 años desde el último enfrentamiento entes una computadora y un campeón mundial actual. Después de 1997 se disipó la duda: Logistello era significativamente mejor que cualquier jugador humano.[12]​

1998: Michael Buro retiró Logistello. El interés investigativo disminuyó un tanto, pero algunos programas como Ntest, Saio, Edax, Cassio, WZebra y Herakles, continuaron desarrollándose.

2004: Ntest se convirtió en el mejor programa, significativamente mejor que Logistello.[13]​

2005: Ntest, Saio, Edax, Cyrano y WZebra, ya eran significativamente mejores que Logistello. Ntest y WZebra se retiraron.

2011: Saio, Edax and Cyrano, llegaron a ser mucho más rápidos que Logistello y otros programas.

Lista de los principales programas de Otelo/Reversi

[editar]
  1. Saio (Saio) por Benedetto Romano
  2. Cyrano por Bruno Causse
  3. Edax (Edax Archivado el 6 de abril de 2013 en Wayback Machine.) por Richard Delorme
  4. Cassio (Cassio) por Stéphane Nicolet
  5. Ymatioun por Youri Matiounine
  6. Pirate por Roger H. Hughston
  7. NTest (Ntest) por Chris Welty
  8. WZebra (WZebra) por Gunnar Andersson
  9. Logistello por Michael Buro
  10. Pointy Stone (Pointy Stone) por Jonathan Kreuzer
  11. Herakles (Herakles) por Kostas Tournavitis - el mejor programa de Otelo para 10x10
  12. Tothello (Tothello) por F. Pittner - el mejor programa de Otelo para 4x4 y 6x6
  13. Iagno (Iagno) GNOME-Versión de Reversi (Open-Source)
  14. Daisy Reversi (Daisy Reversi) por Pavel Matlash - el mejor programa de Otelo para 12x12, 14x14, 16x16, 18x18, 20x20, 22x22 y 24x24
  15. Cyrano (Cyrano java applet) por Bruno Causse

Sitios relacionados

[editar]

Referencias

[editar]
  1. ↑ Jean-Christophe Weill (1992). The NegaC* Search. ICCA Journal, Vol. 15, No. 1, pp. 3-7
  2. ↑ Buro, M., "Experiments with Multi-ProbCut and a New High-Quality Evaluation Function for Othello", Games in AI Research, H.J. van den Herik, H. Iida (ed.), ISBN 90-621-6416-1, 2000
  3. ↑ Jean-Christophe Weill (1996). The ABDADA Distributed Minimax Search Agorithm. Proceedings of the 1996 ACM Computer Science Conference, pp. 131-138. ACM, New York, N.Y, reprinted ICCA Journal Vol. 19, No. 1
  4. ↑ Mark Brockington (1997). KEYANO Unplugged - The Construction of an Othello Program. Technical Report TR-97-05, Department of Computing Science, University of Alberta.
  5. ↑ Rainer Feldmann, Peter Mysliwietz, Burkhard Monien (1991). A Fully Distributed Chess Program. Advances in Computer Chess 6
  6. ↑ a b c d e f Writing an Othello program April 02, 2007
  7. ↑ a b Solution of Othello 4 x 4 Archivado el 7 de julio de 2011 en Wayback Machine. September 02, 2008
  8. ↑ Perfect play in 6x6 Othello from two alternative starting positions November 17, 2004
  9. ↑ Edax 4.0 Opening Book Archivado el 8 de enero de 2011 en Wayback Machine. November 01, 2008
  10. ↑ A free software for solving 4x4 and 6x6 othello
  11. ↑ Saio's book
  12. ↑ The History of Computer Games
  13. ↑ Othello Indonesia

Enlaces externos

[editar]
Obtenido de «https://es.wikipedia.org/w/index.php?title=Otelo_en_computadoras&oldid=162390182»