计算概论大作业——黑白棋AI设计

2016年1月16日3,21813

一周前从学长那得知了北京大学计算概论的大作业黑白棋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名