Première descente minimax

L'étude des jeux : attracteurs et minmax · niveau 2

É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. Il reste à $\circ$ trois lignes gagnables (1-4-7, 7-8-9, 3-6-9) : la note est $5 - 3 = 2$ .
Coup C (jouer un coin adjacent 3) : Même note de $3$ .
Analyse : À la profondeur 1, le minimax écarte le coup B mais ne parvient pas à départager les coups A et C 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) tend un piège (si $\circ$ répond sur un bord, $\times$ obtient une double menace), ce qui en fait un coup supérieur.

Énoncé

Corrigé

Exercices semblables