Hispanopedia Wiki
Articulo de referencia

complejidad del juego

La teoría de juegos combinatorios mide la complejidad de los juegos de varias maneras: Complejidad del espacio de estados (el número de posiciones de juego legales a partir de l...

Hispanopedia WikiContenido en espanolLectura gratuita

La teoría de juegos combinatorios mide la complejidad de los juegos de varias maneras:

  1. Complejidad del espacio de estados (el número de posiciones de juego legales a partir de la posición inicial)
  2. Tamaño del árbol de juego (número total de juegos posibles)
  3. Complejidad de la decisión (número de nodos hoja en el árbol de decisión más pequeño para la posición inicial)
  4. Complejidad del árbol de juego (número de nodos hoja en el árbol de decisión de ancho completo más pequeño para la posición inicial)
  5. Complejidad computacional (dificultad asintótica de un juego a medida que crece de forma arbitraria)

Estas medidas implican comprender las posiciones del juego, los posibles resultados y la complejidad computacional de los distintos escenarios de juego.

Medidas de complejidad del juego

Complejidad del espacio de estados

La complejidad del espacio de estados de un juego es el número de posiciones de juego legales alcanzables desde la posición inicial del juego. [ 1 ]

Cuando esto es demasiado difícil de calcular, a menudo se puede calcular un límite superior contando también (algunas) posiciones ilegales (posiciones que nunca pueden surgir en el transcurso de una partida).

Tamaño del árbol de juego

El tamaño del árbol de juego es el número total de juegos posibles que se pueden jugar. Este es el número de nodos hoja en el árbol de juego con raíz en la posición inicial del juego.

El árbol de juego suele ser mucho mayor que el espacio de estados, ya que las mismas posiciones pueden darse en muchos juegos realizando movimientos en un orden diferente (por ejemplo, en un juego de tres en raya con dos X y una O en el tablero, esta posición podría haberse alcanzado de dos maneras distintas dependiendo de dónde se colocó la primera X). A veces se puede calcular un límite superior para el tamaño del árbol de juego simplificando el juego de forma que solo aumente el tamaño del árbol (por ejemplo, permitiendo movimientos ilegales) hasta que sea manejable.

En los juegos donde el número de movimientos no está limitado (por ejemplo, por el tamaño del tablero o por una regla sobre la repetición de posiciones), el árbol de juego es generalmente infinito.

Árboles de decisión

Un árbol de decisión es un subárbol del árbol de juego, donde cada posición se etiqueta como "gana el jugador A", "gana el jugador B" o "empate" si se puede demostrar que dicha posición tiene ese valor (suponiendo que ambos jugadores jueguen de la mejor manera) examinando únicamente las demás posiciones del grafo. Las posiciones terminales se pueden etiquetar directamente: cuando le toca mover al jugador A, una posición se etiqueta como "gana el jugador A" si alguna posición sucesora es una victoria para A; "gana el jugador B" si todas las posiciones sucesoras son victorias para B; o "empate" si todas las posiciones sucesoras son empates o victorias para B. (Cuando le toca mover al jugador B, las posiciones correspondientes se marcan de forma similar).

Los dos métodos siguientes para medir la complejidad de un juego utilizan árboles de decisión:

Complejidad de la decisión

La complejidad de decisión de un juego es el número de nodos hoja en el árbol de decisión más pequeño que establece el valor de la posición inicial.

complejidad del árbol de juego

La complejidad del árbol de juego es el número de nodos hoja en el árbol de decisión de ancho completo más pequeño que establece el valor de la posición inicial. [ 1 ] Un árbol de ancho completo incluye todos los nodos en cada profundidad. Esta es una estimación del número de posiciones que habría que evaluar en una búsqueda minimax para determinar el valor de la posición inicial.

Es difícil incluso estimar la complejidad del árbol de juego, pero para algunos juegos se puede dar una aproximación medianteGRAMOTdo≥bd{\displaystyle GTC\geq b^{d}}donde b es el factor de ramificación promedio del juego y d es el número de capas en un juego promedio.

Complejidad computacional

La complejidad computacional de un juego describe la dificultad asintótica del mismo a medida que crece arbitrariamente, expresada en notación O grande o como pertenencia a una clase de complejidad . Este concepto no se aplica a juegos particulares, sino a juegos que se han generalizado para que puedan ampliarse arbitrariamente, normalmente jugándolos en un tablero de n x n . (Desde el punto de vista de la complejidad computacional, un juego en un tablero de tamaño fijo es un problema finito que puede resolverse en O(1), por ejemplo, mediante una tabla de consulta que relaciona las posiciones con el mejor movimiento en cada posición).

La complejidad asintótica se define por el algoritmo más eficiente para resolver el juego (en términos de cualquier recurso computacional que se esté considerando). La medida de complejidad más común, el tiempo de cálculo , siempre está acotada inferiormente por el logaritmo de la complejidad asintótica del espacio de estados, ya que un algoritmo de solución debe funcionar para cada estado posible del juego. Estará acotada superiormente por la complejidad de cualquier algoritmo particular que funcione para la familia de juegos. Observaciones similares se aplican a la segunda medida de complejidad más utilizada, la cantidad de espacio o memoria de computadora utilizada por el cálculo. No es obvio que exista un límite inferior para la complejidad espacial de un juego típico, porque el algoritmo no necesita almacenar estados del juego; sin embargo, se sabe que muchos juegos de interés son PSPACE-difíciles , y se deduce que su complejidad espacial también estará acotada inferiormente por el logaritmo de la complejidad asintótica del espacio de estados (técnicamente, el límite es solo un polinomio en esta cantidad; pero generalmente se sabe que es lineal).

  • La estrategia minimax de búsqueda en profundidad utilizará un tiempo de cálculo proporcional a la complejidad del árbol del juego (ya que debe explorar todo el árbol) y una cantidad de memoria polinómica en el logaritmo de la complejidad del árbol (ya que el algoritmo siempre debe almacenar un nodo del árbol en cada profundidad de movimiento posible, y el número de nodos en la mayor profundidad de movimiento es precisamente la complejidad del árbol).
  • La inducción hacia atrás utilizará tanto memoria como tiempo en proporción a la complejidad del espacio de estados, ya que debe calcular y registrar el movimiento correcto para cada posición posible.

Ejemplo: tres en raya

Para el tres en raya , un límite superior simple para el tamaño del espacio de estados es 3 9 = 19 683. (Hay tres estados para cada una de las nueve celdas). Este recuento incluye muchas posiciones ilegales, como una posición con cinco cruces y ningún cero, o una posición en la que ambos jugadores tienen una fila de tres. Un recuento más cuidadoso, eliminando estas posiciones ilegales, da 5478. [ 2 ] [ 3 ] Y cuando las rotaciones y reflexiones de las posiciones se consideran idénticas, solo hay 765 posiciones esencialmente diferentes.

Para delimitar el árbol de juego, existen 9 movimientos iniciales posibles, 8 respuestas posibles, y así sucesivamente, de modo que hay como máximo 9! o 362.880 juegos en total. Sin embargo, los juegos pueden resolverse en menos de 9 movimientos, y una enumeración exacta arroja 255.168 juegos posibles. Si se consideran las rotaciones y reflexiones de posiciones como equivalentes, solo quedan 26.830 juegos posibles.

La complejidad computacional del tres en raya depende de cómo se generalice . Una generalización natural es a juegos de m , n , k : se juegan en un tablero de m por n , donde el ganador es el primer jugador en conseguir k en línea. Este juego se puede resolver en DSPACE ( mn ) buscando en todo el árbol del juego. Esto lo sitúa en la importante clase de complejidad PSPACE ; con más trabajo, se puede demostrar que es PSPACE-completo . [ 4 ]

Complejidades de algunos juegos conocidos

Debido a la gran complejidad de los juegos, esta tabla muestra el límite superior de su logaritmo en base 10 (es decir, el número de dígitos). Todos los números que se muestran a continuación deben interpretarse con precaución: cambios aparentemente menores en las reglas de un juego pueden modificarlos drásticamente (y, por lo general, son estimaciones aproximadas), llegando a ser mucho mayores que los números mostrados.

Notas

  1. ↑ El bridge doble (es decir, problemas dobles en el contexto del bridge por contrato ) no es un juego de mesa propiamente dicho, pero tiene un árbol de juego similar y se estudia en el bridge computacional . La mesa de bridge puede considerarse como si tuviera un espacio para cada jugador y baza para jugar una carta, lo que corresponde a un tablero de tamaño 52. La complejidad del árbol de juego es una cota superior muy débil: 13! elevado a la potencia de 4 jugadores independientemente de la legalidad. La complejidad del espacio de estados es para un reparto dado; igualmente independientemente de la legalidad pero con muchas transposiciones eliminadas. Los últimos 4 pliés son siempre movimientos forzados con factor de ramificación 1.

Referencias

  1. 1 2 3 4 5 6 7 8 9 10 11 12 Victor Allis (1994). Búsqueda de soluciones en juegos e inteligencia artificial (PDF) (tesis doctoral). Universidad de Limburgo, Maastricht, Países Bajos. ISBN 90-900748-8-0.
  2. ↑ "combinatoria - Cálculo de elección de espacio de estados de tres en raya" . Mathematics Stack Exchange . Consultado el 8 de abril de 2020 .
  3. ↑ T, Brian (20 de octubre de 2018). "Btsan/generate_tictactoe" . GitHub . Consultado el 8 de abril de 2020 .
  4. ↑ Stefan Reisch (1980). "Gobang ist PSPACE-vollständig (Gobang es PSPACE completo)". Acta Informática . 13 (1): 59– 66. doi : 10.1007/bf00288536 . S2CID 21455572 . 
  5. ^ Stefan Reisch (1981 ) . "Hex ist PSPACE-vollständig (Hex es PSPACE-completo)". Acta Informe (15): 167-191 .
  6. ↑ Slany, Wolfgang (2000). "La complejidad de los juegos de Ramsey en grafos". En Marsland, T. Anthony; Frank, Ian (eds.). Computers and Games, Segunda Conferencia Internacional, CG 2000, Hamamatsu, Japón, 26-28 de octubre de 2000, Artículos revisados . Lecture Notes in Computer Science. Vol. 2063. Springer. pp. 186–203 . doi : 10.1007/3-540-45579-5_12 . ISBN   978-3-540-43080-3.
  7. 1 2 3 4 5 6 HJ van den Herik; JWHM Uiterwijk; J. van Rijswijck (2002). «Juegos resueltos: Ahora y en el futuro» . Inteligencia artificial . 134 ( 1– 2): 277– 311. doi : 10.1016/S0004-3702(01)00152-7 .
  8. ↑ Orman, Hilarie K. (1996). "Pentominós: una victoria del primer jugador" (PDF) . En Nowakowski, Richard J. (ed.). Juegos sin azar: Artículos del Taller de Juegos Combinatorios celebrado en Berkeley, CA, del 11 al 21 de julio de 1994. Publicaciones del Instituto de Investigación de Ciencias Matemáticas. Vol. 29. Cambridge University Press. pp. 339–344 . ISBN   0-521-57411-0. MR 1427975 . 
  9. ↑ John Tromp (2010). "El patio de juegos de Conecta Cuatro de John" .
  10. ↑ Edelkamp, ​​Stefan y Peter Kissmann. “Clasificación simbólica de juegos generales para dos jugadores”. KI 2008: Avances en inteligencia artificial, editado por Andreas R. Dengel et al., vol. 5243, Springer Berlin Heidelberg, 2008, pp. 185–92. DOI.org (Crossref), https://doi.org/10.1007/978-3-540-85845-4_23 .
  11. ^ Véase van den Herik et al para conocer las reglas.
  12. ↑ Lachmann, Michael; Moore, Cristopher; Rapaport, Ivan (2002). "¿Quién gana en Domineering en tableros rectangulares?". En Nowakowski, Richard (ed.). More Games of No Chance: Proceedings of the 2nd Combinatorial Games Theory Workshop held in Berkeley, CA, July 24–28, 2000 . Mathematical Sciences Research Institute Publications. Vol. 42. Cambridge University Press. pp. 307– 315. ISBN   0-521-80832-4. MR 1973019 . 
  13. ↑ Jonathan Schaeffer; et al. (6 de julio de 2007). "El juego de damas está resuelto" . Science . 317 (5844): 1518– 1522. Bibcode : 2007Sci...317.1518S . doi : 10.1126/science.1144079 . PMID 17641166. S2CID 10274228 .   
  14. ↑ Schaeffer, Jonathan (2007). "Game over: Black to play and table in checkers" (PDF) . ICGA Journal . 30 (4): 187–197 . doi : 10.3233/ICG-2007-30402 . Archivado del original (PDF) el 3 de abril de 2016.
  15. 1 2 J. M. Robson (1984). "N by N checkers is Exptime complete". SIAM Journal on Computing . 13 (2): 252– 267. doi : 10.1137/0213018 .
  16. ↑ Véase Allis 1994 para consultar las reglas.
  17. ↑ Bonnet, Edouard; Jamain, Florian; Saffidine, Abdallah (2013). "Sobre la complejidad de los juegos de cartas de bazas" . En Rossi, Francesca (ed.). IJCAI 2013, Actas de la 23.ª Conferencia Internacional Conjunta sobre Inteligencia Artificial, Pekín, China, 3-9 de agosto de 2013. IJCAI/AAAI. págs. 482–488 . 
  18. ^ MPD Schadd; MHM Winands; JWHM Uiterwijk; HJ van den Herik; MHJ Bergsma (2008). "La mejor jugada en Fanorona lleva al empate" (PDF) . Nuevas Matemáticas y Computación Natural . 4 (3): 369– 387. doi : 10.1142/S1793005708001124 .
  19. ↑ Galassi, Andrea (2018). "Un límite superior para la complejidad de Tablut" .
  20. 1 2 Bell, George I. (2009). "El juego más corto de damas chinas y problemas relacionados". Enteros . 9. arXiv : 0803.1245 . Bibcode : 2008arXiv0803.1245B . doi : 10.1515/INTEG.2009.003 . S2CID 17141575 . 
  21. 1 2 Kasai, Takumi; Adachi, Akeo; Iwata, Shigeki (1979). "Clases de juegos de guijarros y problemas completos". SIAM Journal on Computing . 8 (4): 574– 586. doi : 10.1137/0208046 . MR 0573848 . Demuestra la completitud de la generalización a grafos arbitrarios.
  22. ↑ Iwata, Shigeki; Kasai, Takumi (1994). "El juego de Otelo en unnorte×norte{\displaystyle n\times n}"board is PSPACE-complete" . Theoretical Computer Science . 123 (2): 329– 340. doi : 10.1016/0304-3975(94)90131-7 . MR 1256205 . 
  23. ↑ Robert Briesemeister (2009). Análisis e implementación del juego OnTop (PDF) (Tesis). Universidad de Maastricht, Departamento de Ingeniería del Conocimiento.
  24. ↑ Mark HM Winands (2004). Informed Search in Complex Games (PDF) (Tesis doctoral). Universidad de Maastricht, Maastricht, Países Bajos. ISBN 90-5278-429-9.
  25. ↑ El tamaño del espacio de estados y del árbol de juego para el ajedrez se estimó por primera vez en Shannon, Claude (1950). "Programación de una computadora para jugar ajedrez" (PDF) . Revista Filosófica . 41 (314). Archivado del original (PDF) el 6 de julio de 2010.Shannon dio estimaciones de 10 43 y 10 120 respectivamente, menores que el límite superior en la tabla, que se detalla en el número de Shannon .
  26. ↑ Fraenkel, Aviezri S. ; Lichtenstein, David (1981). "Cálculo de una estrategia perfecta paranorte×norte{\displaystyle n\times n}El ajedrez requiere tiempo exponencial ennorte{\displaystyle n}" . Journal of Combinatorial Theory, Series A . 31 (2): 199– 214. doi : 10.1016/0097-3165(81)90016-9 . MR 0629595 . 
  27. ↑ Gualà, Luciano; Leucci, Stefano; Natale, Emanuele (2014). "Bejeweled, Candy Crush y otros juegos de combinar tres son (NP-)difíciles". Conferencia IEEE de 2014 sobre Inteligencia Computacional y Juegos, CIG 2014, Dortmund, Alemania, 26-29 de agosto de 2014. IEEE. pp. 1–8 . arXiv : 1403.5830 . doi : 10.1109/CIG.2014.6932866 . ISBN  978-1-4799-3547-5.
  28. ↑ Diederik Wentink (2001). Análisis e implementación del juego Gipf (PDF) (Tesis). Universidad de Maastricht.
  29. ↑ Chang-Ming Xu; Ma, ZM; Jun-Jie Tao; Xin-He Xu (2009). "Mejoras en la búsqueda del número de prueba en Connect6". Conferencia China de Control y Decisión de 2009. pág. 4525. doi : 10.1109/CCDC.2009.5191963 . ISBN  978-1-4244-2722-2. S2CID 20960281 . 
  30. ↑ Hsieh, Ming Yu; Tsai, Shi-Chun (1 de octubre de 2007). "Sobre la equidad y la complejidad de los juegos generalizados k en fila" . Theoretical Computer Science . 385 ( 1–3 ): 88–100 . doi : 10.1016/j.tcs.2007.05.031 .
  31. ↑ Tesauro, Gerald (1 de mayo de 1992). "Cuestiones prácticas en el aprendizaje de la diferencia temporal" . Machine Learning . 8 ( 3–4 ): 257–277 . doi : 10.1007/BF00992697 .
  32. ↑ Witter, RT (2021). El backgammon es difícil. En: Du, DZ., Du, D., Wu, C., Xu, D. (eds) Optimización combinatoria y aplicaciones. COCOA 2021. Lecture Notes in Computer Science(), vol. 13135. Springer, Cham. https://doi.org/10.1007/978-3-030-92681-6_38
  33. 1 2 Shi-Jim Yen, Jr-Chang Chen; Tai-Ning Yang; Shun-Chin Hsu (marzo de 2004). "Ajedrez chino por computadora" (PDF) . Revista de la Asociación Internacional de Juegos de Computadora . 27 (1): 3– 18. doi : 10.3233/ICG-2004-27102 . S2CID 10336286. Archivado del original (PDF) el 14 de junio de 2007. 
  34. 1 2 Donghwi Park (2015). "Complejidad del estado espacial del ajedrez coreano y el ajedrez chino". arXiv : 1507.06401 [ math.GM ].
  35. ↑ Chorus, Pascal. "Implementación de un reproductor informático para abulón mediante alfa-beta y búsqueda de Montecarlo" (PDF) . Departamento de Ingeniería del Conocimiento, Universidad de Maastricht . Consultado el 29 de marzo de 2012 .
  36. ↑ Kopczynski, Jacob S (2014). Pushy Computing: Complexity Theory and the Game Abalone (Tesis). Reed College.
  37. ↑ Joosten, B. "Creando un agente de juego de Havannah" (PDF) . Recuperado el 29 de marzo de 2012 .
  38. ↑ E. Bonnet; F. Jamain; A. Saffidine (25 de marzo de 2014). "Havannah y TwixT son PSPACE-completos". arXiv : 1403.6518 [ cs.CC ].
  39. ↑ Kevin Moesker (2009). Txixt: Teoría, análisis e implementación (PDF) (Tesis). Facultad de Humanidades y Ciencias de la Universidad de Maastricht.
  40. ↑ Glendenning, Lisa (mayo de 2005). Dominando Quoridor (PDF) . Ciencias de la Computación (tesis de licenciatura). Universidad de Nuevo México . Archivado del original (PDF) el 15 de marzo de 2012.
  41. ↑ Cathleen Heyden (2009). Implementación de un jugador informático para Carcassonne (PDF) (Tesis). Universidad de Maastricht, Departamento de Ingeniería del Conocimiento.
  42. ↑ El factor de ramificación inferior es para el segundo jugador.
  43. ↑ Kloetzer, Julien; Iida, Hiroyuki; Bouzy, Bruno (2007). "El enfoque de Montecarlo en Amazons" (PDF) . Computer Games Workshop, Ámsterdam, Países Bajos, 15-17 de junio de 2007. pp. 185–192 . 
  44. ↑ Hensgens, PPLM (2001). "Un enfoque basado en el conocimiento del juego de las amazonas" (PDF) . Universidad de Maastricht, Instituto de Conocimiento y Tecnología de Agentes.
  45. ↑ RA Hearn (2 de febrero de 2005). "Amazons es PSPACE-completo". arXiv : cs.CC/0502013 .
  46. ^ Iida, Hiroyuki; Sakuta, Makoto; Rollason, Jeff (enero de 2002). "Shogi informático" . Inteligencia artificial . 134 ( 1– 2): 121– 144. doi : 10.1016/S0004-3702(01)00157-6 .
  47. ↑ H. Adachi; H. Kamekawa; S. Iwata (1987). "El shogi en un tablero de n × n se completa en tiempo exponencial". Trans. IEICE . J70-D: 1843– 1852.
  48. ↑ FC Schadd (2009). Técnicas de búsqueda de Montecarlo en el juego de mesa moderno Thurn and Taxis (PDF) (Tesis). Universidad de Maastricht. Archivado del original (PDF) el 14 de enero de 2021.
  49. ↑ John Tromp; Gunnar Farnebäck (2007). "Combinatoria del Go" .Este artículo deriva los límites 48 < log(log( N )) < 171 para el número de juegos posibles N .
  50. ↑ Tromp, John (2016). "Número de posiciones legales de Go" .
  51. ↑ "Estadísticas sobre la duración de una partida de go" .
  52. ↑ JM Robson (1983). "La complejidad del Go". Procesamiento de la información; Actas del Congreso IFIP . págs. 413–417 . 
  53. ↑ Christ-Jan Cox (2006). "Análisis e implementación del juego Arimaa" (PDF) .
  54. ↑ David Jian Wu (2011). "Clasificación y evaluación de movimientos en el juego de Arimaa" (PDF) .
  55. ↑ Brian Haskin (2006). "Una mirada al factor de ramificación de Arimaa" .
  56. ↑ AFC Arts (2010). Juego competitivo en Stratego (PDF) (Tesis). Maastricht.
  57. ↑ CDA Evans y Joel David Hamkins (2014). "Valores de juego transfinitos en ajedrez infinito". arXiv : 1302.4377 [ math.LO ].
  58. ^ Stefan Reisch, Joel David Hamkins y Phillipp Schlicht (2012). "El problema del mate en n del ajedrez infinito es decidible". Conferencia sobre computabilidad en Europa : 78– 88. arXiv : 1201.5597 .{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
  59. ↑ Alex Churchill, Stella Biderman y Austin Herrick (2020). "Magic: the Gathering es Turing completo". arXiv : 1904.09828 [ cs.AI ].{{cite arXiv}}: CS1 maint: varios nombres: lista de autores ( enlace )
  60. ↑ "Combinaciones infinitas en MTG: 39 increíbles combinaciones para probar" .
  61. ↑ Stella Biderman (2020). "Magic: the Gathering es tan difícil como la aritmética". arXiv : 2003.05119 [ cs.AI ].
  62. ↑ Lokshtanov, Daniel; Subercaseaux, Bernardo (14 de mayo de 2022). "Wordle es NP-difícil". arXiv : 2203.16713 [ cs.CC ].

Véase también

  • La complejidad computacional de los juegos y rompecabezas, según David Eppstein.