Dossier — concevoir l'IA d'un jeu de plateau

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

Énoncé

On étudie le jeu du "Domineering" sur un plateau $4 \times 4$ (le joueur 1 pose des dominos verticaux $2 \times 1$ , le joueur 2 des dominos horizontaux, le premier bloqué a perdu). Proposer un modèle et analyser la faisabilité d'une résolution exacte.

Corrigé

Modélisation : Un état est défini par le couple (ensemble des cases libres, joueur au trait). Les états finals sont ceux où le joueur au trait ne dispose d'aucun emplacement libre compatible pour poser son domino.
Taille de l'espace d'états : Le nombre maximal de configurations des cases libres est de $2^{16} = 65536$ . En multipliant par les 2 joueurs au trait, on obtient un espace d'états de $131072$ configurations au maximum (en réalité bien moins de positions sont atteignables par des coups légaux). Cet espace étant très petit, une résolution exacte par Minimax mémoïsé est tout à fait réalisable en quelques secondes.
Verdict : Le calcul exact montre que le premier joueur possède une stratégie gagnante sur un plateau $4 \times 4$ .
Heuristique pour grands plateaux (ex: $8 \times 8$ ) : On évalue la mobilité des joueurs : $h = (nombre d’emplacements verticaux libres) - (nombre d’emplacements horizontaux libres)$ .

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.