某手势小游戏-人工智能
我们班有许多人玩这个游戏的，于是我和 xhj 就开始研究这东西的较优策略。
规则
这个游戏有一个变量 气。
玩家出招需要用到气，当气不够的时候直接死亡。
谁先杀死对方取胜。
- 攒气 耗气 -1
- 单枪 耗气 1 克(1)
- 双枪 耗气 2 克(1,2,4)
- 防御 耗气 0
- 反弹 耗气 1 克(2,3)
以这个规则来看，第一招肯定是攒气。
算法1
首先，我们想到了运用字符串匹配算法，预测对手出招，并以此来选择招数对付。
我们可以把对手所有局出的所有招数合成一个字符串 save。
[1, 4, 2, 1, 1, 5, 1, 9(局中空格), 3 ...]
把当前局一局对手出过的招数合成字符串 now。
我们每次把 now 的所有后缀在 save 中匹配一下，保存所有匹配到的字符串下一个字符（对方可能出的招数）出现的次数。
然后每次选择出现次数最多的就行了。
我们除了
A
C
AC
AC自动机 以外没有什么好的算法可以来做这个工作了，但是
A
C
AC
AC自动机 时间复杂度也很高。
于是我们尝试改进这个算法
改进
我们打算简化这个算法。我们每次选择长度为
5
5
5 的后缀来匹配就行了，并且只保留
1000
1000
1000 个 save 里的东西。然后直接用
K
M
P
KMP
KMP 来计算就行了。
算法2
我又尝试了另一种算法，我们将所有招数路径（第一个到第
n
n
n 个招数形成的路径），到一个
t
r
i
e
trie
trie 树里。
对于每一种走法，我们给他一个权值，代表当前路径的优劣度。
我们每次出招时，都会在
t
r
i
e
trie
trie 树的一个节点里，我们每次选择权值最高的节点，对于有多个相同节点的情况，我们随机选择一个。
这个权值在输的时候会减一，赢的时候会加一。
我们会发现，这个招数路径无限的长，因为我们没有招数长度限制。
我们直接采用动态开点，直到这个权值不为
0
0
0 ，才增加。
这个版本对战随机出招程序大致打平了。
改进
我们反思改进，发现这个算法可能会出现陷入某个局部最优解情况。
我们于是加了一个 rand()，让他有几率不遵从这个条件，他会随机选择一个数。
这样就可以有几率发现另一条更好的路径了。
这个版本和随机对战，得到了
65000
:
34000
65000:34000
65000:34000 （右边是随机）的好成绩。
和有一定规律的随机对战，变成了
34000
:
65000
34000:65000
34000:65000。
这个随机版本是随机，然后添加一些关于双方气的判断，比如说当自己气为
2
2
2 ，对方气为
0
0
0 时，直接出
3
3
3，这样对方必死。
这个版本和上面的
K
M
P
KMP
KMP 改进算法结合后，把比分变成了
4832
:
5168
4832:5168
4832:5168，因为时间复杂度太高了，只能跑这么多次
大家有没有什么好算法，可以评论一下。