一个简易的五子棋bot

在两年前…我就想搞一个五子棋bot来愉快玩耍。然后在这么久之后,我不想写题然后颓废…我才搞出一个棋力一般的五子棋bot。(智障选手生无可恋)

当我第一次想写这个bot的时候,我就想肯定价值越大的位置越好嘛!于是直接判可以成5的位置,计算分数,然后贪最大的。当时我甚至没有怎么了解OI,所以根本不知道这个东西被称为估价函数。

结果呢?跑起来被我自己吊着打……于是当时我弃疗了,留下了一个vb写的对局棋盘框架。

究其原因,我的估价函数是非常不优秀……因为我直接取了做了估价函数;并且统计方式是,从一个点向上下左右扩展,这导致本来成不了5的点都会被统计进入答案。

一年后(去年)我重新看代码的时候发现了这个问题,于是我改变了估价方式,从统计一个点变成了对于所有成5的可能全部判一遍,并且给每种可能成5情况的所有点同时加上价值。这样做,虽然似乎不能准确地判断出死活(例如死4仍然有活4一半的价值),但是已经可以比较清晰的体现棋子位置的价值了。同时经过手动退火(……),找到了一些看起来比较优秀的估价值。跑起来,终于能下赢我自己啦!同时百度上面的智障五子棋小游戏也下平了。

然后拿去班上给同学玩,结果被吊着打。(……)

首先,这样做的话估价函数的强弱完全决定了这个bot棋力的强弱,但是事实上找到的估价函数并没有非常优秀。其次,我的统计方式本来就不太科学,例如上面的判死活等等。

然而最重要的是,贪心短视地令人嗤之以鼻。

考虑如上的局面。此时如果是纯贪心,那么通常来说都会选择(7, 5),因为按照估计函数的计算(7, 5)更加优秀;然而事实上,如果不走(8, 5),那么白棋走(8, 5)就已经是杀棋了。

于是那时的我想起,有往后算XX步的说法,恍然大悟:哦原来可以使用搜索。然后我写了一个搜三步的程序……不过因为我当时对局面的判断取得是总和而不是最大值,效果非常差。

然后今年我又想颓废,于是我就重新看了看自己的程序,发现简直是个逗逼……

重新写了一个基于以下策略的五子棋bot:
1. Min-Max搜索,加上Alpha-Beta剪枝;
2. 为方便Alpha-Beta剪枝,每步对决策按估价函数排序,选择尽量大的先搜索;
3. 估价函数应设计为一定要能够体现出输赢,并且尽量反映局势。注意到五子棋的输赢和全局关系不大,只要一个地方非常优就可以赢了,所以这里我采用的是max(我)-max(敌)作为反应局势。

看起来非常靠谱……事实上,我调调写写搞了很久,结果效果和贪心差不多。

直到一天半后,我才发现:

哇,我botzone上面的黑白读反了。

改了以后瞬间在botzone上登顶了。

(2017.06.12 17:05)

然而实际上这个bot棋力是不够的……甚至我随便下了一个手机五子棋都下不过;一些同学也可以轻易手爆这个bot。

假定估价函数足够准确,那么采用Min-Max搜索出的结果应该是非常好的。
然而现实总是没有那么令人满意……总是。很难找到一种准确的评价局面的方式,原因和贪心的错误类似。这里如果没法准确评价局面,那么Min-Max搜出来的最好结果也不是最好的。

更正确的姿势是用蒙特卡洛树搜索,即基于一定程度随机化的搜索。这种搜索通常来说都有一个特性,以随机化为基础,并且只看游戏终局带来的影响。即,不到游戏结束,不停止往更深的地方搜索。这样虽然是随机化的,但是效果会好很多。Hob让我写uct……然而我觉得我不能继续颓废在bot上面了,于是就暂时先写到这里了。

辣个Alpha-Beta……代码在botzone上开源了。(虽然很辣鸡且代码奇丑无比QAQ

UPD: 已经被打爆啦 QAQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

ˆ Back To Top