Note
SHIPPED 🚢 at https://minimio.ai
Warning
This write-up is an active work in progress. Some benchmarks and claims are changing as I continue to revisit the project. My speed of experimentation outpaced my speed of understanding.
This is the public write-up for a private repository, so some of the content is intentionally vague or incomplete.
Note
This maze solver was intended as a weekend project where I naively thought I could implement a maze-solving neural network in a weekend, that could solve 100% of unseen mazes. How wrong I was.
Play with it live yourself https://minimio.ai
This project was/is an experiment across 47 distinct phases, initially attempting to create a 100% solve rate maze-solving neural network from scratch, then quickly realizing I'm not going to achieve that, so instead trying to solve the highest % of mazes with the most compact neural network representation.
The flagship maze solver occured in phase 43 at - 14 bytes (not including the runtime, the 14 bytes is the state machine) - with a 96.5% solve rate on unseen/untrained mazes upto a 21x21 grid, at which point increasing grid size decreases the solve rate - to what exact extent I am yet to measure and benchmark.
The maze-solving agent/s were trained on "perfect" mazes, "perfect" mazes with "loops", "open" grids with no walls, and open grids with walls/obstacles/islands.
A common critique of these sorts of training regimens is that the models learn maze-solving specigic to the maze-generation algorithm they were trained on. To understand if that was the case, the benchmarking suite was extended to contain other common/famous maze-generation algorithms for benchmarking only - not for training. For the flagship models, the median solve rate drops by roughly 1% on alternative maze generation algorithms. A result that indicates the models are not actually biased to the training-specific mazes.
... Also known as throwing shit at the wall and seeing what sticks. 47 or so times.
Caution
I'm not a Machine Learning Engineer, so I literally don't know if an idea is stupid or not, so as you'll notice I just try things and sometimes they work. Is there a method to the madness? You tell me.
The grids are setup as 2D square grids of cells. The network / agent only sees walls immediately surrounding it (I experimented with 4 wall bits (N / S / E / W etc) as well as 8 wall bits ( N / NE / NW / E / W / S / SW / SE)).
The agent does not get a "map" nor coordinates. Its basically a little critter feeling around in the dark.
The first experiments I tried was giving the agent memory. Why? Because if you run these earlier models, they often get stuck in loops and can never exit them. So my "pre-history" experiments were to add memory. Memoryless actually performed pretty well, 4 bits of memory was the magic number. 8 was too much. 2 was too little. These memory models started "searching" rather than just getting stuck.
I thought it would be clever to create different types of memory to further improve the model - "fast" memory and "slow" memory, kind of like a human brain in a way, or, something that can be thought of as reflexes. Reflexes are effectively the immediate observations (there is a wall to my right, so don't go there). Fast and slow memory was too complicated, effectively fast memory was just normal memory and slow memory was memory bits we wanted to change less often based on meeting some condition or threshold. These fast/slow memory models performed worse than the "normal" memory model.
I kept hitting a wall with models failing due to loops. These early models were around 160-300 bytes each, but they would effectively hit a portion of a maze (such as a long wall run) and get stuck looping around it forever. One thing I noticed is different models would get stuck in different kinds of loops, so I was trying to think of ways to "break" them out of it (without cheating).
I had an idea about an "observer" network that was trained to watch the main maze network, and trained to "nudge" the original network when it would get stuck. But this didn't work, when the models were combined into one model the message "channel" effectively was a constant and these models performed poorly yet again.
From the above a simpler idea was born - "what move did I just make, and did I move" - effectively Proprioception for the model. This was a pretty big breakthrough, for the first time a model was solving >80+% of mazes. I then thought, if looking back gives such a big jump to the solve rate, maybe looking ahead one cell will too? Nope. No improvement.
The next real breakthrough was in changing the model while it runs. I was experimenting with ideas such as "fatigue" and "split-brains". Split-brains was insane - my original experiments were using 2 bit weights for each neuron, instead I thought what if we make each neuron a single bit, and then superimpose 2 neurons into 1, and flip between the weights on a fixed-step "clock". Like the network itself has 2 brains it switches between every 16 steps (16 steps then switch was the winning "number of steps").
And it works. Then I thought, okay what about 3 weights per neuron? Nope.
Then the biggest breakthroughs of the whole project, that finally got the solve rate from mid 80% to 90%+ with a SMALLER model: changing what the model senses. Instead of an information dense 4 bits for the goal, I swapped to a coarse 4 way compass (N / S / E / W). Then an even better version, replacing the whole compass with a single 1 bit "hot"/"cold" wherein "hot" literally just means is the goal "ahead of you" (plane based)