消除王的蒙特卡罗树搜索（mcts）解法初探

更新时间2021/1/31680 浏览攻略

0. 缘由

获得消除王的较优解一直是我的愿望之一（所谓较优解，就是大概能上榜的意思）。接近两年前， wall-knight的帖子已经提出过一种思路（虽然现在来看略粗糙了），在那以后，我慢慢弄懂了召合的消除规则，最近了解到了mcts方法，就尝试了一下，效果是尚可的，凌晨时在第一，现在应该是第二。

1.我是消除王的规则

消除王当然符合一般的消除规则，即：

交换：交换怪物位置→ 初始消除→ ①下落→ ②补充→③一般消除→ 如③进行则跳转至①

拖出：拖出怪物→ ①下落→ ②补充→ ③一般消除→如③进行则跳转至①

具体可见于：

【屠龙之技】论消除规则

【屠龙之技】消除规则的补完

消除王的特殊之处在于，其补充队列是固定、每12个一循环的，所以如果初始状态和进行的操作相同，最终的结果就完全一样（这和章节、魔王等是不同的），即消除王不涉及任何随机过程，因此较优解更容易得到，也更容易比较（有排行榜）。

任一步操作之前/之后，我们都可以用沙盘+剩余步数+分数以及目前在补充序列中的位置来完全描述当前的状态。记作S(table,steps,score,fill_id)。

对于任一状态，我们都可以选择（可以造成消除的）交换或拖出。这样的操作记作a，即：S-a->S'

显然，对于初始状态S0，我们有几十种可选的操作，相应可得到几十种S1，每个S1又对应几十个S2，如果我们将所有可能性画出来，就形成了一棵n叉树。这棵树有多大？以今天（2021年1月3日）的消除王举例，共45步，每步至少算30种可能，即使不算拖紫拖橙加的步数，也有30^45=2.95×10^66种可能。这个数量并不太大，至少比宇宙中原子的数量少得多——我的意思是，当然也比围棋的可能性少得多，围棋尚可以解决，消除王当然要轻松容易得多。我们知道AlphaGo的原理是一个经过了很多优化的蒙特卡罗树搜索（mcts），那么消除王能不能用一个简单的mcts就解决呢？

2.蒙特卡罗树搜索和改动

具体步骤可以参见：如何学习蒙特卡罗树搜索（MCTS）这里不赘述。

一言以蔽之，mcts的大致步骤是，选择，扩展，模拟和回溯，其基本思想是，我们显然不能完整构建出前述的n叉树（除非量子计算机被成功发明），那么就应该选择较有价值的分支进行扩展，其判断依据是：

其中v'表示当前树节点，v表示父节点，Q表示这个树节点的累计quality值，N表示这个树节点的visit次数，c是一个常量。这个公式并不难理解，它是选择分支时的一个综合考虑，兼顾先前选择较少的分支+quality值较大的分支。由于目的是分数最高，令quality=η*score，η是归一化参数，如今天的最高分大概是10000+，η=0.0001较好。另一方面，η实际上可以起到调节收敛速度的作用，η较大时收敛快，最终分数可能就较低，反之收敛慢，分数可能高一点；

另外，随机扩展的结果并不好，这里我作出的改动是，只会进行造成消除数最多和次多的交换和紫、橙拖出，消除数最多很容易实现，用fill_id最大的就可（当然理应使用消除数前n的交换，待改进）；

模拟时则是简单的在每一步，都任意选择所有可行操作之一，直至没有步数然后给出分数。总的来说不算复杂，希望大家都可以复现成功。

3.一些细节

说一下C++实现时的数据结构好了，复现可以参考，更具体的如果有人感兴趣我会更新在楼下。

首先是游戏状态：

操作步骤：

这里四个数全正时为交换，x2=y2=-1时就是拖出[x1,y1]

最重要的组成树的node：

前两个不解释了；

isAllExplored 主要是为了解决消除完成之后，程序会可能不断选择同样的路线导致重复，因此消除完成时isAllExplored=true，而所有子节点均探索完成之后，父节点的isAllExplored值也为true；parent，children，state不解释；

后面的大致是，对于一个state，我们有若干可选的操作，这些都存储在vector<struct action> feasibleActions中，而任一节点只存储它所选的那个操作的序号，即subNode->parent->feasibleActions[subNode->actId]是subNode的上一个操作。

4.目前的发现

mcts很容易陷入局部最优，我们当然可以设定更小的η来增大搜索的广度，但是会极大提高计算量，而且很可能无法得到更优的结果，因为最优解可能在离局部最优很远的地方——拖橙。没错，mcts不会拖橙，即使限制某个家族不拖紫，因为太菜也无法达到拖橙的效果（最多的时候好像是两紫两蓝）。

总的来说可以改进的地方还很多，慢慢来吧。

5.额外的话

在搞清楚消除规则之后，目前已经做到了：

1）战棋消除，35波时38~45均消；

2）魔王消除，主力14紫+肉盾1橙

3）消除王消除，可以上榜，以后再争第一

还差一个就是竞技场啦，竞技场补充队列随机，而且限时，是最麻烦的部分了，希望有搞定的一天~

召唤与合成

9.8

前往论坛

只看作者

写下你的想法...

椰奶清补凉

游戏玩得好好的，本来今天挺开心的，看了大佬的帖子，又是数列又整英文的，一下子就不高兴了。看不懂……

5楼

2021/1/3

林木甜

作者

不至于不至于

2021/1/3

椰奶清补凉

@林木甜

哈哈哈哈hhhhh哈哈哈哈

2021/1/3

战神叶飘零

消除王一直存在一个问题，存不存在前几步废棋的铺垫，导致中间某一步迎来大量消除，像类似的可能又存在多少种？James应该明白这个问题。

20楼

2021/1/4

林木甜

作者

我优化使用的mcts不能回答这一问题，因为我只选择了消除较多的分支进行拓展。如果是全部可能都拓展，目前我的机器没有这样的算力。但是就我的经验，不大可能出现你说的情况。

2021/1/5

战神叶飘零

首先，我先承认你这个算法我没学过，不懂。但是关于消除王这个机制，我比较懂，有这种情况，当初我连续拿下七次消除王第一的时候，反复进行过此类测试，浪费前面两三步进行简单的消除或者说只是移动位置铺垫，再进行一次比较棒的消除，积分会比你每一次都尽可能多的消除积分来的多。按你的算法，只能说每一步都是当前最优解，但是存在的问题是，假如我第一步是最大消除，那么第二步在第一步的基础上再进行一次最大消除，能比第一步铺垫，第二步进行最大消除更大吗？答案是明显不能，以此类推，更不可能。如果真要找寻最优解，目前的算力确实是达不到的，而你的这种算法，只能算是假设每一步都是最优解的情况下得来的最优解。当步数之间有更多关联的时候，你的最优解是不成立的。

2021/1/5