FSM and Snake

Snake is one of the less serious applications of FSM (from a research perspective). It is an old retro game, where the player maneuvers the "snake", avoiding eating itself and crashing into walls. The snake can eat food while playing to grow in length, thus reducing the space it has to manoeuvre. A player wins when the whole screen is filled. There are various strategies that perform well and some play perfectly (a hamiltonian cycle) every game.

I thought it could would be an interesting application for FSM. I coded a basic model of snake and implemented the FSM idea as follows:

The snake has full knowledge of its surroundings, where the walls are and where its body will be. It knows where the apple(s) is but does not know where the next apple will spawn after eating the current one. As such, the snake assumes the apple will spawn uniformly in one of the available squares.
The "State" that the snake is maximising its access to is it's length. The snake takes actions that provide the greatest variety of possible lengths.
The snake can perfectly model its actions up to a depth of $tau$ . Actions that lead to terminal states, i.e collisions with itself or a wall, are not explored further.
The snake calculates the path-entropy of its current actions, and selects the one with the largest entropy.

Here is an example game, played by a FSM-snake (SPAAM Snake) with depth 12:

Firstly, we note there is an attraction to food. This is because having food accessible within the depth 12 search allows for the snake to choose different points at which to eat. As such, the path-entropy of actions towards the food are larger. Sometimes, this includes eating the food immediately, and other times avoiding the food. We see this early on: at 0:02 the snake chooses to orbit the food multiple times before eating it. This can be explained by the heuristic of where the next food will occur. In computation, sometimes the next food will spawn close by after eating it, and other times it will spawn far away. Only when the path entropy of eating the food is large enough will the snake choose to eat. This can also be seen at 0:18.

Another emergent behaviour is eating the food from the wall side and heading into the open centre. This can be seen at 0:24. Since heading into the open space has more diverse paths available, there are also more opportunity to eat the next food when desired. Eating food towards the wall means the next actions are more forced which leads to lower path-entropy.

Finally, we can see that the snake likes to follow its own tail. This is intelligent behaviour, since the space evacuated by the tail will be free for the head to move into. Occasionally, there is greedy opportunities to eat food. However, if the snake can see that there are no surviving paths, then it chooses to continue to play the game and loop back around, rather than eat the food and die. If the deaths are at a deeper point than the tree search, the snake can kill itself by accident. Below is another game at depth 6 (SPAAM Snake 2).

Notice that the snake is more hesitant to eat the food. This is because the smaller depth requires the hypothetical food to spawn closer to the original food when doing the FSM calculation. The death at the end was because the snake had accidentally trapped itself; its death was outside of the tree search the action before, but afterwards cannot see an escape and so picks randomly between the actions (which have equal FSM entropy).

I hope you can see that FSM can produce intelligent behaviour, without explicit instruction. Only was "diversity of snake lengths" coded up, yet the snake is capable of playing a sophisticated game. The quality of behaviour is directly related to the length of tree-search, and $Tau to infinity$ (or the size of box) would be able to play without death.