AI for Magic Tower (Part III)

Sorry, this entry is only available in 中文. For the sake of viewer convenience, the content is shown below in the alternative language. You may click the link to switch the active language.

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

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

那么,应该怎么搜索呢?

深搜的尝试

最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,有与您的进一步交流~