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 se suele aplicar a los juegos de estrategia abstractos, y especialmente a los juegos con información completa y ningún elemento de azar; resolver dicho juego puede usar la teoría de juegos combinatorios y/o asistencia informática.

Resumen

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

Ultra-weak

Demostrar si el primer jugador va a ganar, perder o sacar de la posición inicial, dado juego perfecto en ambos lados. Esto puede ser una prueba no constructiva (posiblemente implicando un argumento de estrategia) que en realidad no necesita determinar ningún movimiento del juego perfecto.

Weak

Proveer un algoritmo que asegure una victoria para un jugador, o un sorteo para cualquiera, contra cualquier posible movimiento por el oponente, desde el principio del juego.

Fuerte

Proporcionar un algoritmo que pueda producir movimientos perfectos desde cualquier posición, incluso si los errores ya se han cometido en uno o ambos lados.

A pesar de su nombre, muchos teóricos de juegos creen que los juegos "ultradébiles" Las pruebas son las más profundas, interesantes y valiosas. "Ultradébil" Las pruebas 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.

Por el contrario, "fuerte" las demostraciones a menudo proceden por la fuerza bruta, utilizando una computadora para buscar exhaustivamente en un árbol de juegos para descubrir qué sucedería si se lograra un juego perfecto. La prueba resultante da 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 de manera trivial un algoritmo minimax que atraviese exhaustivamente el árbol del juego. Sin embargo, dado que para muchos juegos no triviales, dicho algoritmo requeriría una cantidad de tiempo inviable para generar un movimiento en una posición determinada, no se considera que un juego se resuelva débil o fuertemente a menos que el hardware existente pueda ejecutar el algoritmo en un tiempo razonable. Muchos algoritmos se basan en una enorme base de datos generada previamente y, en la práctica, no son más que nada.

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 mediante 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; por el contrario, un juego débilmente resuelto puede perder su atractivo si la estrategia ganadora es lo suficientemente simple de recordar (por ejemplo, Maharajah and the Sepoys). Una solución ultradé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, 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. Según las reglas de un juego, se pueden evaluar todas las posiciones finales posibles (como victoria, derrota o empate). Por razonamiento inverso, 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. Como ejemplo, un jugador perfecto en una posición empatada 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 de 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 al azar 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 que juega aún podría beneficiarse de las soluciones del juego desde ciertas posiciones del final del juego (en forma de bases de tablas del final del juego), lo que le permitirá jugar perfectamente después de algún punto en el juego. Los programas informáticos de ajedrez son bien conocidos por hacer esto.

Juegos resueltos

Awari (un juego de la familia Mancala)

La variante de Oware permitiendo el final del juego "grand slams" fue resuelta fuertemente por Henri Bal y John Romein en el Vrije Universiteit en Amsterdam, Países Bajos (2002). Cualquier jugador puede forzar el juego en un sorteo.

Patillos

Fue resuelto. Si 2 jugadores juegan perfectamente, el juego continuará indefinidamente.

Conectar cuatro

El juego de Connect Four ha sido resuelto

Resuelto primero por James D. Allen el 1o de octubre de 1988, e independientemente por Victor Allis el 16 de octubre de 1988. El primer jugador puede forzar una victoria. Fue resuelto por la base de datos de 8 libras de John Tromp (Feb 4, 1995). Resolvido débilmente para todos los tamaños de la tabla donde el ancho+altura es a la mayoría de 15 (así como 8×8 a finales de 2015) (Feb 18, 2006).

Trajes de inglés (comparadores)

Esta variante 8×8 de draughts fue resuelta débilmente el 29 de abril de 2007, por el equipo de Jonathan Schaeffer. Desde la posición de inicio estándar, ambos jugadores pueden garantizar un sorteo con un juego perfecto. Checkers es el juego más grande que se ha resuelto hasta la fecha, con un espacio de búsqueda de 5×10²⁰. El número de cálculos involucrados fue de 10¹⁴, que se hicieron durante un período de 18 años. El proceso implicado de 200 computadoras de escritorio en su pico hasta alrededor de 50.

Fanorona

Resolvido débilmente por Maarten Schadd. El juego es un sorteo.

Gomoku gratis

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

Fantasma

Resuelto por Alan Frank usando Diccionario oficial de jugadores de scrabble en 1987.

Hexapawn

3×3 variante resuelta como una victoria para negro, varias otras variantes más grandes también resuelto.

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 de primer jugador. Mark Rawlings, de Gaithersburg, MD, ha cuantificado la magnitud de la primera victoria del jugador en la variante (6/6) (2015). Después de la creación de 39 GB de bases de datos de endgame, las búsquedas por un total de 106 días de tiempo de CPU y más de 55 nudos trillones, se comprobó que, con un juego perfecto, el primer jugador gana en 2. Tenga en cuenta que todos estos resultados se refieren a la variante Empty-pit Capture y por lo tanto son de interés muy limitado para el juego estándar. El análisis del juego de reglas estándar ha sido publicado ahora 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 marcha, sin embargo, se ha demostrado que es una victoria por lo menos 4 para el primer jugador.

L juego

Fácilmente solvable. Cualquier jugador puede forzar el juego en un sorteo.

Perder ajedrez

Resolvido débilmente como una victoria para el comienzo blanco con 1. e3.

Maharajah y los Sepoys

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

Nim

Fue resuelto.

Nueve hombres moris

Resuelto por Ralph Gasser (1993). Cualquier jugador puede forzar el juego en un sorteo.

Orden y Caos

Orden (Primer jugador) gana.

Ohvalhu

Resolvido débilmente por humanos, pero probado por ordenadores. (Dakon es, sin embargo, no idéntico a Ohvalhu, el juego que realmente había sido observado por de Voogt)

Pangki

Fue resuelto por Jason Doucette (2001). El juego es un sorteo. Sólo hay dos primeros movimientos únicos si descartas posiciones reflejadas. Uno fuerza el sorteo, y el otro da al adversario una victoria forzada en 15.

Pentago

Fuertemente resuelto por Geoffrey Irving con el uso de un supercomputador en NERSC. El primer jugador gana.

Pentominos

Resolvido débilmente por H. K. Orman. Es una victoria para el primer jugador.

Quarto

Resuelto por Luc Goossens (1998). Dos jugadores perfectos siempre dibujarán.

Qubic

Resolvido débilmente por Oren Patashnik (1980) y Victor Allis. El primer jugador gana.

Renju-como juego sin reglas de apertura involucrado

Reclamado por János Wagner e István Virág (2001). Una victoria de primer jugador.

Sim

Resolvido débilmente: ganar para el segundo jugador.

Teeko

Resuelto por Guy Steele (1998). Dependiendo de la variante ya sea una victoria de primer jugador o un sorteo.

Tres hombres moris

Trivialmente solvable. Cualquier jugador puede forzar el juego en un sorteo.

Tres mosqueteros

Fue 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 fuertemente solvable debido al pequeño árbol del juego. El juego es un sorteo si no se cometen errores, sin ningún error posible en el movimiento de apertura.

Tigres y cabras

Resolvido débilmente por Yew Jin Lim (2007). El juego es un sorteo.

Wythoff juego

Fue resuelto por W. A. Wythoff en 1907.

Resoluciones débiles

Tigres y cabras

Resolvido débilmente por Yew Jin Lim (2007). El juego es un sorteo.

Pentominos

Resolvido débilmente por H. K. Orman. Es una victoria para el primer jugador.

Juegos parcialmente resueltos

Ajedrez

La resolución completa de ajedrez sigue siendo difícil, y se especula que la complejidad del juego puede impedir que se solucione. Mediante el análisis de computación retrogrado, se han encontrado bases de mesas de juego final (fuentes soluciones) para los juegos 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úmeros reducidos de piezas. También se han resuelto algunas otras variantes populares; por ejemplo, una solución débil a Maharajah y los Sepoys es una serie de movimientos fácilmente memorables que garantizan la victoria al jugador de "sepoys".

Vamos.

El tablero 5×5 fue débilmente resuelto para todos los movimientos de apertura en 2002. El tablero 7×7 fue débilmente resuelto en 2015. Los humanos suelen jugar en una tabla de 19×19 que es más de 145 órdenes de magnitud más compleja que 7×7.

Hex

Un argumento de estrategia (como lo utiliza John Nash) muestra que todos los tamaños de la tabla cuadrada no pueden perderse por el primer jugador. Combinado con una prueba de la imposibilidad de un sorteo, esto muestra que el juego es una primera victoria de jugador (por lo que es ultra-mojado resuelto). En tamaños de tablas particulares, más se sabe: es resuelto fuertemente por varios ordenadores para tamaños de tablero hasta 6×6. Las soluciones débiles son conocidas por tamaños de tablero 7×7 (utilizando una estrategia de intercambio), 8×8, y 9×9; en el caso 8×8, una solución débil es conocida por todos los movimientos de apertura. Solución fuerte de Hex en un N×N consejo es poco probable ya que el problema se ha demostrado que está completo PSPACE. Si Hex se juega en un N×N + 1) tablero entonces el jugador que tiene la distancia más corta para conectar siempre puede ganar por una simple estrategia de emparejamiento, incluso con la desventaja de jugar segundo.

International draughts

Todas las posiciones del juego final con dos a siete piezas fueron resueltas, así como posiciones con 4×4 y 5×3 piezas donde cada lado 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 de computación mostró que era muy probable que terminara en un sorteo si ambos jugadores jugaban perfectamente.

m,n,k-game

Es trivial demostrar que el segundo jugador nunca puede ganar; ver el argumento de la estrategia-asignación. Casi todos los casos se han resuelto débilmente k ≤ 4. Algunos resultados son conocidos por k = 5. Los juegos se dibujan para k ≥ 8.

Reversi (Othello)

Resolvido débilmente en un tablero 4×4 y 6×6 como un segundo jugador gana en julio de 1993 por Joel Feinstein. En un tablero de 8×8 (el estándar) es matemáticamente sin resolver, aunque el análisis de la computadora muestra un sorteo probable. No se suponen estimaciones más que mayores posibilidades para el jugador inicial (Black) en 10×10 y existen tablas más grandes.