stringtranslate.com

Complejidad del juego

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

  1. Complejidad del espacio de estados (el número de posiciones de juego legales desde la posición inicial),
  2. Tamaño del árbol de juegos (número total de juegos posibles),
  3. Complejidad de decisión (número de nodos de 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 de 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 arbitrariamente).

Estas medidas implican la comprensión de las posiciones del juego, los posibles resultados y los cálculos necesarios para varios 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, es decir, posiciones que nunca pueden surgir en el curso de un juego.

Tamaño del árbol de juegos

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

El árbol de juego suele ser mucho más grande que el espacio de estados porque las mismas posiciones pueden aparecer en muchos juegos haciendo 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 diferentes 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 una manera que solo aumente el tamaño del árbol de juego (por ejemplo, permitiendo movimientos ilegales) hasta que se vuelva manejable.

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

Árboles de decisión

Las dos medidas siguientes utilizan la idea de un árbol de decisión , que es un subárbol del árbol de juego, con cada posición etiquetada con "jugador A gana", "jugador B gana" o "empate", si se puede demostrar que esa posición tiene ese valor (suponiendo el mejor juego de ambos lados) examinando solo otras posiciones en el gráfico. (Las posiciones terminales se pueden etiquetar directamente; una posición con el jugador A para mover se puede etiquetar "jugador A gana" si cualquier posición sucesora es una victoria para A, o etiquetar "jugador B gana" si todas las posiciones sucesoras son victorias para B, o etiquetar "empate" si todas las posiciones sucesoras son empate o victorias para B. Y correspondientemente para las posiciones con B para mover).

Complejidad de decisiones

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

Complejidad del árbol de juegos

La complejidad del árbol de juego de un juego es la cantidad de nodos de 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 uno tendrí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 juegos, pero para algunos juegos se puede dar una aproximación elevando el factor de ramificación promedio del juego b a la potencia del número de capas d en un juego promedio, o:

.

Complejidad computacional

La complejidad computacional de un juego describe la dificultad asintótica de un juego a medida que crece de forma arbitraria, expresada en notación O mayúscula o como pertenencia a una clase de complejidad . Este concepto no se aplica a juegos particulares, sino a juegos que se han generalizado de modo que se puedan hacer arbitrariamente grandes, típicamente jugándolos en un tablero de n por n . (Desde el punto de vista de la complejidad computacional, un juego en un tablero de tamaño fijo es un problema finito que se puede resolver en O(1), por ejemplo, mediante una tabla de búsqueda desde las posiciones hasta la mejor jugada en cada posición).

La complejidad asintótica se define por el algoritmo más eficiente (en términos de cualquier recurso computacional que uno esté considerando) para resolver el juego; la medida de complejidad más común ( tiempo de cálculo ) siempre está limitada 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á limitada 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 comúnmente utilizada, la cantidad de espacio o memoria de computadora utilizada por el cálculo. No es obvio que exista un límite inferior en la complejidad espacial para 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-hard , y se deduce que su complejidad espacial también estará limitada 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).

Ejemplo: tres en raya (tres en raya)

En el caso del 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 celda y 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 posiciones se consideran idénticas, solo hay 765 posiciones esencialmente diferentes.

Para delimitar el árbol de juegos, hay 9 movimientos iniciales posibles, 8 respuestas posibles, etc., de modo que hay como máximo 9! o 362.880 juegos en total. Sin embargo, los juegos pueden requerir menos de 9 movimientos para resolverse, y una enumeración exacta da 255.168 juegos posibles. Cuando se consideran las rotaciones y las reflexiones de posiciones iguales, hay solo 26.830 juegos posibles.

La complejidad computacional del tres en raya depende de cómo se generalice . Una generalización natural es a m , n , k -juegos : se juega en un tablero de m por n y el ganador es el primer jugador que consigue k en una fila. Es evidente de inmediato que este juego se puede resolver en DSPACE ( mn ) buscando en todo el árbol de juego. Esto lo coloca en la importante clase de complejidad PSPACE . Con un poco más de 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 de su logaritmo en base 10 (en otras palabras, el número de dígitos). Todos los números siguientes deben considerarse con precaución: cambios aparentemente menores en las reglas de un juego pueden cambiar los números (que de todos modos suelen ser estimaciones aproximadas) en factores tremendos, que fácilmente podrían ser mucho mayores que los números mostrados.

Nota: ordenado por tamaño del árbol de juego

Notas

  1. ^ El bridge de doble ficticio (es decir, los problemas de doble ficticio en el contexto del bridge de contrato ) no es un juego de mesa propiamente dicho, pero tiene un árbol de juego similar y se estudia en el bridge informático . Se puede considerar que la mesa de bridge tiene una ranura para cada jugador y una baza para jugar una carta, lo que corresponde a un tamaño de tablero de 52. La complejidad del árbol de juego es un límite superior muy débil: 13! elevado a la cuarta potencia de jugadores independientemente de la legalidad. La complejidad del espacio de estados es para un reparto determinado; igualmente independientemente de la legalidad pero con muchas transposiciones eliminadas. Las últimas 4 jugadas son siempre movimientos forzados con factor de ramificación 1.

Referencias

  1. ^ abcdefghijkl 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". Intercambio de pila de matemáticas . 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. ^ abcd 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 grafos de Ramsey". En Marsland, T. Anthony; Frank, Ian (eds.). Computers and Games, Second International Conference, CG 2000, Hamamatsu, Japón, 26-28 de octubre de 2000, Documentos revisados . Lecture Notes in Computer Science. Vol. 2063. Springer. págs. 186–203. doi :10.1007/3-540-45579-5_12.
  7. ^ abcdef 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: la victoria del primer jugador" (PDF) . En Nowakowski, Richard J. (ed.). Juegos sin azar: artículos del taller de juegos combinatorios celebrado en Berkeley, California, del 11 al 21 de julio de 1994. Publicaciones del Instituto de Investigación de Ciencias Matemáticas. Vol. 29. Cambridge University Press. págs. 339–344. ISBN . 0-521-57411-0.Sr. 1427975  .
  9. ^ Consulte van den Herik et al para conocer las reglas.
  10. ^ John Tromp (2010). "El patio de juegos de John".
  11. ^ Lachmann, Michael; Moore, Cristopher; Rapaport, Ivan (2002). "¿Quién gana en Domineering en tableros rectangulares?". En Nowakowski, Richard (ed.). Más juegos sin azar: Actas del 2º Taller de teoría de juegos combinatorios celebrado en Berkeley, CA, del 24 al 28 de julio de 2000. Publicaciones del Instituto de Investigación de Ciencias Matemáticas. Vol. 42. Cambridge University Press. págs. 307–315. ISBN 0-521-80832-4. Sr.  1973019.
  12. ^ 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.
  13. ^ Schaeffer, Jonathan (2007). "Game over: Black to play and empatan en damas" (PDF) . ICGA Journal . 30 (4): 187–197. doi :10.3233/ICG-2007-30402. Archivado desde el original (PDF) el 2016-04-03.
  14. ^ ab JM Robson (1984). "N por N comprobadores es Exptime completo". Revista SIAM de Computación . 13 (2): 252–267. doi :10.1137/0213018.
  15. ^ Véase Allis 1994 para conocer las reglas.
  16. ^ Bonnet, Edouard; Jamain, Florian; Saffidine, Abdallah (2013). "Sobre la complejidad de los juegos de cartas con bazas". En Rossi, Francesca (ed.). IJCAI 2013, Actas de la 23.ª Conferencia conjunta internacional sobre inteligencia artificial, Pekín, China, 3-9 de agosto de 2013. IJCAI/AAAI. págs. 482–488.
  17. ^ 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.
  18. ^ Andrea Galassi (2018). "Un límite superior para la complejidad del tablut".
  19. ^ ab GI Bell (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.
  20. ^ ab Kasai, Takumi; Adachi, Akeo; Iwata, Shigeki (1979). "Clases de juegos de guijarros y problemas completos". Revista SIAM de Computación . 8 (4): 574–586. doi :10.1137/0208046. MR  0573848.Demuestra la completitud de la generalización a gráficos arbitrarios.
  21. ^ Iwata, Shigeki; Kasai, Takumi (1994). "El juego Othello en un tablero n × n {\displaystyle n\times n} es PSPACE-completo". Ciencias Informáticas Teóricas . 123 (2): 329–340. doi : 10.1016/0304-3975(94)90131-7 . MR  1256205.
  22. ^ Robert Briesemeister (2009). Análisis e implementación de Game OnTop (PDF) (Tesis). Universidad de Maastricht, Departamento de Ingeniería del Conocimiento.
  23. ^ Mark HM Winands (2004). Búsqueda informada en juegos complejos (PDF) (tesis doctoral). Universidad de Maastricht, Maastricht, Países Bajos. ISBN 90-5278-429-9.
  24. ^ El tamaño del espacio de estados y del árbol de juego del ajedrez fueron estimados por primera vez por Claude Shannon (1950). "Programación de una computadora para jugar ajedrez" (PDF) . Philosophical Magazine . 41 (314). Archivado desde el original (PDF) el 2010-07-06.Shannon dio estimaciones de 10 43 y 10 120 respectivamente, menores que el límite superior de la tabla, que se detalla en el número de Shannon .
  25. ^ Fraenkel, Aviezri S. ; Lichtenstein, David (1981). "El cálculo de una estrategia perfecta para ajedrez n × n {\displaystyle n\times n} requiere tiempo exponencial en n {\displaystyle n} ". Journal of Combinatorial Theory, Serie A . 31 (2): 199–214. doi : 10.1016/0097-3165(81)90016-9 . MR  0629595.
  26. ^ Gualà, Luciano; Leucci, Stefano; Natale, Emanuele (2014). "Bejeweled, Candy Crush y otros juegos de combinar tres son (NP-)difíciles". Conferencia IEEE 2014 sobre inteligencia computacional y juegos, CIG 2014, Dortmund, Alemania, 26-29 de agosto de 2014. IEEE. págs. 1–8. arXiv : 1403.5830 . doi :10.1109/CIG.2014.6932866.
  27. ^ Diederik Wentink (2001). Análisis e implementación del juego Gipf (PDF) (Tesis). Universidad de Maastricht.
  28. ^ Chang-Ming Xu; Ma, ZM; Jun-Jie Tao; Xin-He Xu (2009). "Mejoras en la búsqueda de números de prueba en connect6". Conferencia de Control y Decisión de China de 2009. pág. 4525. doi :10.1109/CCDC.2009.5191963. ISBN 978-1-4244-2722-2.S2CID20960281  .​
  29. ^ Hsieh, Ming Yu; Tsai, Shi-Chun (1 de octubre de 2007). "Sobre la equidad y complejidad de los juegos generalizados k-in-a-row". Ciencias de la Computación Teórica . 385 (1–3): 88–100. doi : 10.1016/j.tcs.2007.05.031 . Consultado el 12 de abril de 2018 en dl.acm.org.
  30. ^ Tesauro, Gerald (1 de mayo de 1992). "Cuestiones prácticas en el aprendizaje de diferencias temporales". Aprendizaje automático . 8 (3–4): 257–277. doi : 10.1007/BF00992697 .
  31. ^ ab Shi-Jim Yen, Jr-Chang Chen; Tai-Ning Yang; Shun-Chin Hsu (marzo de 2004). "Computer Chinese Chess" (PDF) . Revista de la Asociación Internacional de Juegos de Computadora . 27 (1): 3–18. doi :10.3233/ICG-2004-27102. S2CID  10336286. Archivado desde el original (PDF) el 14 de junio de 2007.
  32. ^ ab Donghwi Park (2015). "Complejidad espacio-estado del ajedrez coreano y del ajedrez chino". arXiv : 1507.06401 [math.GM].
  33. ^ Chorus, Pascal. "Implementación de un reproductor informático para abulón mediante búsquedas Alpha-Beta y Monte-Carlo" (PDF) . Departamento de Ingeniería del Conocimiento, Universidad de Maastricht . Consultado el 29 de marzo de 2012 .
  34. ^ Kopczynski, Jacob S (2014). Pushy Computing: Teoría de la complejidad y el juego Abalone (Tesis). Reed College.
  35. ^ Joosten, B. "Creación de un agente de reproducción de Havannah" (PDF) . Consultado el 29 de marzo de 2012 .
  36. ^ E. Bonnet; F. Jamain; A. Saffidine (25 de marzo de 2014). "Havannah y TwixT son PSPACE-completos". arXiv : 1403.6518 [cs.CC].
  37. ^ Kevin Moesker (2009). Txixt: Theory, Analysis, and Implementation (PDF) (Tesis). Facultad de Humanidades y Ciencias de la Universidad de Maastricht.
  38. ^ Lisa Glendenning (mayo de 2005). Mastering Quoridor (PDF) . Informática (tesis de licenciatura). Universidad de Nuevo México . Archivado desde el original (PDF) el 15 de marzo de 2012.
  39. ^ Cathleen Heyden (2009). Implementación de un reproductor informático para Carcassonne (PDF) (Tesis). Universidad de Maastricht, Departamento de Ingeniería del Conocimiento.
  40. ^ El factor de ramificación inferior es para el segundo jugador.
  41. ^ 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.
  42. ^ PPLM Hensgens (2001). "Un enfoque basado en el conocimiento del juego de las Amazonas" (PDF) . Universidad de Maastricht, Instituto de Conocimiento y Tecnología de Agentes.
  43. ^ RA Hearn (2 de febrero de 2005). "Amazons es PSPACE-completo". arXiv : cs.CC/0502013 .
  44. ^ Hiroyuki Iida; Makoto Sakuta; Jeff Rollason (enero de 2002). "Shogi informático". Inteligencia artificial . 134 (1–2): 121–144. doi : 10.1016/S0004-3702(01)00157-6 .
  45. ^ H. Adachi; H. Kamekawa; S. Iwata (1987). "El shogi en un tablero n × n se completa en tiempo exponencial". Trad. IEICE . J70-D: 1843–1852.
  46. ^ 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 desde el original (PDF) el 14 de enero de 2021.
  47. ^ John Tromp; Gunnar Farnebäck (2007). "Combinatoria del Go".En este artículo se derivan los límites 48<log(log( N ))<171 sobre el número de juegos posibles N .
  48. ^ John Tromp (2016). "Número de posiciones legales de Go".
  49. ^ JM Robson (1983). "La complejidad de Go". Procesamiento de la información; Actas del Congreso de la IFIP . págs. 413–417.
  50. ^ Christ-Jan Cox (2006). "Análisis e implementación del juego Arimaa" (PDF) .
  51. ^ David Jian Wu (2011). "Clasificación y evaluación de movimientos en el juego de Arimaa" (PDF) .
  52. ^ Brian Haskin (2006). "Una mirada al factor de ramificación de Arimaa".
  53. ^ AFC Arts (2010). Juego competitivo en Stratego (PDF) (Tesis). Maastricht.
  54. ^ CDA Evans y Joel David Hamkins (2014). "Valores de juego transfinitos en ajedrez infinito". arXiv : 1302.4377 [math.LO].
  55. ^ 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 )
  56. ^ Alex Churchill, Stella Biderman y Austin Herrick (2020). «Magic: The Gathering es Turing Complete». arXiv : 1904.09828 [cs.AI].{{cite arXiv}}: CS1 maint: varios nombres: lista de autores ( enlace )
  57. ^ Stella Biderman (2020). "Magic: The Gathering es tan difícil como la aritmética". arXiv : 2003.05119 [cs.AI].
  58. ^ Lokshtanov, Daniel; Subercaseaux, Bernardo (14 de mayo de 2022). "Wordle es NP-hard". arXiv : 2203.16713 [cs.CC].

Véase también

Enlaces externos