Algorithmes et jeux
Recherche de chemin
Cinq algorithmes de recherche de chemin sur grille, côte à côte, autour […]
Othello
Encadrez et retournez les pions de l’adversaire, 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
- 01Le plateau fait 8 par 8. Les noirs commencent avec deux pions chacun au centre, et jouent toujours en premier.
- 02À votre tour, vous posez un pion sur une case vide de façon à encadrer au moins une ligne droite de pions adverses (en ligne, en colonne ou en diagonale) entre le nouveau pion et un autre des vôtres.
- 03Chaque pion encadré prend votre couleur. Un coup qui ne retourne rien est interdit.
- 04Si vous n’avez aucun coup légal, vous passez. Quand plus personne ne peut jouer, le plus souvent parce que le plateau est plein, celui qui a le plus de pions gagne.
- 05Les coins ne peuvent jamais être retournés, c’est pourquoi les cases voisines sont dangereuses à prendre trop tôt.
Algorithmes
- 01Minimax →O(b^d)
Examine chaque coup légal jusqu’à une profondeur fixe, en supposant que chaque camp choisit ce qui l’arrange le mieux, et remonte les scores dans l’arbre.
Étapes- Générer chaque coup légal et le jouer.
- Recommencer depuis la nouvelle position pour l’autre camp, jusqu’à la profondeur voulue ou la fin de la partie.
- Noter les feuilles avec l’évaluation, puis en remontant prendre le score le plus haut aux tours de l’IA et le plus bas aux vôtres.
- Jouer le coup dont la branche a le meilleur score.
- 02Élagage alpha-bêta →O(b^(d/2)) au mieux
Un minimax qui cesse d’explorer une branche dès qu’elle est prouvée moins bonne qu’une branche déjà trouvée. Il renvoie le même coup, généralement après bien moins de positions.
Étapes- Porter deux bornes dans l’arbre : alpha, le meilleur que l’IA peut déjà garantir, et bêta, le meilleur que vous pouvez déjà garantir.
- Si le score d’une branche dépasse la borne de l’autre camp, personne ne choisirait d’y aller : on ignore ses coups restants.
- Essayer d’abord les coups qui paraissent les meilleurs (coins avant bords) pour que les bornes se resserrent tôt et que davantage de branches soient ignorées.
- 03Recherche arborescente Monte Carlo →O(itérations × longueur de partie)
N’a pas besoin de fonction d’évaluation. Il joue de nombreuses parties aléatoires à partir de chaque coup possible et retient lesquels gagnent.
Étapes- Sélection : descendre dans l’arbre en choisissant l’enfant au meilleur équilibre entre taux de victoire et rareté des essais (UCT).
- Expansion : ajouter un nouveau coup à l’arbre.
- Simulation : finir la partie avec des coups aléatoires.
- Rétropropagation : ajouter le résultat à chaque position du chemin. Recommencer des milliers de fois, puis jouer le coup le plus visité.
- 04Références gloutonne et aléatoireO(b)
Le glouton joue le coup qui paraît le meilleur un pas plus loin ; l’aléatoire joue n’importe quel coup légal. Ils montrent ce que les recherches plus profondes apportent vraiment.
Pages d’algorithmes
Chacun a sa propre page : les étapes, le coût et les autres projets où il intervient.
Comment ça marche
- 01L’IA voit le jeu comme un arbre : chaque coup légal mène à une position, et depuis chacune l’adversaire a ses propres coups. Le menu de l’adversaire change la part de cet arbre qu’elle examine, et la façon de juger ce qu’elle trouve.
- 02À Othello, compter les pions au début ne gagne presque jamais. L’évaluation récompense donc ce qui dure : les coins et les bords, plus la mobilité, c’est-à-dire le nombre de coups que vous avez par rapport à l’adversaire. Le nombre de pions ne compte que vers la fin.
- 03Appuyez sur « Comparer les algorithmes ici » en pleine partie pour lancer les quatre joueurs qui cherchent sur la même position et voir quel coup chacun choisit et combien de positions il lui a fallu.