Maze Solver

The Maze Solver demo builds a hedge maze in front of you and asks the genetic algorithm to guide a mouse from its hole in the top-left corner to the cheese in the bottom-right. There is exactly one path from the start to the cheese. The GA does not feel its way along step by step. Instead it evolves a plan: a signpost in every cell of the maze, the whole route decided in advance. Each time the mouse stands on a cell, that cell's signpost picks one of the open exits, so no move is ever wasted on a wall. Most of a signpost's range picks one of the ways forward, but the top part of it means "turn back the way you came". A random plan therefore dithers and doubles back, and a good plan has to learn which way to point at every fork on the route. In a dead end the mouse always turns round. A plan also has a move budget of three times the length of the shortest route, so it can't simply wander until it bumps into the cheese. Because each signpost belongs to one cell, changing one changes one decision and leaves the rest of the route alone, which is what lets the population fix a wrong turn without undoing the others.

The Maze¶

Every run draws a brand new maze. It is a perfect maze, which means there are no loops and no closed-off rooms. Between any two cells there is one and only one path. That makes it a fair, solvable puzzle that still looks different each time. Press Reset and you get a different maze and a fresh population of plans.

How a Run Looks¶

Click Start. Forty candidate plans are scored for each generation. The best one is drawn as the mouse running its route one cell at a time, leaving a trail that shades from blue to orange, and every other plan of the generation moves along with it as a faint line with a dot at its head, so you can see how the population spreads through the maze. Turn off Show all paths next to the Start button to draw only the best plan. The previous best route stays on the canvas as a faint dashed line underneath, so you can see how the new one differs. When a plan reaches the cheese its route glows. What the population has to learn is which branch to take at each fork and not to double back.

With the default settings (an eleven-by-eleven maze) the first plan usually reaches the cheese after a handful to a few dozen generations, not straight away. After that the population keeps shortening the route until it takes the shortest one: compare Plan (moves the best plan takes) with Shortest (moves on the shortest possible route) in the stats bar. In our tests (24 mazes), no random plan reached the cheese, the first one did at generation 14 in a typical run (between 1 and 55), and every run ended on the exact shortest route within the default 120 generations.

When the animation finishes, the platform evolves the population. The fittest plans become parents, their choices are recombined and nudged by mutation, and the next generation arrives a moment later to try again. By default three generations evolve for every one you see animated; the ones in between are scored and fed back without being drawn. The history strip under the canvas keeps the best plan's path from every animated generation so you can scroll back and watch the route reach deeper into the maze.

What Fitness Rewards¶

A plan earns more for getting closer to the exit, measured as how far its closest point still is from the exit through the corridors. Stepping back onto a cell it already visited costs a tiny amount. Reaching the exit is a big jump up, and once a plan can reach the exit, plans that get there in fewer moves score higher. So the population first learns to escape at all, then learns to escape efficiently.

The Loop at a Glance¶

Your browser owns the maze and the scoring. The server only evolves the plans.

Settings to Try¶

The Settings panel lets you change the maze size, from a quick six-by-six up to a sixteen-by-sixteen. Small mazes are solved almost at once; bigger ones need more generations, and on the largest sizes a run sometimes doesn't reach the cheese before the generation limit (in our tests, 19 of 24 sixteen-by-sixteen runs did within 120 generations). Raise Max generations or press Reset for a new maze if that happens. You can also tune the genetic algorithm itself: mutation probability and range, tournament size, how many elites carry over, and the maximum number of generations. These changes apply on the next Reset.

Under Animation, Generations per animated step (1 to 10, default 3) sets how many generations evolve for each one that is drawn. Higher values let the run reach a solution in fewer watched steps. This one applies straight away, with no Reset needed.

For more on how the demos catalog works, see What the Demos Do.