La teoria de jocs combinatoris posseïx diverses maneres de medir la complexitat en els jocs. Este artícul descriu cinc d'elles: complexitat estat-espai, tamany de l'arbre del joc, complexitat de les decisions, complexitat de l'arbre del joc, i complexitat computacional.

Mides de la complexitat d'un joc

  • La complexitat de l'estat-espai d'un joc és el número de posicions llegals del joc accessibles des de la posició inicial del joc.

Quan açò és massa difícil de calcular, un llímit superior pot ser computat a sovint incloent les posicions illegals o les posicions que mai poden presentar-se en el curs d'un joc.

  • El tamany de l'arbre del joc és el número total de les instàncies possibles que puguen ser aplicades al joc, és dir, és el número dels nodos full en l'arbre del joc la raïl del qual és la posició inicial.L'arbre del joc és sumament més gran que la complexitat de l'estat-espai perque les mateixes posicions poden ocórrer en moltes instàncies del joc, fent moviments en divers orde (per eixemple, en una partida del Tres en ralla en dos X i un O en el tauler, esta posició s'hauria pogut alcançar de dos maneres diferents, depenent d'on va ser posat el primer X). Un llímit superior per al tamany de l'arbre del joc pot ser computat a voltes, simplificant el joc de manera que aumente només el tamany de l'arbre del joc (per eixemple, permetent moviments illegals) fins que aplega a ser manejable.

No obstant, per als jocs a on el número de moviments no es llimita (per eixemple pel tamany del tauler, o per una regla sobre la repetició de la posició) l'arbre del joc és infinit.

Les dos següents mides usen un arbre de decisió. Un arbre de decisió és un subárbol de l'arbre del joc, en cada nodo etiquetat com a “jugador A gana”, “jugador B guanya” o “empat”, a on pot provar-se que eixe nodo té eixe valor (assumint que abdós jugadors fan el millor moviment) solament en examinar atres nodos del grafo. (Els nodos terminals poden ser etiquetats directament; un nodo en la que li toque moure al jugador A pot etiquetar-se en “jugador A gana” si nodo successor és una victòria para A, o etiquetage en “jugador B guanya” si tots els nodos successors, són victòries per a B, o etiquetage com a “empat” si tots els nodos successors són o empats o victòria per a B. I de manera anàloga, per a les posicions en les que mou B).

  • La complexitat de decisió d'un joc és el número de nodos full en l'arbre de decisió més chicotet que establix el valor de la posició inicial. Tot arbre inclou totes les possibles decisions per al jugador que mou en segon lloc, pero solament una

possibilitat per a cada decisió del jugador que comença la partida.

  • La complexitat del jugue-arbre d'un joc és el número de nodos full de l'arbre de decisió complet en esgambi que establix un valor en la posició inicial. (Un arbre complet en esgambi inclou tots els nodos de tots els nivells). Esta és una estimació del número de posicions que podríem tindre que evaluar en una busca usant l'algoritme minimax per a determinar el valor de la posició inicial. És difícil estimar la complexitat del jugue-arbre, pero per a alguns jocs un llímit inferior raonable pot donar-se elevant el número de fills mig de cada nodo al número de tandes que hi ha en el joc mig.
  • El cost computacional d'un joc descriu la dificultat asintòtica d'un joc que creix de manera arbitrària, expressada en notació de cota superior o com a membre d'una classe de complexitat. Este concepte no és aplicable a jocs concrets, pero si a jocs que han segut formalisats per a que puguen ser aleatòriament grans, generalment jugant-los en un tauler de n per n. (Des del punt de vista de la complexitat computacional d'un joc en un tauler de tamany fix, és un problema finit que es pot resoldre en O(1), per eixemple, en una taula de busca de posicions en el millor moviment en cada posició).

Eixemple: Tres en ralla

Per al joc de Tres en ralla podríem tindre un llímit de 39 = 19.683 maneres de reblir el tauler (tres possibles estats per a cada cela i nou celes). Este conte inclou moltes posicions illegals tals com una posició en cinc creus i sense zeros, o una posició en la que abdós jugadors tenen una fila de tres. Aplicant a estes restriccions, tenim un conte millorat, en la que eliminant estes posicions illegals, podríem tindre 5.478 combinacions per a reblir. Encara que... són considerades idèntiques, hi ha solament 765 posicions estrictament diferents. Si atenem a la cota superior de l'arbre que genera el tauler, tenim 9!=362.880 (9 posicions per al primer moviment, 8 per al segon, i aixina successivament). Este conte inclou partides i moviments illegals, ya que el joc pot haver terminat. Si refinem llavors les combinacions tenim 255.168 possibles moviment. Si ademés afegim que les rotacions de les posicions són considerades les mateixes, tenim només 26.830 llançaments. La complexitat computacional del tres en ralla depén de la forma en que estiga formalisat. Una formalisació natural seria jocs m,n,k, que seria un tauler de m x n sent el guanyador el que conseguix obtindre k en ralla. És trivial que el joc pot ser resolt DSPACE (mn) en la busca de l'arbre del joc. Açò ho coloca en una classe de complexitat important, PSPACE. En una miqueta més de treball es pot demostrar que és PSPACE-complet.[1]

Vore també

Notes i referències

  1. ↑ Stefan Reisch(1980).«Gobang ist PSPACE-vollstandig (Gomoku is PSPACE-complete)».Acta Informatica.13: 5966.


Referències