魔塔小游戏中的AI(三)

当我们实现了建图以后,就面临了最大的问题:算法问题。

首先,如果在不考虑使用一些人工智能算法比如神经网络、遗传算法等,也不考虑随机算法如蒙特卡洛算法等的情况下,无疑只能采用最常见的搜索。

那么,应该怎么搜索呢?

深搜的尝试

最naïve的方法,无疑是带有回溯的深度优先搜索,其大概算法描述如下:

  1. 如果当前能直接拿到宝物,则把宝物拿光。
  2. 对于其他每个不是宝物的节点,尝试走该节点;在此过程中记录哪些点已经走过。
  3. 重复1-2,直到不能走了就回溯,然后选择下一条路。

理论上而言,这种naïve的深搜方法,是可以尝试所有可能性的,一定能得到解。但是事实证明,根本不可能得到结果,其复杂度大概是消耗节点(门或者怪物的节点)的全排列,根本不可能在合理的时间内实现!

因此,如果要使用深搜,就必须加条件,也就是我们所说的“估值函数”。我考虑的估值函数综合了勇士的生命、攻防、钥匙等数量,其表达式如下:

score=hp+1000*(atk+def)+60*mdef+300*yellow+450*blue+600*red

然后,让勇士每次搜索k步,找到每种情况的最终状态进行评分,并选择最好的最终状态的分数作为这个方向的最终评分。

然而,却无法得到解。倒不是没有输出,而是解法根本没办法战胜Boss,甚至靠近都不能!不管怎么改变估值函数和步数k,都是不可行的。

另外一个问题就是,在深搜过程中,需要不断进行节点的合并操作,而回溯过程中则需要不断将合并后的节点进行分离,这样的合并和分离操作是非常耗时的,这也是深搜最大的问题之一。

而且最关键的是,对于下面这张图:

一开始给了个蓝钥匙,而Boss面前有个蓝门。如果我们随意开蓝门的话,可能导致Boss面前的蓝门无法开启!而这个,却是我们的DFS所完全无法解决的。

这么多问题,促使我最后放弃了深度优先搜索。

广度优先搜索

深搜不可行后,自然就想到了广度优先搜索(BFS)。

如果要广度优先搜索,那么就必须用一个队列来记录当前已经探索过的情况,每次从队首弹出一个元素进行扩展,扩展后的元素放入队列等待下次使用。

而相比DFS,使用BFS会面临几个比较大的问题,将在下面一一进行阐述。

地图状态的保存

在广度优先搜索里,一个非常大的问题就是:如何保存每一步探索的状态?

很容易想到的是,在状态中记录整张图的信息。每次我取出一个状态,选择一个节点,然后合并节点(重构整张图),并将新的图存入新的状态。

但是这样,每个状态都有一份截然不同的全图信息,这样需要消耗极为大量的内存,事实证明是不可行的。

那么,能否不用每次都拷贝一遍全图,而是只记录“变化”的部分呢?

可以的,有一种很巧妙的算法。

[java]
1
2
3
4
5
6
7
8
9
10
11
12
13
// 状态类
public class State {
    // 当前勇士所在的节点(活跃节点)
    Node current;
    // 初始的原图信息;所有状态的Graph都是相同的。
    Graph graph;
    // 某个节点是否已经访问过。
    boolean[] visited;
    // 到当前状态,所经过的节点路径。
    ArrayList<String> route;
    // 到当前状态,所经过的消耗节点数目。
    int cnt;
}

上面是状态类,下面将进行详细分析:

  • Node current 为“活跃节点”,也就是勇士当前所在的节点。初始时current为List中的0号节点。(还记得Node类的定义里有个Hero吗?只有“活跃节点”它才不为NULL。)
  • Graph graph 记录了初始的原图信息。这个信息是不会改变的,所有状态的Graph都是相同的。
  • boolean[] visited 记录了,每个节点是否被访问过。其长度大小为graph中的List长度。我们实际上只需要记录哪些点已经被访问过即可。
  • ArrayList<String> route 记录了,到当前状态所经过的节点路径。我们最终只需要输出最终状态的route即可。
  • int cnt 代表了到当前状态,所经过的消耗节点(含有门或怪物的节点)数目。有关这一点之后会再详细说明。

而在搜索的过程中:每次从活跃节点的邻接节点中寻找一个visited为true的消耗节点,将消耗节点的内容合并到活跃节点上,并把visited标true。

换句话说,我们实际上是每次都构建了一个新的活跃节点,它是原活跃节点和某个正常节点的合并。而我们只需要考虑从合并之后的活跃节点向外出发,不用考虑别的节点如何回来。
因此,我们只需要设置好活跃节点的出边,并不需要对原图中的任何边进行改变,换句话说,我们的合并后的活跃节点对于原图的拓扑结构不会有任何影响。

因此,我们只需要存当前的活跃节点,以及我已经走过了哪些节点(visited数组);通过这种方式,就可以很容易保存地图的状态了。

节点的合并,状态的转移

下一个问题就是,如何合并节点,进而进行状态的转移操作。

节点的合并其实很容易实现:

[java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 合并当前节点和另一个节点,visited为已经访问过的节点
public Node merge(Node another, boolean[] visited) {
    // 创建一个新的节点,是当前节点的拷贝
    Node node = new Node(type, new Hero(hero), null, null, 0,
            another.f, another.x, another.y);
    node.linked = new HashSet<>(linked);

    // 如果存在宝物:获得宝物
    if (another.item!=null)
        node.hero.getItem(another.item);

    // 如果存在门:开门
    for (int v: another.doors) {
        if (v==1) node.hero.yellow--;
        if (v==2) node.hero.blue--;
        if (v==3) node.hero.red--;
    }

    // 如果存在怪物:战斗并削减生命值
    for (Monster monster: another.monsters) {
        node.hero.hp -= Util.getDamage(node.hero, monster);
    }

    // 不合法的勇士状态
    if (!node.hero.isValid())
        return null;

    // 合并邻接节点
    for (Node to: another.linked) {
        if (!visited[to.id])
            node.addNode(to);
    }

    return node;
}

这样合并了节点后,我们就可以进一步进行状态的转移:

[java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 将当前状态通过与某个节点合并,从而转移到另一个状态
public State merge(Node node) {
    // 确保节点没有被访问过,而且可以进行转移
    if (visited[node.id] || !current.linked.contains(node))
        return null;
    // 进行节点的合并
    Node another = current.merge(node, visited);
    // 合并后的节点不合法
    if (another==null) return null;
    // 将新节点覆盖到当前节点
    current=another;
    // 标记节点已被访问
    visited[node.id]=true;
    // 记录路径
    route.add(current.toString());
    // 尽可能去吃掉新节点周围的宝物
    eatItem();
    // 记录消耗节点的个数
    cnt++;
    return this;
}

而,贪心地尽可能去吃掉周边宝物的代码如下,也十分简单。

[java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 尽可能吃掉周边宝物
public void eatItem() {
    boolean has=true;
    while (has) {
        has=false;
        for (Node node: current.linked) {
            if (visited[node.id]) continue;
            if (!node.shouldEat(current.hero)) continue;
            has=true;
            current=current.merge(node, visited);
            visited[node.id]=true;
            break;
        }
    }
}

注意到我们每次是吃了一个节点后,立刻重新开始遍历,以免出现问题。

停止搜索的条件

我们可以设置什么时候停止继续向下搜索,并记录当前结果,再选择一个最好的结果输出。

停止条件可以设置为如下几种:

  • 搜索到了一定数量的消耗节点,即state中的cnt大于某个数。该条件主要是为了避免状态数过多,一般建议40-50之间比较合适。
  • (如果存在Boss)打败Boss,也就是Boss节点的visited为true。
  • 其他自定义的停止条件,比如冲到商店啊,拿到红钥匙为止啊,等等;可以根据具体的塔来分别设置不同的停止搜索条件。

状态的表示

另一个要注意的点就是,如何表示某个状态是否已经计算过,从而避免重复计算?

我们可以直接使用visited数组表示,将visited数组转成01字符串,再转成long型结构,并使用HashSet来进行记录。

而且,我们不需要记录所有的节点,而是可以只考虑消耗节点。这是因为,宝物节点总是会贪心地被吃掉,因此如果消耗节点固定了,那么宝物节点也会被固定。

所以,可以用如下代码来对State进行hash:

[java]
1
2
3
4
5
6
7
8
9
10
public long hash() {
    long val=0;
    int i=0;
    for (Node node: graph.list) {
        if (node.doors.isEmpty() && node.monsters.isEmpty()) continue;
        if (visited[node.id]) val|=(1L<<i);
        i++;
    }
    return val;
}

优先队列的设计

在广度优先搜索中,队列是非常重要的,其直接关系到搜索顺序,进而影响到搜索结果。

在最初,我直接采用如下的估值函数来对状态进行估值分析(对于不同的塔,设置参数有所不同):

score=hp+1000*(atk+def)+60*mdef+300*yellow+450*blue+600*red

但是,这样往往会出现一个问题,例如还是这个图:

使用直接的估值函数,会在打败黑色史莱姆后立刻去开黄门,因为这样能直接获得血瓶,让估值变得更高。

但是,事实上最佳做法应该是打败黑色史莱姆后,再去打绿色史莱姆,开下面的黄门再打黑色史莱姆获得两把钥匙和宝石,再去开那个黄门。这条路明显在整个估值过程中会比刚刚的弱,但是却是最佳的。

其问题可以抽象为下面这样一个简单的问题:

当前有A, B两种选择,B后面紧挨着C选择。如果打败了A可以得到一个大血瓶,打败了B什么都得不到,但是接着往下打C则可以获得大量宝石收益。

使用估值函数会产生如下判断:

  1. 打败A,获得血瓶,加入队列。
  2. 打败B,什么都无法获得,加入队列。
  3. 状态1中的估值比2高,弹出队列;打败B,什么都获取不到。
  4. 状态3中的估值比2高,弹出队列;打败C,获得大量收益。
  5. 然后再访问状态2时,打败C再选择A时,会因为之前已经计算过该状态而放弃,这样导致实际算出来结果比正确值要小。

为了避免这个情况的发生,我们需要确保整个搜索过程都要是最优的。而要保证最优,只需要保证计算某状态时,能抵达该状态的所有状态我们都计算过。

换句话说,我们可以先按照cnt从小到大进行排序(确保计算某状态时,所有可达此状态的可能性都被计算过);然后再按照估值函数从大到小排序。

[java]
1
2
3
4
PriorityQueue<State> queue=new PriorityQueue<>((o1,o2)->{
    if (o1.cnt==o2.cnt) return o2.getScore()-o1.getScore();
    return o1.cnt-o2.cnt;
});

事实上,这是使用了动态规划的思想,也就是计算某个状态实际上会先计算其所有子状态。这种方法是可以保证最优的。

缺点是,可能会把所有可能出现的状态都给计算了一遍,队列中会存放大量相同的状态,导致空间复杂度较高。

一个比较好的剪枝方法是,使用一个HashMap,记录每个状态的当前最高分;后面如果计算出现了相同状态且得分低于它,则不加入队列。这样不会改变计算的状态总数,但是却可以有效缩减队列中的元素数目,这样既节省了内存,优先队列的插入与删除也大大节约了时间。

[java]
1
2
3
4
5
6
State another=new State(state).merge(node);
if (another==null) continue;
String hash=another.hashString();
if (map.getOrDefault(hash, -1)>another.getScore()) continue;
map.put(hash, another.getScore());
queue.offer(another);

 

======> 上述算法可以有效算出MAX,但是会造成队列中存放大量的状态 <======

由于优先队列内存放了State,插入和删除操作都是log级别的,当存放状态过多(>800W)时会导致特别慢。
如果出现了这种情况,请不要使用动态规划,对cnt排序;而是直接用getScore的得分对状态进行排序,这样的话优先队列元素数目不会超过2-3W。

 

总之,如果状态数不多,或者想算出当前MAX,请对cnt进行排序;否则直接对getScore排序即可。

其他优化

还有一些其他的小点可以进行优化。

比如,我可以设置“无效消耗节点”不进行拓展。所谓无效消耗节点,就是一个怪物或者一个门,是否合并这个节点,对活跃节点的相邻节点不会有任何变化,它就像孤零零地放在那里。那么,有什么必要去合并它呢?

比如,我可以在贪心地吃掉血瓶和宝石时,同样贪心地直接打掉当前地图上的无伤怪物。这样也可以进行一些剪枝,等等。

总之,还有很多都是可以优化的。

 

 

到这里,单层塔的基本算法就已经结束了。在下一篇博客里,我将对一些其他的细节,以及如何具体将AI投入使用等来进行讨论。

 

大家可以关注我的开源项目https://github.com/ckcz123/magic-tower-AI/,star或fork一下,感谢支持~

如果您有什么意见建议,或者比较好的想法的话,欢迎邮件至ckcz123@126.comckcz12345@gmail.com与我联系,也可以在魔塔吧官方交流QQ群里搜索“小艾”联系到我。期待对于AI,有与您的进一步交流~