Wikipedia

Complejidad en los juegos

Este artículo o sección sobre ocio necesita ser wikificado, por favor, edítalo para que cumpla con las convenciones de estilo.
Este aviso fue puesto el 11 de junio de 2008.

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.

Medidas de la complejidad de un juego

editar
  • La complejidad del estado-espacio de un juego es el número de posiciones legales del juego accesibles desde la posición inicial del juego.[1]​

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.

  • El tamaño del árbol del juego es el número total de las instancias posibles que puedan ser aplicadas al juego, es decir, es el número de los nodos hoja en el árbol del juego cuya raíz es la posición inicial.El árbol del juego es sumamente más grande que la complejidad del estado-espacio porque las mismas posiciones pueden ocurrir en muchas instancias del juego, haciendo movimientos en diverso orden (por ejemplo, en una partida del Tres en raya con dos X y un O en el tablero, esta posición se habría podido alcanzar de dos maneras diferentes, dependiendo de dónde fue puesto el primer X). Un límite superior para el tamaño del árbol del juego puede ser computado a veces, simplificando el juego de manera que aumente sólo el tamaño del árbol del juego (por ejemplo, permitiendo movimientos ilegales) hasta que llega a ser manejable.

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).

  • 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. Todo árbol incluye todas las posibles decisiones para el jugador que mueve en segundo lugar, pero solo una

posibilidad para cada decisión del jugador que comienza la partida.

  • La complejidad del juego-árbol de un juego es el número de nodos hoja del árbol de decisión completo en anchura que establece un valor en la posición inicial.[1]​ (Un árbol completo en anchura incluye todos los nodos de todos los niveles). Ésta es una estimación del número de posiciones que podríamos tener que evaluar en una búsqueda usando el algoritmo minimax para determinar el valor de la posición inicial. Es difícil estimar la complejidad del juego-árbol, pero para algunos juegos un límite inferior razonable puede darse elevando el número de hijos medio de cada nodo al número de turnos que hay en el juego medio.
  • El coste computacional de un juego describe la dificultad asintótica de un juego que crece de manera arbitraria, expresada en notación de cota superior o como miembro de una clase de complejidad. Este concepto no es aplicable a juegos concretos, pero si a juegos que han sido formalizados para que puedan ser aleatoriamente grandes, generalmente jugándolos en un tablero de n por n. (Desde el punto de vista de la complejidad computacional de un juego en un tablero de tamaño fijo, es un problema finito que se puede resolver en O(1), por ejemplo, con una tabla de búsqueda de posiciones en el mejor movimiento en cada posición).

Ejemplo: Tres en raya

editar

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]​

Complejidad de algunos juegos conocidos

editar

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]​

Véase también

editar

Notas y referencias

editar
  1. ↑ a b c d e f g h i j k l m n ñ o p q r s t u v w x y z aa Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence. Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. ISBN 90-900748-8-0. 
  2. ↑ a b c d Stefan Reisch (1980). «Gobang ist PSPACE-vollstandig (Gomoku is PSPACE-complete)». Acta Informatica 13: 5966. 
  3. ↑ Hilarie K. Orman: Pentominoes: A First Player Win in Games of no chance, MSRI Publications – Volume 29, 1996, pages 339-344. Online: pdf.
  4. ↑ Jonathan Schaeffer et al (6 de julio de 2007). «Checkers is Solved». Science. 
  5. ↑ a b J. M. Robson (1984). «N by N checkers is Exptime complete». SIAM Journal on Computing, 13 (2): 252-267. doi:10.1137/0213018. 
  6. ↑ See Allis 1994 for rules
  7. ↑ a b M.P.D. Schadd, M.H.M. Winands, J.W.H.M. Uiterwijk, H.J. van den Herik and M.H.J. Bergsma (2008). «Best Play in Fanorona leads to Draw». New Mathematics and Natural Computation 4 (3): 369-387. 
  8. ↑ S. Iwata and T. Kasai (1994). «The Othello game on an n*n board is PSPACE-completo». Theor. Comp. Sci. 123 (123): 329-340. doi:10.1016/0304-3975(94)90131-7. 
  9. ↑ Stefan Reisch (1981). «Hex ist PSPACE-vollständig (Hex is PSPACE-complete)». Acta Inf. (15): 167-191. 
  10. ↑ a b The size of the state space and game tree for chess were first estimated in Claude Shannon (1950). «Programming a Computer for Playing Chess». Philosophical Magazine 41 (314). Archivado desde el original el 15 de marzo de 2010. Consultado el 5 de junio de 2008.  Shannon gave estimates of 1043 and 10120 respectively, smaller than the estimates in the table, which are from Victor Allis's thesis. See Shannon number for details.
  11. ↑ Aviezri Fraenkel and D. Lichtenstein (1981). «Computing a perfect strategy for n×n chess requires time exponential in n». J. Comb. Th. A (31): 199-214. 
  12. ↑ «On the fairness and complexity of generalized k-in-a-row games». Consultado el 2009. 
  13. ↑ «Copia archivada». Archivado desde el original el 26 de febrero de 2009. Consultado el 15 de abril de 2008. 
  14. ↑ a b Donghwi Park (2015). «Space-state complexity of Korean chess and Chinese chess». 
  15. ↑ R. A. Hearn (2 de febrero de 2005). «Amazons is PSPACE-complete». 
  16. ↑ a b Shi-Jim Yen, Jr-Chang Chen, Tai-Ning Yang, and Shun-Chin Hsu (marzo de 2004). «Computer Chinese Chess». International Computer Games Association Journal 27 (1): 3-18. Archivado desde el original el 9 de julio de 2015. 
  17. ↑ H. Adachi, H. Kamekawa, and S. Iwata (1987). «Shogi on n × n board is complete in exponential time». Trans. IEICE. J70-D: 1843-1852. 
  18. ↑ a b Christ-Jan Cox (2006). «Analysis and Implementation of the Game Arimaa». 
  19. ↑ Brian Haskin (2007). «Arimaa Branching Factor». 
  20. ↑ John Tromp and Gunnar Farnebäck (2007). «Combinatorics of Go».  (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última). This paper derives the bounds 48<log(log(N))<171 on the number of possible games N.
  21. ↑ J. M. Robson (1983). «The complexity of Go». Information Processing; Proceedings of IFIP Congress. pp. 413-417. 

Enlaces externos

editar
Obtenido de «https://es.wikipedia.org/w/index.php?title=Complejidad_en_los_juegos&oldid=151893291»