Juego resuelto - Solved game

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 a la perfección. Este concepto se suele aplicar a los juegos de estrategia abstractos , y especialmente a los juegos con información completa y sin elementos de azar; La resolución de un juego de este tipo puede utilizar la teoría de juegos combinatoria y / o la asistencia informática.

Visión general

Un juego de dos jugadores se puede resolver en varios niveles:

Ultra-débil
Demuestre si el primer jugador ganará, perderá o empatará desde la posición inicial, con un juego perfecto en ambos lados. Esta puede ser una prueba no constructiva (posiblemente involucrando un argumento de robo de estrategia ) que no necesita determinar ningún movimiento de la jugada perfecta.
Débil
Proporcione un algoritmo que asegure una victoria para un jugador, o un empate para cualquiera, contra cualquier posible movimiento del oponente, desde el comienzo del juego. Es decir, produzca al menos un juego ideal completo (todos los movimientos comienzan a terminar) con la prueba de que cada movimiento es óptimo para el jugador que lo realiza.
Fuerte
Proporcione un algoritmo que pueda producir movimientos perfectos desde cualquier posición, incluso si ya se han cometido errores en uno o ambos lados.

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

Por el contrario, las pruebas "sólidas" a menudo proceden por la fuerza bruta, utilizando una computadora para buscar exhaustivamente un árbol del juego para averiguar qué sucedería si se realizara el 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 las razones más profundas por las que algunos juegos se pueden resolver como un empate, y otros juegos aparentemente muy similares se pueden resolver como 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, tal algoritmo requeriría una cantidad de tiempo inviable para generar un movimiento en una posición dada, un juego no se considera resuelto débil o fuertemente a menos que el algoritmo pueda ser ejecutado por hardware existente en una posición determinada. tiempo razonable. Muchos algoritmos se basan en una enorme base de datos pregenerada y, de hecho, no son más.

Como ejemplo de una solución fuerte, el juego de tic-tac-toe se puede resolver como un empate para ambos jugadores con un juego perfecto (un resultado que incluso los escolares pueden determinar manualmente). Juegos como nim también admiten un análisis riguroso utilizando la teoría de juegos combinatoria .

Si un juego se resuelve no es necesariamente lo mismo que si sigue siendo interesante para los humanos. Incluso un juego fuertemente resuelto puede ser interesante si su solución es demasiado compleja para ser memorizada; a la inversa, un juego resuelto débilmente puede perder su atractivo si la estrategia ganadora es lo suficientemente simple de recordar (por ejemplo, Maharajah y los cipayos ). 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 la teoría de juegos , el juego perfecto es el comportamiento o la 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 se resuelve el juego. Según las reglas de un juego, se puede evaluar cada posible posición final (como una victoria, una derrota o un empate). Mediante el razonamiento hacia atrás , uno 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 que se evalúan por igual. Por ejemplo, un jugador perfecto en una posición empatada siempre obtendría un empate o una victoria, nunca una derrota. Si hay varias 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 puede generalizarse a juegos de información no perfectos , como la estrategia que garantizaría el resultado mínimo esperado 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 la misma probabilidad (1/3). La desventaja de 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 de juego aún podría beneficiarse de las soluciones del juego desde ciertas posiciones del juego final (en forma de tablas de finales del juego ), lo que le permitirá jugar perfectamente después de algunos años. punto en el juego. Los programas de ajedrez por computadora son bien conocidos por hacer esto.

Juegos resueltos

Awari (un juego de la familia Mancala )
Henri Bal y John Romein en la Vrije Universiteit de Ámsterdam , Países Bajos (2002) resolvieron enérgicamente la variante de Oware que permite el final del juego con "grand slams" . Cualquiera de los jugadores puede forzar el juego a empate.
Palillos
El segundo jugador siempre puede forzar una victoria.
Conectar cuatro
Resuelto primero por James D. Allen el 1 de octubre de 1988, e independientemente por Victor Allis el 16 de octubre de 1988. El primer jugador puede forzar una victoria. Fuertemente resuelto por la base de datos de 8 capas de John Tromp (4 de febrero de 1995). Resuelto débilmente para todos los tamaños de tabla donde el ancho + alto es como máximo 15 (así como 8 × 8 a fines de 2015) (18 de febrero de 2006).
Borradores ingleses (damas)
Esta variante de borradores de 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. Damas es el juego más grande que se ha resuelto hasta la fecha, con un espacio de búsqueda de 5 × 10 20 . 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 punto máximo hasta alrededor de 50.
Fanorona
Débilmente resuelto por Maarten Schadd. El juego es un empate.
Gomoku gratis
Resuelto por Victor Allis (1993). El primer jugador puede forzar una victoria sin reglas de apertura.
Fantasma
Resuelto por Alan Frank usando el Diccionario oficial de jugadores de Scrabble en 1987.
Maleficio
  • Un argumento de robo de estrategia (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 ultra-débil resuelto como una victoria del primer jugador.
  • Fuertemente resuelto por varias computadoras para tamaños de placa de hasta 6 × 6.
  • Jing Yang ha demostrado una estrategia ganadora (solución débil) para tableros de tamaño 7 × 7, 8 × 8 y 9 × 9.
  • Una estrategia ganadora para Hex con intercambio es conocida por el tablero 7 × 7.
  • Es poco probable que se resuelva de manera sólida Hex en una placa N × N, ya que se ha demostrado que el problema es completo con PSPACE .
  • Si se juega Hex en un tablero N × ( N +1), el jugador que tenga la distancia más corta para conectarse siempre puede ganar con una simple estrategia de emparejamiento, incluso con la desventaja de jugar segundo.
  • Se conoce una solución débil para todos los movimientos de apertura en el tablero de 8 × 8.
Hexaengendro
Variante 3 × 3 resuelta como una victoria para el negro, también se resolvieron varias otras variantes más grandes.
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. Mark Rawlings, de Gaithersburg, MD, 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 totalizan 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 de pozo vacío. variante y, por lo tanto, tienen un interés muy limitado para el juego estándar. El análisis del juego de reglas estándar ahora se ha publicado 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 por al menos 4 para el primer jugador.
L juego
Fácilmente solucionable. Cualquiera de los jugadores puede forzar el juego a empate.
Perder ajedrez
Débilmente resuelto como una victoria para las blancas comenzando con 1. e3.
Maharajá y los cipayos
Este juego asimétrico es una victoria para el jugador de cipayos con un juego correcto.
Nim
Fuertemente resuelto.
Morris de nueve hombres
Resuelto por Ralph Gasser (1993). Cualquiera de los jugadores puede forzar el juego a empate.
Orden y caos
Orden (primer jugador) gana.
Ohvalhu
Débilmente resuelto por humanos, pero probado por computadoras. (Dakon, sin embargo, no es idéntico a Ohvalhu, el juego que en realidad había sido observado por De Voogt)
Pangki
Fuertemente resuelto por Jason Doucette (2001). El juego es un empate. Solo hay dos primeros movimientos únicos si descarta posiciones reflejadas. Uno fuerza el empate y el otro le da al oponente una victoria forzada en 15.
Pentominós
Débilmente resuelto por HK Orman. Es una victoria para el primer jugador.
Poddavki ("Damas de regalo rusas")
Resuelto por Osipov y Morozev en 2011. Una victoria blanca.
Libro en cuarto
Resuelto por Luc Goossens (1998). Dos jugadores perfectos siempre dibujarán.
Qubic
Débilmente resuelto por Oren Patashnik (1980) y Victor Allis . El primer jugador gana.
Juego tipo Renju sin reglas de apertura involucradas
Reclamado resuelto por János Wagner e István Virág (2001). Una victoria para el primer jugador.
Sim
Débilmente resuelto: gana para el segundo jugador.
Teeko
Resuelto por Guy Steele (1998). Dependiendo de la variante, el primer jugador gana o empata.
Morris de tres hombres
Trivialmente solucionable. Cualquiera de los jugadores puede forzar el juego a empate.
Tres mosqueteros
Fuertemente resuelto por Johannes Laire en 2009, y débilmente resuelto por Ali Elabridi en 2017. Es una victoria para las piezas azules (los hombres del cardenal Richelieu, o el enemigo).
Tic-tac-toe
Trivialmente muy resoluble debido al pequeño árbol de juego. El juego es un empate si no se cometen errores, sin posibilidad de error en el movimiento de apertura.
Tigres y cabras
Débilmente resuelto por Yew Jin Lim (2007). El juego es un empate.
El juego de Wythoff
Fuertemente resuelto.

Juegos parcialmente resueltos

Ajedrez
Artículo principal: Resolver ajedrez
La resolución completa del ajedrez sigue siendo difícil de alcanzar, y se especula que la complejidad del juego puede impedir que se resuelva. A través del análisis informático retrógrado , se han encontrado tablas de finales de juego (soluciones sólidas) para todos los finales de tres a siete piezas , contando a los dos reyes como piezas.
Se han resuelto algunas variantes de ajedrez en un tablero más pequeño con número reducido de piezas . También se han resuelto algunas otras variantes populares; por ejemplo, una solución débil para Maharajah and the Sepoys es una serie de movimientos fácilmente memorables que garantizan la victoria al jugador "cipay".
Ir
El tablero de 5 × 5 se resolvió débilmente para todos los movimientos de apertura en 2002. El tablero de 7 × 7 se resolvió débilmente en 2015. Los humanos suelen jugar en un tablero de 19 × 19 que es más de 145 órdenes de magnitud más complejo que el 7 × 7.
Borradores internacionales
Se resolvieron todas las posiciones finales con dos a siete piezas, así como posiciones con piezas 4 × 4 y 5 × 3 donde cada lado tenía un rey o menos, posiciones con cinco hombres contra cuatro hombres, posiciones con cinco hombres contra tres hombres y uno. 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 empate si ambos jugadores jugaban perfectamente.
m , n , k -juego
Es trivial demostrar que el segundo jugador nunca puede 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 dibujan para k ≥ 8.
Reversi (Otelo)
Resuelto débilmente en un tablero de 4 × 4 y 6 × 6 como segunda victoria de jugador en julio de 1993 por Joel Feinstein. En una placa de 8 × 8 (la estándar) está matemáticamente sin resolver, aunque el análisis por computadora muestra un posible empate. No existen estimaciones sólidas que no sean mayores posibilidades para el jugador inicial (negro) en tableros de 10 × 10 y mayores.

Ver también

Referencias

Otras lecturas

  • Allis, ¿ vencer al campeón mundial? Lo último en juegos de computadora. en Nuevos enfoques para la investigación de juegos de mesa.

enlaces externos