Comment des pandas qui ne voient presque rien apprennent à sortir d'un labyrinthe en un minimum d'actions : les règles, les capteurs, la fitness, l'entraînement en Python et la version qui évolue en direct dans votre navigateur.
Le labyrinthe est une grille de cases (10 × 10 par défaut). Le panda part de la case en haut à gauche, tourné vers l'est. La sortie est une ouverture dans le mur est de la case en bas à droite.
À chaque pas, il choisit une seule action parmi trois : avancer d'une case, tourner à gauche ou tourner à droite sur place. Tourner compte autant qu'avancer : le score se mesure en actions, et le but est d'en faire le moins possible.
Avancer dans un mur ne fait rien, mais coûte une action. La partie s'arrête quand le panda sort, après 4 × taille² actions (400 pour un 10 × 10), ou s'il repasse plus de 4 fois sur la même case avec la même orientation : il tourne en rond.
Les labyrinthes sont « parfaits » : un seul chemin relie deux cases, sans boucle. On les creuse par exploration en profondeur (recursive backtracker) : depuis la case courante, on perce un mur vers un voisin pas encore visité, choisi au hasard. Quand il n'y en a plus, on revient en arrière.
Le hasard est piloté par une graine : la même graine donne toujours le même labyrinthe. C'est ce qui permet d'entraîner sur les graines 1 à 20 et de tester sur d'autres que le panda n'a jamais vues.
vues = {(0, 0)}
pile = [(0, 0)]
while pile:
x, y = pile[-1]
voisins = [(d, x + DX[d], y + DY[d]) for d in range(4)
if ... and (x + DX[d], y + DY[d]) not in vues]
if not voisins:
pile.pop() # cul-de-sac : on revient en arrière
continue
d, nx, ny = rng.choice(voisins)
self.murs[y][x][d] = False # on perce le mur des deux côtés
self.murs[ny][nx][(d + 2) % 4] = False
vues.add((nx, ny))
pile.append((nx, ny))Deux parcours en largeur préparent ensuite le terrain. Le premier calcule la distance de chaque case à la sortie : elle sert à noter les pandas qui ne sortent pas. Le second explore les couples (case, orientation) pour trouver le nombre minimal d'actions, virages compris. C'est la référence affichée partout : « minimum : 93 actions ».
Le panda n'a pas le plan. À chaque pas, son réseau de neurones reçoit 8 nombres :
Le vecteur vers la sortie, projeté sur l'axe du regard et sur l'axe de droite, divisé par la taille du labyrinthe.
Les entrées 4 à 6 sont la seule mémoire du panda : il sait ce qu'il vient de faire, rien de plus. Elles suffisent pour une règle classique, « suivre le mur de gauche » : si rien à gauche et que je ne viens pas de tourner, je tourne à gauche ; sinon j'avance si je peux ; sinon je tourne à droite. Cette règle sort de tout labyrinthe parfait.
devant = vx * DX[d] + vy * DY[d] # projection sur l'axe du regard
cote = vx * DX[droite] + vy * DY[droite] # projection sur l'axe de droite
return [
float(lab.mur(x, y, d)), float(lab.mur(x, y, gauche)), float(lab.mur(x, y, droite)),
float(derniere == 0), float(derniere == 1), float(derniere == 2),
devant / lab.taille, cote / lab.taille,
]Le réseau rend 3 valeurs, une par action. Contrairement au premier jeu, le panda ne fait qu'une chose à la fois : on prend la plus forte (argmax).
for pas in range(1, PAS_MAX + 1):
sortie = net.activate(capteurs(lab, x, y, d, derniere))
action = int(np.argmax(sortie))
if action == 0:
if not lab.mur(x, y, d):
if (x, y) == lab.sortie and d == 1:
return 1 + (1 - pas / PAS_MAX) # sorti !
x, y = x + DX[d], y + DY[d]
meilleureDist = min(meilleureDist, lab.distances[(x, y)])
elif action == 1:
d = (d + 3) % 4 # tourner à gauche
else:
d = (d + 1) % 4 # tourner à droite| Résultat | Python (par labyrinthe) | Navigateur |
|---|---|---|
| Sorti en n actions | 1 + (1 − n / 400) | 1 + minimum / n |
| Pas sorti | 0,99 × (1 − distance la plus courte atteinte / distance au départ) | |
Sortir rapporte toujours plus que ne pas sortir. Entre deux pandas sortis, le plus rapide gagne. Entre deux pandas bloqués, celui qui s'est le plus approché de la sortie gagne : c'est ce qui permet à l'évolution de progresser avant la toute première sortie.
En Python, la fitness est la somme sur les 20 labyrinthes d'entraînement (maximum 40). Dans le navigateur, on n'entraîne que sur le labyrinthe affiché, avec une formule qui vaut exactement 2 au nombre minimal d'actions : l'évolution s'arrête d'elle-même quand elle l'atteint.
labyrinthe.py fait évoluer 60 pandas pendant 150 générations, chacun jouant les 20 mêmes labyrinthes d'entraînement. La simulation ne dessine rien : une génération prend environ 0,7 seconde.
| Moment | Ce que fait le meilleur panda |
|---|---|
| Génération 14 | Sort des 20 labyrinthes : il a trouvé une façon de suivre les murs. Sûr, mais lent. |
| Génération 44 | Fonce vers la sortie grâce à la boussole : presque le minimum d'actions, mais reste bloqué dans 1 labyrinthe sur 20. |
| Fin | 19 labyrinthes d'entraînement sur 20 ; 17 sur 20 jamais vus, en 1,00 fois le minimum d'actions en moyenne. |
Pourquoi pas 20 sur 20 et rapide ? Sans vraie mémoire, le panda ne peut pas savoir qu'il est déjà passé par un cul-de-sac. Suivre la boussole est rapide mais peut boucler ; suivre un mur est sûr mais fait des détours. La fitness récompense assez la vitesse pour que NEAT accepte un échec en échange. L'option --memoire essaie un réseau récurrent, qui garde un état d'un pas à l'autre.
Les 17 sur 20 jamais vus montrent qu'il n'a pas appris des plans par cœur. Avec seulement 5 labyrinthes d'entraînement (premier essai), il les réussissait tous mais échouait sur ceux qu'il ne connaissait pas.
Avec --export-web, chaque partie de chaque génération est enregistrée sous forme d'une suite de lettres (A avancer, G gauche, D droite). La page rejoue ces lettres sur le plan : 150 générations × 60 pandas × 3 labyrinthes tiennent en 2 Mo. Le champion final est exporté avec ses poids et ses biais, pour être rejoué à l'identique dans le navigateur (« Essayer le champion »).
.venv/bin/pip install -r requirements.txt
python labyrinthe.py # 300 générations, bilan sur 20 labyrinthes jamais vus
python labyrinthe.py --generations 150 --graine 1 --export-web # régénère les données de la démo
python labyrinthe.py --memoire # essai avec un réseau récurrent
./deploy.sh # publie les pages sur rdv-app.fr