Modéliser la course à 10

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

Énoncé

Décrire formellement l'arène du jeu de la course à 10. Déterminer à la main les positions gagnantes en remontant depuis 10 et en déduire l'issue de la partie en jeu parfait.

Corrigé

Sommets : Les états sont $S_{1} = {(t, J_{1})}$ et $S_{2} = {(t, J_{2})}$ pour la valeur courante $t \in [0, 9]$ . Les états finals sont $(10, J_{2}) \in F_{1}$ (gagné par $J_{1}$ ) et $(10, J_{1}) \in F_{2}$ (gagné par $J_{2}$ ).
Coups : Arcs de la forme $(t, J) \to (t + 1, autre)$ et $(t, J) \to (t + 2, autre)$ .
Raisonnement à rebours :
Depuis $9$ ou $8$ , le joueur au trait peut jouer vers $10$ et gagner. Les positions $9$ et $8$ sont gagnantes pour le joueur au trait.
Depuis $7$ , tout coup joué mène à $8$ ou $9$ , offrant une position gagnante à l'adversaire. La position $7$ est donc perdante pour le joueur au trait.
De proche en proche, on identifie les positions perdantes pour le joueur au trait : ${7, 4, 1}$ . Les autres positions ${9, 8, 6, 5, 3, 2, 0}$ sont gagnantes pour le joueur au trait.
Verdict : Le total initial étant $0$ , la position $(0, J_{1})$ est gagnante pour le premier joueur. La stratégie gagnante de $J_{1}$ consiste à jouer $+ 1$ au premier coup pour atteindre $1$ , puis à compléter le coup de l'adversaire pour atteindre successivement $4$ , $7$ et enfin $10$ (en jouant $3 - p$ si l'adversaire joue $p$ ).

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.