AlphaSnake: Policy Iteration on a Nondeterministic NP-Hard Markov Decision Process (Student Abstract)

Kevin Du, Ian Gemp, Yi Wu

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.

Visual progression of AlphaSnake filling a 10x10 grid.

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.

Win rate improvement over 6,000 training games.

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

Abstract

Reinforcement learning has been used to approach well-known NP-hard combinatorial problems in graph theory. Among these, Hamiltonian cycle problems are exceptionally difficult to analyze, even when restricted to individual instances of structurally complex graphs. In this paper, we use Monte Carlo Tree Search (MCTS), the search algorithm behind many state-of-the-art reinforcement learning algorithms such as AlphaZero, to create autonomous agents that learn to play the game of Snake, a game centered on properties of Hamiltonian cycles on grid graphs. The game of Snake can be formulated as a single-player discounted Markov Decision Process (MDP), where the agent must behave optimally in a stochastic environment. Determining the optimal policy for Snake, defined as the policy that maximizes the probability of winning -- or win rate -- with higher priority and minimizes the expected number of time steps to win with lower priority, is conjectured to be NP-hard. Performance-wise, compared to prior work in the Snake game, our algorithm is the first to achieve a win rate over 0.5 (a uniform random policy achieves a win rate < 2.57 x 10^{-15}), demonstrating the versatility of AlphaZero in tackling NP-hard problems.
BibTeX
@inproceedings{du2023alphasnake,
  author = {Kevin Du and Ian Gemp and Yi Wu and Yingying Wu},
  title = {{AlphaSnake: Policy Iteration on a Nondeterministic NP-Hard Markov Decision Process (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i13.26962},
}
Figure