Jeux, stratégies et recherche heuristique

Cours · informatique (MP2I/MPI), chapitre 27 · MP2I et MPI · le début du chapitre, la suite sur Adloun

L'algorithme minmax : un joueur maximise la valeur, l'adversaire la minimise, de bas en haut de l'arbre de jeu.

27.1 Deux joueurs, un graphe

Un jeu à deux joueurs se modélise par un graphe : les sommets sont les positions, les arcs les coups. Ce qui distingue un jeu d'un simple graphe est que les sommets se partagent en deux : ceux où c'est à $J_{1}$ de jouer, ceux où c'est à $J_{2}$ . Le graphe est donc biparti au sens du contrôle, sinon des arêtes — et le programme le dit ainsi : « on considère des jeux à deux joueurs ( $J_{1}$ et $J_{2}$ ) modélisés par des graphes bipartis ».

Définition 27.1Jeu d'accessibilité

Un jeu d'accessibilité se joue sur un graphe orienté dont les sommets sont partagés en $S_{1}$ (contrôlés par $J_{1}$ ) et $S_{2}$ (contrôlés par $J_{2}$ ). Un jeton part d'une position initiale ; le joueur qui contrôle la position courante choisit l'arc à suivre. $J_{1}$ gagne s'il atteint un ensemble de positions cibles.

Le programme distingue « trois types d'états : les états gagnants pour $J_{1}$ , les états gagnants pour $J_{2}$ et les états de match nul ».

Définition 27.2Stratégie

Une stratégie pour $J_{1}$ est une fonction qui, à chaque position de $S_{1}$ , associe un coup. Elle est gagnante depuis $p$ si, quels que soient les coups de $J_{2}$ , la partie qui en résulte est gagnée par $J_{1}$ . Une position est gagnante pour un joueur s'il y possède une stratégie gagnante.

Le programme précise : « on ne considère que les stratégies sans mémoire » — le coup ne dépend que de la position courante, jamais de l'histoire de la partie.

ImportantPourquoi les stratégies sans mémoire suffisent

C'est un fait remarquable, et il justifie la restriction du programme : dans un jeu d'accessibilité, si un joueur a une stratégie gagnante, il en a une sans mémoire. Le calcul des attracteurs le montre par construction — il produit, position par position, un coup qui ne regarde rien d'autre.

Cela signifie qu'une stratégie gagnante se range dans un simple tableau indexé par les positions, et non dans un arbre d'historiques.

27.2 Les attracteurs

Définition 27.3Attracteur

L'attracteur de $J_{1}$ vers un ensemble cible $C$ est l'ensemble des positions depuis lesquelles $J_{1}$ peut forcer l'arrivée dans $C$ . On le calcule par étages :

$A_{0} = C, A_{k + 1} = A_{k} \cup {p \in S_{1} : \exists p \to q, q \in A_{k}} \cup {p \in S_{2} : \forall p \to q, q \in A_{k}} .$

ImportantLa dissymétrie entre

\exists

\forall

est tout le jeu

Sur une position que $J_{1}$ contrôle, il lui suffit d'un bon coup : c'est le $\exists$ . Sur une position que $J_{2}$ contrôle, tous les coups doivent mener au but, puisque $J_{2}$ choisira le pire pour $J_{1}$ : c'est le $\forall$ .

Ces deux quantificateurs sont exactement ceux du chapitre chap:logique, et ils portent ici toute la différence entre « je peux » et « je suis forcé ».

Exercices du chapitre

Le jeu des allumettes corrigé
Le cul-de-sac de $J_{2}$ corrigé
Les feuilles qu'alpha-bêta ne regarde pas corrigé
L'effet d'horizon corrigé
Une heuristique qui surestime corrigé
Admissible et pourtant non monotone corrigé

La suite du cours · Tous les exercices du chapitre