Snake-AI 贪吃蛇AI的简易实现

贪心算法

寻找的局部最优解即贪吃蛇的头部到食物的最短路径，这种方法在一定程度上可以正常的运行，但在随着游戏过程的不断继续，蛇的身体会逐渐变长，只考虑蛇头和食物之间最短路径而忽略了身体的阻碍，只能获得少量的分数。

A*寻路算法

常见的寻路算法有很多种，比如经典的BFS、DFS、Dijkstra。关于BFS在贪吃蛇问题上的简易实现：

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]

   • 蛇首八个方向上

     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。