Arbre de joc

Arbre de joc sencer del tic-tac-toe.

Un arbre de joc és un gràfic que representa tots els estats de joc possibles dins d’aquest joc, això en el context de la teoria de joc combinatòria, que normalment estudia jocs seqüencials amb informació perfecta. Aquests jocs inclouen jocs coneguts com els escacs, les dames, el Go i el tic-tac-toe. Es pot utilitzar per mesurar la complexitat d'un joc, ja que representa totes les maneres possibles en què un joc pot sortir. A causa dels grans arbres de joc de joc complexos com els escacs, els algoritmes dissenyats per jugar a aquesta classe de joc utilitzaran arbres de joc parcials, cosa que fa factible la computació en ordinadors moderns. Existeixen diversos mètodes per resoldre els arbres de caça. Si es pot generar un arbre de joc complet, es pot utilitzar un algorisme determinista, com ara la inducció cap enrere o l’ anàlisi retrògrad. Algorismes aleatoris i algorismes Minimax com MCTS es poden utilitzar en casos en què un arbre de joc complet no sigui factible, basats en el nombre de Shannon i fent ús de bitboards.

Comprensió de l'arbre de joc

En teoria de jocs, un arbre de joc és un graf dirigit de tipus arbre els nodes representen posicions en el joc i del qual arestes representen moviments dels jugadors. Qualsevol successió de jugades es pot representar per un camí connex dins l'arbre de joc. Si el joc acaba sempre després dun nombre finit de passos, llavors larbre té un nombre finit de nodes. El nombre de nodes a l'arbre complet d'un joc és el nombre de totes les possibles jugades. Per exemple, per al joc de les 3 en ratlla hi ha 255.168 nodes.

Per entendre millor l’arbre de joc, es pot pensar com una tècnica per analitzar els jocs adversaris, que determinen les accions que realitza el jugador per guanyar el joc. En la teoria de jocs, un arbre de joc és un gràfic dirigit els nodes del qual són posicions en un joc (per exemple, la disposició de les peces en un joc de taula) i les vores dels quals es mouen (per exemple, per moure peces d'una posició a una altra sobre un tauler).

L’ arbre de joc complet per a un joc és l’arbre de joc que comença a la posició inicial i conté tots els moviments possibles de cada posició; l'arbre complet és el mateix que l'obtingut a partir de la representació de joc de forma extensa. Per ser més específics, el joc complet és una norma per al joc en teoria de joc. Que pot expressar clarament molts aspectes importants. Per exemple, la seqüència d’accions que poden prendre les parts interessades, les seves decisions en cada punt de decisió, informació sobre les accions realitzades per altres parts interessades quan cada part pren una decisió i els beneficis de tots els possibles resultats de joc.

Les dues primeres capes de l’arbre del joc per al tic-tac-toe.

El diagrama mostra els dos primers nivells, o capes, a l’arbre de joc per al tic-tac-toe. Les rotacions i els reflexos de les posicions són equivalents, de manera que el primer jugador té tres opcions de moviment: al centre, a la vora o a la cantonada. El segon jugador té dues opcions per respondre si el primer jugador jugava al centre, en cas contrari cinc opcions. Etcètera.

El nombre de nodes de fulles a l’arbre de joc complet és el nombre de maneres diferents en què es pot jugar. Per exemple, l'arbre de joc per al tic-tac-toe té 255.168 nodes.

Els arbres de joc són importants en la intel·ligència artificial ia una manera de triar el millor moviment en un joc és buscar en l'arbre de joc utilitzant qualsevol dels nombrosos algoritmes de recerca arbre, combinat amb regles minimax per podar l'arbre. L’arbre de joc per al tic-tac-toe es pot determinar fàcilment, però els arbres de joc complets per a jocs més complexes com els escacs són massa grans per arribar al final. En lloc d'això, un programa de joc d'escacs busca un arbre de joc parcial: normalment tantes capes de la posició actual com es pot cercar en el temps disponible. Excepte el cas dels arbres de joc "patològics" (que a la pràctica són bastant rars), augmentar la profunditat de cerca (és a dir, el nombre de capes cercades) en general millora la possibilitat de triar el millor moviment.

Els jocs de dues persones també es poden representar com I-O arbres. Perquè el primer jugador guanyi una partida, hi ha d’haver un moviment guanyador per a tots els moviments del segon jugador. Això es representa a l'arbre i-o mitjançant la disjunció per representar els moviments alternatius del primer jugador i l'ús de la conjunció per representar tots els moviments del segon jugador.

Resolució d'arbres de joc

Un arbre de joc arbitrari que ha estat completament acolorit

Versió de l'algorisme determinista

Amb un arbre de joc complet, és possible "resoldre" el joc, és a dir, trobar una seqüència de moviments que pot seguir el primer o el segon jugador que garanteixin el millor resultat possible per a aquest jugador (normalment una victòria o un llaç). L'algorisme (que generalment s'anomena inducció cap enrere o anàlisi retrògrada) es pot descriure recursivament de la següent manera.

1. Pintar la capa final de l’arbre de joc de manera que totes les victòries del jugador 1 tinguin un color determinat (blau al diagrama), que totes les victòries del jugador 2 tinguin un altre color (vermell al diagrama) i que tots els enllaços tinguin un tercer color (Gris al diagrama).
2. Mirar la següent capa. Si hi ha un node de color oposat al jugador actual, pintar-lo també com aquest jugador. Si tots els nodes immediatament inferiors són del color del mateix jugador, pintar-lo també per al mateix jugador. En cas contrari, pinteu aquest node com un enllaç
3. Repetir-ho per a cada capa, movent-se cap amunt, fins que tots els nodes siguin de colors. El color del node arrel determinarà la naturalesa del joc

El diagrama mostra un arbre de joc per a un joc arbitrari, acolorit utilitzant l'algorisme anterior.

Normalment és possible resoldre un joc (en aquest sentit tècnic de "resoldre") utilitzant només un subconjunt de l'arbre de joc, ja que en molts jocs no cal analitzar un moviment si hi ha un altre moviment que sigui millor per al mateix jugador (per exemple, la poda alfa-beta es pot utilitzar en molts jocs deterministes).

Qualsevol subarrendament que es pot utilitzar per resoldre el joc es coneix com un arbre de decisions, i les mides dels arbres de decisió de diverses formes s'utilitzen com a mesures de complexitat del joc.

Versió d'algorismes aleatoris

Es poden utilitzar algoritmes aleatoris per resoldre arbres de joc. Hi ha dos avantatges principals en aquest tipus d’implementació: rapidesa i practicitat. Mentre que es pot fer una versió determinista de la resolució d’arbres de joc a Ο(n), l’algorisme aleatoritzat següent té un temps d’execució esperat de θ(n^0.792) si cada node de l’arbre de joc té un grau 2. A més, és pràctic perquè els algorismes aleatoris són capaços de "frustrar un enemic", és a dir, un oponent no pot vèncer el sistema d'arbres de joc coneixent l'algorisme utilitzat per resoldre l'arbre de joc perquè l'ordre de resolució és aleatori.

La següent és una implementació de l'algorisme aleatòria de solució d'arbre de joc:

def gt_eval_rand(u) -> bool:
"""Returns True if this node evaluates to a win, otherwise False"""
if u.leaf:
return u.win
else:
random_children = (gt_eval_rand(child) for child in random_order(u.children))
if u.op == "OR":
return any(random_children)
if u.op == "AND":
return all(random_children)

L'algorisme fa ús de la idea de " curtcircuit ": si el node arrel es considera un operador "OR", llavors una vegada que es troba un True, l’arrel es classifica com True; al contrari, si el node arrel es considera un operador "AND" llavors una vegada es troba un False, l’arrel es classifica com False .

Bibliografia

• Hu, Te Chiang. Combinatorial Algorithms. Courier Dover Publications, 2002. ISBN 0-486-41962-2. 
• Judea Pearl, Heuristics, Addison-Wesley, 1984