In this project, I confront the A* algorithm with a neural AI. I make use of the framework from the Unity asset manager.

This project is about checking which method would make the most sense. Thereby several edge cases were set up, which both methods have to face.

1. Traditional AI A* algorithm. Mode 1.
   If this checkbox is checked, the ML agent is disabled and the snake moves to the next apple according to the A* algorithm. 
   
   
2. Machine learning agent. Mode 2
   If this checkbox is activated, the A* AI is deactivated and the machine learning AI is activated. Clicking Start may take a few seconds as a GameObject is created. edge cases are deactivated.
   If no mode is selected you can play the snake yourself with (W,A,S,D).
   
   

3. Naive solution
   If this checkbox is activated the snake resp. the algorithm proceeds with a naive solution approach of mine. More details later in the documentation.
   

   
   

4. Ignore the last 3 snake parts
   If this checkbox is activated, the last three nodes on which the snake is located are ignored for the A* algorithm for the next three steps.
   
   

5. Edge cases
   Here I have created three edge cases. If the mode is set to "normal" the snake always starts at the same position, this will be important for the ML agent later. I will deal with the edge cases separately.
   

When the game starts, a grid is created on which the snake moves. At the same time, a pathfinding grid is created based on the game grid. This grid has 10 fields on the X-axis and 10 fields on the Y-axis.

If the mode is in AI A* mode, the path is recalculated every time the snake reaches a new node. An edge weight of 10 is used, regardless of whether the movement is horizontal or vertical. The 10 is only used to make it easier to implement a diagonal movement with a weight of 14 if needed (14 => √200).

If you select the first limiting case, the situation shown above occurs. The A* algorithm tries to calculate the shortest path to the apple for the next two movements but does not find a valid path. The result is that the snake runs against the wall.

However, if you choose to ignore the last three parts of the queue, the path calculation will ignore the yellow framed area and the algorithm will find a path to the apple.

In the second limiting case, we can see that the snake finds a successful way to the apple if it does not ignore the last three parts. It is interesting to see that even if each part of the snake is declared as "not-accessible", it always moves to the left before going up, even if the path is recalculated each time.

However, ignoring the last three parts of the snake does not lead to a successful result, as in edge case 1, because the snake bites its tail. Logically, since it recognizes the shortest way directly to the apple.

The third borderline case was very interesting for me and kept me a bit busy, because the A* algorithm of course always looks for the shortest way to the apple, but does not expect to continue playing afterward.

For this reason, I came to a naive solution approach. In this approach, before each path calculation, it is checked whether there are at least two accessible fields around the apple. If this is not the case, the longest path to the apple is calculated. Since this calculation takes place with each node change, the snake recognizes immediately if the path is free and takes from the moment the shortest way to the apple.

I had problems with the neural AI because my Snake behaves completely different than most documentation about the ML Agent on the internet. For example, I don't have a collider or a GameObject from the beginning, because the snake is created only after you press play.

Nevertheless, I managed to implement the AI and let it learn, it got a positive reward of one when it got the apple and a negative reward of two when it collides against itself or the wall.

I used the coordinates of the head and the apple as observation points and let the AI learn overnight. Unfortunately, I had to find out that it reaches the max. two apples in the ideal case. Whereby it gets the first one most of the time. This is probably because the first apple always spawns at the same place. Unfortunately, the documentation for ML in Unity is rather poor for 2D games. Due to the high success with the first apple, I could imagine that a dynamic environment is much harder for the AI to learn (apple spawns randomly in the grid). However, this is just a thesis.

Link to Subversion: ​https://christian-brueckl.de:8443/svn/SnakeAI/​​​

_________________________

Username: showcase
Password: showcase