Abstract
AlphaSnake adapts the AlphaZero framework to the game of Snake, modeled as a nondeterministic, NP-hard Markov Decision Process (MDP). By integrating Monte Carlo Tree Search (MCTS) with a discounted reward structure and stochastic branching for random apple placement, the model achieves a 94.4% win rate on a 10x10 board. This work demonstrates that policy iteration can effectively solve complex, stochastic combinatorial problems with long horizons.
Introduction
The game of Snake serves as a significant proxy for challenging problems in graph theory, specifically the search for Hamiltonian cycles—paths that visit every node in a graph exactly once. Determining an optimal policy for Snake, which maximizes win rates while minimizing path length, is conjectured to be NP-hard.
While most reinforcement learning (RL) research focuses on deterministic environments, Snake is inherently nondeterministic due to the random appearance of apples. This stochasticity, combined with a "long horizon" where a snake may take thousands of steps to fill a board, presents a grueling test for standard RL algorithms. AlphaSnake aims to prove that the policy iteration and search algorithms pioneered by AlphaZero can be generalized to solve these complex, stochastic combinatorial problems.
Methods
The researchers modified the AlphaZero architecture to accommodate a single-player, stochastic MDP:
- Discounted MDP: Unlike games with terminal rewards (e.g., Chess), Snake provides intermediate rewards for eating apples. A discounted value function $V(s)$ was implemented to prioritize immediate progress while maintaining the long-term goal of board completion.
- Stochastic MCTS: The standard adversarial MCTS was adapted by replacing the opponent with a "chance" agent. When an apple is consumed, the search tree branches uniformly across all possible next apple locations.
- Action Pruning: To optimize the computational budget, the environment simulates "forced actions" in states where only one legal move exists, allowing the agent to focus search depth on critical decision points.
- Reward Shaping: The agent receives +1 for eating an apple, -10 for crashing, and +10 for successfully filling the board.
Key Results
AlphaSnake was trained over 6,000 games on a $10 \times 10$ grid using a tree search size of 200 states per move. The model significantly outperformed all baseline strategies.
The final model achieved a 94.4% win rate in 1,000 test games, with an average snake length of 98.227 on the 100-cell board. In comparison, uniform random policies and naive tree searches failed to achieve any wins. Notably, while a fixed Hamiltonian cycle strategy guarantees a win in theory, it is too computationally slow to succeed within practical step limits. AlphaSnake learns to find efficient paths, optimizing for both survival and time.
Conclusion
This research represents the first instance of an RL algorithm achieving a win rate over 50% in this specific Snake formulation. While the $10 \times 10$ grid demonstrates proof-of-concept, future work will address scalability to larger state spaces. The authors suggest that this approach could be extended to real-world "security games" or anti-poaching strategies, where defenders must navigate stochastic environments against unpredictable adversaries.
Summary updated