Amazons

• Amazon Chess Program for Data Structures course design.

• Amazons(亚马逊棋),是1988年由阿根廷人WalteZamkauska发明的双人棋类游戏，由国际象棋中后的走法衍生而来，属于两人零和完备信息博弈。目前亚马逊棋是ICGA国际机器博弈锦标赛和全国大学生计算机博弈大赛的比赛项目之一。

• Wiki百科链接

• BotZone评判平台链接

使用方法

• 评测平台使用：在BotZone中创建机器人，上传代码，即可创建机器人与人类/其他机器人对战。

• 本地使用：直接运行即可。输入为特定格式的双方历史下棋位置，输出为当前决策的下棋位置。注意需要将栈内存设置得更大一些。

算法和创新

关键词

• 蒙特卡罗搜索
• 极大极小搜索
• αβ剪枝
• 评估函数
• 权重调整
• 弃用STL容器，改用数组以加速
• 弃用大根堆，在环境下改用简单顺序查找

算法思路

棋局开始时，接收输入信息，首先根据当前回合数判断采用哪种搜索策略，依据回合数选择蒙特卡罗搜索或者采用极大极小搜索。在两种搜索过程中，依据评估函数对当前棋局的优劣程度进行判断并量化，从而为搜索提供数据支持，使得搜索过程更加准确。

创新点

首先搭建了一个简易评估函数+简单极大极小搜索的版本，然后慢慢优化评估函数，改进极大极小搜索，增加蒙特卡罗搜索，引入特殊判断，逐渐完善我们小组的程序。

我们采用了蒙特卡罗搜索树的模型，但略有不同。经典的蒙特卡洛搜索树在rollout的阶段，是双方不断下子直到回合结束。但是在我们的棋局中，由于棋步很多，且为了在所有可行走法中随机选择需要首先得到所有可行走法，这样效率极低，且准度极低。因此，我们采取了和极大极小搜索中一样的评估函数，rollout改为直接评估当前棋局并返回。由于我们的评估值并不是0/1值，因此使用函数将评估值映射到0-1之间，用来代替UCB值之中的胜率。另外，与经典的蒙特卡洛不同的是，在UCB值的计算中，我们融入了极大极小的思想，在极大极小层中采用不同的胜率计算。

即使如此，搜索的次数在前期仍然不够高，达不到想要的次数。于是我们在整个程序中寻找可能降低效率的部分，将一些STL容器如<vector>和<queue>使用数组实现，增加了大约30%的模拟次数。

在通过UCB值选择扩展的子节点时，本来使用了大根堆来维护子树UCB值的降序序列，但由于每次调整的时间消耗大，以及我们模拟次数的限制，因此反而不如简单的顺序查找。

在极大极小搜索中，为了提高搜索效率，结合了αβ剪枝，剪去了一些不必要的分支，减少拓展节点数，使得搜索到目标层数的时间大幅度减少。且采用动态层数的搜索方式，即只要时间有余，会在当前层数的搜索完毕后，尝试搜索更多的层数。

搜索策略的选择上我们也下了一些功夫，根据我们不断测试，我们发现，在前6回合里，蒙特卡罗搜索选择的节点能占到总模拟次数的10%左右，我们选择蒙特卡罗搜索，在6-12回合之间，仅仅占到4%-5%左右，所以这个区间段我们采用极大极小搜索，而到了12回合之后，蒙特卡罗搜索选择的节点基本上能占到总模拟次数的50%以上，这时候我们就选择用蒙特卡罗搜索。

在多次探索中，通过不断观察我们模拟测试时的棋局，我们发现了一种常常出现的特殊情况：到了后期阶段，很多棋子的分布已经确定，也就是说，棋子活动范围已经划定好，那些棋子已经占有了自己的领地，那么这种情况下，这些棋子就不再移动，转而去选择那些尚可争夺领地的棋子，为此专门写了一个判断函数。但是实战发现，有时就应该让对手先移动，我们再根据对手的移动来进行移动，因此后续被删去。

在参数调整方面，我们起初按照着搜集的论文写出了一个简易版的评估函数，当时的评估函数只有三个参数，根据回合数分成四种情况，赋予不同权重。后来对评估函数的参数进行优化，使用了五个参数，使得我们的评估函数能更准确评估当前棋局的优劣情况。

对于参数调整，我们下载了botzone的本地模拟器，然后用鼠标连点器自动模拟多次对局，然后统计胜率，经过不断测试，选取胜率较高的区间范围，再加以精细调节参数，最后调整出了一套较优的参数来使用。

但实际上，由于本地测试的次数不够多，且没有一个理想的对手作为判断依据，且不能仅仅以和某个对手的对局的胜负情况作为评判程序逻辑好坏的标准，因此参数调整这方面有很大的遗憾，没有更高级的工具和思路进行调整。

总结

在代码完成的过程中，我们尝试了很多个版本，四个人加起来创建了上百个bot反复模拟测试，尤其是在程序超时的时候，为了查出程序到底哪里耗费的时间最多，我们在程度各个程序段加入计时代码，反复查找最耗时的地方。

起初我们用的是极大极小搜索，但是发现无论是αβ剪枝还是其它的一些剪枝算法（PVS算法、渴望算法）等搜索效率都比较低，得出结论极大极小搜索并不是很适用于亚马逊棋，于是我们就又写了蒙特卡洛搜索。

关于模拟次数不足的问题。我们测试了一些排名靠前的代码，发现他们的模拟次数远在我们之上，大概相差十多倍，我们尝试寻找模拟次数不足的问题，对此我们进一步优化了评估函数，大幅度减少了评估函数的时间，最后将搜索效率提高了许多。

在使用蒙特卡罗树搜索时，由于模拟次数不足，导致如果使用传统方法，双方依次随机落子直到一方胜利的思想几乎不可用。所以我们决定引入评估函数的评估值到UCB之中代替rollout的过程。我们尝试过把所有的评估值输出出来做个统计，最后采取映射函数的方式，将评估值映射到0-1之间，直接代替胜率参与UCB值的计算。

总结来说，无论是极大极小搜索还是蒙特卡洛树搜索，模型已经基本固定，且模拟次数在固定时间内基本已经达到了最优。因此最重要的仍然是评估函数。而评估函数的几个参数，前人也已基本敲定，关键在于参数系数的调整。在蒙特卡洛搜索树模型中，C值和胜率值映射这些参数的调整，以及上述评估函数系数的调整，由于目前所学知识不够，且时间不足，没能进行精细调整把控，十分可惜！

参考文献

[1] Jens Lieberum. An evaluation function for the game of amazons.[j]. Theoretical Computer Science. 349 (2005) 230–244.

[2] Xiali Li,Liang Hou,Licheng Wu. UCT Algorithm in Amazons Human-computer Games.[j].

[3] 郭琴琴，李淑琴，包华. 亚马逊棋机器博弈系统中评估函数的研究.[j]. 计算机工程与应用. 2012,48(34).

[4] 基于 PVS 搜索算法的亚马逊棋博弈系统的设计. 李卓轩，李媛，冉冠阳，王静文.[j]. 智能计算机与应用. 第8卷第5期

[5] 张柳.基于极大极小搜索算法的亚马逊棋博弈系统的研究.[D].沈阳.东北大学系统科学研究所.2010年6月