使用遗传算法+神经网络解决贪食蛇游戏

在网上无意看到的一个项目，感觉还是蛮有意思的：

​​https://github.com/greerviau/SnakeAI​​

==========================================

代码不知道是用什么语言写的，不过这个不重要，这个比较有借鉴的是这个项目的设计。

都知道现在搞AI游戏的都是用CNN+Reinforcement Learning，但是实际上有很多游戏不使用CNN而使用MLP依然可以有效果的，而且Reinforcement Learning算法需要设计Reward函数，而最终的算法性能和这个Reward函数的设计有极大关系，使用神经网络MLP+遗传算法的设计则避免了设计Reward函数而使用设计fitness函数，虽然fitness函数的设计依旧有些难度但是总是要比reward函数的设计要简单些。

该算法的设计大致为：

Evolution

Natural Selection

Each generation a population of 2000 snakes is created. For the first generation, all of the neural nets in each of the snakes are initialized randomly. Once the entire population is dead, a fitness score is calculated for each of the snakes. Using these fitness scores, some of the best snakes are selected to reproduce. In reproduction two snakes are selected and the neural nets of each are crossed and then the resulting child is mutated. This is repeated to create a new population of 2000 new snakes.

Fitness

A snakes fitness is dependant on how long the snake stays alive as well as its score. However they are not equally important, having a higher score is rewarded more than a snake who simply stays alive. There is the possibility however that a snake may evolve a strategy where it loops in a certain pattern and never dies. Even though having a high score is prioritized more, if a snake can stay alive forever then that is a clear problem. To avoid this each snake is giving 200 starting moves at the beginning of its life. Every time it eats a piece of food it gains 100 more moves, with a maximum of 500 moves. This means that snakes who evolve to go in loops will eventually die and snakes who go for the food will not only have a higher score, but stay alive longer.

Crossover & Mutation

When two snakes are selected for reproduction, what happens is that the snakes brains are crossed with each other. What this means is that part of one parents brain is mixed with part of the second parents and the resulting brain is assigned to the child. After the crossover the brain is also mutated according to a mutation rate. The mutation rate determines how much of the brain will be randomly altered.

====================================================

重点设计为fitness函数。

Snake

Neural Network

Each snake contains a neural network. The neural network has an input layer of 24 neurons, 2 hidden layers of 16 neurons, and one output layer of 4 neurons. Note: Network can now be customized with the number of hidden layers as well as the number of neurons in the hidden layers.

Vision

The snake can see in 8 directions. In each of these directions the snake looks for 3 things:

• Distance to food
• Distance to its own body
• Distance to a wall

3 x 8 directions = 24 inputs. The 4 outputs are simply the directions the snake can move.

这里蛇对环境的感知是人为给予的，也就是说这不同的3个指标的8个方向的数据都是实时的人为从环境中获得的。虽然这个vision的设定不是很能理解透，不过估计这个方向距离的起始点为蛇的蛇头点。

======================================================