informatique (tronc commun des prépas scientifiques) · Chapitre 20 · Exercice de TD
Dossier — concevoir l'IA d'un jeu de plateau
L'étude des jeux : attracteurs et minmax · niveau 3 (difficile)
Énoncé
On étudie le jeu du "Domineering" sur un plateau (le joueur 1 pose des dominos verticaux , 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 . En multipliant par les 2 joueurs au trait, on obtient un espace d'états de 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 .
- Heuristique pour grands plateaux (ex: ) : On évalue la mobilité des joueurs : .