Choice of inputs features for Snake game

Question

I am designing a neural network using Deep Q-Learning, which teaches an agent how to play Snake (The classic Nokia game from the 90'ies). The goal of the game is to navigate the snake on a playing field (2D), and to eat a randomly placed fruit. As the Snake eats the fruit, it grows in length. The game ends if the snake hits the game border, or it self, so as the number of fruits consumed increases, so does the difficulty of navigating without hitting something.

I have trained the Snake game on a 10x10 playing field using the following inputs:

1. x direction of the snake
2. y direction of the Snake
3. The fraction of playing field occupied by the snake itself
4. A bool which says if the fruit is in front of the snake (from it's current direction)
5. A bool which says if the fruit is to the left of the snake (from it's current direction)
6. A bool which says if collision (game over) in front of the snake is possible
7. A bool which says if collision to the right is possible
8. A bool which says if collision to the left is possible

With this choice of inputs I am getting the Snake agent to work reasonably well, and score until it plateaus out. I have examined the cases where the snake dies, and it all happens when it has no way of escaping, for example, it turns around and blocks its own path, until it finally has no where to go. This is more likely to happen as the Snake increases in lenght.

I was thinking on how I could improve this performance. It seems to me, that the reason the Snake can make a self-blocking turn is because of the inputs. Since the path it takes is clear, there's no information, that the next path is not, or that continuing further down will eventually lead to game over. If the Snake agent was aware of all obstacles in each step, i.e. the entire state-space, then I could imagine that would help train the network towards finding the optimal path without ending up blocking itself.

Since I have made the Snake game myself, I can return to the agent a matrix, or an unfolded vector, which contains the inputs for each column / row on the playing field. A blocked cell would be set to 0, a free cell 1, the fruit cell has value 0.75 and the snake head (which moves) could be assigned value 0.25. After trying this approach, I have to say I was unsuccesful. The snake ends up just turning in circles, even if I use the same reward system as the 8 input case shown above.

I am therefore trying to understand what is happening here. Am I missing information? I would think the full 10x10 state space would give me exactly enough information to lead to the correct evaluation of the next path. I would very much like to hear someone elses input to this approach.

Thanks a lot

Answer 1

Before we start to tweak with you Agent-Environment setup, there are couple of important things to note

• Q-Learning

  Q-learning as a fundamental is a greedy approach based on Action Value functions. When I say action value what I mean to say is this $q_\pi(s,a) = p(\hat{s},r | s, a)[r + \gamma(V(\hat{s}))]$.

  This means according to $\pi$ policy the Action value for taking action "$a$" at state "$s$" is the probability of taking reaching state "$\hat{s}$" and getting a reward "$r$" given the current state is "$s$" and action taken is "$a$" multiplied by sum of immediate reward "$r$" and expected future reward given by future state value(s) "$V(\hat{s})$".

  Please note the $p(\hat{s},r | s, a)$ is only available in deterministic modelling technique (model based methods) and this part is not available for stochastic modelling techniques (model-free methods). For model-free methods we execute multiple experiments and take the expected value in accordance with Law of Large Numbers. Which is what we do in common Deep Reinforced Learning implementations.

  The above formulation for future rewards can be expanded in series using the state-value formulation as $V(s) = \pi(a,s)q_\pi(s,a)$, where $\pi$ is the policy we are following aka probability of taking action $a$ when in state $s$.

  Why is it termed Greedy?

  This is because while using the fundamental of multiple experiments, with every action I take the immediate reward, and the max q_value ($q$) associated with the next_state to update my current q_value.

In Q-learning the future state reward is what you calculate by submitting the next_state to the network and taking max of the q_values attained. (Hence, Greedy!!)

Crux of the above

Having said all the above (Duh!), what is in it for us?

In Q-Learning, your reward is key for your model learn, i.e. "$r$" immediate reward and the future reward ($V(\hat{s})$)

• When the state-space is limited

  For example, a numerical tic-tac-toe game, in such cases it is ideal to have discrete reward system, such as the one suggested by you.

• When the state-space is very large (the problem statement you are tackling)

  In such cases, it is ideal to have a continuous reward mechanism, i.e. rewards should be more variable in nature, like continuous values.

• Suggestions

  1. You can define the reward function in the environment has the 10$\sqrt{2}$ - Euclidean distance between the face of your snake and the fruit it is trying to reach. The reason I am doing it (10$\sqrt{2}$ minus) is because the maximum distance could be 10$\sqrt{2}$ (considering it is 10X10 board). This would help you to have a more variable/continuous rewards for your model to learn with (since you are using neural networks for training them). As your Snake goes closer to the fruit this value will keep on increasing. One cavet, if by taking an action, your snake reaches fruit, you can provide it a specific constant (extra) reward, and if it hits its own self, or the borders you penalize it with a specific constant. So that the model understand better.

  2. You can define your state (input vector to your NN) as 100 dimension array (10X10 grid) with each element signifying if there a object in the that area or not. 1 means it is fruit, 0 means it is snakes own body and 0.5 means it is free for movement. The idea is to limit the input values of the vectors between 0~1. As your agent takes action, the values in the state will keep on changing.

  3. The output of your network should have 3 neurons, each signifying the $q$ of each of action (front/right/left movement). For get_action function you will get the action pertaining to max(q_value), and keep on adding things in your memory d_que. Subsequently you can trigger model_train methods at every episode/or even at after every step.

  4. Lastly, the hyper parameters would be the discount factor $\gamma$ you choose and the learning rate $\alpha$ you use for the NN network. That's something you will have to experiment. Along the depth of your ANN. I think a single hidden layer should be enough.

  5. For the last layer of your NN, please use a linear activation function, and not a relu activation function.

  6. Please run many-many-many experiments, something in millions for optimum training. There could be multiple ways of monitoring your model's learning process. How many games won, how much fruit eating it is able to achieve in 1 game etc.

Hope the above helps.