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

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）消除王消除，可以上榜，以后再争第一

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