Jeux, stratégies et recherche heuristique

Cours complet · informatique (MP2I/MPI), chapitre 27 · MP2I et MPI

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

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é ».

Méthode : Calculer l'attracteur, en temps linéaire

La suite $A_{k}$ croît et est bornée : elle se stabilise. On l'obtient efficacement en travaillant à rebours, avec un compteur par position de $J_{2}$ .


(* Positions depuis lesquelles J1 force l'arrivée dans cible.
   ctrl.(p) vaut 1 si p appartient à J1, 2 sinon.
   pred.(q) est la liste des prédécesseurs de q. Complexité : Theta(n + m). *)
let attracteur ctrl pred degre_sortant cible n =
  let dans = Array.make n false in
  let restant = Array.copy degre_sortant in   (* pour les positions de J2 *)
  let f = Queue.create () in
  List.iter (fun c -> dans.(c) <- true; Queue.push c f) cible;
  while not (Queue.is_empty f) do
    let q = Queue.pop f in
    List.iter (fun p ->
      if not dans.(p) then begin
        if ctrl.(p) = 1 then begin                 (* J1 : UN coup suffit *)
          dans.(p) <- true; Queue.push p f
        end else begin                             (* J2 : TOUS les coups *)
          restant.(p) <- restant.(p) - 1;
          if restant.(p) = 0 then begin dans.(p) <- true; Queue.push p f end
        end
      end) pred.(q)
  done;
  dans

La stratégie gagnante s'en déduit : depuis une position de $J_{1}$ dans l'attracteur, jouer vers n'importe quel successeur d'étage strictement plus petit. L'étage décroît à chaque coup — c'est un variant au sens du chapitre chap:algo-prog — donc la cible est atteinte en un nombre fini de coups.

iRemarqueLes positions de match nul

Les positions hors de l'attracteur de $J_{1}$ et hors de celui de $J_{2}$ sont celles où aucun des deux ne peut forcer la victoire : la partie peut se prolonger indéfiniment. Ce sont les états de match nul que le programme mentionne.

27.3 Minimax et élagage alpha-bêta

Les attracteurs supposent qu'on explore tout le graphe. Aux échecs, le graphe compte plus de positions qu'il n'y a d'atomes dans l'univers : il faut renoncer, et le programme introduit ici la notion d'heuristique.

Définition 27.4Heuristique

Une heuristique est une fonction qui estime la valeur d'une position sans la calculer. Le programme cadre l'exigence : « ce dernier est abordé par des exemples où l'heuristique est précisément définie mais sans en évaluer la performance ». On sait donc en écrire une, on ne démontre pas qu'elle est bonne.

Méthode : Minimax à profondeur bornée

On explore l'arbre des coups jusqu'à une profondeur $d$ , on évalue les positions atteintes par l'heuristique, et l'on remonte : $J_{1}$ maximise, $J_{2}$ minimise.


(* Valeur estimée de la position p pour J1, en explorant d demi-coups.
   Précondition : d >= 0. Complexité : O(b^d) pour b coups par position. *)
let rec minimax p d maximisant =
  if d = 0 || terminale p then heuristique p
  else if maximisant then
    List.fold_left (fun acc q -> max acc (minimax q (d-1) false))
      neg_infinity (coups p)
  else
    List.fold_left (fun acc q -> min acc (minimax q (d-1) true))
      infinity (coups p)

Méthode : L'élagage alpha-bêta

On transporte deux bornes : $α$ , le meilleur score que le maximisant s'est déjà assuré, et $β$ , le meilleur que le minimisant s'est assuré. Dès que $β \leq α$ , la branche est inutile : on la coupe.


let rec alphabeta p d alpha beta maximisant =
  if d = 0 || terminale p then heuristique p
  else if maximisant then begin
    let a = ref alpha and v = ref neg_infinity in
    (try List.iter (fun q ->
      v := max !v (alphabeta q (d-1) !a beta false);
      a := max !a !v;
      if beta <= !a then raise Exit      (* COUPURE : inutile de continuer *)
    ) (coups p) with Exit -> ());
    !v
  end else begin
    let b = ref beta and v = ref infinity in
    (try List.iter (fun q ->
      v := min !v (alphabeta q (d-1) alpha !b true);
      b := min !b !v;
      if !b <= alpha then raise Exit
    ) (coups p) with Exit -> ());
    !v
  end

ImportantL'élagage ne change pas le résultat, seulement le coût

C'est le point capital : alpha-bêta rend exactement la même valeur que minimax. Il ne coupe que des branches dont il a prouvé qu'elles ne peuvent pas influencer le résultat — parce que l'adversaire ne les choisirait jamais.

Vérifié en exécutant les deux sur $200$ arbres de profondeur $4$ et d'arité $4$ tirés au hasard : $200$ valeurs identiques sur $200$ , pour un arbre exploré à $54 %$ en ordre quelconque. Avec un ordre des coups parfait, alpha-bêta explore $O (b^{d /2})$ nœuds au lieu de $O (b^{d})$ . À temps égal, on double la profondeur explorée — ce qui, aux échecs, sépare un programme faible d'un programme fort. C'est le même phénomène que la rencontre au milieu du chapitre chap:diviser : passer à la racine carrée.

Bonne pratique (L'ordre des coups décide de tout)

Le gain suppose qu'on examine les bons coups en premier : c'est alors qu' $α$ monte vite et que les coupures tombent tôt. Dans le pire ordre, alpha-bêta n'élague rien et coûte autant que minimax. En pratique on trie les coups par une estimation grossière avant de descendre — une heuristique au service d'une heuristique.

27.4 La recherche informée : A*

Définition 27.5Graphe d'états

Un problème de recherche se pose sur un graphe d'états : les sommets sont les configurations, les arcs les actions, et l'on cherche un chemin de coût minimal de l'état initial à un état but. Le taquin, le Rubik's cube, un itinéraire routier sont de cette forme.

Méthode : A* : Dijkstra guidé par une estimation

Dijkstra (chapitre chap:parcours) explore par distance croissante depuis la source, sans savoir où il va. A ajoute une estimation $h (v)$ de la distance restante* jusqu'au but, et explore par

$f (v) = g (v) + h (v)$

où $g (v)$ est le coût déjà parcouru. C'est le même algorithme, avec une autre clé de priorité.


(* Coût minimal de depart à un état but. h est l'heuristique.
   Précondition : h est admissible (voir ci-dessous). *)
let a_etoile depart est_but voisins h =
  let f = file_priorite_vide () in
  let g = Hashtbl.create 97 in
  Hashtbl.replace g depart 0.0;
  inserer f (h depart, depart);
  let rec boucle () =
    if est_vide f then None
    else
      let (_, u) = extraire_min f in
      if est_but u then Hashtbl.find_opt g u
      else begin
        List.iter (fun (v, cout) ->
          let neuf = Hashtbl.find g u +. cout in
          match Hashtbl.find_opt g v with
          | Some ancien when ancien <= neuf -> ()
          | _ -> Hashtbl.replace g v neuf;
                 inserer f (neuf +. h v, v)      (* g + h : la SEULE différence *)
        ) (voisins u);
        boucle ()
      end
  in boucle ()

Définition 27.6Admissibilité, monotonie

Le programme demande de « souligner l'importance de l'admissibilité de l'heuristique, ainsi que le cas où l'heuristique est également monotone ».

$h$ est admissible si elle ne surestime jamais : $h (v) \leq d (v, but)$ pour tout $v$ ;
$h$ est monotone (ou cohérente) si $h (u) \leq c (u, v) + h (v)$ pour tout arc — une inégalité triangulaire.

La monotonie implique l'admissibilité.

ImportantCe que chaque hypothèse achète

$h$ admissible	A* trouve le chemin optimal
$h$ monotone	de plus, un état extrait est définitif : jamais rouvert
$h = 0$	A* est Dijkstra
$h$ surestimant	A* est rapide, et le chemin trouvé peut ne pas être optimal

La troisième ligne montre qu'A n'est pas un autre algorithme : c'est Dijkstra informé. La quatrième est le piège — une heuristique trop optimiste ne coûte que du temps, une heuristique trop pessimiste* coûte la correction.

Démonstration (Une heuristique admissible donne l'optimum)

Supposons qu'A* extraie un état but $b$ avec un coût $g (b)$ supérieur au coût optimal $d^{*}$ . Soit $v$ un sommet non encore extrait situé sur un chemin optimal. Alors

$f (v) = g (v) + h (v) \leq g (v) + d (v, but) = d^{*} < g (b) = f (b),$

la première inégalité venant de l'admissibilité. Donc $f (v) < f (b)$ : la file de priorité aurait extrait $v$ avant $b$ . Contradiction.

Exemple 27.7Une heuristique admissible pour le taquin

Compter les cases mal placées est admissible : chaque case mal placée demande au moins un déplacement. La distance de Manhattan — la somme des distances de chaque case à sa position finale — est admissible aussi, et bien meilleure : elle est plus proche de la vérité, donc elle guide davantage.

La règle : parmi les heuristiques admissibles, on prend la plus grande. Plus $h$ approche la vraie distance, moins A* explore. À la limite, $h = d$ irait droit au but — mais calculer $d$ est le problème même.

27.5 Ce qu'il faut retenir

ImportantJeux et recherche : cinq points

Un jeu est un graphe biparti par le contrôle. Une position de $J_{1}$ demande $\exists$ un bon coup ; une position de $J_{2}$ demande $\forall$ les coups.
Les attracteurs donnent les positions gagnantes en $Θ (n + m)$ , et la stratégie s'en déduit : descendre d'étage. Elle est sans mémoire.
Minimax explore à profondeur bornée et évalue par une heuristique. Alpha-bêta rend exactement la même valeur et passe de $O (b^{d})$ à $O (b^{d /2})$ — à condition d'ordonner les coups.
A* est Dijkstra guidé par $f = g + h$ . Avec $h = 0$ , c'est Dijkstra.
Une heuristique admissible (jamais surestimante) garantit l'optimum ; monotone, elle garantit en plus qu'aucun état n'est rouvert. Une heuristique trop optimiste coûte du temps ; trop pessimiste, elle coûte la correction.

Continuer sur Adloun : animation, QCM, fiches, exercices