Le tournoi des profondeurs

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 20 — L'étude des jeux : attracteurs et minmax

Énoncé

Pour le jeu de la course à 21 (celui qui annonce 21 gagne, prise de 1 à 3), on définit l'heuristique volontairement simpliste $h (t) = t /21$ . Faire s'affronter des agents Minimax de profondeurs $1$ , $2$ et $4$ . Expliquer comment la profondeur d'exploration compense la simplicité de l'heuristique.

Corrigé

Agent P1 (profondeur 1) : Il cherche à maximiser la valeur immédiate de $h$ , ce qui le pousse à jouer systématiquement $+ 3$ pour augmenter le total le plus vite possible. C'est un jeu naïf.
Agent P2 (profondeur 2) : Il anticipe la réplique immédiate de l'adversaire. Il bat facilement P1 en identifiant les fins de partie à portée de main.
Agent P4 (profondeur 4) : Il calcule les états sur 4 coups d'avance. Dès que le total atteint $13$ ou plus, l'horizon d'exploration de P4 lui permet d'atteindre la fin de la partie (état final à 21) ou une position perdante pour l'adversaire. P4 joue alors de manière parfaitement exacte. La profondeur compense l'imprécision de la fonction heuristique en rapprochant la frontière d'évaluation des états terminaux réels dont la valeur ( $\pm 1, 0$ ) est exacte et incontestable.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.