Diferencia entre revisiones de «Juego resuelto»

De Wikipedia, la enciclopedia libre
Ir a siguiente diferencia →
Contenido eliminado Contenido añadido
VisualWikitexto
Juscelk (discusión · contribs.)
5065 ediciones
Página creada con «{{traducción|art=Solved game|ci=en}} Un '''juego resuelto''' es un juego cuyo resultado (ganar, perder o empatar) se puede predecir correctamente desde cualquier posic…»
(Sin diferencias)

Revisión del 21:49 20 ene 2021

Este artículo o sección se está traduciendo del idioma inglés a partir del artículo Solved game. Por esta razón, puede haber lagunas de contenidos, errores sintácticos o escritos sin traducir. Puedes colaborar con Wikipedia continuando con la traducción desde el artículo original.

Un juego resuelto es un juego cuyo resultado (ganar, perder o empatar) se puede predecir correctamente desde cualquier posición, asumiendo un juego perfecto por parte de ambos jugadores. 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.

Descripción general

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 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 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]​

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

Juegos resueltos

Awari (un juego de la familia Mancala)
Henri Bal y John Romein en la Vrije Universiteit en Amsterdam, 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 tabla 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×1020.[9]​ El número de cálculos involucrados fue de 1014, 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 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 para 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 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]​ The game is a draw if no mistakes are made, with no mistake possible on the opening move.
Bagh-Chal (Tigres y cabras)
Débilmente resuelto por Yew Jin Lim (2007). El juego es un empate.[26]​

Juegos parcialmente resueltos

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 de juego (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 una placa de 8 × 8 (la 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.

Véase también

Referencias

  1. ↑ a b Victor Allis (1994). «PhD thesis: Searching for Solutions in Games and Artificial Intelligence». Department of Computer Science. University of Limburg. Consultado el 14 de julio de 2012. 
  2. ↑ H. Jaap van den Herik, Jos W.H.M. Uiterwijk, Jack van Rijswijck, Games solved: Now and in the future, Artificial Intelligence 134 (2002) 277–311.
  3. ↑ Bowling, M.; Burch, N.; Johanson, M.; Tammelin, O. (Jan 2015). «Heads-up limit hold'em poker is solved». Science 347 (6218): 145-9. PMID 25574016. S2CID 3796371. doi:10.1126/science.1259433.  Parámetro desconocido |citeseerx= ignorado (ayuda)
  4. ↑ Philip Ball (8 de enero de 2015). «Game Theorists Crack Poker». Nature. Nature. S2CID 155710390. doi:10.1038/nature.2015.16683. Consultado el 13 de enero de 2015. 
  5. ↑ Robert Lee Hotz (8 de enero de 2015). «Computer Conquers Texas Hold 'Em, Researchers Say». Wall Street Journal. 
  6. ↑ a b «John's Connect Four Playground». tromp.github.io. 
  7. ↑ «UCI Machine Learning Repository: Connect-4 Data Set». archive.ics.uci.edu. 
  8. ↑ Schaeffer, Jonathan (19 de julio de 2007). «Checkers Is Solved». Science 317 (5844): 1518-22. PMID 17641166. S2CID 10274228. doi:10.1126/science.1144079. Consultado el 20 de julio de 2007. 
  9. ↑ «Project - Chinook - World Man-Machine Checkers Champion». Consultado el 19 de julio de 2007. 
  10. ↑ Mullins, Justin (19 de julio de 2007). «Checkers 'solved' after years of number crunching». NewScientist.com news service. Consultado el 6 de diciembre de 2020. 
  11. ↑ Optimal Strategy in "Guess Who?": Beyond Binary Search by Mihai Nica.
  12. ↑ P. Henderson, B. Arneson, and R. Hayward[webdocs.cs.ualberta.ca/~hayward/papers/solve8.pdf, Solving 8×8 Hex ], Proc. IJCAI-09 505-510 (2009) Retrieved 29 June 2010.
  13. ↑ Price, Robert. «Hexapawn». www.chessvariants.com. 
  14. ↑ Solving Kalah by Geoffrey Irving, Jeroen Donkers and Jos Uiterwijk.
  15. ↑ Solving (6,6)-Kalaha by Anders Carstensen.
  16. ↑ Watkins, Mark. «Losing Chess: 1. e3 wins for White». Consultado el 17 January 2017. 
  17. ↑ Nine Men's Morris is a Draw by Ralph Gasser
  18. ↑ «solved: Order wins - Order and Chaos». 
  19. ↑ Pangki is strongly solved as a Draw by Jason Doucette
  20. ↑ Geoffrey Irving: "Pentago is a first player win" http://perfect-pentago.net/details.html
  21. ↑ Hilarie K. Orman: Pentominoes: A First Player Win in Games of no chance, MSRI Publications – Volume 29, 1996, pages 339-344. Online: pdf.
  22. ↑ Teeko, by E. Weisstein
  23. ↑ Elabridi, Ali. «Weakly Solving the Three Musketeers Game Using Artificial Intelligence and Game Theory». 
  24. ↑ Three Musketeers, by J. Lemaire
  25. ↑ Tic-Tac-Toe, by R. Munroe
  26. ↑ Yew Jin Lim. On Forward Pruning in Game-Tree Search. Ph.D. Thesis, National University of Singapore, 2007.
  27. ↑ 5×5 Go is solved by Erik van der Werf
  28. ↑ «首期喆理围棋沙龙举行 李喆7路盘最优解具有里程碑意义_下棋想赢怕输_新浪博客». blog.sina.com.cn.  (que dice que la solución de 7x7 sólo está débilmente resuelta y todavía se está investigando, 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 maneras de jugar que no afectan el resultado)
  29. ↑ Counting legal positions in Go (enlace roto disponible en este archivo)., Tromp and Farnebäck, accessed 2007-08-24.
  30. ↑ Some of the nine-piece endgame tablebase by Ed Gilbert
  31. ↑ «6×6 Othello weakly solved». Archivado desde el original el 1 de noviembre de 2009.  Parámetro desconocido |url-status= ignorado (ayuda)

Lecturas adicionales

En inglés:

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

Enlaces externos

En inglés:

Obtenido de «https://es.wikipedia.org/w/index.php?title=Juego_resuelto&oldid=132564311»