A* : murs sur la grille, frontière qui réfléchit
Dessine un labyrinthe, passe de Dijkstra à A*, et regarde l'ensemble ouvert poursuivre le but jusqu'au plus court chemin.
La semaine dernière, un filtre spam Naive Bayes comptait les mots et lançait les dés. Cette semaine, la machine fait quelque chose de plus vieux et plus tranchant : chercher. Pas d’apprentissage sur données, pas de bavardage ; juste une frontière de possibilités qui grandit jusqu’à un chemin.
A* est le cheval de bataille des cartes de jeux, de la robotique et des puzzles. Tu gardes un ensemble ouvert de cases à revisiter, notées par distance parcourue plus une heuristique vers le but. Avec une sous-estimation sûre (Manhattan sur la grille), le chemin reste le plus court, mais tu visites bien moins de cases qu’en recherche aveugle. Heuristique à zéro : Dijkstra, optimal, patient, un peu gaspilleur. C’est l’IA symbolique classique : états explicites, coûts explicites, un planificateur comme un agent dont le raisonnement est visible.
Comment jouer :
- Labyrinthe crée un plan aléatoire à chaque clic, ou pose des murs (reclique pour enlever).
- Déplace Départ et But avec les puces Modifier.
- Lancer la recherche et observe ouvert vs fermé ; Pas pour une expansion.
- Fais glisser le poids heuristique de 1 (A*) à 0 (Dijkstra) sur le même plan.
Essaie ceci :
- Sur la carte par défaut (départ au centre, but en haut à droite), lance avec heuristique 1,00 : la frontière vise le but ; note les nœuds développés (souvent ~40).
- Sans déplacer les murs, heuristique 0 et relance : l’onde remplit plus la grille ; les nœuds développés montent fort (souvent 100+) et les pas du chemin restent identiques.
- Charge Labyrinthe et compare 1,00 vs 0 : Dijkstra doit développer nettement plus de cases qu’A* (souvent ~1,5×).
- Bloque le but avec des murs : message honnête « pas de chemin ».
Pourquoi c’est important
Deep Blue a gagné aux échecs en cherchant des millions de positions ; les systèmes experts encodaient des planificateurs en règles avant la mode des réseaux. AlphaGo mélange apprentissage et recherche (Monte Carlo), mais l’intuition commence ici : monde en graphe, noter les coups, développer le prometteur. A* est la version polie qui refuse de gaspiller quand une boussole vers le but existe.
Les éditions précédentes ? Perceptron, Markov, morpion, convolution, Q-learning, BPE, gradient, k-means, réseau, attention, bandit, ELIZA, Hopfield ou spam Naive Bayes.