1
$\begingroup$

I am trying to build a network able to play snake game. This is my very first attempt to do such stuff. Unfortunately, I've stuck and even have no idea how to reason about the problem.

I use reinforcement neural network approach (q-leaning). My network is built on top of Keras. I use 6 input neurons for my snake:

  • 1 - is any collision directly behind
  • 2 - is any collision directly on the right
  • 3 - is any collision directly on the left
  • 4 - is snack up front (no matter how far)
  • 5 - is a snack on the right side (no matter how far)
  • 6 - is a snack on the left side (no matter how far)

the output has 3 neurons:

  • 1 - do nothing (go ahead)
  • 2 - turn right
  • 3 - turn left

I believe this is a sufficient set of information to make proper decisions. But the snake seems to not even grasp the concept of not hitting the wall - which results with instant death.

I use the following rewards table:

  • 100 for getting the snack
  • -100 for hitting wall/tail
  • 1 for staying alive (each step)

Snake tends to run randomly no matter how many training iterations it gets.

The code is available on my github: https://github.com/ayeo/snake/blob/master/main.py

$\endgroup$
  • $\begingroup$ The problem can be fixed stepwise. The first thing to do is to take the automated AI player out of the loop and play the game manual with the arrow keys. If the python game engine works, this shouldn't be a problem and the human player is able to solve a level. The next step is to reactivate the AI system carefully by fade in the planned action as overlay image to the snake map. The human plays the game, but the q-learning algorithm gives visual feedback, what he would do instead of the human. This allows to bugfix the program and detect at which point the neural network is wrong. $\endgroup$ – Manuel Rodriguez Jul 4 at 13:04
  • $\begingroup$ you were right. Aside from some problem with my agent model mentioned in another post here, there were few naughty bugs directly in my game engine (env) $\endgroup$ – ayeo Jul 5 at 19:17
1
$\begingroup$

I cannot comment much on your setup for inputs and outputs. It seems adequate to get some control, but does not cover the fully Markov state for the game, so I would expect that will limit the agent from ever being truly optimal. I would expect it to learn to play the game though, if you were implementing Q learning with a neural network correctly.

In your code, you are implementing a basic Q learning loop. It seems correct. However, this combination of Q learning and neural networks is known not to work - or more accurately, it rarely works this simply. The problem is mainly to do with the network receiving its own initially biased outputs back as new targets, plus receiving updates in correlated form (data on each time step is strongly correlated with data from previous time step). These biases are too large for the Q learning process to overcome, and typically the result is an agent that fixates on a single default action, because it has learned an inflated action value for it.

The problem is well known in RL research and called "The Deadly Triad" by Sutton & Barto.

The usual solution to this with Q learing is called DQN or "Deep" Q Learning ("Deep" is in quotes because this should be applied even if you just have a single hidden layer).

In basic DQN, you need to add the following features:

  • An experience replay table. Instead of training directly on experience as it is received, instead store $s, a, r, s'$ in memory. When it is time later in the loop to train the NN for a step, take a random sample of some M items (e.g. 32 items) as a mini-batch, calculate a latest target for them, and train once on the mini batch. You will need logic to only start this training process once you have some minimal amount of experience from behaving randomly (e.g. 500 random steps).

  • A "target network". When generating target Q values, use a cloned copy of the learning network, and only update this clone every N steps (with N typically set at 1000 or 10000).

These two additions are not really optional, even for really basic environments. You will need to add them to your script.

$\endgroup$
  • $\begingroup$ Storing the past experience into a memory which is 32 items long, sounds like model-based reinforcement learning which will fail because the features are under-specified. Additional its unclear how the memory should predict future outcome of the snake game. $\endgroup$ – Manuel Rodriguez Jul 4 at 13:37
  • $\begingroup$ @ManuelRodriguez: The memory is not 32 elements in my example, it is not specified in the answer, but typically thousands. The sample from this memory on each step is e.g. 32. You are right that this memory can be thought of as a model, and there is some cross-over here with the background planning method Dyna-Q where this is made explicit. The memory does not need to "predict future outcome", it is used as raw data for the Q-learning algorithm which does predict longer-term outcomes by consuming smaller pieces of trajectory and combining them into value functions $\endgroup$ – Neil Slater Jul 4 at 13:45
  • $\begingroup$ thank you so much! I've read a bit about the stuff you had mentioned. It works better than I thought it will! The codebase has been updated - maybe someone would find it useful $\endgroup$ – ayeo Jul 5 at 19:15
  • $\begingroup$ Thanks @ayeo. It would help me if you accept this answer (the tick mark on under the voting scores), to show that is was useful. Especially as the voting so far makes it look like the answer is not useful - I think due to a misunderstanding by the voter, but that is not under my control. $\endgroup$ – Neil Slater Jul 5 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.