La teoría de juegos combinatorios tiene varias formas de medir la complejidad del juego . Este artículo describe cinco de ellos: complejidad del espacio de estados, tamaño del árbol del juego, complejidad de decisiones, complejidad del árbol del juego y complejidad computacional.
Medidas de complejidad del juego
Complejidad del espacio de estados
La complejidad del espacio de estado de un juego es el número de posiciones de juego legales accesibles desde la posición inicial del juego. [1]
Cuando esto es demasiado difícil de calcular, un límite superior a menudo se puede calcular 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 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 estado porque las mismas posiciones pueden ocurrir en muchos juegos al hacer movimientos en un orden diferente (por ejemplo, en un juego de tic-tac-toe con dos X y una O en el tablero, esto posición podría haberse alcanzado de dos formas diferentes dependiendo de dónde se colocó la primera X). Un límite superior para el tamaño del árbol del juego a veces se puede calcular 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 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 la repetición de la posición), el árbol del juego es generalmente infinito.
Árboles de decisión
Las siguientes dos medidas usan la idea de un árbol de decisiones , 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 del sucesor es una victoria para A, o como "el jugador B gana" si todas las posiciones del sucesor son victorias para B, o etiquetado como "empate" si todas las posiciones sucesoras son empatadas o gana para B. Y correspondientemente para las posiciones con B para moverse.
Complejidad de decisiones
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 juegos
La complejidad del árbol de juego de un 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 uno tendría que evaluar en una búsqueda minimax para determinar el valor de la posición inicial.
Incluso es difícil estimar la complejidad del árbol del juego, 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 pertenencia a una clase de complejidad . Este concepto no se aplica a juegos en particular, sino más bien a los juegos que han sido generalizadas para que puedan hacerse arbitrariamente grande, típicamente por jugar con ellos en un n -by- n bordo. (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 consulta 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 se 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 del espacio 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 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 profundidad primero utilizará un tiempo de cálculo proporcional a la complejidad del árbol del juego, ya que debe explorar el árbol completo y una cantidad de polinomio de memoria en el logaritmo de la complejidad del árbol, ya que el algoritmo siempre debe almacenar un nodo de la complejidad del árbol. árbol en cada posible profundidad de movimiento, 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 la memoria como el tiempo proporcionales a la complejidad del espacio de estado, ya que debe calcular y registrar el movimiento correcto para cada posición posible.
Ejemplo: tic-tac-toe (ceros y cruces)
Para tic-tac-toe , 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 sin ceros, o una posición en la que ambos jugadores tienen una fila de tres. Un recuento más cuidadoso, eliminando estas posiciones ilegales, da 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 del juego, hay 9 posibles movimientos iniciales, 8 posibles respuestas, y así sucesivamente, ¡de modo que hay como máximo 9! o 362,880 juegos en total. Sin embargo, los juegos pueden tardar menos de 9 movimientos en resolverse, y una enumeración exacta da 255,168 juegos posibles. Cuando las rotaciones y reflejos de posiciones se consideran iguales, solo hay 26.830 juegos posibles.
La complejidad computacional del tic-tac-toe depende de cómo se generalice . Una generalización natural es m , n , k -juegos : se juega en un tablero de m por n y el ganador es 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 coloca en la clase de complejidad importante PSPACE . Con un poco más de trabajo, se puede demostrar que está completo en PSPACE . [4]
Complejidades de algunos juegos conocidos
Debido al gran tamaño de las complejidades del juego, esta tabla da el techo de su logaritmo a base 10. (En otras palabras, el número de dígitos). Todos los siguientes números deben considerarse con precaución: cambios aparentemente menores en las reglas de un juego pueden cambiar los números (que a menudo son estimaciones aproximadas de todos modos) por factores tremendos, que fácilmente podrían ser mucho mayores que los números mostrados.
Nota: ordenado por tamaño de árbol de juego
Juego | Tamaño de la placa (posiciones) | Complejidad del espacio de estados (como logaritmo a base 10) | Complejidad del árbol de juegos (como logaritmo a base 10) | Duración media del juego ( pliegues ) | Factor de ramificación | Árbitro | Clase de complejidad del juego generalizado adecuado |
---|---|---|---|---|---|---|---|
Tic-tac-toe | 9 | 3 | 5 | 9 | 4 | PSPACE-completo [5] | |
Sim | 15 | 3 | 8 | 14 | 3,7 | PSPACE-completo [6] | |
Pentominós | 64 | 12 | 18 | 10 | 75 | [7] [8] | ?, pero en PSPACE |
Kalah [9] | 14 | 13 | 18 | 50 | [7] | La generalización no está clara | |
Conectar cuatro | 42 | 13 | 21 | 36 | 4 | [1] [10] | ?, pero en PSPACE |
Dominante (8 × 8) | 64 | 15 | 27 | 30 | 8 | [7] | ?, pero en PSPACE ; en P para determinadas dimensiones [11] |
Congkak | 14 | 15 | 33 | [7] | |||
Borradores en inglés (8x8) (damas) | 32 | 20 o 18 | 31 | 70 | 2.8 | [1] [12] | EXPTIME-complete [13] |
Awari [14] | 12 | 12 | 32 | 60 | 3,5 | [1] | La generalización no está clara |
Qubic | 64 | 30 | 34 | 20 | 54,2 | [1] | PSPACE-completo [5] |
Puente falso doble [nb 1] | (52) | <17 | <40 | 52 | 5,6 | PSPACE-completo [15] | |
Fanorona | 45 | 21 | 46 | 44 | 11 | [dieciséis] | ?, pero en EXPTIME |
Morris de nueve hombres | 24 | 10 | 50 | 50 | 10 | [1] | ?, pero en EXPTIME |
Tablut | 81 | 27 | [17] | ||||
Borradores internacionales (10x10) | 50 | 30 | 54 | 90 | 4 | [1] | EXPTIME-complete [13] |
Damas chinas (2 juegos) | 121 | 23 | 180 | [18] | EXPTIME -completa [19] | ||
Damas chinas (6 juegos) | 121 | 78 | 600 | [18] | EXPTIME -completa [19] | ||
Reversi (Otelo) | 64 | 28 | 58 | 58 | 10 | [1] | PSPACE-completo [20] |
OnTop (juego base 2p) | 72 | 88 | 62 | 31 | 23,77 | [21] | |
Líneas de acción | 64 | 23 | 64 | 44 | 29 | [22] | ?, pero en EXPTIME |
Gomoku (15x15, estilo libre) | 225 | 105 | 70 | 30 | 210 | [1] | PSPACE-completo [5] |
Hexagonal (11x11) | 121 | 57 | 98 | 50 | 96 | [7] | PSPACE-completo [5] |
Ajedrez | 64 | 47 | 123 | 70 | 35 | [23] | EXPTIME-complete (sin la regla de dibujo de 50 movimientos ) [24] |
Bejeweled y Candy Crush (8x8) | 64 | <50 | 70 | [25] | NP-duro | ||
GIPF | 37 | 25 | 132 | 90 | 29,3 | [26] | |
Conectar6 | 361 | 172 | 140 | 30 | 46000 | [27] | PSPACE-completo [28] |
Chaquete | 28 | 20 | 144 | 55 | 250 | [29] | La generalización no está clara |
Xiangqi | 90 | 40 | 150 | 95 | 38 | [1] [30] [31] | ?, se cree que es EXPTIME-complete |
Abulón | 61 | 25 | 154 | 87 | 60 | [32] [33] | PSPACE-hard , y en EXPTIME |
Havannah | 271 | 127 | 157 | 66 | 240 | [7] [34] | PSPACE-completo [35] |
Twixt | 572 | 140 | 159 | 60 | 452 | [36] | |
Janggi | 90 | 44 | 160 | 100 | 40 | [31] | ?, se cree que es EXPTIME-complete |
Quoridor | 81 | 42 | 162 | 91 | 60 | [37] | ?, pero en PSPACE |
Carcassonne (juego base 2p) | 72 | > 40 | 195 | 71 | 55 | [38] | La generalización no está clara |
Amazonas (10x10) | 100 | 40 | 212 | 84 | 374 o 299 [39] | [40] [41] | PSPACE-completo [42] |
Shogi | 81 | 71 | 226 | 115 | 92 | [30] [43] | EXPTIME-complete [44] |
Thurn y Taxis (2 j.) | 33 | 66 | 240 | 56 | 879 | [45] | |
Ir (19x19) | 361 | 170 | 360 | 150 | 250 | [1] [46] [47] | EXPTIME-complete [48] |
Arimaa | 64 | 43 | 402 | 92 | 17281 | [49] [50] [51] | ?, pero en EXPTIME |
Stratego | 92 | 115 | 535 | 381 | 21.739 | [52] | |
Ajedrez infinito [nb 2] | infinito | infinito | infinito | infinito | infinito | [55] | Desconocido, pero mate-in-n es decidible [56] |
Magia: el encuentro | Infinito | Ilimitado | Ilimitado | infinito | infinito | [57] | AH-duro [58] |
Notas
- ^ El puente doble ficticio (es decir, problemas de doble ficticio en el contexto del puente contractual ) 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 es un límite superior muy débil: ¡13! al poder de 4 jugadores independientemente de la legalidad. La complejidad del espacio de estados es para un trato dado; igualmente independientemente de la legalidad pero con muchas transposiciones eliminadas. Tenga en cuenta que las últimas 4 capas son siempre movimientos forzados con factor de ramificación 1.
- ^ El ajedrez infinito es una clase de juegos, que incluye Chess on an Infinite Plane y Trappist-1 como ejemplos. [53] [54]
Referencias
- ↑ a b c d e f g h i j k l Victor Allis (1994). Búsqueda de soluciones en juegos e inteligencia artificial (PDF) (tesis doctoral). Universidad de Limburg, Maastricht, Holanda. ISBN 90-900748-8-0.
- ^ "combinatoria - TicTacToe State Space Elija cálculo" . Intercambio de pila de matemáticas . Consultado el 8 de abril de 2020 .
- ^ T, Brian (2018-10-20), Btsan / generate_tictactoe , consultado el 2020-04-08
- ^ Stefan Reisch (1980). "Gobang ist PSPACE-vollständig (Gobang es PSPACE-completo)". Acta Informatica . 13 (1): 59–66. doi : 10.1007 / bf00288536 . S2CID 21455572 .
- ^ a b c d Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex es PSPACE-completo)". Acta Inform. (15): 167-191.
- ^ Slany, Wolfgang (26 de octubre de 2000). La complejidad de Graph Ramsey Games . Springer-Verlag. págs. 186–203. ISBN 9783540430803. Consultado el 12 de abril de 2018 , a través de dl.acm.org.
- ^ a b c d e f 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 .
- ↑ Hilarie K. Orman: Pentominoes: A First Player Win in Games of no chance , Publicaciones de MSRI - Volumen 29, 1996, páginas 339-344. En línea: pdf .
- ^ Ver van den Herik et al para conocer las reglas.
- ^ John Tromp (2010). "John's Connect Four Playground" .
- ^ Michael Lachmann; Cristopher Moore; Ivan Rapaport (julio de 2000), ¿Quién gana dominando en tablas rectangulares? , Taller de investigación de teoría de juegos combinatoria MSRI
- ^ Jonathan Schaeffer; et al. (6 de julio de 2007). "Damas se resuelve". Ciencia . 317 (5844): 1518-1522. Código Bibliográfico : 2007Sci ... 317.1518S . doi : 10.1126 / science.1144079 . PMID 17641166 . S2CID 10274228 .
- ^ a b JM Robson (1984). "N by N checkers es Exptime completo". Revista SIAM de Computación . 13 (2): 252–267. doi : 10.1137 / 0213018 .
- ^ Ver Allis 1994 para las reglas
- ^ Bonnet, Édouard; Jamain, Florian; Saffidine, Abdallah (3 de agosto de 2013). Sobre la complejidad de los juegos de cartas con trucos . AAAI Press. págs. 482–488. ISBN 9781577356332.
- ^ MPD Schadd; MHM Winands; JWHM Uiterwijk; HJ van den Herik; MHJ Bergsma (2008). "La mejor jugada de Fanorona lleva al empate" (PDF) . Nuevas Matemáticas y Computación Natural . 4 (3): 369–387. doi : 10.1142 / S1793005708001124 .
- ^ Andrea Galassi (2018). "Un límite superior sobre la complejidad de Tablut" .
- ^ a b GI Bell (2009). "El juego más corto de damas chinas y problemas relacionados" . Enteros . 9 . arXiv : 0803.1245 . Código Bibliográfico : 2008arXiv0803.1245B . doi : 10.1515 / INTEG.2009.003 . S2CID 17141575 .
- ^ a b Takumi Kasai; Akeo Adachi; Shigeki Iwata (1979). "Clases de juegos de guijarros y problemas completos". Revista SIAM de Computación . 8 (4): 574–586. doi : 10.1137 / 0208046 . Prueba la integridad de la generalización a gráficos arbitrarios.
- ^ S. Iwata; T. Kasai (1994). "El juego Othello en un tablero n * n está completo para PSPACE". Theor. Computación. Sci . 123 (2): 329–340. doi : 10.1016 / 0304-3975 (94) 90131-7 .
- ^ Robert Briesemeister (2009). Análisis e implementación del juego OnTop (PDF) (Tesis). Universidad de Maastricht, Departamento de Ingeniería del Conocimiento.
- ^ Mark HM Winands (2004). Búsqueda informada en juegos complejos (PDF) (tesis doctoral). Universidad de Maastricht, Maastricht, Holanda. ISBN 90-5278-429-9.
- ^ El tamaño del espacio estatal y el árbol de juego para el 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 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 .
- ^ Aviezri Fraenkel ; D. Lichtenstein (1981), "Calcular una estrategia perfecta para el ajedrez n × n requiere tiempo exponencial en n", J. Combin. Teoría Ser. A , 31 (2): 199–214, doi : 10.1016 / 0097-3165 (81) 90016-9
- ^ L. Gualà; S. Leucci; E. Natale (2014). "Bejeweled, Candy Crush y otros juegos Match-Three son (NP-) Difíciles". arXiv : 1403,5830 [ cs.CC ].
- ^ Diederik Wentink (2001). Análisis e implementación del juego Gipf (PDF) (Tesis). Universidad de Maastricht.
- ^ Chang-Ming Xu; Ma, ZM; Jun-Jie Tao; Xin-He Xu (2009). "Mejoras en la búsqueda de números de prueba en connect6". 2009 Conferencia de Control y Decisión de China . pag. 4525. doi : 10.1109 / CCDC.2009.5191963 . ISBN 978-1-4244-2722-2. S2CID 20960281 .
- ^ Hsieh, Ming Yu; Tsai, Shi-Chun (1 de octubre de 2007). "Sobre la equidad y la complejidad de los juegos de k-en-una-fila generalizados" . 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.
- ^ Tesauro, Gerald (1 de mayo de 1992). "Problemas prácticos en el aprendizaje de la diferencia temporal" . Aprendizaje automático . 8 (3–4): 257–277. doi : 10.1007 / BF00992697 .
- ^ a b 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 . Archivado desde el original (PDF) el 14 de junio de 2007.
- ^ a b Parque Donghwi (2015). "Complejidad del estado espacial del ajedrez coreano y del ajedrez chino". arXiv : 1507.06401 [ matemáticas.GM ].
- ^ Coro, Pascal. "Implementación de un reproductor de computadora para abulón usando Alpha-Beta y Monte-Carlo Search" (PDF) . Departamento de Ingeniería del Conocimiento, Universidad de Maastricht . Consultado el 29 de marzo de 2012 .
- ^ Kopczynski, Jacob S (2014). Computación agresiva: teoría de la complejidad y el abulón del juego (tesis). Reed College.
- ^ Joosten, B. "Creación de un agente de juego de Havannah" (PDF) . Consultado el 29 de marzo de 2012 .
- ^ E. Bonnet; F. Jamain; A. Saffidine (25 de marzo de 2014). "Havannah y TwixT son PSPACE-completos". arXiv : 1403,6518 [ cs.CC ].
- ^ Kevin Moesker (2009). TWIXT: TEORÍA, ANÁLISIS E IMPLEMENTACIÓN (PDF) (Tesis). Universidad de Maastricht, Facultad de Humanidades y Ciencias de la Universidad de Maastricht.
- ^ 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.
- ^ Cathleen Heyden (2009). Implementación de un reproductor de computadora para Carcassonne (PDF) (Tesis). Universidad de Maastricht, Departamento de Ingeniería del Conocimiento.
- ^ El factor de ramificación más bajo es para el segundo jugador.
- ^ Julien Kloetzer; Hiroyuki Iida; Bruno Bouzy (2007), El enfoque de Montecarlo en Amazonas , CiteSeerX 10.1.1.79.7640
- ^ PPLM Hensgens (2001). "Un enfoque basado en el conocimiento del juego de las amazonas" (PDF) . Universiteit Maastricht, Instituto de Conocimiento y Tecnología de Agentes.
- ^ RA Hearn (2 de febrero de 2005). "Amazons es PSPACE-completo". arXiv : cs.CC/0502013 .
- ^ Hiroyuki Iida; Makoto Sakuta; Jeff Rollason (enero de 2002). "Computadora shogi". Inteligencia artificial . 134 (1-2): 121-144. doi : 10.1016 / S0004-3702 (01) 00157-6 .
- ^ H. Adachi; H. Kamekawa; S. Iwata (1987). "Shogi en tablero n × n se completa en tiempo exponencial". Trans. IEICE . J70-D: 1843–1852.
- ^ FC Schadd (2009). Técnicas de búsqueda de Montecarlo en el juego de mesa moderno Thurn and Taxis (PDF) (Tesis). Universidad de Maastricht.
- ^ John Tromp; Gunnar Farnebäck (2007). "Combinatoria de Go" .En este trabajo se deriva la grada 48
N )) <171 en el número de posibles juegos N . - ^ John Tromp (2016). "Número de posiciones legales de Go" .
- ^ JM Robson (1983). "La complejidad de Go". Procesamiento de información; Actas del Congreso de la IFIP . págs. 413–417.
- ^ Christ-Jan Cox (2006). "Análisis e Implementación del Juego Arimaa" (PDF) .
- ^ David Jian Wu (2011). "Move Ranking y Evaluación en el Juego de Arimaa" (PDF) .
- ^ Brian Haskin (2006). "Una mirada al factor de ramificación de Arimaa" .
- ^ AFC Arts (2010). Juego competitivo en Stratego (PDF) (Tesis). Maastricht.
- ^ Reglas del juego de ajedrez en un plano infinito
- ^ Reglas del juego Trappist-1
- ^ CDA Evans y Joel David Hamkins (2014). "Valores de juego transfinitos en ajedrez infinito". arXiv : 1302.4377 [ matemáticas.LO ].
- ^ Stefan Reisch, Joel David Hamkins y Phillipp Schlicht (2012). "El problema del mate en n del ajedrez infinito es decidible" (PDF) . Conferencia sobre Computabilidad en Europa : 78–88. arXiv : 1201.5597 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Alex Churchill, Stella Biderman y Austin Herrick (2020). "Magic: the Gathering is Turing Complete" (PDF) . Diversión con algoritmos . arXiv : 1904.09828 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Stella Biderman (2020). "Magia: la reunión es tan difícil como la aritmética". arXiv : 2003.05119 [ cs.AI ]. Parámetro desconocido
|url=
ignorado ( ayuda )
Ver también
- Ir y matemáticas
- Juego resuelto
- Resolviendo ajedrez
- Número de Shannon
- lista de juegos y rompecabezas NP-complete
- lista de juegos y rompecabezas completos de PSPACE
enlaces externos
- David Eppstein 's complejidad computacional de juegos y rompecabezas