stringtranslate.com

Complejidad del juego

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

  1. Complejidad del espacio de estados (el número de posiciones legales del juego desde la posición inicial),
  2. Tamaño del árbol de juegos (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 juegos (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 comprender las posiciones del juego, los posibles resultados y los cálculos necesarios para diversos escenarios del 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 transcurso de un juego.

Tamaño del árbol de juego

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

El árbol del juego suele ser mucho más grande que el espacio de estados porque las mismas posiciones pueden ocurrir en muchos juegos al realizar movimientos en un orden diferente (por ejemplo, en un juego de tres en raya con dos X y una O en el tablero, esto La 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 del juego simplificando el juego de una manera que solo aumente el tamaño del árbol del juego (por ejemplo, permitiendo movimientos ilegales) hasta que se vuelva manejable.

Para juegos donde 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 del juego es generalmente infinito.

Árboles de decisión

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

Complejidad de la decisión

La complejidad de la 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 juegos

La complejidad del árbol de juego de un juego es el número de nodos de hoja en el árbol de decisión más pequeño de ancho completo 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 b del juego 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 arbitrariamente, expresada en notación O grande o como membresía en una clase de complejidad . Este concepto no se aplica a juegos particulares, sino más bien a juegos que se han generalizado para que puedan hacerse arbitrariamente grandes, normalmente 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 puede resolverse en O(1), por ejemplo, mediante una tabla de búsqueda desde posiciones hasta el mejor movimiento en cada posición).

La complejidad asintótica está definida 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 por el logaritmo de la complejidad asintótica del espacio de estados, ya que un algoritmo de solución debe funcionar para todos los estados posibles del juego. Estará limitado por la complejidad de cualquier algoritmo particular que funcione para la familia de juegos. Se aplican observaciones similares 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 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 de ello se deduce que su complejidad espacial también estará limitada 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)

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 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 estos puestos ilegales, arroja 5.478. [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 juego, 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, las partidas pueden tardar menos de 9 movimientos en resolverse, y una enumeración exacta arroja 255.168 partidas posibles. Cuando se consideran iguales las rotaciones y los reflejos de posiciones, sólo hay 26.830 juegos posibles.

La complejidad computacional del tres en raya depende de cómo se generaliza . Una generalización natural es m , n , k -juegos : jugados en un tablero m por n , siendo el ganador el primer jugador en obtener k seguidos. Inmediatamente queda claro que 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 un poco más de trabajo se puede demostrar que está completo en PSPACE . [4]

Complejidades de algunos juegos conocidos

Debido a la gran complejidad de los juegos, esta tabla proporciona el límite máximo 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 a menudo son estimaciones aproximadas) por factores tremendos, que fácilmente podrían ser mucho mayores que los números mostrados.

Nota: ordenados por tamaño del árbol del juego

Notas

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

Referencias

  1. ^ abcdefghijkl Víctor 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 del espacio de estados de TicTacToe". Intercambio de pilas 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 gráficos de Ramsey". En Marsland, T. Anthony; Frank, Ian (eds.). Computers and Games, Segunda Conferencia Internacional, CG 2000, Hamamatsu, Japón, 26 al 28 de octubre de 2000, artículos revisados . Apuntes de conferencias sobre informática. vol. 2063. Saltador. 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: el primer jugador gana" (PDF) . En Nowakowski, Richard J. (ed.). Juegos sin posibilidad: artículos del taller de juegos combinatorios celebrado en Berkeley, CA, del 11 al 21 de julio de 1994 . Publicaciones del Instituto de Investigaciones en Ciencias Matemáticas. vol. 29. Prensa de la Universidad de Cambridge. págs. 339–344. ISBN 0-521-57411-0. SEÑOR  1427975.
  9. ^ Consulte van den Herik et al para conocer las reglas.
  10. ^ John Tromp (2010). "Zona de juegos John's Connect Four".
  11. ^ Lachmann, Michael; Moore, Cristopher; Rapaport, Iván (2002). "¿Quién gana Dominante en tableros rectangulares?". En Nowakowski, Richard (ed.). Más juegos sin posibilidad: Actas del segundo taller de teoría de juegos combinatorios celebrado en Berkeley, CA, del 24 al 28 de julio de 2000 . Publicaciones del Instituto de Investigaciones en Ciencias Matemáticas. vol. 42. Prensa de la Universidad de Cambridge. págs. 307–315. ISBN 0-521-80832-4. SEÑOR  1973019.
  12. ^ Jonathan Schaeffer; et al. (6 de julio de 2007). "Las damas están resueltas". Ciencia . 317 (5844): 1518-1522. Código Bib : 2007 Ciencia... 317.1518S. doi : 10.1126/ciencia.1144079 . PMID  17641166. S2CID  10274228.
  13. ^ Schaeffer, Jonathan (2007). "Se acabó el juego: las negras juegan y sacan damas" (PDF) . Revista ICGA . 30 (4): 187–197. doi :10.3233/ICG-2007-30402. Archivado desde el original (PDF) el 3 de abril de 2016.
  14. ^ ab JM Robson (1984). "N por N fichas es Exptime completo". Revista SIAM de Computación . 13 (2): 252–267. doi :10.1137/0213018.
  15. ^ Consulte Allis 1994 para conocer las reglas.
  16. ^ Capo, Eduardo; Jamain, Florián; Saffidine, Abdallah (2013). "Sobre la complejidad de los juegos de cartas con bazas". En Rossi, Francesca (ed.). IJCAI 2013, Actas de la 23ª Conferencia Internacional Conjunta sobre Inteligencia Artificial, Beijing, China, 3 al 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 a la complejidad de Tablut".
  19. ^ ab GI Bell (2009). "El juego más corto de damas chinas y problemas relacionados". Enteros . 9 . arXiv : 0803.1245 . Código Bib : 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. SEÑOR  0573848.Demuestra la integridad de la generalización a gráficos arbitrarios.
  21. ^ Iwata, Shigeki; Kasai, Takumi (1994). "El juego de Otelo en un tablero de n × n {\displaystyle n\times n} está completo en PSPACE". Informática Teórica . 123 (2): 329–340. doi : 10.1016/0304-3975(94)90131-7 . SEÑOR  1256205.
  22. ^ Robert Briesemeister (2009). Análisis e Implementación del Juego 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 el árbol de juego del ajedrez se estimaron por primera vez en Claude Shannon (1950). "Programación de una computadora para jugar al ajedrez" (PDF) . Revista Filosófica . 41 (314). Archivado desde el original (PDF) el 6 de julio de 2010.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). "Calcular una estrategia perfecta para el ajedrez n × n {\displaystyle n\times n} requiere un tiempo exponencial en n {\displaystyle n} ". Revista de teoría combinatoria, serie A. 31 (2): 199–214. doi : 10.1016/0097-3165(81)90016-9 . SEÑOR  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 juegos e inteligencia computacional, CIG 2014, Dortmund, Alemania, 26 al 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; Mamá, ZM; Jun-Jie Tao; Xin-He Xu (2009). "Mejoras en la búsqueda de números de prueba en connect6". Conferencia China de Control y Decisión de 2009 . pag. 4525. doi : 10.1109/CCDC.2009.5191963. ISBN 978-1-4244-2722-2. S2CID  20960281.
  29. ^ Hsieh, Ming Yu; Tsai, Shi-Chun (1 de octubre de 2007). "Sobre la equidad y complejidad de los juegos generalizados de k en fila". Informática Teórica . 385 (1–3): 88–100. doi : 10.1016/j.tcs.2007.05.031 . Consultado el 12 de abril de 2018 a través de 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). "Ajedrez chino por ordenador" (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 Parque Donghwi (2015). "Complejidad del estado espacial del ajedrez coreano y del ajedrez chino". arXiv : 1507.06401 [matemáticas.GM].
  33. ^ Coro, Pascal. "Implementación de un reproductor informático para abulón mediante búsqueda 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). Computación agresiva: teoría de la complejidad y el juego Abalone (Tesis). Reed College.
  35. ^ Joosten, B. "Creación de un agente de juego de Havannah" (PDF) . Consultado el 29 de marzo de 2012 .
  36. ^ E. capó; F. Jamain; A. Saffidine (25 de marzo de 2014). "Havannah y TwixT están completos en PSPACE". arXiv : 1403.6518 [cs.CC].
  37. ^ Kevin Moesker (2009). Txixt: Teoría, análisis e implementación (PDF) (Tesis). Facultad de Humanidades y Ciencias de la Universidad de Maastricht.
  38. ^ Lisa Glendenning (mayo de 2005). Dominar el Quoridor (PDF) . Ciencias de la Computación (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 Montecarlo en la Amazonia" (PDF) . Taller de juegos de ordenador, Ámsterdam, Países Bajos, 15 a 17 de junio de 2007 . págs. 185-192.
  42. ^ PPLM Hensgens (2001). "Un enfoque del juego de las Amazonas basado en el conocimiento" (PDF) . Universiteit 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 el tablero n × n se completa en un tiempo exponencial". Trans. 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. ^ Juan Tromp; Gunnar Farneback (2007). "Combinatoria de Go".Este artículo deriva los límites 48<log(log( N ))<171 en el número de juegos posibles N .
  48. ^ John Tromp (2016). "Número de posiciones legales de Go".
  49. ^ JM Robson (1983). "La complejidad del Go". Procesamiento de información; Actas del Congreso IFIP . págs. 413–417.
  50. ^ Cristo-Jan Cox (2006). «Análisis e Implementación del Juego Arimaa» (PDF) .
  51. ^ David Jian Wu (2011). "Ranking 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. ^ Artes AFC (2010). Juego competitivo en Stratego (PDF) (Tesis). Mastrique.
  54. ^ CDA Evans y Joel David Hamkins (2014). "Valores de juego transfinitos en ajedrez infinito". arXiv : 1302.4377 [matemáticas.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}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
  56. ^ Alex Churchill, Stella Biderman y Austin Herrick (2020). "Magic: the Gathering es Turing completo". arXiv : 1904.09828 [cs.AI].{{cite arXiv}}: Mantenimiento CS1: 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-duro". arXiv : 2203.16713 [cs.CC].

Ver también

enlaces externos