一周前从学长那得知了北京大学计算概论的大作业黑白棋AI，正好最近从炉石脱坑，去凑了个热闹

http://botzone.org/games

网站上有规则和交互方式，在此不再赘述

游戏界面大概长这样，支持bot间或者人机对战

每回合要求程序读入局面信息，输出落子位置

1.一开始熟悉一下给出的样例程序的框架，做一些小测试。

因为之前没怎么接触黑白棋，也不懂有什么策略。样例给出的是随机落子，就把样例修改了一下，比如每次选择能占有最多格子的落子处，结果打不过样例……

2.AI框架

(1)极大极小搜索与AlphaBeta剪枝

一般AI的框架是把局面做一个估价，反应某一方的情况，数值越大代表优势越大，然后构建博弈树通过搜索得到较优策略。

比方说上面就是把占有的格子数当做一方的估价

假设博弈的两方叫做A和B，不妨设当前轮到A

如果A只考虑走一步，那么当然是走到一个对A估价最大的局面

如果A能往后考虑到B的下一步，B要走一个对A估价最小的局面，那A的落子就要使得下一步B落子后局面对A估价尽量大

A往后考虑若干步，以此类推，要使得A若干步后到达的局面对A估价尽量大。

局面之间形成一个树形结构，因为每一方每次有约10种走法，我们将博弈树限制在7-10层。

叶结点局面直接估价，其余结点用上述思路在树上深搜得出估价。

还有一个AlphaBeta剪枝，是说搜索一个结点的一些子节点一定不会改变这个结点的估价，就考虑剪枝

这两部分具体参见http://home.ustc.edu.cn/~baj/publications/concluding2007-Bai.pdf

(2)

可以通过改变搜索顺序来提高效率，在开局和终局也可以适当增加搜索树层数

3.初步研究估价函数

(1)

围棋中有一个术语，叫做“金角银边草肚皮”，黑白棋也适用，意思是格子的重要性不同

角是一般比赛中获胜的关键，为了尽可能占有角，每个角周围三个格子（星位）就尽量不去占

因此我们给不同的格子制定不同的权值，而不是单纯以占有格子数来评价局面

(2)

行动力与稳定子

看了基本的黑白棋策略，发现有这两个概念

行动力：可选落子点总数。

稳定子：不可能被翻转的子。（右上角的一些黑棋是稳定子）

稳定子不好精确计算，我们仅把那些八个方向都没有空格的子视为稳定子

实际上这是一个充分不必要条件

前期对局势的判断，应当基于这两个参数

(3)

奇偶性

一个区域指的是棋盘上一块空着的区域，通常（并非总是）包括一个角，与其它区域隔开（右上角是一个区域）。

如果要填入一个偶数空的区域，通常最后下入其中要好一些。这就是说，你希望对手先下入区域，之后你跟进，试图吃回一些你的对手刚刚吃掉的棋子。

这是黑白棋中一个很重要的理论，在实践中发现它很有效，一个区域大小 <= 6 时我尝试将奇偶性考虑在内，如果落子的区域大小为奇数，则提高估价，否则减少这一步的估价，即我们希望在奇数区域落子。

(4)

经过观察，我得出了一些结论

通常一方跳过回合会导致失败，少有例外

在游戏早期，一方的子越少越有利，这可能跟行动力有关

失败的一方通常在边角的占领上处于劣势，强大的AI较重视边上的稳定子

4.改进估价函数

对一个局面的估价越准确，AI的决策就会越明智，我发现对战中常出现这样的情况 

如左图，白方占领了边上中间的若干个，但是这些子不稳定，黑方占有1B和1H的可能性提高

甚至如右图，边上的白子很大可能被翻

——有时去占边并不能占到便宜

改进AI对边的评价，设计一个动态规划算法，只考虑边上一行/列的8个棋子，给这3^8种情况的估价

八个格子占满的估价直接计算，角的权重2，边的权重为1

否则考虑一方有一定概率在某个空格落子

比如左图，三个格子黑白方等概率占，右图1B黑方有大概率占，1A黑白方等概率

使用记忆化搜索转移

当边上形成稳定子时，估价会明显提高，鼓励AI形成边上的优势

大概思路如此，再花一些时间调整参数，花了几个晚上

代码390行，目前botzone天梯已进前5名