Algorithmes et jeux
Recherche de chemin
Cinq algorithmes de recherche de chemin sur grille, côte à côte, autour […]
Puissance 4
Lâchez des jetons et alignez-en quatre, face à une IA que vous pouvez régler sur minimax, alpha-bêta, recherche arborescente Monte Carlo ou sur des joueurs plus simples. Écrit d’abord en Python, puis réécrit en TypeScript pour cette page.
Démo interactive
La première version de ce jeu et de son IA a été écrite en Python. Python ne s’exécute pas dans un navigateur : le plateau jouable ici est une réécriture en TypeScript des mêmes idées. Choisissez l’un des cinq adversaires ci-dessous.
Règles
- 01La grille compte 7 colonnes et 6 lignes, et se tient debout. Deux joueurs jouent chacun leur tour, le premier joueur commence.
- 02À votre tour, vous choisissez une colonne et y lâchez un jeton. Il tombe dans la case vide la plus basse de cette colonne. Une colonne pleine ne peut pas être choisie.
- 03Le premier joueur à aligner quatre de ses jetons, en ligne, en colonne ou sur l’une des deux diagonales, gagne tout de suite.
- 04Si les 42 cases sont remplies sans alignement de quatre, la partie est nulle.
- 05Avec un jeu parfait des deux côtés, celui qui commence peut toujours gagner, mais seulement en commençant par la colonne centrale.
Algorithmes
- 01Minimax →O(7^d)
Déroule toutes les suites de coups jusqu’à une profondeur choisie, en supposant que vous répondez toujours au mieux, et choisit le premier coup de la meilleure suite.
Étapes- Essayer chacune des sept colonnes au maximum pour l’IA.
- Depuis chaque résultat essayer les sept colonnes pour vous, et ainsi de suite jusqu’à la profondeur choisie.
- Un alignement de quatre rapporte un score énorme à celui qui le fait, et plus tôt vaut mieux que plus tard. Les autres feuilles reçoivent l’évaluation par comptage de lignes.
- Remonter les scores dans l’arbre, en maximisant aux tours de l’IA et en minimisant aux vôtres.
- 02Élagage alpha-bêta →O(7^(d/2)) au mieux
La même recherche avec deux bornes mises à jour au fil du calcul, pour ne jamais explorer les branches sans espoir. Essayer la colonne centrale en premier fait venir les coupes plus tôt.
Étapes- Garder alpha (ce que l’IA est déjà sûre d’obtenir) et bêta (ce à quoi vous êtes déjà sûr de la limiter).
- Dès qu’alpha atteint bêta, le reste de cette branche ne peut plus changer la décision : on arrête.
- Ordonner les colonnes 4, 3, 5, 2, 6, 1, 7 pour essayer d’abord les coups les plus forts.
- 03Recherche arborescente Monte Carlo →O(itérations × longueur de partie)
Juge une colonne selon la fréquence à laquelle des parties aléatoires qui commencent par elle se terminent par une victoire, en concentrant les parties sur les colonnes prometteuses à mesure qu’elle apprend.
Étapes- Sélectionner un chemin dans l’arbre avec UCT, qui équilibre l’exploitation des bonnes colonnes et l’exploration des colonnes peu essayées.
- Étendre avec une colonne non essayée, puis finir la partie avec des coups aléatoires.
- Ajouter le résultat (victoire, nul ou défaite) à chaque position du chemin.
- Après le nombre de parties choisi, jouer la colonne la plus visitée.
- 04Références gloutonne et aléatoireO(7)
Le glouton choisit la colonne dont la position obtenue est la mieux notée tout de suite ; l’aléatoire lâche n’importe où. Les battre est le minimum pour une vraie recherche.
Pages d’algorithmes
Chacun a sa propre page : les étapes, le coût et les autres projets où il intervient.
Comment ça marche
- 01Puissance 4 offre au plus sept coups par tour : une recherche peut donc voir loin, et le menu de l’adversaire permet de choisir comment elle s’en sert.
- 02Les positions sont jugées en comptant les 69 lignes de quatre possibles. Une ligne que vous seul pouvez encore compléter vaut d’autant plus qu’elle est proche d’être finie, une ligne que seul l’adversaire peut compléter joue contre vous, et la colonne centrale vaut un bonus car elle appartient au plus grand nombre de lignes.
- 03Appuyez sur « Comparer les algorithmes ici » pour lancer les quatre joueurs qui cherchent sur la position actuelle. Le minimax et l’alpha-bêta choisissent la même colonne, mais l’alpha-bêta y arrive en examinant bien moins de positions.