stringtranslate.com

juego resuelto

Un juego resuelto es un juego cuyo resultado (ganar, perder o empatar ) se puede predecir correctamente desde cualquier posición, asumiendo que ambos jugadores juegan perfectamente. Este concepto suele aplicarse a los juegos de estrategia abstractos , y especialmente a los juegos con información completa y sin ningún elemento de azar; Resolver un juego de este tipo puede utilizar la teoría de juegos combinatorios y/o asistencia informática.

Descripción general

Una partida para dos jugadores se puede resolver en varios niveles: [1] [2]

Solución ultradébil
Demuestre si el primer jugador ganará, perderá o empatará desde la posición inicial, dado un juego perfecto en ambos lados. Esta puede ser una prueba no constructiva (posiblemente involucrando un argumento de robo de estrategia ) que en realidad no necesita determinar ningún movimiento de la jugada perfecta.
solución débil
Proporcionar un algoritmo que asegure una victoria para un jugador, o un empate para cualquiera de ellos, contra cualquier posible movimiento del oponente, desde el comienzo del juego.
Solución fuerte
Proporcionar un algoritmo que pueda producir movimientos perfectos [ se necesita aclaración ] desde cualquier posición, incluso si ya se han cometido errores [ se necesita aclaración ] en uno o ambos lados.

A pesar de su nombre, muchos teóricos de juegos creen que las pruebas "ultradébiles" son las más profundas, interesantes y valiosas. Las pruebas "ultradébiles" requieren que un académico razone sobre las propiedades abstractas del juego y muestre cómo estas propiedades conducen a ciertos resultados si se logra un juego perfecto. [ cita necesaria ]

Por el contrario, las pruebas "contundentes" a menudo se realizan por fuerza bruta: utilizando una computadora para buscar exhaustivamente en un árbol de juego y descubrir qué pasaría si se lograra un juego perfecto. La prueba resultante proporciona una estrategia óptima para cada posición posible en el tablero. Sin embargo, estas pruebas no son tan útiles para comprender razones más profundas por las que algunos juegos se pueden resolver con un empate y otros, aparentemente muy similares, se pueden resolver con una victoria.

Dadas las reglas de cualquier juego de dos personas con un número finito de posiciones, siempre se puede construir trivialmente un algoritmo minimax que atraviese exhaustivamente el árbol del juego . Sin embargo, dado que para muchos juegos no triviales un algoritmo de este tipo requeriría una cantidad de tiempo inviable para generar un movimiento en una posición determinada, no se considera que un juego esté resuelto débil o fuertemente a menos que el algoritmo pueda ejecutarse mediante hardware existente en un tiempo razonable. Muchos algoritmos se basan en una enorme base de datos pregenerada y, en la práctica, no son más que nada.

Como ejemplo simple de una solución fuerte, el juego de tres en raya se puede resolver fácilmente como un empate para ambos jugadores con un juego perfecto (un resultado determinable manualmente). Juegos como nim también admiten un análisis riguroso utilizando la teoría de juegos combinatoria .

Que un juego se resuelva no es necesariamente lo mismo que si sigue siendo interesante para los humanos jugarlo. Incluso un juego bien resuelto puede seguir siendo interesante si su solución es demasiado compleja para memorizarla; por el contrario, un juego mal resuelto puede perder su atractivo si la estrategia ganadora es lo suficientemente sencilla de recordar (por ejemplo, Maharajah and the Sepoys ). Una solución ultradébil (por ejemplo, Chomp o Hex en un tablero suficientemente grande) generalmente no afecta la jugabilidad.

juego perfecto

En teoría de juegos , el juego perfecto es el comportamiento o estrategia de un jugador que conduce al mejor resultado posible para ese jugador independientemente de la respuesta del oponente. El juego perfecto de un juego se conoce cuando se resuelve el juego. [1] Según las reglas de un juego, se puede evaluar cada posición final posible (como victoria, derrota o empate). Mediante el razonamiento hacia atrás , se puede evaluar recursivamente una posición no final como idéntica a la posición que está a un movimiento de distancia y mejor valorada para el jugador cuyo movimiento es. Por lo tanto, una transición entre posiciones nunca puede resultar en una mejor evaluación para el jugador en movimiento, y un movimiento perfecto en una posición sería una transición entre posiciones igualmente evaluadas. Por ejemplo, un jugador perfecto en una posición empatada siempre empataría o ganaría, nunca perdería. Si hay múltiples opciones con el mismo resultado, a veces se considera que el juego perfecto es el método más rápido que conduce a un buen resultado, o el método más lento que conduce a un mal resultado.

El juego perfecto se puede generalizar a los juegos de información no perfecta , como la estrategia que garantizaría el resultado mínimo esperado más alto independientemente de la estrategia del oponente. Por ejemplo, la estrategia perfecta para piedra, papel o tijera sería elegir aleatoriamente cada una de las opciones con igual (1/3) de probabilidad. La desventaja en este ejemplo es que esta estrategia nunca explotará las estrategias no óptimas del oponente, por lo que el resultado esperado de esta estrategia frente a cualquier estrategia siempre será igual al resultado mínimo esperado.

Aunque es posible que (todavía) no se conozca la estrategia óptima de un juego, una computadora que juega aún podría beneficiarse de las soluciones del juego desde ciertas posiciones de finales (en forma de tablas de finales ), lo que le permitirá jugar perfectamente después de algunas punto en el juego. Los programas de ajedrez informáticos son bien conocidos por hacer esto.

Juegos resueltos

Awari (un juego de la familia Mancala )
La variante de Oware que permitía finales de juego con "grand slams" fue resuelta firmemente por Henri Bal y John Romein en la Vrije Universiteit de Ámsterdam , Países Bajos (2002). Cualquiera de los jugadores puede forzar el empate.
Palillos
Fuertemente resuelto. Si dos jugadores juegan perfectamente, el juego continuará indefinidamente. [ cita necesaria ]
Conecta cuatro
El juego de Connect Four ha sido solucionado
Resuelto primero por James D. Allen el 1 de octubre de 1988 e independientemente por Victor Allis el 16 de octubre de 1988. [3] El primer jugador puede forzar una victoria. Fuertemente resuelto por la base de datos de 8 capas de John Tromp [4] (4 de febrero de 1995). Resuelto débilmente para todos los tamaños de tableros donde el ancho + alto es como máximo 15 (así como 8 × 8 a finales de 2015) [3] (18 de febrero de 2006).
gomoku gratis
Resuelto por Victor Allis (1993). El primer jugador puede forzar una victoria sin reglas de apertura. [1]
Fantasma
Resuelto por Alan Frank usando el Diccionario oficial de jugadores de Scrabble en 1987. [5]
Hexapawn
La variante 3×3 se resolvió como una victoria para las negras, y también se resolvieron varias otras variantes más grandes. [6]
Kalah
La mayoría de las variantes resueltas por Geoffrey Irving, Jeroen Donkers y Jos Uiterwijk (2000), excepto Kalah (6/6). La variante (6/6) fue resuelta por Anders Carstensen (2011). En la mayoría de los casos se demostró una fuerte ventaja del primer jugador. [7] [8] Mark Rawlings, de Gaithersburg, Maryland, ha cuantificado la magnitud de la victoria del primer jugador en la variante (6/6) (2015). Después de la creación de 39 GB de bases de datos de finales, búsquedas que suman un total de 106 días de tiempo de CPU y más de 55 billones de nodos, se demostró que, con un juego perfecto, el primer jugador gana por 2. Tenga en cuenta que todos estos resultados se refieren a la captura del pozo vacío. variante y por lo tanto tienen un interés muy limitado para el juego estándar. Se ha publicado un análisis del juego de reglas estándar para Kalah(6,4), que es una victoria por 8 para el primer jugador, y Kalah(6,5), que es una victoria por 10 para el primer jugador. El análisis de Kalah(6,6) con las reglas estándar está en curso, sin embargo, se ha demostrado que es una victoria de al menos 4 para el primer jugador.
juego l
Fácilmente solucionable. Cualquiera de los jugadores puede forzar el empate.
Maharajá y los cipayos
Este juego asimétrico es una victoria para el jugador cipayo que juega correctamente. [ cita necesaria ]
nim
Fuertemente resuelto. [9]
Morris de nueve hombres
Resuelto por Ralph Gasser (1993). Cualquiera de los jugadores puede forzar el empate. [10] [11]
Orden y caos
El orden (primer jugador) gana. [12]
Ohvalhu
Débilmente resuelto por humanos, pero probado por computadoras. [ cita necesaria ] (Sin embargo, Dakon no es idéntico a Ohvalhu, el juego que en realidad había sido observado por de Voogt) [ cita necesaria ]
pangki
Fuertemente resuelto por Jason Doucette (2001). [13] El juego es un empate. Sólo hay dos primeros movimientos únicos si descartas las posiciones reflejadas. Uno fuerza el empate y el otro le da al oponente una victoria forzada en 15 movimientos.
pentágono
Resuelto enérgicamente por Geoffrey Irving con el uso de una supercomputadora en NERSC . El primer jugador gana.
Libro en cuarto
Resuelto por Luc Goossens (1998). Dos jugadores perfectos siempre empatarán. [14] [15] [16]
Juego tipo Renju sin reglas de apertura involucradas
János Wagner e István Virág (2001) afirman que está resuelto. [ cita necesaria ] Una victoria del primer jugador.
teko
Resuelto por Guy Steele (1998). Dependiendo de la variante, el primer jugador gana o empata. [17]
Morris de tres hombres
Triviamente solucionable. Cualquiera de los jugadores puede forzar el empate. [ cita necesaria ]
Tres mosqueteros
Resuelto fuertemente por Johannes Laire en 2009, y resuelto débilmente por Ali Elabridi en 2017. [18] Es una victoria para las piezas azules (los hombres del cardenal Richelieu, o el enemigo). [19]
tres en raya
Trivialmente muy solucionable debido al árbol de caza menor. [20] El juego es un empate si no se cometen errores, sin que sea posible cometer errores en el movimiento inicial.
El juego de Wythoff
Resuelto firmemente por WA Wythoff en 1907. [21]

Resoluciones débiles

Damas en inglés (damas)
Esta variante de drafts 8×8 fue resuelta débilmente el 29 de abril de 2007 por el equipo de Jonathan Schaeffer . Desde la posición inicial estándar, ambos jugadores pueden garantizar un empate con un juego perfecto. [22] Damas tiene un espacio de búsqueda de 5×10 20 posibles posiciones de juego. [23] El número de cálculos involucrados fue 10 14 , que se realizaron durante un período de 18 años. El proceso involucró desde 200 computadoras de escritorio en su punto máximo hasta alrededor de 50. [24]
Fanorona
Débilmente resuelto por Maarten Schadd. El juego es un empate. [25]
perder ajedrez
Débilmente resuelto como una victoria para las blancas comenzando con 1. e3. [26]
Otelo (Reversi)
Débilmente resuelto en 2023 por Hiroki Takizawa, investigador de Preferred Networks . [27] Desde la posición inicial estándar en un tablero de 8x8, una jugada perfecta de ambos jugadores resultará en un empate. Othello es el juego más grande resuelto hasta la fecha, con un espacio de búsqueda de 10 28 posiciones de juego posibles.
pentominós
Débilmente resuelto por HK Orman. [28] Es una victoria para el primer jugador.
Qubic
Débilmente resuelto por Oren Patashnik (1980) y Victor Allis . El primer jugador gana.
Sim
Débilmente resuelto: gana para el segundo jugador. [ cita necesaria ]
Corderos y tigres
Débilmente resuelto por Yew Jin Lim (2007). El juego es un empate. [29]

Juegos parcialmente resueltos

Ajedrez
Resolver completamente el ajedrez sigue siendo difícil de alcanzar y se especula que la complejidad del juego puede impedir que alguna vez se resuelva. Mediante análisis informático retrógrado , se han encontrado tablas de finales (soluciones fuertes) para todos los finales de tres a siete piezas , contando los dos reyes como piezas.
Se han solucionado algunas variantes del ajedrez en un tablero más pequeño y con un número reducido de piezas . También se han resuelto algunas otras variantes populares; por ejemplo, una solución débil para Maharajah y los cipayos es una serie de movimientos fácilmente memorables que garanticen la victoria al jugador "cipayos".
Ir
El tablero de 5×5 se resolvió débilmente para todos los movimientos de apertura en 2002. [30] El tablero de 7×7 se resolvió débilmente en 2015. [31] Los humanos suelen jugar en un tablero de 19×19, que tiene más de 145 órdenes de magnitud más. complejo que 7×7. [32]
Maleficio
Un argumento de robo de estrategia (como el utilizado por John Nash ) muestra que el primer jugador no puede perder todos los tamaños de tableros cuadrados. Combinado con una prueba de la imposibilidad de un empate, esto muestra que el juego es en el que el primer jugador gana (por lo que se resuelve de forma ultradébil). [ cita necesaria ] Sobre tamaños de tablero particulares, se sabe más: varias computadoras lo resuelven en gran medida para tamaños de tablero de hasta 6 × 6. [ cita necesaria ] Se conocen soluciones débiles para tamaños de tablero 7 × 7 (usando una estrategia de intercambio ), 8 × 8 y 9 × 9; [ cita necesaria ] en el caso de 8 × 8, se conoce una solución débil para todos los movimientos de apertura. [33] Es poco probable que se resuelva fuertemente Hex en un tablero N × N ya que se ha demostrado que el problema es PSPACE completo . [ cita necesaria ] Si Hex se juega en un tablero N × ( N + 1), entonces el jugador que tiene la distancia más corta para conectar siempre puede ganar con una estrategia de emparejamiento simple, incluso con la desventaja de jugar en segundo lugar. [ cita necesaria ]
Borradores internacionales
Se resolvieron todas las posiciones de finales con dos a siete piezas, así como posiciones con piezas de 4×4 y 5×3 donde cada bando tenía un rey o menos, posiciones con cinco hombres contra cuatro hombres, posiciones con cinco hombres contra tres hombres y una rey, y posiciones con cuatro hombres y un rey contra cuatro hombres. Las posiciones de los finales fueron resueltas en 2007 por Ed Gilbert de Estados Unidos. El análisis informático mostró que era muy probable que terminara en empate si ambos jugadores jugaban perfectamente. [34] [ se necesita una mejor fuente ]
m , n , k -juego
Es trivial demostrar que el segundo jugador nunca podrá ganar; ver argumento de robo de estrategia . Casi todos los casos se han resuelto débilmente para k ≤ 4. Se conocen algunos resultados para k = 5. Los juegos se sortean para k ≥ 8. [ cita necesaria ]

Ver también

Referencias

  1. ^ a b C Allis, Louis Victor (23 de septiembre de 1994). Búsqueda de Soluciones en Juegos e Inteligencia Artificial (tesis doctoral). Maastricht: Rijksuniversiteit Limburg. ISBN 90-9007488-0.
  2. ^ H. Jaap van den Herik , Jos WHM Uiterwijk, Jack van Rijswijck, Juegos resueltos: ahora y en el futuro , Inteligencia artificial 134 (2002) 277–311.
  3. ^ ab "Zona de juegos John's Connect Four". tromp.github.io .
  4. ^ "Repositorio de aprendizaje automático de la UCI: conjunto de datos Connect-4". archive.ics.uci.edu .
  5. ^ Frank, Alan (1 de agosto de 1987). "Cazafantasmas". Formas de palabras . 20 (4).
  6. ^ Precio, Robert. "Hexapawn". www.chessvariants.com .
  7. ^ Resolviendo Kalah por Geoffrey Irving, Jeroen Donkers y Jos Uiterwijk.
  8. ^ Resolviendo (6,6) -Kalaha por Anders Carstensen.
  9. ^ Bouton, CL (1901-1902), "Nim, un juego con una teoría matemática completa ", Annals of Mathematics , 3 (14): 35–39, doi :10.2307/1967631, JSTOR  1967631
  10. ^ Gasser, Ralph (1996). "Resolviendo el Morris de nueve hombres". En Nowakowski, Richard (ed.). Juegos sin azar (PDF) . vol. 29. Cambridge: Prensa de la Universidad de Cambridge. págs. 101-113. ISBN 9780521574112. Archivado desde el original (PDF) el 24 de julio de 2015 . Consultado el 3 de enero de 2022 .
  11. ^ Morris de nueve hombres es un empate de Ralph Gasser
  12. ^ "resuelto: el orden gana: orden y caos".
  13. ^ Pangki está fuertemente resuelto como empate por Jason Doucette
  14. ^ http://wouterkoolen.info/Talks/quarto.pdf [ URL básica PDF ]
  15. ^ "414298141056 ¡Basta con sorteos en cuarto!".
  16. ^ "Cuarto". Archivado desde el original el 12 de octubre de 2004.
  17. ^ Teeko, por E. Weisstein
  18. ^ Elabridi, Ali. "Resolver débilmente el juego de los tres mosqueteros utilizando inteligencia artificial y teoría de juegos" (PDF) .
  19. ^ Tres mosqueteros, de J. Lemaire
  20. ^ Tres en raya, por R. Munroe
  21. ^ Wythoff, WA (1907), "Una modificación del juego de nim", Nieuw Archief voor Wiskunde , 7 (2): 199–202
  22. ^ Schaeffer, Jonathan (19 de julio de 2007). "Las damas están resueltas". Ciencia . 317 (5844): 1518–22. Código bibliográfico : 2007 Ciencia... 317.1518S. doi : 10.1126/ciencia.1144079 . PMID  17641166. S2CID  10274228.
  23. ^ "Proyecto - Chinook - Campeón mundial de damas hombre-máquina" . Consultado el 19 de julio de 2007 .
  24. ^ Mullins, Justin (19 de julio de 2007). "Las damas 'resueltas' después de años de hacer cálculos numéricos". Servicio de noticias NewScientist.com . Consultado el 6 de diciembre de 2020 .
  25. ^ MPD Schadd; MHM Winands; JWHM Uiterwijk; HJ van den Herik; MHJ Bergsma (2008). "La mejor jugada en Fanorona lleva al empate" (PDF) . Nuevas Matemáticas y Computación Natural . 4 (3): 369–387. doi :10.1142/S1793005708001124. Archivado desde el original (PDF) el 4 de marzo de 2016 . Consultado el 8 de abril de 2015 .
  26. ^ Watkins, marca. "Perder ajedrez: 1. e3 gana para las blancas" (PDF) . Consultado el 17 de enero de 2017 .
  27. ^ Takizawa, Hiroki (30 de octubre de 2023). "Otelo está resuelto". arXiv : 2310.19387 [cs.AI].
  28. ^ Hilarie K. Orman: Pentominós: un primer jugador gana en juegos sin posibilidades , Publicaciones de MSRI - Volumen 29, 1996, páginas 339-344. En línea: pdf.
  29. ^ Tejo Jin Lim. Sobre la poda hacia adelante en Game-Tree Search Archivado el 25 de marzo de 2009 en Wayback Machine . Doctor. Tesis, Universidad Nacional de Singapur , 2007.
  30. ^ 5 × 5 Go lo resuelve Erik van der Werf
  31. ^ "首期喆理围棋沙龙举行 李喆7路盘最优解具有里程碑意义_下棋想赢怕输_新浪博客". blog.sina.com.cn. _(que dice que la solución 7x7 está débilmente resuelta y todavía está bajo investigación, 1. el komi correcto es 9 (4,5 piedras); 2. hay múltiples árboles óptimos - los primeros 3 movimientos son únicos - pero dentro de los primeros 7 movimientos hay son 5 árboles óptimos; 3. Hay muchas formas de jugar que no afectan el resultado)
  32. ↑ Contando posiciones legales en Go Archivado el 30 de septiembre de 2007 en Wayback Machine , Tromp y Farnebäck, consultado el 24 de agosto de 2007.
  33. ^ P. Henderson, B. Arneson y R. Hayward, [webdocs.cs.ualberta.ca/~hayward/papers/solve8.pdf Resolución de 8 × 8 Hex], Proc. IJCAI-09 505-510 (2009) Consultado el 29 de junio de 2010.
  34. ^ Algunas de las tablas de finales de nueve piezas de Ed Gilbert

Otras lecturas

enlaces externos