Graphes de jeu

Certains jeux (échecs, Othello, Awélé) peuvent être décrits à l'aide d'un graphe dont les sommets sont les configurations possibles (positions des pièces, etc) du jeu et les arcs sont les coups permis par les règles du jeu ; on notera $s\to s'$ s'il existe un coup changeant la configuration $s$ en $s'$. On s'intéressera aux jeux à deux joueurs à information complète : on suppose qu'ils jouent à tour de rôle, que chacun connaît la configuration du jeu et que le hasard n'intervient pas.

Une configuration est finale si aucun coup n'est permis à partir de celle-ci. Dans un certain nombre de jeux, une configuration finale est perdante pour le joueur qui s'y trouve. Si l'on connaît l'intégralité du graphe du jeu, on peut décider de proche en proche, à partir des configurations finales, si une configuration est gagnante ou perdante, en appliquant les deux règles suivantes :

• une configuration est gagnante s'il existe un coup menant à une configuration perdante,
• une configuration est perdante si tout coup mène à une configuration gagnante.

Un jeu est à somme nulle si les gains d'un joueur représentent exactement les pertes de l'autre joueur. Supposons maintenant que la perte du joueur qui se trouve dans la configuration finale $s$ est donnée par l'entier $p_f(s)\in \mathbf{Z}$. Appelons les deux joueurs Xavier et Yvette : si Xavier perd $p_f(s)$, Yvette perd $-p_f(s)$, c'est-à-dire gagne $p_f(s)$. Toujours si l'on connaît l'intégralité du graphe du jeu, on peut étendre $p_f$ en une fonction $p$ définie pour toutes les configurations, par les règles suivantes :

• si $s$ est une configuration finale, $p(s)=p_f(s)$,
• si $s$ est une configuration gagnante, $p(s)=\max_{s\to s'\ \mathrm{perdante}}p(s')$,
• si $s$ est une configuration perdante, $p(s)=\min_{s\to s'\ \mathrm{gagnante}}p(s')$.

La fonction $p$ est une évaluation complète du jeu, pour des joueurs cherchant à maximiser leurs gains et minimiser leurs pertes. La construction de $p$ se fait donc de façon ascendante, en remontant à partir des feuilles du graphe : chaque noeud $s$ se trouve affecté d'un attribut $p(s)$, qui est synthétisé, c'est-à-dire calculé de façon ascendante à partir des attributs $p(s')$ des successeurs $s'$ de $s$.