Snake Neuroevolution - Snakes going mad :))

Question

Hello everyone,

I have a more complex issue regarding a more complex problem. I have this app, which shows an animation of snakes (from the POPULAR game of "Snake") that learn to win the game using a genetic algorithm.

It works like this:
* A Snake Object Pool of 50 snakes with an individual "brain" as a Neural Network
* Each snake tries the game until it dies
* Each snake will have a score and at the end of the generation, the following happen:
* Fitnesses are calculated as normalized values
* The best 6 snakes from the current generation are chosen
* There are 10% chances a brain is mutated
* Two random brains are chosen and they crossover to make a new one
* The new brains are given to the snakes and the next generation begins
* Each neural network is made of 5 input nodes,

The problems are:
* The most important one is that after a few generations, the snake just follows the nearest wall.
* Apparently I don't know how to fix to the loopworm bug, where the snakes just go in a loop. I tried decreasing the score when they get further away, but it also affects the other snakes

The Neural Network library is taken from the Coding Train on Youtube, and the playlist that shows you how it was created is here: https://www.youtube.com/watch?v=XJ7HLz9VYz0&list=PLRqwX-V7Uu6aCibgK1PTWWu9by6XFdCfh

The project I am talking about is on Github here: https://github.com/gamirou/SmartSnake

Thank you everyone!

Answer 1

Gami I am a bit busy lately for code debugging, but just to clear out about backprop -- it transmits the error back to the network nodes and based on that the weights are adjusted.
Haven't yet looked at your code and it will take me a while since it's in JS, but perhaps you could experiment with penalties for unwanted behaviour to minimize the chance they will follow the same wrong pattern? From what you described, it seems to me it is somewhat calculated as the "best option" anyway, and is reproduced by all the snakes...

Answer 2

how do you calculate fitness ? maibe they stay alive the longest time, if they folow the wall.

Answer 3

Max Each node consists of a matrix. When I crossover two neural networks, I take the matrices, and make new matrices with half of the weights from both networks. Does backpropagation work with a genetic algorithm? From what I know, backpropagation is used when you know the desired move.

Answer 4

Kuba Siekierzyński Ok, I get it. But how do I know the desired move. How do I calculate the error? I tried experimenting with the penalties,I increased it to -10 for going away, but it still goes to the closest wall.

Answer 5

Thank you Pedro Demingos

Answer 6

Apple Blossom Yet, there are no interfaces present because it is JS, you are kind of right. JS is a prototype-based language, but I coded using inheritance and polymorphism ideas. However, this was not the question xD

Answer 7

Filip Dobeš All absolute values of scores are added to a variable called total. Then each fitness is currentScore / total.

Answer 8

Max My score is incremented each time the snake stays alive and gets closer to the food. If it goes away, the score gets 10 points taken away and if it eats the food it gets 100 points. I thought about changing the fitness function, but I decides to leave it like this to see what you guys think about it.

Answer 9

how are you doing the crossover? mixing two neural nets might not have the desired effect. using backpropagation might be more useful

Answer 10

@Gami yeah sorry i meant that you should try using gradient decent or something on the fitness function to find better weights. i looked over your code and saw that you use some kind of distance to food as the score? have you tried just using the snake length as score or modifying the score to include multiple factors?

Answer 11

I’m just here to say that this is really nice. I’ve always wanted to code a simple evolutionary game. :P

Answer 12

Wow, that's a really supportive community, but not very helpful unfortunately... I have done a huge mistake posting this on Sololearn. I helped a lot of people on this platform, but it doesn't seem I get any help back! Thank you Sololearn! Awesome

Answer 13

yeah big suprise, mixing matrices is not a useful way of breeding and nobody here can fix it.
how is it a big mistake to post it here? its not like you lost anything by posting here except for a trivial amount of time. is it really that suprising that you didn‘t get much help in a forum for beginners?

you are looking for something like the NEAT algorithm by the way.

Answer 14

@Max I expected this, but I thought I might get answers from some more advanced users. This forum is mainly for beginners, not JUST beginners

Answer 15

yes but the probability that someone that is advanced and doing neuroevolution is on this forum is pretty low, especially since other algorithms dominate neural network research right now.
additionally javascript is a very unusual language for neural networks so the few people that have the knowledge might not answer since they are only using python with numpy and tensorflow and don‘t want to dig through the code until they find the relevant part that does the learning. i didn‘t reply anymore for example because i wasn‘t sure where exactly everything was happening since i don‘t have time to read about all of the libraries you use and since i didn‘t find where you are updating score(it‘s not happening in snake.js i think).

Answer 16

Glancing quickly at the description sounds like a mixture between inheritance and polymorphism structure, with possible interface implementation.