Probleme – Le morpion, résolu

Exercice · niveau 3 (difficile) · informatique (MP2I/MPI), chapitre 27 — Jeux, stratégies et recherche heuristique

Énoncé

On résout complètement le morpion $3 \times 3$ par minimax exhaustif : pas d'heuristique, pas de profondeur bornée, on descend jusqu'aux positions terminales, valuées $+ 1$ (victoire de $X$ ), $0$ (nul) ou $- 1$ (victoire de $O$ ).

Quelle est la valeur de la position initiale ?
Combien de nœuds minimax visite-t-il ? Et alpha-bêta ?
Quelle est la valeur de chacun des neuf premiers coups ?
$X$ ouvre au centre. Quelles réponses de $O$ perdent la partie ?

Corrigé

1. La valeur est $0$ : le morpion est nul quand les deux joueurs jouent parfaitement. C'est le troisième type d'état du programme, et il apparaît ici à la racine.

2. Le compte, mesuré.

	nœuds visités	part
minimax exhaustif	$549946$	$100 %$
alpha-bêta, cases dans l'ordre $0, \dots, 8$	$18297$	$3, 33 %$
alpha-bêta, centre puis coins puis côtés	$7275$	$1, 32 %$

Les trois rendent la valeur $0$ . Alpha-bêta divise le travail par $30$ , et un bon ordre le divise encore par $2, 5$ — soit $75$ fois moins de nœuds que minimax, sur exactement le même jeu et avec exactement le même résultat.

Noter que $549946$ n'est pas $9! = 362880$ : les parties s'arrêtent dès qu'un alignement est formé, et l'on compte tous les nœuds de l'arbre, pas seulement les feuilles. Ce nombre est celui de l'arbre des parties, positions répétées comprises — deux ordres de coups menant à la même grille sont deux nœuds distincts. Une table de transposition les fusionnerait et ferait tomber le compte à quelques milliers.

3. Les neuf premiers coups. Mesuré : les neuf valent $0$ . Aucun premier coup ne gagne, aucun ne perd. Le centre n'a donc pas d'avantage théorique — c'est un résultat que l'intuition dément, et il faut le mesurer pour l'accepter. Ce que le centre apporte est ailleurs : il laisse à l'adversaire moins de réponses correctes, donc plus d'occasions de se tromper. La valeur minimax suppose l'adversaire parfait ; elle ne dit rien du risque.

4. Après $X$ au centre. Mesuré :

réponse de $O$	valeur	conclusion
un coin ( $0, 2, 6, 8$ )	$0$	nul
un côté ( $1, 3, 5, 7$ )	$+ 1$	$X$ gagne

Une seule règle à retenir, et elle est exacte : contre une ouverture au centre, $O$ doit jouer un coin. Les quatre côtés perdent, tous les quatre.

Ce que ce problème illustre du chapitre. Le morpion est le plus petit jeu où tout le mécanisme est visible : les trois types d'états y coexistent, minimax y est exhaustif donc exact, l'élagage y divise le coût par $30$ sans changer une valeur, et l'ordre des coups le divise encore. Il montre aussi la frontière : $549946$ nœuds tiennent en une seconde, mais le même calcul sur le puissance $4$ ( $4, 5 \times 1 0^{12}$ positions légales) n'a été mené à bien qu'en $1988$ , au prix d'un effort considérable, et aux échecs il reste hors d'atteinte. C'est exactement là que l'heuristique devient nécessaire, et le cours en fait le pivot du chapitre.

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.