fbpx
Wikipedia

Complejidad en los juegos

Julio 03, 2022

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

  • 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

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

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

  • Juego resuelto
  • Lista de juegos y rompecabezas NP-completos
  • Lista de juegos y rompecabezas PSPACE-completos

Notas y referencias

  1. ↑ 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. ↑ 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. ↑ 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. ↑ 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. ↑ 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. . Archivado desde el original el 26 de febrero de 2009. Consultado el 15 de abril de 2008. 
  14. ↑ 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. ↑ Shi-Jim Yen, Jr-Chang Chen, Tai-Ning Yang, and Shun-Chin Hsu (marzo de 2004). . 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. ↑ 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

  •   Datos: Q903738

Julio 03, 2022
complejidad, juegos, este, artículo, sección, sobre, ocio, necesita, wikificado, favor, edítalo, para, cumpla, convenciones, estilo, este, aviso, puesto, junio, 2008, teoría, juegos, combinatorios, posee, diversas, maneras, medir, complejidad, juegos, este, ar. Este articulo o seccion sobre ocio necesita ser wikificado por favor editalo para que cumpla con las convenciones de estilo Este aviso fue puesto el 11 de junio de 2008 La teoria de juegos combinatorios posee diversas maneras de medir la complejidad en los juegos Este articulo describe cinco de ellas complejidad estado espacio tamano del arbol del juego complejidad de las decisiones complejidad del arbol del juego y complejidad computacional Indice 1 Medidas de la complejidad de un juego 2 Ejemplo Tres en raya 3 Complejidad de algunos juegos conocidos 4 Vease tambien 5 Notas y referencias 6 Enlaces externosMedidas de la complejidad de un juego EditarLa complejidad del estado espacio de un juego es el numero de posiciones legales del juego accesibles desde la posicion inicial del juego 1 Cuando esto es demasiado dificil de calcular un limite superior puede ser computado a menudo incluyendo las posiciones ilegales o las posiciones que nunca pueden presentarse en el curso de un juego El tamano del arbol del juego es el numero total de las instancias posibles que puedan ser aplicadas al juego es decir es el numero de los nodos hoja en el arbol del juego cuya raiz es la posicion inicial El arbol del juego es sumamente mas 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 posicion se habria podido alcanzar de dos maneras diferentes dependiendo de donde fue puesto el primer X Un limite superior para el tamano del arbol del juego puede ser computado a veces simplificando el juego de manera que aumente solo el tamano del arbol del juego por ejemplo permitiendo movimientos ilegales hasta que llega a ser manejable Sin embargo para los juegos donde el numero de movimientos no se limita por ejemplo por el tamano del tablero o por una regla sobre la repeticion de la posicion el arbol del juego es infinito Las dos siguientes medidas usan un arbol de decision Un arbol de decision es un subarbol del arbol 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 analoga para las posiciones en las que mueve B La complejidad de decision de un juego es el numero de nodos hoja en el arbol de decision mas pequeno que establece el valor de la posicion inicial Todo arbol incluye todas las posibles decisiones para el jugador que mueve en segundo lugar pero solo unaposibilidad para cada decision del jugador que comienza la partida La complejidad del juego arbol de un juego es el numero de nodos hoja del arbol de decision completo en anchura que establece un valor en la posicion inicial 1 Un arbol completo en anchura incluye todos los nodos de todos los niveles Esta es una estimacion del numero de posiciones que podriamos tener que evaluar en una busqueda usando el algoritmo minimax para determinar el valor de la posicion inicial Es dificil estimar la complejidad del juego arbol pero para algunos juegos un limite inferior razonable puede darse elevando el numero de hijos medio de cada nodo al numero de turnos que hay en el juego medio El coste computacional de un juego describe la dificultad asintotica de un juego que crece de manera arbitraria expresada en notacion 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 jugandolos en un tablero de n por n Desde el punto de vista de la complejidad computacional de un juego en un tablero de tamano fijo es un problema finito que se puede resolver en O 1 por ejemplo con una tabla de busqueda de posiciones en el mejor movimiento en cada posicion Ejemplo Tres en raya EditarPara el juego de Tres en raya podriamos tener un limite 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 posicion con cinco cruces y sin ceros o una posicion 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 podriamos tener 5 478 combinaciones para rellenar Aunque son consideradas identicas hay solo 765 posiciones estrictamente diferentes Si atendemos a la cota superior del arbol que genera el tablero tenemos 9 362 880 9 posiciones para el primer movimiento 8 para el segundo y asi 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 ademas anadimos que las rotaciones de las posiciones son consideradas las mismas tenemos solo 26 830 lanzamientos La complejidad computacional del tres en raya depende de la forma en que este formalizado Una formalizacion natural seria juegos m n k que seria 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 busqueda del arbol del juego Esto lo coloca en una clase de complejidad importante PSPACE Con un poco mas de trabajo se puede demostrar que es PSPACE completo 2 Complejidad de algunos juegos conocidos EditarDebido a la gran cantidad de complejidades en los juegos esta tabla da la aproximacion superior de su logaritmo en base 10 Los numeros mostrados a continuacion deben ser considerados con precaucion cambios aparentemente pequenos en las reglas del juego pueden cambiar estos numeros que no son estimaciones demasiado exactas por tremendos factores que pueden ser facilmente mucho mayores que los datos ofrecidos Juego Tamano del tablero cells Complejidad estado espacio como log en base 10 Complejidad del arbol del juego como log en base 10 Longitud media del juego numero de turnos Clase de complejidad del juego formalizadoTres en raya 9 3 5 9 PSPACE completo 2 Pentomino 64 12 18 10 3 pero en PSPACEConecta cuatro 42 14 1 21 1 36 1 pero en PSPACEDamas 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 esta incompleta Qubic 64 30 1 34 1 20 1 PSPACE completo 2 Fanorona 45 21 7 46 7 22 pero en EXPTIMENine Men s Morris 24 10 1 50 1 pero en EXPTIMEDamas internacionales 10x10 50 30 1 54 1 90 1 EXPTIME completo 5 Damas chinas 2 conjuntos 121 23 pero en EXPTIMEDamas chinas 6 conjuntos 121 35 pero en EXPTIMELineas de accion 64 24 56 63 pero en EXPTIMEReversi 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 generalizacion esta incompleta Xiangqi 90 40 14 150 1 80 se cree que es EXPTIME completoJanggi 90 44 14 160 se cree que es EXPTIME completoQuoridor 81 42 162 pero en PSPACEAmazonas 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 EXPTIMEGo board game 19x19 361 171 20 360 1 150 1 EXPTIME completo 21 Vease tambien EditarJuego resuelto Lista de juegos y rompecabezas NP completos Lista de juegos y rompecabezas PSPACE completosNotas y referencias Editar a b c d e f g h i j k l m n 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 a b c d Stefan Reisch 1980 Gobang ist PSPACE vollstandig Gomoku is PSPACE complete Acta Informatica 13 5966 Hilarie K Orman Pentominoes A First Player Win in Games of no chance MSRI Publications Volume 29 1996 pages 339 344 Online pdf Jonathan Schaeffer et al 6 de julio de 2007 Checkers is Solved Science 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 See Allis 1994 for rules 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 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 Stefan Reisch 1981 Hex ist PSPACE vollstandig Hex is PSPACE complete Acta Inf 15 167 191 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 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 On the fairness and complexity of generalized k in a row games Consultado el 2009 Copia archivada Archivado desde el original el 26 de febrero de 2009 Consultado el 15 de abril de 2008 a b Donghwi Park 2015 Space state complexity of Korean chess and Chinese chess R A Hearn 2 de febrero de 2005 Amazons is PSPACE complete 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 H Adachi H Kamekawa and S Iwata 1987 Shogi on n n board is complete in exponential time Trans IEICE J70 D 1843 1852 a b Christ Jan Cox 2006 Analysis and Implementation of the Game Arimaa Brian Haskin 2007 Arimaa Branching Factor John Tromp and Gunnar Farneback 2007 Combinatorics of Go enlace roto disponible en Internet Archive vease el historial la primera version y la ultima This paper derives the bounds 48 lt log log N lt 171 on the number of possible games N J M Robson 1983 The complexity of Go Information Processing Proceedings of IFIP Congress pp 413 417 Enlaces externos EditarDavid Eppstein s Computational Complexity of Games and Puzzles Datos Q903738 Obtenido de https es wikipedia org w index php title Complejidad en los juegos amp oldid 139489761, wikipedia, wiki, leyendo, leer, libro, biblioteca,

español

, española, descargar, gratis, descargar gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, imagen, música, canción, película, libro, juego, juegos