Juego resuelto

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

Ultra-débil

Demostrar 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 implicando un argumento de robo de estrategia) que no necesita determinar ningún movimiento de la jugada perfecta.

Débiles

Proporcionar 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, producir 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. No significa necesariamente que un programa de computadora que use la solución jugará de manera óptima contra un oponente imperfecto.

Fuerte

Proporcionar 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 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 logra un juego perfecto.^{[cita requerida]}

Por el contrario, las pruebas "sólidas" a menudo proceden por la fuerza bruta, utilizando una computadora para buscar exhaustivamente un árbol de juego para averiguar qué pasarí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 un 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 sólida, 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 combinatorios.

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 suficientemente grande) generalmente no afecta la jugabilidad.

Por otra parte, incluso si el juego no se soluciona, es posible que un algoritmo produce una buena solución aproximada: por ejemplo, un artículo en Science de enero de 2015, afirma que su bot de póquer Texas hold 'em Cepheus garantiza que una vida humana de juego no es suficiente para establecer con significación estadística que su estrategia no es una solución exacta.[3][4][5]

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.[1] Con base en las reglas de un juego, cada posible posición final puede evaluarse (como una victoria, una derrota o un empate). Por 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. Por 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 final (en forma de bases de tablas de finales), 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.

Awari (un juego de la familia Mancala)

Henri Bal y John Romein en la Vrije Universiteit en Ámsterdam, Holanda (2002) resolvieron fuertemente la variante de Oware que permite el final del juego "grand slams". Cualquiera de los jugadores puede forzar el juego a empate.

Palillos

El segundo jugador siempre puede forzar una victoria.^{[cita requerida]}

Conecta 4

Resuelto primero por James D. Allen el 1 de octubre de 1988, e independientemente por Victor Allis el 16 de octubre de 1988.[6] El primer jugador puede forzar una victoria. Fuertemente resuelto por la base de datos de 8 capas de John Tromp[7] (4 de febrero de 1995). Resuelto débilmente para todos los tamaños de tablero donde el ancho + alto es como máximo 15 (así como 8 × 8 a finales de 2015)[6] (18 de febrero de 2006).

Damas inglesas

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.[8] Las damas es el juego más grande que se ha resuelto hasta la fecha, con un espacio de búsqueda de 5×10²⁰.[9] El número de cálculos involucrados fue de 10¹⁴, 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.[10]

Fanorona

Débilmente resuelto por Maarten Schadd. El juego es un empate.^{[cita requerida]}

Gomoku

Resuelto por Victor Allis (1993). El primer jugador puede forzar una victoria sin reglas de apertura.

Ghost

Resuelto por Alan Frank usando el Diccionario oficial de jugadores de Scrabble en 1987.^{[cita requerida]}

Guess Who?

Fuertemente resuelto por Mihai Nica en 2016.[11] El primer jugador tiene un 63% de posibilidades de ganar con un juego óptimo de ambos lados.

Hex

• Un argumento de robo de estrategia (como lo usa John Nash) muestra que el primer jugador no puede perder todos los tamaños de tablero cuadrado. 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 tablero 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 para el tablero 7 × 7.
• Es poco probable que se resuelva de manera sólida Hex en tablero de N × N, ya que se ha demostrado que el problema es PSPACE completo.
• 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..[12]

Hexapawn

Variante 3 × 3 resuelta como una victoria para el negro, también se resolvieron varias otras variantes más grandes.[13]

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 gran ventaja para el primer jugador.[14][15] 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. Hay que tener en cuenta que todos estos resultados se refieren a la variante de captura a cielo abierto 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.

Juego L

Fácilmente solucionable. Cualquiera de los jugadores puede forzar el juego a empate.

Ajedrez pierde-gana

Débilmente resuelto como una victoria para las blancas comenzando con 1. e3.[16]

Maharajá y los cipayos

Este juego asimétrico es una victoria para el jugador de cipayos con un juego correcto.

Nim

Fuertemente resuelto.

Juego del molino

Resuelto por Ralph Gasser (1993). Cualquiera de los jugadores puede forzar el juego a empate.[17]

Orden y caos

Orden (primer jugador) gana.[18]

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).[19] 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.

Pentago

Fuertemente resuelto.[20] El primer jugador gana.

Pentominós

Débilmente resuelto por HK Orman.[21] Es una victoria para el primer jugador.

Poddavki (damas rusas)

Resuelto por Osipov y Morozev en 2011. Una victoria blanca.^{[cita requerida]}

Quarto

Resuelto por Luc Goossens (1998). Dos jugadores perfectos siempre empatará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 como 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.[22]

Three men's morris

Trivialmente solucionable. Cualquiera de los jugadores puede forzar el juego a empate.

Los tres mosqueteros

Fuertemente resuelto por Johannes Laire en 2009, y débilmente resuelto por Ali Elabridi en 2017.[23] Es una victoria para las piezas azules (los hombres del cardenal Richelieu, o el enemigo).[24]

Tic-tac-toe

Trivialmente muy resoluble debido al pequeño árbol de juego.[25] El juego es un empate si no se cometen errores, sin posibilidad de equivocarse en la jugada inicial.

Bagh-Chal (Tigres y cabras)

Débilmente resuelto por Yew Jin Lim (2007). El juego es un empate.[26]

Ajedrez

La solució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 (soluciones sólidas) para 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 el Maharajah y los cipayos es una serie de movimientos fácilmente memorables que garantizan la victoria al jugador "cipayo".

Go

El tablero de 5 × 5 se resolvió débilmente para todos los movimientos de apertura en 2002.[27] El tablero de 7 × 7 se resolvió débilmente en 2015.[28] Los humanos suelen jugar en un tablero de 19 × 19 que es más de 145 órdenes de magnitud más complejo que 7 × 7.[29]

Damas

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.[30]

Juego m, n, k

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 (Othello)

Resuelto débilmente en un tablero de 4 × 4 y 6 × 6 como segunda victoria de jugador en julio de 1993 por Joel Feinstein.[31] En tablero de 8 × 8 (el estándar) está matemáticamente sin resolver, aunque el análisis por computadora muestra un empate probable. No existen estimaciones fuertemente supuestas que no sean mayores posibilidades para el jugador inicial (negro) en tableros de 10 × 10 y mayores.

• Ajedrez por computadora
• Go por computadora
• Otelo en computadoras
• Complejidad en los juegos
• Teorema de Zermelo

En inglés:

• Allis, Beating the World Champion? The state-of-the-art in computer game playing. en New Approaches to Board Games Research.

En inglés:

• Complejidad computacional en juegos y acertijos
• GamesCrafters