The Snake game was popularized by its appearance on Nokia cell phones in 1997 but has been recreated in several forms for multiple computing platforms since 1978. The game is very simple: the snake is controlled by the player and is allowed to move inside a 2-dimensional playing field surrounded by walls. At each discrete interval, called a time step or step, the snake must move forward, turn left, or turn right as the game requires that the snake cannot stop moving. The game will randomly generate and place one piece of food in the game field at a time. When the snake moves onto a piece of food, the food is eaten and the snake's length grows by one. The goal is to eat as many pieces of food without ending the game by colliding the snake into itself or the walls. [1]
In our game settings, the playing field will be 10 units tall and 10 units wide consisting of 100 available spaces. The snake will initially begin at the top-left corner, facing right, with an initial length of 2 units. Therefore, the snake can eat 98 pieces of food before filling up the entire playing field.
All the problem solvers are subclasses of BaseSolver. The subclasses override BaseSolver.next_direc() to return the next moving direction of the snake.
Path Solver provides methods to find the shortest path and the longest path from the snake's head to other points on the game map. This solver does not directly decide the next moving direction of the snake, but help other solvers to work it out.
Path Solver uses breadth-first search to find the shortest path. Intuitively, we expect the path to be as straight as possible so there will be less scattered empty points on the map. In the implementation, the trick is that during each iteration, the adjacent point in the last traverse direction will be traversed first.
The longest path problem on the game map (i.e., a cyclic, undirected and unweighted graph) is NP-hard. Path Solver uses a heuristic algorithm to find suboptimal solutions.
Suppose we want to find the longest path from point A to point B on a 4*4 game map. The algorithm first finds the shortest path between the two points and then extends each pair of path pieces until no extensions can be found:
Greedy Solver lets the snake eat the food along the shortest path if it thinks it is safe. Otherwise, it makes the snake wander around until a safe path can be found. This solver depends on Path Solver to find the shortest path and the longest path on the game map.
Concretely, to find the snake S1's next moving direction D, the solver follows the steps below:
- Compute the shortest path P1 from S1's head to the food. If P1 exists, go to step 2. Otherwise, go to step 4.
- Move a virtual snake S2 (the same as S1) to eat the food along path P1.
- Compute the longest path P2 from S2's head to its tail. If P2 exists, let D be the first direction in path P1. Otherwise, go to step 4.
- Compute the longest path P3 from S1's head to its tail. If P3 exists, let D be the first direction in path P3. Otherwise, go to step 5.
- Let D be the direction that makes S1 the farthest from the food.
Hamilton Solver builds a hamiltonian cycle on the game map first and then directs the snake to eat the food along the cycle path. To reduce the average steps the snake takes to success, the solver enables the snake to take shortcuts if possible. This solver depends on Path Solver to find the longest path on the game map.
Before the snake starts moving, Hamilton Solver finds the longest path from the snake's head to its tail, which forms a hamiltonian cycle on the map:
Following a fixed cycle path all the time is tedious and time-consuming. Hamilton Solver directs the snake to take shortcuts according to the rules below. [2]
