Loading AI tools
De Wikipedia, la enciclopedia libre
La teoría de juegos combinatorios posee diversas maneras de medir la complejidad en los juegos. Este artículo describe cinco de ellas: complejidad estado-espacio, tamaño del árbol del juego, complejidad de las decisiones, complejidad del árbol del juego, y complejidad computacional.
Cuando esto es demasiado difícil de calcular, un límite superior puede ser computado a menudo incluyendo las posiciones ilegales o las posiciones que nunca pueden presentarse en el curso de un juego.
Sin embargo, para los juegos donde el número de movimientos no se limita (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 infinito.
Las dos siguientes medidas usan un árbol de decisión. Un árbol de decisión es un subárbol del árbol del juego, con cada nodo etiquetado como “jugador A gana”, “jugador B gana” o “empate”, donde puede probarse que ese nodo tiene ese valor (asumiendo que ambos jugadores hacen el mejor movimiento) solo con examinar otros nodos del grafo. (Los nodos terminales pueden ser etiquetados directamente; un nodo en la que le toque mover al jugador A puede etiquetarse con “jugador A gana” si nodo sucesor es una victoria para A, o etiquetado con “jugador B gana” si todos los nodos sucesores, son victorias para B, o etiquetado como “empate” si todos los nodos sucesores son o empates o victoria para B. Y de manera análoga, para las posiciones en las que mueve B).
posibilidad para cada decisión del jugador que comienza la partida.
Para el juego de Tres en raya podríamos tener un límite de 39 = 19.683 maneras de rellenar el tablero (tres posibles estados para cada celda y nueve celdas). Esta cuenta incluye muchas posiciones ilegales tales como una posición con cinco cruces y sin ceros, o una posición en la que ambos jugadores tienen una fila de tres. Aplicando a estas restricciones, tenemos una cuenta mejorada, en la que eliminando estas posiciones ilegales, podríamos tener 5.478 combinaciones para rellenar. Aunque... son consideradas idénticas, hay solo 765 posiciones estrictamente diferentes. Si atendemos a la cota superior del árbol que genera el tablero, tenemos 9!=362.880 (9 posiciones para el primer movimiento, 8 para el segundo, y así sucesivamente). Esta cuenta incluye partidas y movimientos ilegales, ya que el juego puede haber terminado. Si refinamos entonces las combinaciones tenemos 255.168 posibles movimiento. Si además añadimos que las rotaciones de las posiciones son consideradas las mismas, tenemos sólo 26.830 lanzamientos. La complejidad computacional del tres en raya depende de la forma en que esté formalizado. Una formalización natural sería juegos m,n,k, que sería un tablero de m x n siendo el ganador el que consigue obtener k en raya. Es trivial que el juego puede ser resuelto DSPACE (mn) con la búsqueda del árbol del juego. Esto lo coloca en una clase de complejidad importante, PSPACE. Con un poco más de trabajo se puede demostrar que es PSPACE-completo.[2]
Debido a la gran cantidad de complejidades en los juegos, esta tabla da la aproximación superior de su logaritmo en base 10. Los números mostrados a continuación deben ser considerados con precaución: cambios aparentemente pequeños en las reglas del juego pueden cambiar estos números (que no son estimaciones demasiado exactas) por tremendos factores, que pueden ser fácilmente mucho mayores que los datos ofrecidos.
Juego | Tamaño del tablero
(cells) |
Complejidad estado-espacio
(como log en base 10) |
Complejidad del árbol del juego
(como log en base 10) |
Longitud media del juego
(número de turnos) |
Clase de complejidad del juego formalizado |
---|---|---|---|---|---|
Tres en raya | 9 | 3 | 5 | 9 | PSPACE-completo[2] |
Pentominó | 64 | 12 | 18 | 10[3] | ?, pero en PSPACE |
Conecta cuatro | 42 | 14[1] | 21[1] | 36[1] | ?, pero en PSPACE |
Damas inglesas (8x8) | 32 | 20[4] or 18[1] | 31[1] | 70[1] | EXPTIME-completo[5] |
Oware[6] | 12 | 12[1] | 32[1] | 60[1] | La generalización está incompleta. |
Qubic | 64 | 30[1] | 34[1] | 20[1] | PSPACE-completo[2] |
Fanorona | 45 | 21[7] | 46[7] | 22 | ?, pero en EXPTIME |
Nine Men's Morris | 24 | 10[1] | 50[1] | ? | ?, pero en EXPTIME |
Damas internacionales (10x10) | 50 | 30?[1] | 54[1] | 90[1] | EXPTIME-completo[5] |
Damas chinas (2 conjuntos) | 121 | 23 | ? | ? | ?, pero en EXPTIME |
Damas chinas (6 conjuntos) | 121 | 35 | ? | ? | ?, pero en EXPTIME |
Líneas de acción | 64 | 24 | 56 | 63 | ?, pero en EXPTIME |
Reversi | 64 | 28[1] | 58[1] | 58[1] | PSPACE-completo[8] |
Hex (11x11) | 121 | 56 | ? | 40 | PSPACE-completo[9] |
Gomoku (15x15, freestyle) | 225 | 105?[1] | 70[1] | 30[1] | PSPACE-completo[2] |
Ajedrez | 64 | 50[10] | 123[10] | 80 | EXPTIME-completo[11] |
Conecta6 | 361 | 172 | 70 or 140 | 15 or 30 | PSPACE-completo[12] |
Backgammon | 28 | 20 | 144 | 50-60[13] | La generalización está incompleta. |
Xiangqi | 90 | 40[14] | 150[1] | 80? | ?, se cree que es EXPTIME-completo |
Janggi | 90 | 44[14] | 160 | ? | ?, se cree que es EXPTIME-completo |
Quoridor | 81 | 42 | 162 | ? | ?, pero en PSPACE |
Amazonas (10x10) | 100 | 40 (cota superior) | ? | ? | PSPACE-completo[15] |
Shōgi | 81 | 71[16] | 226[16] | 110? | EXPTIME-completo[17] |
Arimaa | 64 | 43[18] | 296[18] | 70[19] | ?, pero en EXPTIME |
Go (board game) 19x19 | 361 | 171[20] | 360[1] | 150[1] | EXPTIME-completo[21] |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.