Arbre de jeu

Un arbre de jeu arbitraire entièrement coloré avec l'algorithme suivant

Avec un arbre de jeu complet, il est possible de «résoudre» le jeu, c'est-à-dire de trouver une séquence de coups que le premier ou le deuxième joueur peut suivre et qui garantira le meilleur résultat possible pour ce joueur (généralement une victoire ou une égalité). L'algorithme (qui est généralement appelé raisonnement rétrograde ou analyse rétrograde) peut être décrit de manière récursive comme suit, en partant d'un arbre de jeu complet non coloré :

1. Colorez le dernier niveau de l'arbre de jeu de sorte que toutes les victoires du joueur 1 soient colorées dans un sens (bleu dans le diagramme), toutes les victoires du joueur 2 soient colorées d'une autre façon (rouge dans le diagramme) et toutes les égalités soient colorées d'une troisième façon (gris sur le diagramme).
2. Remontez aux nœuds du niveau supérieur. Si l'un des fils d'un nœud est de couleur opposée au joueur actuel, colorez le nœud de la couleur de ce fils. Si tous les fils d'un nœud sont de la même couleur que le joueur actuel, colorez ce nœud de la même couleur. Sinon, colorez ce nœud avec une égalité.
3. Répétez l'étape 2, en vous déplaçant vers le haut, jusqu'à ce que tous les nœuds soient colorés. La couleur du nœud racine déterminera la nature du jeu.

Il est généralement possible de résoudre un jeu (dans ce sens technique de «résoudre») en utilisant uniquement un sous-ensemble de l'arbre de jeu, car dans de nombreux jeux, un mouvement n'a pas besoin d'être analysé s'il y a un autre mouvement qui est meilleur pour le même joueur. C'est le principe utilisé pour l'élagage alpha-bêta qui peut être utilisé dans de nombreux jeux déterministes.

Tout sous-arbre pouvant être utilisé pour résoudre le jeu est connu sous le nom d'arbre de décision, et la taille des arbres de décision de différentes formes est utilisée comme mesure de la complexité du jeu[2].

Un autre moyen pour résoudre les arbres de jeu est l’utilisation d'algorithmes randomisés. Cette méthode présente deux avantages important: la rapidité et la praticité. Alors qu'une version déterministe de la résolution des arbres de jeu peut être effectuée en Ο(n), l'algorithme aléatoire suivant a un temps d'exécution attendu de θ(n^0.792) si chaque nœud de l'arbre de jeu a le degré 2. Son côté pratique vient du fait qu'un adversaire ne peut pas battre le système d'arbres de jeu en connaissant l'algorithme utilisé pour résoudre l'arbre de jeu car l'ordre de résolution est aléatoire.

L'algorithme suivant est une version possible de résolution d'arbre de jeu de façon aléatoire[3]:

def gt_eval_rand(u) -> bool:
  """Renvoie True si ce noeud est évalué en victoire, sinon renvoie 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'algorithme utilise l'idée de "court-circuit": Dans le cas où la racine est considéré comme un "OR "opérateur, elle est classée comme True si un True est trouvé dans l'arbre; inversement, dans le cas où la racine est considéré comme un "AND "opérateur, elle est classée comme False si un False est trouvé dans l'arbre.