ıllı Internet y Tecnologías de la Información (2018)

internet, Hosting, dominios, seo, antivirus, banco de imágenes, páginas web, tiendas online

[Enciclopedia Online Gratuita] Diccionario de Internet y Tecnologías de la Información y la Comunicación (TIC):

ıllı Complejidad en los juegos wiki: info, historia y vídeos

videos internet

salud  Complejidad en los juegos 


La teoría de combinatoria para juegos tiene distintas formas de medir la dificultad en los juegos. Este artículo describe 5 de ellas: dificultad estado-espacio, tamaño del árbol del juego, dificultad de las resoluciones, dificultad del árbol del juego, y dificultad computacional.



Medidas de la dificultad de un juego



  • La dificultad del estado-espacio de un juego es el número de situaciones legales del juego alcanzables desde la situación inicial del juego.

Cuando esto es demasiado bastante difícil de calcular, un límite superior puede ser computado frecuentemente incluyendo las situaciones ilegales o bien las situaciones que jamás pueden presentarse en el curso de un juego.



  • El tamaño del árbol del juego es el total de las instancias posibles que puedan ser aplicadas al juego, esto es, es el número de los nodos hoja en el árbol del juego cuya raíz es la situación inicial.El árbol del juego es sumamente más grande que la dificultad del estado-espacio por el hecho de que exactamente las mismas situaciones pueden acontecer en muchas instancias del juego, haciendo movimientos en diverso orden (por poner un ejemplo, en una partida del 3 en raya con 2 X y un O bien en el tablero, esta situación se habría podido lograr de 2 formas diferentes, en dependencia de dónde fue puesto el primer X). Un límite superior para el tamaño del árbol del juego puede ser computado en ocasiones, facilitando el juego de forma que aumente solo el tamaño del árbol del juego (por poner un ejemplo, dejando movimientos ilegales) hasta el momento en que llega a ser manejable.

Sin embargo, para los juegos donde el número de movimientos no se restringe (por poner un ejemplo por el tamaño del tablero, o bien por una regla sobre la reiteración de la situación) el árbol del juego es infinito.Las 2 siguientes medidas emplean un árbol de resolución. Un árbol de resolución es un subárbol del árbol del juego, con cada nodo etiquetado como “jugador A gana”, “jugador B gana” o bien “empate”, donde puede probarse que ese nodo tiene ese valor (asumiendo que los dos 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 desplazar al jugador A puede etiquetarse con “jugador A gana” si nodo sucesor es una victoria para A, o bien etiquetado con “jugador B gana” si todos y cada uno de los nodos sucesores, son victorias para B, o bien etiquetado como “empate” si todos y cada uno de los nodos sucesores son o bien empates o bien victoria para B. Y de forma equivalente, para las situaciones en las que mueve B).



  • La dificultad de resolución de un juego es el número de nodos hoja en el árbol de resolución más pequeño que establece el valor de la situación inicial. Todo árbol incluye todas y cada una de las posibles resoluciones para el jugador que mueve seguidamente, mas solo una

posibilidad para cada resolución del jugador que empieza la partida.



  • La dificultad del juego-árbol de un juego es el número de nodos hoja del árbol de resolución completo en anchura que establece un valor en la situación inicial. (Un árbol completo en anchura incluye todos y cada uno de los nodos de todos y cada uno de los niveles).Ésta es una estimación del número de situaciones que podríamos tener que valorar en una busca utilizando el algoritmo mínimax para determinar el valor de la situación inicial.Es bastante difícil apreciar la dificultad del juego-árbol, mas para ciertos 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 costo computacional de un juego describe la complicad asintótica de un juego que medra de forma arbitraria, expresada en notación de cota superior o bien como miembro de una clase de dificultad. Este término no se puede aplicar a juegos específicos, mas si a juegos que han sido formalizados para poder ser de manera aleatoria grandes, en general jugándolos en un tablero de n por n. (Desde la perspectiva de la dificultad computacional de un juego en un tablero de tamaño fijo, es un inconveniente finito que se puede solucionar en O(1), por servirnos de un ejemplo, con una tabla de busca de situaciones en el mejor movimiento en todos y cada situación).

Ejemplo: 3 en raya


Para el juego de 3 en raya podríamos tener un límite de treinta y nueve = diecinueve y seiscientos ochenta y tres formas de rellenar el tablero (3 posibles estados para cada celda y 9 celdas). Esta cuenta incluye muchas situaciones ilegales como una situación con 5 cruces y sin ceros, o bien una situación en la que los dos jugadores tienen una fila de 3. Aplicando a estas limitaciones, tenemos una cuenta mejorada, en la que suprimiendo estas situaciones ilegales, podríamos tener cinco mil cuatrocientos setenta y ocho combinaciones para rellenar. Si bien... son consideradas idénticas, hay solo setecientos sesenta y cinco situaciones rigurosamente diferentes.Si atendemos a la cota superior del árbol que produce el tablero, tenemos nueve!=362.880 (nueve situaciones para el primer movimiento, ocho para el segundo, y de esta manera consecutivamente). Esta cuenta incluye partidas y movimientos ilegales, puesto que el juego puede haber terminado. Si refinamos entonces las combinaciones tenemos doscientos cincuenta y 5 mil ciento sesenta y ocho posibles movimiento. Si además de esto agregamos que las rotaciones de las situaciones son consideradas exactamente las mismas, tenemos solo veintiseis y ochocientos treinta lanzamientos.La dificultad computacional del 3 en raya depende de la manera en que esté formalizado. Una formalización natural sería m,n,k-games, que sería un tablero de m x n siendo el ganador el que logra conseguir k en raya. Es trivial que el juego puede ser resuelto DSPACE (mn) con la busca del árbol del juego. Esto lo pon en una clase de dificultad esencial, PSPACE. Con un tanto más de trabajo se puede probar que es PSPACE-completo.


Complejidad de ciertos juegos conocidos


Debido a la enorme cantidad de complejidades en los juegos, esta tabla da la aproximación superior de su logaritmo en base diez. Los números mostrados ahora han de ser considerados con precaución: cambios supuestamente pequeños en las reglas del juego pueden mudar estos números (que no son estimaciones demasiado precisas) por tremendos factores, que pueden ser sencillamente mucho mayores que los datos ofrecidos.

JuegoTamaño del tablero

(cells)

Dificultad estado-espacio

(como log en base diez)

Dificultad del árbol del juego

(como log en base diez)

Longitud media del juego

(número de turnos)

Clase de dificultad del juego formalizadoTres en raya9359PSPACE-completoPentominó64121810?, mas en PSPACEConecta cuatro42142136?, mas en PSPACEDamas inglesas (8x8)3220 or 183170EXPTIME-completoOware12123260La generalización está incompleta.Qubic64303420PSPACE-completoFanorona45214622?, mas en EXPTIMENine Men's Morris241050??, mas en EXPTIMEDamas internacionales (10x10)5030?5490EXPTIME-completoDamas chinas (dos conjuntos)12123???, mas en EXPTIMEDamas chinas (seis conjuntos)12135???, mas en EXPTIMELíneas de acción64245663?, mas en EXPTIMEReversi64285858PSPACE-completoHex (11x11)12156?40PSPACE-completoGomoku (15x15, freestyle)225105?7030PSPACE-completoAjedrez645012380EXPTIME-completoConecta636117270 or catorce mil quince or 30PSPACE-completoBackgammon282014450-60La generalización está incompleta.Xiangqi904015080??, se piensa que es EXPTIME-completoJanggi9044160??, se piensa que es EXPTIME-completoQuoridor8142162??, mas en PSPACEAmazonas (10x10)10040 (cota superior)??PSPACE-completoShogi8171226110?EXPTIME-completoArimaa644329670?, mas en EXPTIMEGo (board game) 19x19361171360150EXPTIME-completo

Véase también


Notas y referencias



  1. ? abcdefghijklmnñopqrstuvwxyzaaVictor Allis (mil novecientos noventa y cuatro). Searching for Solutions in Games and Artificial Intelligence. Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. ISBN noventa-novecientos setecientos cuarenta y ocho-ocho-0.
  2. ? abcdStefan Reisch (mil novecientos ochenta). «Gobang ist PSPACE-vollstandig (Gomoku is PSPACE-complete)». Acta Informatica13: cinco mil novecientos sesenta y seis.
  3. ?Hilarie K. Orman: Pentominoes: A First Player Win in Games of no chance, MSRI Publications – Volume veintinueve, mil novecientos noventa y seis, pages trescientos treinta y nueve-trescientos cuarenta y cuatro. Online: pdf.
  4. ?Jonathan Schaeffer et al (seis de julio de dos mil siete). «Checkers is Solved». Science.
  5. ? abJ. M. Robson (mil novecientos ochenta y cuatro). «N by N checkers is Exptime complete». SIAM Journal on Computing,13 (dos): doscientos cincuenta y dos-doscientos sesenta y siete. doi:10.1137/0213018.
  6. ? See Allis mil novecientos noventa y cuatro for rules
  7. ? abM.P.D. Schadd, M.H.M. Winands, J.W.H.M. Uiterwijk, H.J. van den Herik and M.H.J. Bergsma (dos mil ocho). «Best Play in Fanorona leads to Draw». New Mathematics and Natural Computation4 (tres): trescientos sesenta y nueve-trescientos ochenta y siete.
  8. ?S. Iwata and T. Kasai (mil novecientos noventa y cuatro). «The Othello game on an n*n board is PSPACE-completo». Theor. Comp. Sci.123 (ciento veintitres): trescientos veintinueve-trescientos cuarenta. doi:10.1016/0304-3975(noventa y cuatro)90131-siete.
  9. ?Stefan Reisch (mil novecientos ochenta y uno). «Hex ist PSPACE-vollständig (Hex is PSPACE-complete)». Acta Inf. (quince): ciento sesenta y siete-ciento noventa y uno.
  10. ? abThe size of the state space and game tree for chess were first estimated in Claude Shannon (mil novecientos cincuenta). «Programming a Computer for Playing Chess». Philosophical Magazine41 (trescientos catorce). Shannon gave estimates of mil cuarenta y tres and diez ciento veinte 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 (mil novecientos ochenta y uno). «Computing a perfect strategy for n×n chess requires time exponential in n». J. Comb. Th. A (treinta y uno): ciento noventa y nueve-doscientos catorce.
  12. ?«On the fairness and complexity of generalized k-in-a-row games». Consultado el dos mil nueve.
  13. ?«Copia archivada». Archivado desde el original el veintiseis de febrero de dos mil nueve. Consultado el quince de abril de dos mil ocho.
  14. ? abDonghwi Park (dos mil quince). «Space-state complexity of Korean chess and Chinese chess».
  15. ?R. A. Hearn (dos de febrero de dos mil cinco). «Amazons is PSPACE-complete».
  16. ? abShi-Jim Yen, Jr-Chang Chen, Tai-Ning Yang, and Shun-Chin Hsu (marzo de dos mil cuatro). «Computer Chinese Chess». International Computer Games Association Journal27 (1): tres-dieciocho. Archivado desde el original el nueve de julio de dos mil quince.
  17. ?H. Adachi, H. Kamekawa, and S. Iwata (mil novecientos ochenta y siete). «Shogi on n × n board is complete in exponential time». Trans. IEICE. J70-D: mil ochocientos cuarenta y tres-mil ochocientos cincuenta y dos.
  18. ? abChrist-Jan Cox (dos mil seis). «Analysis and Implementation of the Game Arimaa».
  19. ?Brian Haskin (dos mil siete). «Arimaa Branching Factor».
  20. ?John Tromp and Gunnar Farnebäck (dos mil siete). «Combinatorics of Go». (link roto libre en Internet Archive; véase el historial y la última versión). This paper derives the bounds 48<log(log(N))<171 on the number of possible games N.
  21. ?J. M. Robson (mil novecientos ochenta y tres). «The complexity of Go». Information Processing; Proceedings of IFIP Congress. pp. cuatrocientos trece-cuatrocientos diecisiete.

Enlaces externos


  ELIGE TU TEMA DE INTERÉS: 


autoayuda.es   Internet y Tecnologias 

Está aquí: Inicio > [ INTERNET ] > ıllı Complejidad en los juegos wiki: info, historia y vídeos

Las cookies nos permiten ofrecer nuestros servicios. Al utilizar nuestros servicios, aceptas el uso que hacemos de las cookies. Ver políticas