Arbre de jeu

En théorie des jeux, un arbre de jeu est un arbre (au sens de la théorie des graphes) dont les nœuds sont des positions dans un jeu et dont les arêtes sont des mouvements. L'arbre de jeu complet est l'arbre de jeu commençant à la position initiale et contenant tous les mouvements possibles depuis chaque position. vignette| Les deux premiers de l'arbre de jeu pour le tic-tac-toe. Le diagramme ci-contre montre comment coder dans une représentation arborescente le premier tour de jeu au tic-tac-toe : ce sont les deux premiers niveaux dans l'arborescence, la racine représentant la position initiale (une grille vide, en l'occurrence). Les rotations et les réflexions de la grille sont équivalentes, le premier joueur a donc trois choix de déplacement: au centre, au milieu d'un bord ou dans un coin. Le deuxième joueur a deux choix pour la réponse si le premier joueur a joué au centre, sinon cinq choix, ainsi de suite. Le nombre de feuilles dans l'arbre complet du jeu correspond au nombre de parties différentes possibles de jouer au jeu. Par exemple, l'arborescence du tic-tac-toe comporte feuilles. Les arbres de jeu sont importants dans le domaine de l'intelligence artificielle, car une façon de choisir le meilleur coup dans un jeu est de rechercher dans l'arbre du jeu en utilisant l'un des nombreux algorithmes de parcours d'arbre, combinés à des règles de type minimax pour élaguer l'arbre . Le parcours de l'arbre du tic-tac-toe est relativement simple, mais pour des jeux où le nombre de coups possibles est important, comme aux échecs, l'arbre complet du jeu est beaucoup trop grand pour être parcouru. Pour parer à cela un programme de jeu d'échecs recherche un arbre de jeu partiel: le programme parcourt le plus de niveaux possibles depuis la position actuelle dans le temps dont il dispose. Hormis le cas des arbres de jeu «pathologiques» (qui semblent assez rares en pratique), augmenter la profondeur de recherche (c'est-à-dire le nombre de plis recherchés) améliore généralement les chances de choisir le meilleur coup.