  Reinforcement learning has recently been used to approach well-known NP-hard
combinatorial problems in graph theory. Among these problems, 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 \times 10^{-15}$), demonstrating the versatility of AlphaZero
in approaching NP-hard environments.
