What it does This repo pits two AI approaches against the classic Snake game on a tiny 6×6 grid. One agent uses graph search with Hamiltonian paths and deliberate detours; the other learns via deep reinforcement learning (Double DQN). Both are fully implemented in Python with PyTorch support for training.

The interesting bit The graph search agent wins decisively—94% success rate versus the RL agent’s 50%—by treating Snake as a pathfinding puzzle rather than a policy approximation problem. When the snake gets long enough, it hunts for a Hamiltonian cycle to guarantee safe completion; when that fails, it falls back to shortest-path checks and engineered “longer paths” that zig-zag to free up tail space. The RL agent, meanwhile, learns from a 4-channel grid state and relative motion actions, but still struggles with the long-horizon planning that the rule-based system encodes explicitly.

Key highlights

• Graph search averages length 35.86/36 with 94% perfect-game rate over 1000 rounds
• RL agent manages 29.33/36 with 50% success—respectable, but clearly second
• Hamiltonian path search uses Warnsdorf’s heuristic and backtracking; NP-complete, but tractable at this scale
• “Longer path” detours deliberately waste steps to prevent the snake from locking into fixed loops near its tail
• RL uses Double DQN with a CNN+FCN architecture and careful reward shaping (including a hard timeout penalty)

Caveats

• Grid is fixed at 6×6; scaling to larger boards would strain the Hamiltonian search
• RL model requires separate PyTorch install; graph search runs on base dependencies only

Verdict Worth a look if you’re teaching or learning AI fundamentals—it’s a clean, self-contained comparison of classical planning versus modern RL, with the slightly humbling result that clever graph theory still wins on small structured domains. Skip if you need a production Snake solver or want to train on larger environments.