Algorithmes et jeux
Recherche de chemin
Cinq algorithmes de recherche de chemin sur grille, côte à côte, autour […]
HEX
Le jeu de connexion sans match nul, contre une IA dont on peut regarder la recherche. Écrit d’abord en C pour la ligne de commande, puis réécrit en TypeScript pour cette page.
Démo interactive
Chargement de la démo…
Algorithmes
- 01Recherche alpha-bêta →Minimax avec élagage : une branche est abandonnée dès qu’elle ne peut plus changer le meilleur coup, donc l’IA voit plus loin pour le même effort.
- 02Connexion la plus courte (BFS 0-1) →L’évaluation. Pour chaque camp, le nombre de pierres encore nécessaires pour joindre ses deux bords, où ses pierres coûtent 0 et les cases vides 1.
- 03Tri des coups et élagage des candidatsSeules les cases proches des pierres existantes sont essayées, les meilleures d’abord selon l’évaluation, ce qui permet à l’alpha-bêta de couper plus tôt.
Pages d’algorithmes
Chacun a sa propre page : les étapes, le coût et les autres projets où il intervient.
Comment ça marche
- 01HEX est un jeu sans match nul : sur un plateau d’hexagones, un joueur relie les bords du haut et du bas, l’autre ceux de gauche et de droite, et un seul des deux y parvient.
- 02Pour juger une position, l’IA mesure, pour chaque camp, la chaîne la moins chère qui manque encore pour relier ses bords. Vos pierres sont gratuites, les cases vides coûtent 1 et les pierres adverses bloquent : c’est un problème de plus court chemin. Elle préfère les coups qui allongent votre chemin et raccourcissent le sien.
- 03Augmentez la profondeur pour qu’elle anticipe plus loin, et regardez combien de positions elle examine. L’élagage alpha-bêta explique pourquoi ce nombre reste petit.