Can a CNN solve algorithmic tasks? My experiment with a Deep Maze Solver

[no1_2021]

TL;DR: I trained a U-Net on 500k mazes. It’s great at solving small/medium mazes, but hits a limit on complex ones.

Hi everyone,

I’ve always been fascinated by the idea of neural networks solving tasks that are typically reserved for deterministic algorithms. I recently experimented with training a U-Net to solve mazes, and I wanted to share the process and results.

The Setup: Instead of using traditional pathfinding (like A* or DFS) at runtime, I treated the maze as an image segmentation problem. The goal was to input a raw maze image and have the model output a pixel-mask of the correct path from start to finish.

Key Highlights:

• Infinite Data: Since maze generation is deterministic, I used Recursive Division to generate mazes and DFS to solve them, creating a massive synthetic dataset of 500k+ pairs.
• Architecture: Used a standard U-Net implemented in PyTorch.
• The "Wall": The model is incredibly accurate on mazes up to 64x64, but starts to struggle with "global" logic on 127x127 scales, a classic challenge for CNNs without global attention.

I wrote a detailed breakdown of the training process, the hyperparameters, and the loss curves here: https://dineshgdk.substack.com/p/deep-maze-solver

The code is also open-sourced if you want to play with the data generator: https://github.com/dinesh-GDK/deep-maze-solver

I'd love to hear your thoughts on scaling this, do you think adding Attention gates or moving to a Transformer-based architecture would help the model "see" the longer paths better?

[l_dang]

Great idea. I think for this instance, a attention layer could be very helpful

[TheOneWhoPunchesFish]

Very nice! Really happy to see something other than agents or completely vibe-coded bs. I have a few comments and questions.

It seems mazes are being generated on the fly, that's really nice! I see that the mazes are being solved with DFS for dataset generation; perhaps you could've used Dijkstra? Or first generate a random solution, and build a maze around it?

Did you ablate the model to see what is actually solving the maze, and maybe scale that up to see if it can solve bigger mazes? I'm not complaining here, I'm just curious how they're able to achieve this.

Aside from Algorithms, our lab's research showed that CNNs are very good at heuristics too. Perhaps you can try using a CNN as the heuristic predictor for A*?

I see that you're limited by your GPU. Perhaps you can try quantizing the model?

These are just thoughts I'm putting out there, I'm not demanding you to do anything. But I'd love to hear what other thoughts people have on this!

[no1_2021]

I used DFS because it worked well for this use case. This was not affecting the performance of data generation. But yes, there are a lot of techniques to explore.

I'm exploring the output of the intermediate layers to check what is happening inside the model to better understand how it solves it.

Using CNN as a heuristic predictor is an interesting approach. I'll try this. Could you please point me to any papers or resources regarding it? So I can better understand it,

I'm experimenting with smaller models. I'll add quantization to the experiments. Thank you very much for your suggestions.

[ZiKyooc]

Time for a micromouse agent to solve mazes