Perturbed hamiltonian-cycle-based algorithms to solve snake game

• Main Author: Chen, Leonardus
• Other Authors: Chew Lock Yue
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2023
• Subjects: Science::Mathematics::Applied mathematics
• Online Access: https://hdl.handle.net/10356/166541
• Institution: Nanyang Technological University

The snake game is an old classical game with simple rules that, to this date, has yet been completely solved with in the most efficient manner. The concept of Hamiltonian cycle allows to solve the snake game with perfect completion rate, albeit in an inefficient manner. We look into ways to use the concept of Hamiltonian cycle in solving the game more efficiently. More specifically, we look into improving the ideas surrounding Perturbed Hamiltonian Cycle, and subsequently use the improved ideas to implement and optimize various algorithms. Lastly, we run simulations of the algorithms in action and evaluate the results both analytically and experimentally.