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'il existe un coup
changeant la configuration
en
. 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 :
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 est
donnée par l'entier
. Appelons les deux joueurs
Xavier et Yvette : si Xavier perd
, Yvette perd
,
c'est-à-dire gagne
. Toujours si l'on connaît l'intégralité du
graphe du jeu, on peut étendre
en une fonction
définie pour
toutes les configurations, par les règles suivantes :
La fonction est une évaluation complète du jeu, pour des joueurs
cherchant à maximiser leurs gains et minimiser leurs pertes. La
construction de
se fait donc de façon ascendante, en
remontant à partir des feuilles du graphe : chaque noeud
se trouve
affecté d'un attribut
, qui est
synthétisé, c'est-à-dire calculé de
façon ascendante à partir des attributs
des successeurs
de
.