Project1

标题: 训练人工呆萌的方法 [打印本页]
作者: guoxiaomi    时间: 2018-10-20 22:03
标题: 训练人工呆萌的方法
本帖最后由 guoxiaomi 于 2018-10-30 13:33 编辑

填坑的间隙写一点关于AI的内容。

一、引言
在大部分游戏中，玩家和NPC需要不停做出决策。以RMXP的默认战斗为例，玩家需要控制4个角色，每回合从“攻击/特技/物品”等选项中选择一个行动，同时敌人也会根据游戏的设定选择行动，当所有的行动选择完毕后，程序会自动结算效果，播放动画并且进入下一回合。



制作者在设计游戏时，会对游戏的数值、NPC的策略进行反复的调整，从而使得游戏兼具可玩性和挑战性。取决于游戏本身的设定，预设的策略大部分时候比较简单直接。使用简单策略的敌人让很多战斗成为解谜游戏：面对不同的对手，只需采取针对性的策略就可以轻松获胜。让敌人面对不同的场合执行复杂行动的策略，比如模仿人类进行决策（“预判”，“集火”等），往往又很难去设计。原因主要是几乎所有的游戏都非常复杂，制作者受能力和精力限制，无法遍历到所有的情况，试图寻找“完美策略”的成本太高。

但是，有的时候游戏里需要一个能达到人类专家水准的 AI，通常因为有这样的考虑：

1. 对于“对称竞技游戏”，强有力的对手可以极大的提升游戏挑战性
2. 足够强大的 AI 可以找到数值设计中不合理的地方，辅助制作者对平衡性做特定的调整
3. AI 可以学习出超越人类水平的成果，从而给制作者和玩家新的启发

上面所提到的“人类专家”，其实就是指熟悉游戏规则并能做出较优决策的人。专家所拥有的知识称为“专家知识”。在训练 AI 的时候，采用“专家知识”的 AI 往往能很快收敛到最优水平，而不采用“专家知识”的 AI 则需要从零开始学习规则，但是可能学习出“专家知识”之外的，更好的策略。

本文会使用强化学习（Reinforcement Learning）的方法，给出有不同“专家知识”需求的 AI 的训练策略：从完全的专家知识到部分，甚至零专家知识。

二、强化学习简介

强化学习是机器学习的一个分支，特别适用于训练各种场合的 AI。简单的说，强化学习的模型分成两部分：“环境”（Environment）和“玩家”（Agent）。玩家拥有自己的“策略”（Policy），在每一个时刻，玩家都可以从环境中获取一些信息，并且综合成环境的特征（Features），并且这些特征被用于做出决策，从而采取一个合适的行动。当玩家采取了行动后，环境会给与一个奖励（Reward）反馈给玩家，并且更新内部的状态达到下一个环境。在新的环境里，玩家需要继续做出决策，直到环境进入中止状态。而玩家可以从环境的反馈中调整自己的策略，从而在不断的学习和探索中获得更高的奖励。

举一个简单的例子，这是一个阿尔西斯找宝箱的游戏。其中：



1. 阿尔西斯在每步都可以从环境中获得1个特征：当前的X坐标
2. 阿尔西斯在每个格子都可以做出决策“向左走”和“向右走”
3. 阿尔西斯在作出决策之后，环境会发生变化，使得阿尔西斯的X坐标沿着目标方向改变。
4. 如果阿尔西斯到达了宝箱的位置，环境会给与一个（+1）的分数，并且进入中止状态。
5. 如果总步数超过了 10，环境会进入中止状态。

而我们需要训练的策略参数是 p =“在X位置，向右走的概率”，显然，我们很容易找到最优的策略，就是 p = 1。

我们可以取不同的策略参数 p =（0.0，0.1，0.2，0.3，…… 1.0），对于某一个策略参数 p，可以多次让阿尔西斯按照此策略随机的进行左右摇摆，直到环境进入中止状态。然后统计平均得分，最后决定最好的策略参数 p。在这个过程中，复杂的真实游戏环境，被简化为 特征 + 反馈，而阿尔西斯从这些简化的数据中，通过反复的试错、探索，最终获得了优秀的策略（p > 0.7），这一过程就是强化学习。

三、强化学习面临的困难

如果环境变得复杂，这种策略就不是那么简单了，比如说增加了开关、敌人和地刺的“找宝箱2.0”：



1. 阿尔西斯在每步都可以从环境中获得2个特征：当前的X坐标，当前的Y坐标
2. 阿尔西斯在每个格子都可以做出决策“向左走”，“向右走”，“向上走”，“向下走”
3. 阿尔西斯在作出决策之后，环境会发生变化，使得阿尔西斯的X，Y坐标沿着目标方向改变
4. 如果阿尔西斯到达了宝箱的位置，环境会给与一个（+1）的分数，并且进入中止状态。
5. 如果阿尔西斯到达了敌人和地刺的位置，环境会给与一个（-1）的分数，并且进入中止状态。
6. 如果阿尔西斯到达了开关的位置，地刺会消失。
7. 如果总步数超过了 20，环境会进入中止状态。

而我们需要训练的策略参数是 p =“在X，Y位置，向D方向走的概率”。这个问题已经变得无比复杂。很显然，在只知道 X，Y坐标的信息的情况下，阿尔西斯无法区分“打开开关前的交叉点”和“打开开关后的交叉点”这两个状态的区别，从而任何“决定性”的策略都不会成功。我们也很容易找到一个最优的策略，由于数学知识不够，x 和 y 的值稍后补充：

1. 在交叉点，有x%的概率向上，100-x%的概率向右
2. 在交叉点上一格，有y%的概率向上，100-y%的概率向下
3. 在开关处，100%的概率向下
4. 在其他的位置，100%的概率向右

这一最优策略已经非常复杂，尤其是这个策略还是不是“决定性”的。即使在最优策略下，阿尔西斯也并不会像人类一样，径直朝着开关奔去，然后回到交叉点再向右直走拿走宝箱。而是反复在交叉点和开关之间来回踱步，甚至在未打开开关的情况下就走到地刺上求死。

怎么样才能让阿尔西斯像人类一样，做出最优、最短的路径决策呢？上面的找宝箱2.0其实隐藏了一个陷阱，即，阿尔西斯对整个环境并不是全知的。他拿到的信息只有X，Y坐标，连开关、宝箱、敌人的位置也不知道。而人类玩家一眼就能获取到这些信息。之前提到过，把从环境中提取到的，用于给阿尔西斯进行决策的综合信息称为“特征”（Features），选择不同的特征的将获得不同的决策。通常情况下，我们可以手动选取特征——利用“专家知识”——很显然，在这个游戏里，除了X，Y坐标，是否到达开关位置（S）也是很重要的“特征”。如果选取（X，Y，S）作为参数给阿尔西斯进行决策，那么最优的策略显而易见：

1. 在 S=false 时，径直走向开关
2. 在 S=true 时，径直走向宝箱

我们获得了一个决定性的策略，同时这也是和人类专家拥有相同水平的策略。这说明我们利用“专家知识”所选取的特征已经足以解决问题。对于更加复杂的游戏，比如说RMXP的默认战斗，有很多很多的特征可以选择：

1. 我方、敌人各角色的属性和状态：等级、HP、SP……战斗不能、中毒、沉默……装备有XX武器……
2. 我方、敌人的历史行动，当前的回合数
3. 采取的行动以及行动的性质：攻击计算式，属性克制，物品数量……
4. 特定剧情是否触发，开关X是否打开
5. ……

上面的特征，有些看上去非常重要，比如 HP，有些看上去就不是很关键，比如当前的回合数，所以如何选取所需的特征，使得 AI 能够做出和人类相似水平的策略，甚至超越人类水平的策略，本身就非常的困难。何况，即使用到了全部的特征，也有 2 个问题摆在眼前：

1. 特征并没有代表环境的全部信息：卡牌游戏中，对方的手牌是隐藏信息
2. 特征过于丰富，策略极其复杂，无法进行有效的训练：围棋

这两个问题会使得寻找“最优策略”陷入困境。万幸的是，在本文中，我们并不是要找到“最优策略”，而是介绍几个简单的训练人类专家水平 AI 的方法，这些方法计算量较小，具有可操作性，可以用在实际的游戏设计中。

四、决策方案

刚刚的例子里，我们直接采取了“在 X 位置，以概率 p 向 D 方向移动”的策略。这是一种随机策略，同样，也可以有决定性的策略：“在 X 位置，向 D 方向移动”，此时的策略参数就是 D。这两个决策方案，其实都是决策树。我对决策树的知识了解很少，但是决策树的直观表现就是，在不同的条件下进行（单向的）跳转，最终跳转到某个“终止”节点，并且返回此节点对应的行动。决策树里每一个跳转的条件，都可能附带有参数，这些参数是可以进行训练的，从而获得最好的决策方案。



显然，决策树需要很多的“专家知识”来编写，而且不同结构的决策树，对应的 AI 行动风格、最终训练结果也不一样，甚至达不到期望的水平。尽管如此，对于简单的问题，决策树无论是设计还是训练都非常的简单，是一个很好的模型。

还有一种模型是“值函数”（Value Function）。值函数会对读取到的 Features 进行评估，并且给出一个数值来表示 Features 的价值。不仅如此，值函数还可以综合当前可以采取的行动，进行评估，给出“在当前状态下，采取某一个行动”的价值 Q(State, Action) 。自然，有一个合适的值函数可以直接给出行动的参考：直接选择值函数最大的行动，或者，以更高的概率选择值函数最大的行动。

拿前面的“找宝箱游戏”举例，可能训练的结果如下：
决策树：


值函数：

位置向左走向右走
00.40.6
10.21.0
.........


五、环境反馈设置

首先我们要设计好一个实际的 reward 反馈，通常大家就是简单的这么一写，这样试图获得更高分数的 AI 就是试图达到更高的成功率，并降低失败率。

1. 达到成功的终止状态给（+1）
2. 达到失败的终止状态给（-1）

实际上，上面这种简单的 reward 已经足够了。试图以精细调整 reward 而控制 AI 训练结果都是不理智的行为。对于游戏设计者，应该可以脱离RMXP的原始系统，只保留决策和演化的部分用于训练。这样会快很多。

六、训练决策树

决策树中的参数可以是离散的或者是连续的。首先随机初始化这些参数，对于离散的参数，可以先随机取一个值；对于连续的参数，大致设一个覆盖范围，用高斯分布来随机取值 x = N(x0, σ)。如果参数设计的合适，离散的参数也可以用高斯分布来随机取值，下面就假设所有的参数 x 都可以用高斯分布 N(x0, σ) 取值。



每一次随机的初始化，都可以得到一个决策树。使用这些决策树在游戏中实际操作，并对这些决策树的水平进行评估：直接计算平均得分即可。比如说有 100 个决策树，按照得分排序之后，前 20 个决策树被选出来。对这 20 个决策树的每一个参数 x，可以统计出平均值 x0 和标准差 σ，作为下一次随机生成决策树的高斯分布的平均值和标准差的取值。

如此循环筛选多次，当标准差 σ 小于某个特定值的时候，就可以认为合适的中心参数 x0已经被筛选出来了。如果这个方法收敛的很慢，那就看看决策树是不是设计的不够合理。此外可以多试试不同的初始参数，重复练习。

然后我忘了这个算法的名字了。当然，无梯度的优化算法有很多种，上面只是一个也许还行的简单算法。重要的是基于“专家策略”的决策树要设计的好，这样才能既快速收敛，又能达到接近人类的水平。

六、训练价值网络

我们使用 SARSA 算法来训练价值网络，为了使计算加快，问题简化，使用线性函数而不是用神经网络。请参考这里的内容：https://artint.info/2e/html/ArtInt2e.Ch12.S9.SS1.html

首先，基于专家知识，找到合适的 State + Action -> Feature 的对应关系。相比于决策树，这里的 Features 可以更杂乱，等于是减少了对专家知识的需求。简单的方案是所有的 Features 只用 0 和 1两个值，也可以是之外的数。比如：

0. F(0) = 1
1. 当角色1死亡时，F(1) = 1，否则为 0
2. 当角色1被沉默，且使用魔法类特技时，F(2) = 1，否则为 0
3. 当角色1的HP>200，且使用防御时，F(3) = 1，否则为 0
4. F(4) = 角色1的 SP 百分比
5. F(5) = 角色1中毒状态持续回合数
...

Features 最好能够包含状态和可能采取的行动两方面的信息，并且越多越好。那么结合每一个 Feature 的权重 w，值函数可以这样表示出来：
  1. Q(s, a) = w0 + w1 * F1(s, a) + w2 * F2(s, a) + ...
复制代码

如果权重已经训练好，在每一次决策之前，总结一下可以采取的全部行动，假设一个角色可以采取10种行动，4个角色也不过区区10000种，直接穷举所有的 Q(s, a)，取Q最大的行动就行。当然，也可以利用决策树减少行动的数量。

训练权重 w 的方法很简单。首先，随机初始化权重，让 AI 自由玩耍，但是要统计每一步决策前的 Features 和这一步的 Action，称之为“积累经验”，AI 在选取行动的时候，有一定的概率随机走一步，一般取个 0.1：
0. 游戏开始
1. 记录此时的 状态 s0，对所有的行动穷举得到特征 f0(s, a)，结合权重计算所有的 Q0(s, a)，选择的“最佳”行动 a0，游戏执行一步，返回奖励 r0。
2. 记录此时的 状态 s1，对所有的行动穷举得到特征 f1(s, a)，结合权重计算所有的 Q1(s, a)，选择的“最佳”行动 a1，游戏执行一步，返回奖励 r1。
...
N. 游戏终止

注：非常重要的是，在积累经验的时候，AI 会以 e = 0.1 的概率随机走一步，而不是采取Q值最大的行动。

对于每一个行动，记录这些量，如果下一步游戏就终止了，那么不需要下一步的特征：
  1. [当前的特征 f(s, a), 获得的奖励 r, 下一步的特征 f(s', a')]
复制代码

每一个这样的数据就是一条“经验”

当完成了足够多的盘数后，经验已经积累的很多了，就可以开始“训练权重”了。其实也可以每获得一条经验就训练一次。

然后对于每一条经验，计算出 TD_Error 的值，这里的 g 是衰减因子，随便写个 g = 0.9~0.99，基本没啥问题：
  1. td_error = r + g * Q(s', a') - Q(s, a)
复制代码

由于我们已经知道了 f(s, a) 的值，Q(s, a) 只需要挨个乘上对应的权重就行了。对于没有后继步的经验，Q(s', a') = 0。
有了 td_error 就可以更新权重了，对于第 n 个权重：
  1. w[n] += a * td_error * F[n]
复制代码

其中 a 是学习率，基本上从 0.0001 -> 0.0003 -> 0.001 -> 0.003 -> 0.01 -> ... 这样取值，可以试试哪个最合适，一般就取个 a = 0.003 拉倒……

学习完毕之后，就可以继续用新的权重参数，让 AI 继续去积累经验，自己感觉差不多的时候就停吧，这个比较说不准。最好是有一个固定的判据（比如平均分）来评价 AI 的能力。

七、实践出真知
多说无益，我们直接使用上面的两种方案，训练 找宝箱2.0 的 AI！（未完待续）
作者: guoxiaomi    时间: 2018-10-20 23:58
本帖最后由 guoxiaomi 于 2018-10-30 15:52 编辑

先放一个利用强化学习生成卡牌游戏《Card of Spirits》的例子：https://gitlab.com/gxm/rl-cos

使用遗传算法来完成阿尔西斯找宝藏的游戏，因为numpy库对科学计算的良好支持，所以这里用python来写。首先，需要构造一个环境：env.py，里面构造了4个地图，难度依次提升。
具体代码见这里：https://gitee.com/rmxp/codes/x35j704ycudg9va62bmzw30
图中，S=起点，T=陷阱，C=宝箱，M=怪兽，L=开关，+=墙壁，.=通道
PYTHON 代码复制
  1. class FindChest:
  2.     MAP01 = [
  3.         '+++++++++',
  4.         '++++L++++',
  5.         '++++.++++',
  6.         '+S...T.C+',
  7.         '++++.++++',
  8.         '++++M++++',
  9.         '+++++++++'
  10.     ]
  11.  
  12.     MAP02 = [
  13.         '+++++++++',
  14.         '+++L..+M+',
  15.         '++++.++.+',
  16.         '+S...T..+',
  17.         '++++.++.+',
  18.         '++++M++C+',
  19.         '+++++++++'
  20.     ]
  21.  
  22.     MAP03 = [
  23.         '+++++++++',
  24.         '++L....M+',
  25.         '++++.++.+',
  26.         '+S...T..+',
  27.         '++++.++.+',
  28.         '++++M++C+',
  29.         '+++++++++'
  30.     ]
  31.  
  32.     MAP04 = [
  33.         '+++++++++',
  34.         '++L....M+',
  35.         '++++.++.+',
  36.         '+S....T.+',
  37.         '+.++.++.+',
  38.         '+....M+C+',
  39.         '+++++++++'
  40.     ]

设定的策略参数为在 (x, y) 处，当开关的状态 s={0, 1} 时，切换横、竖行走方向的概率（1-p0）和向左（如果沿x轴）、下（如果沿y轴）方行走的概率p1。这样就把原先离散的选择X方向行动改成了连续的概率取值。这个参数可以用 9x6x2x2 的实数矩阵表示。
无理由假定最优策略以及次优策略的参数满足某个高斯分布，接下来用遗传算法来优化参数。


进行如下操作：
1. 随机初始化参数矩阵里的每一个值，取平均值=0.5，标准差=0.5
2. 用这样的平均值和标准差制作100个agent，每个agent尝试1000次，统计成功的次数作为得分
3. 取出分数最高的10个agent，计算这10个agent的参数矩阵的平均值和标准差
4. 回到2继续迭代，直到策略收敛（这里是成功率超过0.99，或者迭代次数超过100）

对于最复杂的地图4，可以看到：
1. 8 次迭代后，遗传算法出现了第一批能成功得分的agent
2. 13 次迭代后，遗传算法得到了得分超过0.5的agent，并且优化的速度非常快
3. 25 次迭代后，得到了超过0.99分的agent
MATLAB 代码复制
  1. [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
  2. [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
  3. [0.003 0.    0.    0.    0.    0.    0.    0.    0.    0.   ]
  4. [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
  5. [0.001 0.    0.    0.    0.    0.    0.    0.    0.    0.   ]
  6. [0.001 0.    0.    0.    0.    0.    0.    0.    0.    0.   ]
  7. [0.007 0.007 0.    0.    0.    0.    0.    0.    0.    0.   ]
  8. [0.005 0.002 0.002 0.001 0.001 0.001 0.    0.    0.    0.   ]
  9. [0.09  0.041 0.036 0.024 0.021 0.017 0.015 0.009 0.009 0.008]
  10. [0.175 0.11  0.102 0.1   0.09  0.078 0.076 0.074 0.072 0.071]
  11. [0.285 0.278 0.254 0.252 0.216 0.213 0.197 0.186 0.173 0.169]
  12. [0.416 0.374 0.356 0.35  0.344 0.323 0.315 0.313 0.293 0.292]
  13. [0.542 0.531 0.514 0.503 0.49  0.474 0.471 0.47  0.464 0.454]
  14. [0.622 0.618 0.616 0.603 0.597 0.594 0.591 0.586 0.584 0.578]
  15. [0.783 0.766 0.739 0.728 0.722 0.717 0.713 0.709 0.699 0.697]
  16. [0.864 0.833 0.826 0.818 0.816 0.803 0.799 0.797 0.796 0.791]
  17. [0.897 0.883 0.882 0.878 0.873 0.871 0.865 0.863 0.858 0.852]
  18. [0.927 0.926 0.926 0.926 0.925 0.911 0.91  0.909 0.907 0.907]
  19. [0.947 0.946 0.945 0.939 0.936 0.936 0.935 0.934 0.929 0.926]
  20. [0.974 0.969 0.965 0.964 0.961 0.961 0.959 0.957 0.956 0.956]
  21. [0.984 0.979 0.977 0.977 0.975 0.975 0.974 0.974 0.973 0.973]
  22. [0.984 0.983 0.982 0.982 0.981 0.981 0.981 0.981 0.978 0.977]
  23. [0.985 0.985 0.984 0.983 0.982 0.982 0.982 0.982 0.982 0.981]
  24. [0.99  0.988 0.987 0.986 0.985 0.985 0.985 0.985 0.984 0.984]
  25. [0.991 0.99  0.989 0.988 0.987 0.986 0.986 0.985 0.985 0.985]

遗传算法并不稳定，可能陷入局部极小值。
为了训练出>0.99分的agent，总共进行了25*100*1000 ~ 10^6 局游戏。这一数据可以与其他的机器学习方法比较。
对于找宝藏的游戏，利用“专家知识”可以选择出合适的特征和决策方案，进而使用遗传算法筛选出得分高的agent。

对于传统的RPG游戏，自然也可以利用专家知识预设好概率性的决策方案，并留下大量的（连续）参数供调整，比如：
1. 在生命低于x的时候有y的概率攻击
2. 有x的概率选择生命值最多的目标
3. 队友生命值低于x的时候有y的概率治疗
等等……

然后构造不同的测试条件，使用上面的方法测试agent的能力，淘汰得分低的agent，不断迭代获得最优的待定参数。
其优点为：训练思路简单粗暴，充分利用专家知识
作者: 89444640    时间: 2018-10-21 11:48
前面看的明白，后面代码那边就完了，只能看个意思……因此思考了一下rpg回合制战斗，

乱敏是基础，因为这个会直接干扰到决策的可能性问题，也就是意外，
敌人boss在一般情况下是1对3~4，难打的情况可以考虑知名rpg ff或者dq中的难打boss策略从而进行模拟。
在属性克制明显的游戏中，让敌人ai可以读取我方当前所有角色的属性抗性以及弱点是个好方法，既可以针对己方弱点有限攻击有巨大属性弱点的角色，也可以利用抗性弱点造成己方角色不能行动。比如经典的臭气息。
敌人bosshp不列为考虑
因此敌人第一回合会有几个决策，
1 集中攻击我方，某属性抗性低的角色 2 削弱我方全体hp 3 针对某角色弱点，进行干扰行动，造成一个或多个角色行动不能
在我方受到损伤的情况下，需要让敌人能读取我方的当前hp和剩余mp状态，甚至可以读取我方当前招式配置，从而预测下回合我方可能会使用的招式，
从而进行优化的处理，有几种处理方式
1 歼灭输出最高的敌人优先使其尽量一直处于不能行动或战斗不能状态 2 歼灭会用招式回复群体hp的角色 3 歼灭速度快的角色（以内最可能先行动，用药或者进攻）4歼灭有明显属性弱点的角色 5 使有异常抗性弱点的人处于行动不能状态
然后ai训练，可以针对玩家攻击选择进行针对性对抗，就是说针对玩家在这个迷宫里的表现，杂鱼积累给boss，让boss运用针对性策略，比如某玩家喜欢上来先加个状态，然后再攻击，ai就优先就干扰他用状态角色的。

这些到底应该怎么处理才更接近人类的思考方式……感觉上都可以，但是如果光用一种也是会显得比较“死”，输了几次后摸到敌人规律，应该可以制定针对性策略，从而胜利，太高了boss绝对打不过，
因为平衡做好了，打boss就是凭借人类处理问题灵活，ai过高把所有可能性都给封死了就惨啦，再加上boss设置的属，会比角色高很多，这个平衡点似乎不太好找啊，如果做这个是否还需要做个难度分级呢？
作者: fux2    时间: 2018-10-31 10:01
专业性比较强了，但还是希望可以帮到一些需要的朋友



欢迎光临 Project1 (https://rpg.blue/) Powered by Discuz! X3.1