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 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 :
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 . Appelons les deux joueurs
Xavier et Yvette : si Xavier perd pf(s), Yvette perd -pf(s),
c'est-à-dire gagne pf(s). Toujours si l'on connaît l'intégralité du
graphe du jeu, on peut étendre pf en une fonction p définie pour
toutes les configurations, par les règles suivantes :
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.