打圈问题优化；

前文提到，针对迭代收敛差的问题，主要考虑

1. 对 snake状态表示 增加方向状态
2. 减少动作循环（转圈）时 reward 的惩罚

目前上述两个方法都已经尝试。

1. 对snake状态表示，目前定义如下：

   特征类型	特征个数	每个特征取值	总特征空间
   头距离四周障碍距离	4 （上、下、左、右）	3个 （0、1、2+）	$3^4$
   头距离food的距离	2 （横、纵）	3个 （0，正距离，负距离）	$3^2$
   头方向	1	4（上、下、左、右）	4

   相比之前，变更如下：

   1. 新增头方向，为了稳妥，直接取了4个方向；
   2. 对距离取值做了裁剪，状态数变少（可能有负面影响，未进一步分析）

   同时也把这块代码重写了——之前写得太糙了。

2. 对转圈惩罚，简单地将其损失设置为

    _step_after_last_gain += 1
    _ref_len = game_state.state_width + game_state.state_height
    times = _step_after_last_gain // _ref_len
    reward = - 1 / 1000 * min(times, 100000)
   

   之前是 -1/1000 * 10^times, reward 直接 overflow 了（QTable用的是numpy）……

上述改动后，比之前似乎是好了一点——看起来分数能到20+了；但是，转圈问题依然得到解决。同时上述reward的惩罚，还是不够合理：惩罚依然是随机的。

打圈问题优化

为什么会打圈。一种想法是，状态空间有点小，会不会不同的状态，在状态表征上一样，导致了行为冲突？这有一定的可能性，至少增大了打圈的概率吧。

但考虑打圈问题本质，还是snake的状态表征刻画不了打圈——也就是，虽然它在打圈，但是snake自己不知道。 这种咋整——在NN里面，那肯定得上序列建模啊——或者用规则特殊处理。在 QLearning 下，序列建模应该是不行，不太可能把长串的历史状态也给记录下来。 那我们就只能加手工特征： 是否在打圈！ 这样snake就能显式地知道自己在打圈了。难点就是怎么做这个特征了。

最后，reward针对打圈问题的惩罚是随机的，这可能破坏已经学好的一些处理逻辑。不过，如果我们的状态包含了“是否在打圈”，可能这个破坏影响也还好。

综上简单分析，当务之急还是先把“是否在打圈”给加上。然后再看看效果。

“是否在打圈”特征

简单地，我们记录下在吃到食物前，snake头走过的位置集合。如果新位置在已走过的位置，那就直接认为它在打圈。也就是说，重复踩之前的位置，就认为在打圈。 这个判定实现起来简单，但没有直接判定”是否在打圈“。试试吧，说不定就足够了——一般情况下，头不需要回到以前走过的位置。

=> 结果出来了，从训练过程来看，打圈的概率大大降低了！ 果然有用呢！

现在训练出来，可以跑30+分了！

看起来这个问题被轻松解决了…… 下一步，还是对reward做一下改进吧。

打圈 reward 改进

想了一下，感觉从 限时 的维度惩罚“打圈”逻辑上更好一点。也就是说，snake游戏要新增一个设置：在吃到下一个food前，不能超过x步。 这个逻辑上是合理的，毕竟如果不合理，那打圈也没有坏处——因为只要没死，我这 snake 不就没问题吗？所以，snake的确应该定义为， 在有限时间中，不死情况下最多吃到的食物量。之前的snake没有限定时间，那么QLearning学到打圈，就相当于学会了“不死”。如果不是reward特殊惩罚， 那的确也没有打的问题。

只要我们的游戏增加了限时，那么理论上也就没必要在reward层面对打圈惩罚了——超过时间，直接FAIL给惩罚。不过，也许区分撞墙和超时， 甚至针对吃到食物时的难度调整reward，效果会更好？这都是后话，先把游戏机制改下吧……

snake 游戏增加最大步数限定

如上，增加最大步数限定。每一个吃食物的周期中，我们的步数上限设置如下：

def _calc_max_remaining_steps(game_state: SnakeStateMachine):
    """Calc max remaing steps. 
    currently we naively impl it:
        1. if only 1 node, go to food, need max `Width + Height`
        2. for a snake line, the head need to bypass the body, most at `snake-body`
        3. duplicated operations, at most 1.2 -> 2 times (when body short, duplicated op should be less)
    """
    _dist_base = game_state.state_width + game_state.state_height
    _body_len_base = len(game_state.snake)
    _multiplier =  1.2 + 0.8 * (_body_len_base / (game_state.state_width * game_state.state_height))
    _max_val = (_dist_base + _body_len_base) * _multiplier
    _max_val = int(_max_val)
    return _max_val

注释已经说明了大概的考虑。不算精确，但也没有太大的问题。

改动后，考虑到以后还可能基于此做NN的方法，有必要把head、方向突出出来，因此还把渲染部分改动了下。现在变成一条彩色的蛇了，哈哈

随后把 reward 中对打圈惩罚的逻辑去掉。重新训练，从效果上，似乎的确也达到了避免打圈的效果。但同等迭代轮次下，似乎有点不稳定…… 一次上来2分就挂了，另外两次到了40分。

先这样，最后再试试扩距离呢。

扩大距离表示

我们先把障碍距离给拉开一些。目前是 $0,1,2+$, 相当于除了碰撞死亡、紧靠，就只有一种状态了。有必要把距离再拆开一点，让蛇知道安全与危险距离。

=> 效果并不好。

因为效果不好，还把距离的度量给改了。具体地，取消了方向，把方向放到障碍距离中了。理论上是等价的。

目前看来，似乎效果不如之前了…… 有改了下reward，还是不怎么样。 额，感觉做的方法不太OK啊

结论

今天弄了小一天，总结来看：

1. 通过增加“是否重复”，配合一定步数的reward惩罚，基本解决了打圈问题
2. 改变了游戏机制，增加了步数限制，去掉了一定步数的reward惩罚，也基本解决了打圈
3. 扩大了距离表示，效果不好；增大训练轮次到10W，依然不好

目前对QLearning方法有点想放弃了——能够很明显的看到局限性：需要手工编码特征；而当前的特征，显然不太行：

1. 不能轻松、准确的表达“转圈”等无效动作
2. 建模的空间太小，只看到snake距离障碍（body+墙）的距离和到food的方向，导致出来的行为基本不是最优：明明快到了，却突然拐弯。

此外，目前还缺失定量的评估效果的脚本，现在都是改动后仅凭手工跑几次来确认效果，远不可靠；需要一个自动评估脚本。

最后，写QLearning的目标是学算法的，然而最后QLearning的贝尔曼公式就直接照着别人写了一遍，其余时间都是在整状态编码，有点本末倒置了。 毕竟贪吃蛇本身是无意义的，有意义的是算法本身。当然，也不能说毫无收获，显然现在知道QLearning的缺陷了：

1. 需要手工编码状态
2. 状态空间全离散，导致空间不可接受的大——比如说4个方向距离的距离，组合的特征空间size就是 $x^4$，$x$ 是距离的取值。这个规模还是有些太大了。 如果直接用现在图像上的编码，不过就是图片的大小，理论上就可以编码所有的特征了（期望吧，后面做 DQL 看看）。
3. reward 的设计挺难的

综上，QLearning 模型挺难学的——需要正确的编码输入，特征空间受限于规模不够有区分性，最后reward需要设计且强化学习天然面临的reward稀疏问题。 好了，先到这里吧。