Complejidad en los juegos

Complejidad en los juegos
Spanish Language Wiki.svg
 Este artículo o sección sobre ocio necesita ser wikificado con un formato acorde a las convenciones de estilo.
Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 11 de junio de 2008.
También puedes ayudar wikificando otros artículos.

La teoría de combinatoria para juegos 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.

Contenido

Medidas de la complejidad de un juego

  • 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 mínimax 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

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

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 generalizacion 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 48[1] 150[1] 80? ?, se cree que es EXPTIME-completo
Quoridor 81 42 162 ? ?, pero en PSPACE
Amazonas (10x10) 100 40 (cota superior) ? ? PSPACE-completo[14]
Shōgi 81 71[15] 226[15] 110? EXPTIME-completo[16]
Arimaa 64 43[17] 296[17] 70[18] ?, pero en EXPTIME
Go (board game) 19x19 361 171[19] 360[1] 150[1] EXPTIME-completo[20]

Véase también

  • Go complexity
  • Solved board games
  • list of NP-complete games and puzzles
  • list of PSPACE-complete games and puzzles

Notas y referencias

  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 ab 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. http://fragrieu.free.fr/SearchingForSolutions.pdf. 
  2. ↑ a b c d Stefan Reisch (1980). «Gobang ist PSPACE-vollstandig (Gomoku is PSPACE-complete)». Acta Informatica 13:  pp. 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):  pp. 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):  pp. 369–387. http://www.personeel.unimaas.nl/Maarten-Schadd/Papers/2008FanoronaJNMNC.pdf. 
  8. ↑ S. Iwata and T. Kasai (1994). «The Othello game on an n*n board is PSPACE-completo». Theor. Comp. Sci. 123 (123):  pp. 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):  pp. 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). http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf.  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):  pp. 199–214. 
  12. ↑ «On the fairness and complexity of generalized k-in-a-row games».
  13. ↑ http://books.nips.cc/papers/txt/nips04/0259.txt
  14. ↑ R. A. Hearn (02-02-2005). «Amazons is PSPACE-complete».
  15. ↑ a b Shi-Jim Yen, Jr-Chang Chen, Tai-Ning Yang, and Shun-Chin Hsu (March 2004). «Computer Chinese Chess». International Computer Games Association Journal 27 (1):  pp. 3–18. http://www.csie.ndhu.edu.tw/~sjyen/Papers/2004CCC.pdf. 
  16. ↑ H. Adachi, H. Kamekawa, and S. Iwata (1987). «Shogi on n × n board is complete in exponential time». Trans. IEICE J70-D:  pp. 1843–1852. 
  17. ↑ a b Christ-Jan Cox (2006). «Analysis and Implementation of the Game Arimaa».
  18. ↑ Brian Haskin (2007). «Arimaa Branching Factor».
  19. ↑ John Tromp and Gunnar Farnebäck (2007). «Combinatorics of Go». This paper derives the bounds 48<log(log(N))<171 on the number of possible games N.
  20. ↑ J. M. Robson (1983). «The complexity of Go». Information Processing; Proceedings of IFIP Congress. pp. 413–417. 

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Mira otros diccionarios:

  • Los Colonos de Catán — Los Colonos de Catán/Los descubridores de Catán Diseñado por Klaus Teuber Editorial …   Wikipedia Español

  • Juegos seculares — Los juegos seculares (en latín Ludi Saeculares y anteriormente Ludi Terentini) eran unas celebraciones religiosas en las que se realizaban sacrificios y se llevaban a cabo representaciones teatrales. Tenían parte en la antigua Roma durante tres… …   Wikipedia Español

  • Juegos tradicionales — Niños jugando en un jardín. Unos juegan al corro con un adulto y otros con un balancín …   Wikipedia Español

  • Los Hombres Lobo de Castronegro — Se ha sugerido que este artículo o sección sea fusionado en Mafia (juego) (discusión). Una vez que hayas realizado la fusión de artículos, pide la fusión de historiales aquí. The Werewolves of Millers Hollow …   Wikipedia Español

  • Historia de los videojuegos — Donkey Kong, de Shigeru Miyamoto (1981), uno de los videojuegos más populares de todos los tiempos. La historia de los videojuegos tiene su origen en la década de 1940 cuando, tras el fin de la Segunda Guerra Mundial, las potencias vencedoras… …   Wikipedia Español

  • 42 Juegos de Siempre — Clubhouse Games 42 Juegos de Siempre Desarrolladora(s) AGENDA Distribuidora(s) Nintendo Plataforma(s) Nintendo DS Fecha(s) de lanzamiento …   Wikipedia Español

  • Diseñador de juegos — Saltar a navegación, búsqueda Un diseñador de juegos es una persona que se encarga de diseñar videojuegos o juegos tradicionales, como juegos de mesa. Diseñador de videojuegos Un diseñador de videojuegos desarrolla el esquema, concepto y… …   Wikipedia Español

  • Historia de los computadores personales — Niños jugando en un computador Amstrad CPC 464 en los años 1980 La historia de los computadores personales comenzó en los años 1970. Un computador personal esta orientado al uso individual y se diferencia de un computador mainframe, donde las… …   Wikipedia Español

  • El Señor de los Anillos, el juego de batallas estratégicas — Para otros usos de este término, véase El Señor de los Anillos (desambiguación). El Señor de los Anillos, el juego de batallas estratégicas Jugadores 2+ Preparación < 10 minutos Duración …   Wikipedia Español

  • El rincón de los niños — Fragmento de Golliwogg s cake walk, última pieza de la suite. El rincón de los niños (Children s corner en inglés), es una suite para piano escrita por el compositor impresionista francés Claude Debussy (Saint Germain en Laye, Francia, 22 de… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”