stringtranslate.com

Juego resuelto

Un juego resuelto es un juego cuyo resultado (ganancia, derrota o empate ) puede predecirse correctamente desde cualquier posición, suponiendo que ambos jugadores juegan a la perfección. Este concepto se aplica habitualmente a juegos de estrategia abstracta y, especialmente, a juegos con información completa y sin ningún elemento de azar; para resolver un juego de este tipo se puede utilizar la teoría de juegos combinatorios y/o la asistencia informática.

Descripción general

Un juego para dos jugadores se puede resolver en varios niveles: [1] [2]

Solución ultra débil

Demuestre si el primer jugador ganará, perderá o empatará desde la posición inicial, dado un juego perfecto de ambos bandos. Esta puede ser una prueba no constructiva (que posiblemente implique un argumento de robo de estrategia ) que no necesita determinar ningún detalle de la jugada perfecta.

Solución débil

Proporcionar un algoritmo que asegure una victoria para un jugador, o un empate para cualquiera, contra cualquier posible jugada del oponente, desde el comienzo del juego.

Solución fuerte

Proporcionar un algoritmo que pueda producir un juego perfecto para ambos jugadores desde cualquier posición, incluso si ya se ha producido un juego imperfecto en uno o ambos lados.

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

En cambio, las demostraciones "fuertes" suelen proceder por la fuerza bruta, es decir, empleando una computadora para buscar exhaustivamente en un árbol de juego qué sucedería si se lograra un juego perfecto. La demostración resultante proporciona una estrategia óptima para cada posición posible en el tablero. Sin embargo, estas demostraciones no son tan útiles para entender las razones más profundas por las que algunos juegos se pueden resolver como empate y otros juegos aparentemente muy similares se pueden resolver como victoria.

Dadas las reglas de cualquier juego de dos personas con un número finito de posiciones, siempre se puede construir de manera trivial un algoritmo minimax que recorrería exhaustivamente el árbol de 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 dada, no se considera que un juego se resuelva de manera débil o fuerte a menos que el algoritmo pueda ejecutarse con hardware existente en un tiempo razonable. Muchos algoritmos se basan en una enorme base de datos pregenerada y, en realidad, no son nada más.

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

El hecho de que un juego se resuelva o no no significa necesariamente que siga siendo interesante para los humanos. Incluso un juego con una solución sólida puede seguir siendo interesante si su solución es demasiado compleja para memorizarla; por el contrario, un juego con una solución débil puede perder su atractivo si la estrategia ganadora es lo suficientemente simple como para recordarla (por ejemplo, Maharajah and the Sepoys ). Una solución ultra débil (por ejemplo, Chomp o Hex en un tablero lo 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 para un juego se conoce cuando el juego está resuelto. [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 que se mueve, y un movimiento perfecto en una posición sería una transición entre posiciones que se evalúan igualmente. Como ejemplo, un jugador perfecto en una posición de empate siempre obtendría un empate o una victoria, nunca una derrota. Si hay múltiples opciones con el mismo resultado, el juego perfecto a veces se considera 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 con información no perfecta , como la estrategia que garantizaría el resultado esperado mínimo más alto independientemente de la estrategia del oponente. Como ejemplo, la estrategia perfecta para piedra, papel o tijera sería elegir aleatoriamente cada una de las opciones con una probabilidad igual (1/3). 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 esperado mínimo.

Aunque la estrategia óptima de una partida puede no ser conocida (aún), una computadora que juegue podría beneficiarse de las soluciones de la partida a partir de ciertas posiciones finales (en forma de tablas de finales ), que le permitirán jugar perfectamente después de cierto punto en la partida. Los programas de ajedrez para computadora son bien conocidos por hacer esto.

Juegos resueltos

Awari (un juego de la familia Mancala )
La variante de Oware que permite "grand slams" de finalización de partidas fue resuelta de forma contundente por Henri Bal y John Romein en la Vrije Universiteit de Ámsterdam , Países Bajos (2002). Cualquier jugador puede forzar el empate.
Palillos
Muy resuelto. Si dos jugadores juegan a la perfección, el juego continuará indefinidamente. [ cita requerida ]
Conecta cuatro
El juego de Conecta Cuatro ha sido resuelto
Resuelto por primera vez 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. Resuelto firmemente 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 tablero donde ancho+alto es como máximo 15 (así como 8x8 a fines de 2015) [3] (18 de febrero de 2006). Resuelto para todos los tamaños de tablero donde ancho+alto es igual a 16 el 22 de mayo de 2024. [5]
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. [6]
Hexapawn (Papa hexagonal)
La variante 3×3 se resolvió como una victoria para las negras; también se resolvieron otras variantes más grandes. [7]
Kalah
La mayoría de las variantes fueron 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. [8] [9]
Juego l
Fácilmente solucionable. Cualquier jugador puede forzar el empate.
El maharajá y los cipayos
Este juego asimétrico es una victoria para el jugador cipayo con un juego correcto. [ cita requerida ]
Nim
Fuertemente resuelto. [10]
Morris de nueve hombres
Resuelto por Ralph Gasser (1993). Cualquier jugador puede forzar el empate. [11] [12]
Orden y Caos
El orden (primer jugador) gana. [13]
Ohvalhu
Resuelto débilmente por humanos, pero probado por computadoras. [ cita requerida ] (Dakon, sin embargo, no es idéntico a Ohvalhu, el juego que en realidad había sido observado por de Voogt) [ cita requerida ]
Pangki
Jason Doucette (2001) resolvió el problema con firmeza. [14] La partida es un empate. Solo hay dos primeros movimientos únicos si se descartan las posiciones reflejadas. Uno fuerza el empate y el otro le da al oponente una victoria forzada en 15 movimientos.
Pentágono
Geoffrey Irving lo resolvió con gran habilidad gracias a una supercomputadora del NERSC . El primer jugador gana.
Libro en cuarto
Resuelto por Luc Goossens (1998). Dos jugadores perfectos siempre empatarán. [15] [16] [17]
Juego tipo Renju sin reglas de apertura involucradas
János Wagner e István Virág (2001) afirman que está resuelto. [18] Una victoria del primer jugador.
Teeko
Resuelto por Guy Steele (1998). Según la variante, el primer jugador gana o hay un empate. [19]
Morris de tres hombres
Trivialmente solucionable. Cualquier jugador puede forzar el empate. [ cita requerida ]
Tres mosqueteros
Resuelto con fuerza por Johannes Laire en 2009 y resuelto con debilidad por Ali Elabridi en 2017. [20] Es una victoria para las piezas azules (los hombres del cardenal Richelieu, o, el enemigo). [21]
Tres en raya
Trivialmente, es muy soluble debido al pequeño árbol de juego. [22] El juego es un empate si no se cometen errores, y no es posible cometer errores en el movimiento de apertura.
El juego de Wythoff
Resuelto firmemente por WA Wythoff en 1907. [23]

Resoluciones débiles

Damas inglesas
El equipo de Jonathan Schaeffer resolvió de forma débil esta variante de 8×8 de las damas el 29 de abril de 2007. Desde la posición inicial estándar, ambos jugadores pueden garantizar un empate con un juego perfecto. [24] Las damas tienen un espacio de búsqueda de 5×10 20 posibles posiciones de juego. [25] El número de cálculos involucrados fue de 10 14 , que se realizaron durante un período de 18 años. El proceso involucró desde 200 computadoras de escritorio en su apogeo hasta alrededor de 50. [26]
Fanorona
Maarten Schadd lo resolvió de forma débil. El juego terminó en tablas. [27]
Perdiendo ajedrez
Se resolvió débilmente en 2016 como una victoria para las blancas a partir de 1. e3. [28]
Otelo (Reversi)
Resuelto débilmente en 2023 por Hiroki Takizawa, investigador de Preferred Networks . [29] Desde la posición inicial estándar en un tablero de 8×8, 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 posibles posiciones de juego.
Pentominós
Débilmente resuelto por HK Orman. [30] Es una victoria para el primer jugador.
Qubic
Resuelto débilmente por Oren Patashnik (1980) y Victor Allis . El primer jugador gana.
Sim
Solución débil: victoria para el segundo jugador. [ cita requerida ]
Corderos y tigres
Yew Jin Lim (2007) lo resolvió de forma débil. El juego terminó en tablas. [31]

Juegos parcialmente resueltos

Ajedrez
La solución total del 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 sólidas) para todos los finales de tres a siete piezas , contando a los dos reyes como piezas.
Se han resuelto algunas variantes del ajedrez en un tablero más pequeño y con un número reducido de piezas . También se han resuelto otras variantes populares; por ejemplo, una solución débil para el Maharajá y los cipayos es una serie de movimientos fácilmente memorables que garantiza la victoria al jugador "cipayos".
Ir
El tablero de 5×5 fue resuelto débilmente para todos los movimientos de apertura en 2002. [32] El tablero de 7×7 fue resuelto débilmente en 2015. [33] Los humanos normalmente juegan en un tablero de 19×19, que es 145 órdenes de magnitud más complejo que el de 7×7. [34]
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 tablero. Combinado con una prueba de la imposibilidad de un empate, esto muestra que el juego es una victoria del primer jugador (por lo que se resuelve de manera ultra débil). [ cita requerida ] En tamaños de tablero particulares, se sabe más: varias computadoras lo resuelven de manera fuerte para tamaños de tablero de hasta 6 × 6. [ cita requerida ] Se conocen soluciones débiles para tamaños de tablero de 7 × 7 (usando una estrategia de intercambio ), 8 × 8 y 9 × 9; [ cita requerida ] en el caso de 8 × 8, se conoce una solución débil para todos los movimientos de apertura. [35] Es poco probable que se resuelva de manera fuerte Hex en un tablero de N × N , ya que se ha demostrado que el problema es PSPACE-completo . [ cita requerida ] Si se juega Hex en un tablero N × ( N + 1), entonces el jugador que tiene la distancia más corta para conectarse siempre puede ganar con una estrategia de emparejamiento simple, incluso con la desventaja de jugar segundo. [ cita requerida ]
Damas internacionales
Se resolvieron todas las posiciones finales con dos a siete piezas, así como posiciones con 4x4 y 5x3 piezas donde cada bando tenía un rey o menos, posiciones con cinco hombres contra cuatro hombres, posiciones con cinco hombres contra tres hombres y un rey, y posiciones con cuatro hombres y un rey contra cuatro hombres. Las posiciones finales fueron resueltas en 2007 por Ed Gilbert de los Estados Unidos. El análisis por computadora mostró que era muy probable que terminara en tablas si ambos jugadores jugaban perfectamente. [36] [ se necesita una mejor fuente ]
m , n , k -juego
Es trivial demostrar que el segundo jugador nunca puede ganar; véase el argumento del robo de estrategia . Casi todos los casos se han resuelto de forma débil para k ≤ 4. Se conocen algunos resultados para k = 5. Los juegos son tablas para k ≥ 8. [ cita requerida ]

Véase también

Referencias

  1. ^ abc 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 "El patio de juegos Conecta 4 de John". tromp.github.io .
  4. ^ "Repositorio de aprendizaje automático de la UCI: conjunto de datos Connect-4". archive.ics.uci.edu .
  5. ^ "ChristopheSteininger/c4". github.com .
  6. ^ Frank, Alan (1 de agosto de 1987). "Los Cazafantasmas". Word Ways . 20 (4).
  7. ^ Price, Robert. "Hexapawn". www.chessvariants.com .
  8. ^ Resolviendo Kalah por Geoffrey Irving, Jeroen Donkers y Jos Uiterwijk.
  9. ^ Resolviendo (6,6) -Kalaha por Anders Carstensen.
  10. ^ 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
  11. ^ Gasser, Ralph (1996). "Resolviendo el Morris de los Nueve Hombres". En Nowakowski, Richard (ed.). Juegos sin azar (PDF) . Vol. 29. Cambridge: Cambridge University Press. págs. 101–113. ISBN 9780521574112Archivado desde el original (PDF) el 24 de julio de 2015. Consultado el 3 de enero de 2022 .
  12. ^ " Nine Men's Morris es un empate" de Ralph Gasser
  13. ^ "resuelto: El orden triunfa - Orden y Caos".
  14. ^ Jason Doucette resuelve con contundencia el empate de Pangki
  15. ^ "Quarto" (PDF) . wouterkoolen.info . Consultado el 29 de febrero de 2024 .
  16. ^ "414298141056 ¡Cuarto sorteo suficiente!".
  17. ^ "Cuarto". Archivado desde el original el 12 de octubre de 2004.
  18. ^ Wágner, János & Virág, István (marzo de 2001). "Resolviendo Renju" (PDF) . Széchenyi Egyetem - Universidad de Győr . pag. 30. Archivado (PDF) desde el original el 24 de abril de 2024 . Consultado el 24 de abril de 2024 .{{cite web}}: Mantenimiento CS1: fecha y año ( enlace )
  19. ^ Teeko, por E. Weisstein
  20. ^ Elabridi, Ali. "Resolución débil del juego de los Tres Mosqueteros utilizando inteligencia artificial y teoría de juegos" (PDF) .
  21. ^ Los tres mosqueteros, de J. Lemaire
  22. ^ Tres en raya, de R. Munroe
  23. ^ Wythoff, WA (1907), "Una modificación del juego de nim", Nieuw Archief voor Wiskunde , 7 (2): 199–202
  24. ^ Schaeffer, Jonathan (19 de julio de 2007). "El juego de damas está resuelto". Science . 317 (5844): 1518–22. Bibcode :2007Sci...317.1518S. doi : 10.1126/science.1144079 . PMID  17641166. S2CID  10274228.
  25. ^ "Proyecto - Chinook - Campeón del mundo de damas hombre-máquina" . Consultado el 19 de julio de 2007 .
  26. ^ Mullins, Justin (19 de julio de 2007). "Las damas se 'resuelven' después de años de análisis numérico". Servicio de noticias NewScientist.com . Consultado el 6 de diciembre de 2020 .
  27. ^ MPD Schadd; MHM Winands; JWHM Uiterwijk; HJ van den Herik; MHJ Bergsma (2008). "La mejor jugada en Fanorona lleva a tablas" (PDF) . Nuevas matemáticas y computación natural . 4 (3): 369–387. doi :10.1142/S1793005708001124. Archivado desde el original (PDF) el 2016-03-04 . Consultado el 2015-04-08 .
  28. ^ Watkins, Mark. "Perdiendo ajedrez: 1. e3 gana para las blancas" (PDF) . Consultado el 17 de enero de 2017 .
  29. ^ Takizawa, Hiroki (30 de octubre de 2023). "Otelo está resuelto". arXiv : 2310.19387 [cs.AI].
  30. ^ Hilarie K. Orman: Pentominós: la victoria del primer jugador en juegos sin posibilidades , MSRI Publications – Volumen 29, 1996, páginas 339-344. En línea: pdf.
  31. ^ Yew Jin Lim. Sobre la poda progresiva en la búsqueda de árboles de caza. Archivado el 25 de marzo de 2009 en Wayback Machine . Tesis doctoral, Universidad Nacional de Singapur , 2007.
  32. ^ 5 × 5 Go lo resuelve Erik van der Werf
  33. ^ "首期喆理围棋沙龙举行 李喆7路盘最优解具有里程碑意义_下棋想赢怕输_新浪博客". blog.sina.com.cn.​(que dice que la solución 7x7 está resuelta débilmente y aún 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 5 árboles óptimos; 3. Hay muchas formas de jugar que no afectan el resultado)
  34. ^ Conteo de 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.
  35. ^ P. Henderson, B. Arneson y R. Hayward, [webdocs.cs.ualberta.ca/~hayward/papers/solve8.pdf Solución de 8×8 Hex], Proc. IJCAI-09 505-510 (2009) Consultado el 29 de junio de 2010.
  36. ^ Algunas de las tablas de finales de nueve piezas de Ed Gilbert

Lectura adicional

Enlaces externos