informatique (tronc commun des prépas scientifiques) · Chapitre 20 · Exercice de TD
Le tournoi des profondeurs
L'étude des jeux : attracteurs et minmax · niveau 3 (difficile)
Énoncé
Pour le jeu de la course à 21 (celui qui annonce 21 gagne, prise de 1 à 3), on définit l'heuristique volontairement simpliste . Faire s'affronter des agents Minimax de profondeurs , et . 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 , ce qui le pousse à jouer systématiquement 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 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 () est exacte et incontestable.