Algorithmes
Les idées derrière les jeux et les recherches de ce site, une page chacune : ce qu’elles font, comment elles fonctionnent pas à pas, ce qu’elles coûtent et où elles sont utilisées.
Des recherches pour les jeux à deux : regarder les coups, les réponses, les réponses à ces réponses, et décider quelle part de cet arbre vaut le temps passé.
Minimax
Regarde toutes les réponses jusqu’à une profondeur fixe, en supposant que chaque camp joue au mieux, et remonte les scores dans l’arbre pour choisir un coup.
Lire l’algorithme→Élagage alpha-bêta
Un minimax qui cesse d’explorer une branche dès qu’il est prouvé qu’elle ne vaut pas mieux qu’une branche déjà trouvée. Le même coup, après bien moins de positions.
Lire l’algorithme→Recherche arborescente Monte Carlo
Joue des milliers de parties aléatoires à partir de chaque coup possible et favorise ceux qui ont le plus gagné, en développant l’arbre là où les résultats semblent prometteurs.
Lire l’algorithme→Références gloutonne et aléatoire
Deux joueurs triviaux : l’un joue n’importe quel coup légal, l’autre le coup qui semble le meilleur tout de suite. Tout vrai algorithme doit les battre.
Lire l’algorithme→Des recherches sur une carte ou un graphe : d’ici à là, par le moins de pas ou le moindre coût, en regardant le moins de cases possible.
Parcours en largeur
Explore la grille en anneaux autour du départ, le plus proche d’abord. Il trouve le chemin qui a le moins de pas.
Lire l’algorithme→Parcours en profondeur
Suit un chemin aussi loin que possible avant de reculer. Il trouve un chemin vite, mais pas forcément court.
Lire l’algorithme→Algorithme de Dijkstra
Développe toujours la case la moins chère à atteindre jusqu’ici, donc il trouve le chemin le moins cher même quand les pas coûtent des montants différents.
Lire l’algorithme→Recherche gloutonne (meilleur d’abord)
Développe toujours la case qui semble la plus proche du but. Rapide en terrain dégagé, mais il peut renvoyer un long chemin.
Lire l’algorithme→A*
Ordonne la frontière par le coût déjà payé plus une estimation de ce qui reste, donc il fonce vers le but comme la recherche gloutonne tout en trouvant le chemin le moins cher.
Lire l’algorithme→Parcours en largeur 0-1
Une recherche de plus court chemin pour les graphes dont les pas coûtent 0 ou 1, avec une liste par coût au lieu d’un tas. HEX l’utilise pour compter les pierres qu’il reste à poser à un joueur.
Lire l’algorithme→