IA de jeu – minimax et élagage alpha-bêta au morpion

InformatiqueDonnées, IA et apprentissage automatique17–18 ans

Utiliser avec ma classe

Jouez au morpion contre une IA qui explore l'arbre de jeu avec minimax. La vue de l'arbre montre chaque coup envisagé par l'IA, le score que minimax lui a attribué et le nombre de positions situées en dessous ; ouvrez une branche pour suivre la recherche vers le bas. Activez l'élagage alpha-bêta pour voir des branches coupées sans que le coup change, comparez les positions explorées et baissez la limite de profondeur pour que l'IA joue assez mal pour être battue.

Leçon : L'intelligence artificielle dans les jeux : arbres de jeu, minimax, recherche à profondeur limitée, fonctions d'évaluation et élagage alpha-bêta

Ce qu’elle montre

Un programme de jeu peut anticiper : il essaie chaque coup, chaque réponse et ainsi de suite, et construit un arbre de jeu. Minimax note les positions finales (victoire, défaite ou nul) et fait remonter les scores dans l'arbre : le joueur au trait choisit le meilleur score, en supposant que l'adversaire fait de même. Le morpion peut être exploré jusqu'au bout, donc une IA à profondeur complète ne perd jamais. Pas les vrais jeux : les programmes s'arrêtent à une limite de profondeur et estiment la position. L'élagage alpha-bêta saute les branches qui ne changeraient pas le choix et donne le même coup avec bien moins de positions explorées.

Mode d’emploi

Touchez une case pour jouer ; l'IA répond. L'arbre montre les choix de l'IA et leurs scores : touchez-en un pour ouvrir sa branche, puis utilisez ▲ Monter ou ⤒ Haut de l'arbre pour revenir. Cochez Élagage alpha-bêta pour comparer. Baissez Limite de profondeur, ou choisissez Score à la limite de profondeur, pour affaiblir l'IA. Analyser cette position montre vos propres options.

Paramètres modifiables

  • Vous jouez X (premier), O (second)
  • Limite de profondeur (coups d'avance) 1–9
  • Score à la limite de profondeur 0 (inconnu), Lignes ouvertes
  • Élagage alpha-bêta

Questions à explorer

  1. Avec une limite de profondeur de 9, pourquoi l'IA ne perd-elle jamais, quelle que soit votre case de départ ?
  2. Quelles cases l'élagage alpha-bêta coupe-t-il en premier, et pourquoi peut-il les sauter ?
  3. En dessous de quelle limite de profondeur pouvez-vous battre l'IA, et comment avez-vous fait ?