Snake-AI 贪吃蛇AI的简易实现，神经网络和遗传算法.zip

# Snake-AI 贪吃蛇AI的简易实现 ## 贪心算法 寻找的局部最优解即贪吃蛇的头部到食物的最短路径，这种方法在一定程度上可以正常的运行，但在随着游戏过程的不断继续，蛇的身体会逐渐变长，只考虑蛇头和食物之间最短路径而忽略了身体的阻碍，只能获得少量的分数。 ## A*寻路算法 常见的寻路算法有很多种，比如经典的BFS、DFS、Dijkstra。关于BFS在贪吃蛇问题上的简易实现： ```go func BFS(graph *Graph, start *Node) { frontier := NewQueue() frontier.Push(food) reached := make(map[*Node]bool) reached[food] = true for !frontier.Empty() { current := frontier.Pop() for _, next := range graph.Neighbors(current) { if !reached[next] { frontier.Push(next) reached[next] = true } } } } ``` 不过BFS资源开销过大，而A*算法既可以找到最短路径也没有搜索很多格子。 但是A*算法也不能通关贪吃蛇。因为在某些情况下“局部最优解”并不是“全局最优解”，比如蛇会走入死胡同但是没有办法回头，这就是游戏性质导致的问题。 ## 遗传算法和神经网络 > 参考：https://www.youtube.com/watch?v=vhiO4WsHA6c&t=171s 其中 - 神经网络用来预测运动方向 - 遗传算法用来优化神经元参数 #### 神经网络 1. 有一个输入层，两个隐层，一个输出层。神经元数量分别是：[32,20,12,4] 2. 隐层激活函数：ReLU，输出层激活函数Sigmoid 3. 输入层有 - 蛇首方向：[1,0,0,0] - 蛇尾方向：[0,0,0,1] - 蛇首八个方向上 ```go dirs := [][]int{{0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}} ``` - 是否有食物 - 是否有身体 - 与边缘的距离 例如： ``` state = [0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1] ``` 4. 输出层代表移动的四个方向 ### 遗传算法 1. 适应度函数：fitness = (frames) + (2^score + (score^2.1)*500) - (((0.25 * frames)^1.3) * (score^1.2)) frames可以用steps代替，即贪吃蛇的存活时间 2. 进化的方式： - 精英选择 TOP10% - 轮盘选择 - 杂交 单点交叉 - 变异 高斯变异 当种群规模足够并且进化到一定程度时，我们就可以看到贪吃蛇游戏的通过全过程。 ## 万能的实现 可以通过让蛇不断的绕圈来实现一个解空间，只是比较浪费时间而已。 ## 后续 可改进的方向：适应度函数，神经网络优化，进化过程的改进。 本仓库只是作为机器学习初学者的一个小demo，还有诸多不足的地方，欢迎pr。 在调试的时候请在终端上进行调试，termbox会在IDE环境下panic，如果不能复现结果欢迎提交issue。