Première descente minimax

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

Énoncé

Soit une partie de morpion où $J_{1}$ ( $\times$ ) a joué au centre et $J_{2}$ ( $\circ$ ) a joué dans un coin. On utilise l'heuristique : $h = (lignes gagnables par \times) - (lignes gagnables par \circ)$ . Évaluer la valeur minimax des différents coups de $J_{1}$ à une profondeur d'exploration de $1$ . Montrer les limites de cette faible profondeur.

Corrigé

Considérons la grille avec $\times$ au centre (case 5) et $\circ$ au coin supérieur gauche (case 1).

Coup A (jouer le coin opposé 9) : $\times$ contrôle les cases 5 et 9. Il y a 5 lignes gagnables pour $\times$ (les lignes ne contenant pas de $\circ$ ). Pour $\circ$ , il reste 2 lignes gagnables. La note de l'état est $5 - 2 = 3$ .
Coup B (jouer un bord adjacent 2) : $\times$ contrôle 5 et 2. Les calculs de lignes gagnables donnent également une note de $3$ .
Coup C (jouer un coin adjacent 3) : Même note de $3$ .
Analyse : À la profondeur 1, le minimax ne parvient pas à départager ces coups car l'heuristique évalue la situation de manière purement statique et immédiate. Une profondeur de $2$ ou plus est indispensable pour anticiper les coups de réponse de l'adversaire et identifier que jouer le coin opposé (case 9) crée une double menace gagnante sur les diagonales, ce qui en fait un coup supérieur.

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.