Juego resuelto

Un juego resuelto es aquel cuyo resultado (victoria, derrota o empate ) puede predecirse correctamente desde cualquier posición, suponiendo que ambos jugadores jueguen a la perfección. Este concepto se aplica generalmente a juegos de estrategia abstractos , 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 o la ayuda de un ordenador.

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

En 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 el juego está resuelto. ^{[ 1 ]} Basándose en las reglas de un juego, cada posición final posible puede evaluarse (como victoria, derrota o empate). Mediante razonamiento inverso , se puede evaluar recursivamente una posición no final como idéntica a la posición que está a un movimiento de distancia y que es la mejor valorada para el jugador cuyo turno es. Por lo tanto, una transición entre posiciones nunca puede resultar en una mejor evaluación para el jugador que mueve, y un movimiento perfecto en una posición sería una transición entre posiciones que se evalúan de igual manera. Por 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 puede generalizarse a juegos con información imperfecta , como la estrategia que garantiza 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 probabilidad (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 otra siempre será igual al resultado mínimo esperado.

Aunque la estrategia óptima de una partida aún no se conozca, un ordenador que juega puede beneficiarse de soluciones de la partida a partir de ciertas posiciones finales (en forma de tablas de finales ), lo que le permitirá jugar a la perfección a partir de cierto punto del juego. Los programas de ajedrez por ordenador son conocidos por hacer esto.

Awari (un juego de la familia Mancala )

La variante de Oware que permite "grand slams" al final de la partida fue resuelta con éxito por Henri Bal y John Romein en la Universidad Libre de Ámsterdam , Países Bajos (2002). Cualquiera de los jugadores puede forzar un empate.

Palillos

Problema resuelto. Si ambos jugadores juegan a la perfección, el juego continuará indefinidamente.

Conecta cuatro

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 fuertemente 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 8×8 a finales 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 ]} En 2025, el tablero clásico de 7x6 fue resuelto fuertemente en términos de una tabla de búsqueda de victoria-empate-derrota. ^{[ 6 ]}

Gomoku gratis

Resuelto por Victor Allis (1993). El primer jugador puede forzar la victoria sin reglas de apertura. ^{[ 1 ]}

Fantasma

Resuelto por Alan Frank utilizando el Diccionario Oficial de Jugadores de Scrabble en 1987. ^{[ 7 ]}

Hexapawn

La variante 3×3 se resolvió como una victoria para las negras; también se resolvieron otras variantes más grandes. ^{[ 8 ]}

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). Se demostró una fuerte ventaja del primer jugador en la mayoría de los casos. ^{[ 9 ] [ 10 ]}

Juego L

Fácil de resolver. Cualquiera de los dos jugadores puede forzar un empate.

El Maharajá y los cipayos

Este juego asimétrico resulta ganador para el jugador cipayos que juegue correctamente.

Nim

Resuelto de manera contundente. ^{[ 11 ]}

El juego de Morris de nueve hombres

Resuelto por Ralph Gasser (1993). Cualquiera de los jugadores puede forzar un empate. ^{[ 12 ] [ 13 ]}

Orden y caos

El orden (primer jugador) gana. ^{[ 14 ]}

Ohvalhu

Resolvedo con dificultad por humanos, pero probado por ordenadores. (Dakon, sin embargo, no es idéntico a Ohvalhu, el juego que de hecho fue observado por de Voogt).

Pangki

Resuelto con solidez por Jason Doucette (2001). ^{[ 15 ]} El juego termina en tablas. Solo hay dos movimientos iniciales únicos si se descartan las posiciones simétricas. Uno fuerza las tablas y el otro le da al oponente una victoria forzada en 15 movimientos.

Pentago

Resuelto con gran habilidad por Geoffrey Irving con la ayuda de una supercomputadora en NERSC . Gana el primer jugador.

Libro en cuarto

Resuelto por Luc Goossens (1998). Dos jugadores perfectos siempre empatarán. ^{[ 16 ] [ 17 ] [ 18 ]}

Juego tipo Renju sin reglas de apertura.

Afirmado estar resuelto por János Wagner e István Virág (2001). ^{[ 19 ]} Una victoria del primer jugador.

Teeko

Resuelto por Guy Steele (1998). Dependiendo de la variante, gana el primer jugador o hay empate. ^{[ 20 ]}

Tres hombres juegan a la morris

Es un problema trivial de resolver. Cualquiera de los dos jugadores puede forzar un empate.

Los tres mosqueteros

Resuelto con firmeza por Johannes Laire en 2009 y con dificultad por Ali Elabridi en 2017. ^{[ 21 ]} Es una victoria para las piezas azules (los hombres del cardenal Richelieu, o el enemigo). ^{[ 22 ]}

Tres en raya

Extremadamente trivialmente resoluble debido al pequeño árbol de juego. ^{[ 23 ]} El juego es tablas si no se cometen errores, sin posibilidad de error en el primer movimiento.

El juego de Wythoff

Resuelto con éxito por WA Wythoff en 1907. ^{[ 24 ]}

Damas inglesas

Esta variante de damas 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 juego perfecto. ^{[ 25 ]} Las damas tienen un espacio de búsqueda de 5×10 ²⁰ posiciones de juego posibles. ^{[ 26 ]} El número de cálculos involucrados fue 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. ^{[ 27 ]}

Fanorona

Resuelto débilmente por Maarten Schadd. La partida termina en tablas. ^{[ 28 ]}

Perder en el ajedrez

Resuelto débilmente en 2016 como una victoria para las blancas comenzando con 1.  e3. ^{[ 29 ]}

Otelo (Reversi)

Resuelto débilmente en 2023 por Hiroki Takizawa, un investigador de Preferred Networks . ^{[ 30 ]} Sin embargo, las conclusiones del artículo son cuestionadas. ^{[ 31 ]} 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 ²⁸ posiciones de juego posibles.

Pentominós

Resuelto débilmente por HK Orman. ^{[ 32 ]} Es una victoria para el primer jugador.

Qubic

Resuelto débilmente por Oren Patashnik (1980) y Victor Allis . Gana el primer jugador.

Sim

Problema resuelto con dificultad: gana el segundo jugador.

Corderos y tigres

Resuelto débilmente por Yew Jin Lim (2007). El juego es tablas. ^{[ 33 ]}

Ajedrez

Resolver completamente el ajedrez sigue siendo un reto, y se especula que la complejidad del juego podría impedir que se resuelva alguna vez. Mediante análisis informáticos retrospectivos y bases de datos de finales , se han encontrado soluciones sólidas para todos los finales de tres a siete piezas , considerando a los dos reyes como piezas.

Se han resuelto algunas variantes del ajedrez en un tablero más pequeño 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 Sepoys es una serie de movimientos fáciles de recordar que garantiza la victoria al jugador que elige a los "sepoys".

Ir

El tablero de 5×5 se resolvió débilmente para todos los movimientos de apertura en 2002. ^{[ 34 ]} El tablero de 7×7 se resolvió débilmente en 2015. ^{[ 35 ]} Los humanos suelen jugar en un tablero de 19×19, que es más de 145 órdenes de magnitud más complejo que el de 7×7. ^{[ 36 ]}

Maleficio

Un argumento de robo de estrategia (como el utilizado por John Nash ) muestra que el primer jugador no puede perder en tableros de todos los tamaños cuadrados. Combinado con una prueba de la imposibilidad de un empate, esto muestra que el juego es una victoria del primer jugador (por lo que está resuelto de forma ultradébil). En tamaños de tablero particulares, se sabe más: está resuelto de forma fuerte por varias computadoras para tableros de hasta 6×6. Se conocen soluciones débiles para tableros de 7×7 (usando una estrategia de intercambio ), 8×8 y 9×9; en el caso de 8×8, se conoce una solución débil para todos los movimientos de apertura. ^{[ 37 ]} Resolver de forma fuerte Hex en un tablero N × N es improbable ya que se ha demostrado que el problema es PSPACE-completo . 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 mediante una estrategia de emparejamiento simple, incluso con la desventaja de jugar segundo.

damas internacionales

Se resolvieron todas las posiciones de final de partida con dos a siete piezas, así como las posiciones con 4×4 y 5×3 piezas donde cada bando tenía un rey o menos, posiciones con cinco piezas contra cuatro, posiciones con cinco piezas contra tres piezas y un rey, y posiciones con cuatro piezas y un rey contra cuatro piezas. Las posiciones de final de partida fueron resueltas en 2007 por Ed Gilbert de Estados Unidos. El análisis informático mostró que era muy probable que terminara en tablas si ambos jugadores jugaban a la perfección. ^{[ 38 ]}

Morabaraba

Resuelto de forma robusta por Gábor E. Gévay (2015). El primer jugador gana en juego óptimo. ^{[ 39 ]}

juego m , n , k

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 débilmente para k ≤ 4. Se conocen algunos resultados para k = 5. Los juegos terminan en empate para k ≥ 8.

• ajedrez por computadora
• Computadora Go
• Otelo informático
• complejidad del juego
• El algoritmo de Dios
• Teorema de Zermelo (teoría de juegos)

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

• Complejidad computacional de juegos y rompecabezas, por David Eppstein.
• GamesCrafters resolviendo juegos de dos personas con información perfecta y sin azar