Nature vs Nurture
Comparing DQN and NEAT for generalisable AI in Pac-Man
Most agents that “beat” Pac-Man have only memorised one maze. This project asks a harder question: if you train an agent on varied mazes, does it cope with layouts it has never seen — and does the way it learns (gradient descent or evolution) change the answer?
I built the game engine and a Gymnasium environment from scratch, trained a Dueling Double DQN and a NEAT population under identical conditions, then tested both on 100 held-out mazes. Awarded 85%.
- Python
- PyTorch
- NEAT-Python
- Gymnasium
- Pygame
- NumPy
- Matplotlib
- CUDA
- Mean test reward
- 1,581NEAT vs 912 DQN
- t(198) = −3.56, p < 0.001
- Win rate, unseen mazes
- 37%NEAT vs 26% DQN
- p = 0.094, not significant
- Held-out test mazes
- 100never seen in training
- seeds 10,000 – 10,099
- Observation space
- 29-Degocentric vector
- no pixels, no CNN
Benchmarks reward memory, not skill
A fixed maze lets an agent learn a route. Win rates look great, and then the layout changes and the policy falls apart. Standard Atari-style benchmarks hide this: the test set is the training set.
So the evaluation here is built to make memorisation impossible to hide. Every episode uses a procedurally generated, BFS-validated maze. Seeds 0–9,999 form the training pool; seeds 10,000–10,099 are a test pool that neither algorithm ever touches. A second pair of runs trains on one fixed maze, as a deliberate memorisation control.
- DQN-randomgradient-based, new maze every episode
- NEAT-randomevolutionary, new maze every episode
- DQN-fixedgradient-based, one maze only
- NEAT-fixedevolutionary, one maze only
One environment, two learners
The game is written in Python and Pygame, with four ghosts using A* pathfinding and distinct targeting rules. A Gymnasium wrapper exposes it to both learners through the same 29-dimensional vector, so any difference in results comes from the learning paradigm rather than from perception. Pixels were rejected on purpose: they would mix a vision problem into a control problem.
Four rays (forward, left, right, back) × six channels: wall, pellet, power pellet, lethal ghost, frightened ghost, visit saturation. Re-ordered to Pac-Man’s heading so identical situations look identical.
Shortest-path distance to the nearest pellet, lethal ghost and frightened ghost. Maze topology respected, not straight-line distance through walls.
Whether frightened mode is active and how long remains, so hunting is never confused with fleeing.
Nurture · Dueling Double DQN
- 2 × 256 shared layers, value and advantage streams
- Prioritised replay on a SumTree, 200k transitions
- 8 vectorised environments, soft target updates
- Trained on an RTX 4060 via CUDA
Nature · NEAT
- Population of 150, starting with zero hidden nodes
- Speciation protects new structure while it matures
- Each genome scored on 3 different mazes, averaged
- Evaluated across 6 worker processes on CPU
NEAT generalised better
On 100 unseen random mazes, NEAT-random out-scored DQN-random on every metric. The reward gap is large and highly significant; the win-rate gap points the same way but, at one episode per seed, does not clear the 0.05 bar.
Bars are scaled within each metric. Each agent was tested at the highest curriculum stage it reached in training.
All four conditions
| Condition | Stage | Win | Mean reward | Median | Pellets | Explored | Ghosts |
|---|---|---|---|---|---|---|---|
| DQN-random | 4 | 26% | 912.4 | 279.1 | 97.9 | 27.9% | 0.17 |
| NEAT-random | 5 | 37% | 1,581.4 | 1,162.4 | 141.7 | 40.3% | 0.32 |
| DQN-fixed | 5 | 6% | 254.0 | −75.9 | 61.4 | 17.1% | 0.28 |
| NEAT-fixed | 7 | 0% | 414.7 | 366.7 | 84.0 | 23.9% | 0.24 |
NEAT’s median reward (1,162) is over four times DQN’s (279), so the gap isn’t a few lucky mazes. Ghost collision was the dominant failure for both: 73 of 100 DQN episodes, 53 of 100 NEAT episodes.
Memorising one maze goes further in training, and fails on new ones
Fixed-maze agents cleared the curriculum faster: DQN reached stage 5 instead of 4, NEAT reached the full game at stage 7 instead of 5. Put them on unseen mazes and both collapse. That is the memorisation effect, measured.
Both gaps are significant (DQN t = −3.98, NEAT t = −9.04, both p < 0.001). NEAT overfit harder when the training distribution was fixed: it generalises better under random mazes, but it isn’t immune to memorisation.
The engineering that made it trainable
-
10,000+~200
Tile-lock stepping
At 60 fps a typical episode is over 10,000 near-identical decisions, and rewards land far from the actions that earned them. The environment now advances the engine internally until Pac-Man reaches the next tile centre, summing the reward, so an episode is roughly 100–300 meaningful decisions.
-
6workers
Parallel NEAT on CPU
Genomes are independent, so each generation of 150 is split across six isolated worker processes. NEAT averaged 0.22 s per episode against DQN’s 5.04 s, about 23× cheaper, because evaluating small feed-forward nets needs no gradient step and no GPU.
-
8envs
A GPU pipeline for DQN
Eight vectorised games, each on a different maze, feed one replay buffer so the network sees varied geometry in every batch. Dueling streams, Double-DQN soft targets and priority-weighted sampling keep the Q-values stable; every gradient update runs on CUDA.
-
8stages
A curriculum with a ghost-eating bridge
From scratch there’s almost no learning signal, so ghosts arrive gradually and promotion needs a sustained win rate over a 150-episode window. Early agents never learned to hunt, so a dedicated stage adds a ghost-eating bonus, then removes it to check the behaviour stuck.
-
3 of 4headings
The bug that hid in a lookup table
The egocentric re-ordering had left, right and backward channels swapped for three of four headings, quietly corrupting threat perception in earlier runs. It was found with a debug view of the rays and Q-values, fixed, and every reported result comes from the corrected build.
What this doesn’t show
- NEAT-random finished only 32,658 of its 75,000-episode budget (shared time ceiling), so the two random runs weren’t matched on episodes.
- The reached-stage test uses a different stage per condition. At a fixed full-game stage 7, nobody won — though NEAT-random still led on reward (625 vs 266, p < 0.001).
- One episode per held-out seed, so no within-seed variance analysis.
- Neither algorithm mastered the full game. This is evidence of relative generalisation, not a solved Pac-Man.
Read the full dissertation
98 pages: literature review, methodology, every table and the full statistical analysis.