春暖花开

五子棋之五元组评分算法

前言

本学期,开始学习 $C$ 语言编程课,期末大作业是一个用 C 语言写的五子棋游戏,该大作业占最后期末成绩的百分之五十,所以不容忽视。最后的成绩高低是所有同学进行比赛,看谁的 $AI$ 厉害,然后根据比赛结果评分,冠军组 $100$ 分,而最后一个普通组只有 $65$ 分,分数相差较大。

大概从 $11$ 月中旬就开始写五子棋,当然,整个程序最关键的部分就是 $AI$ ,大概 $12$ 月份刚开始的时候就按照老师讲的算法写出了一个感觉还不错的程序,之后一直没再调试。比赛前最后一周,感觉自己的 $AI$ 还是很弱,于是,开始进行调参,可是花了一周的时间,没什么效果,反而越调越傻。

昨天晚上,也就是比赛前最后一个晚上,到隔壁一个宿舍,问到他们的五子棋情况,发现大家的好像都很厉害,他们都是用博弈树算法搜了很多层,才意识到自己的真的很菜,一周的调参没起到任何效果。然后又听说他们宿舍的另一位搞 $ACM$ 的大神用了一种很好的算法进行评分,搜了 $8$ 步,可以秒杀电脑上五子棋游戏的大师级别。听了那个评分算法,似乎不是很难实现。原本昨天晚上是想继续调参的,但想想按照之前的算法调参好像真的没什么用,干脆按他们说这个算法重新写一个 $AI$ ,说不定效果更好,虽然不一定能写出来,不过豁出去试一试。于是,七点多的时候,回到宿舍,上网搜了一下,发现有人写了一篇关于这种算法的博客,不过,要说很重要的是这篇博客给出了一个比较完美的该算法评分参数,后来,我在该参数的基础上进行了一些修改,我觉得应该比之前好一些。

从 $7$ 点多开始,先思考了一会怎么实现该算法,然后便开始写,大概写了 $3$ 个多小时, $10$ 点多的时候写好,整个 $AI$ 只有 $213$ 行代码。但不幸的是,存在 $bug$ ,调了半个多小时 $bug$ ,终于可以正常下了。简直不可置信,就进行一个评分,然后完全秒杀之前写的 $AI$ ,效果比我想象中要好很多很多。甚是激动,于是奖励自己玩了两个小时手机,所以一不小心就到了凌晨两点半才睡。

今天早上 $10$ 点多醒来,一点半比赛,于是决定再测试一下程序。没想到却发现了两个致命 $bug$ 。第一个是选择最高分时判断是禁手以后忘记把该点赋为 $0$ ,导致程序进入死循环,就不会再落子。这个 $bug$ 解决了以后,又出现了新的 $bug$ ,$AI$ 一次落了两个子,后来找出 $bug$ :在判断是否禁手时我先进行试探落子,之后忘记恢复,所以才出现一次落了两个子。

于是早饭、午饭都没吃,直接到时间了去教室参加比赛。最后结果 $4$ 胜 $1$ 负进入冠军组,然后又打败老师给的之前一个研究生写的五子棋,直接满分,所以现在 $C$ 语言期末已经有了 $50$ 分,再加上 $20$ 分作业分,就算不参加期末考也已经及格了。

正题

下面,开始说这个算法,其实很简单。

在这之前,先说一下之前的算法:对棋盘上空的点评分,判断在该点落子之后四个方向的格局,比如胜利、活四、半活四、活三等等,然后再判断对手在该点落子以后四个方向的格局,各种情形分别赋分,算出总的分,然后落子,不得不说,这个评分方法真是弱爆了,首先,因为评分偏差,我写了无数个很长 $if$ ,对一些特殊情况单独处理, $AI$ 部分写了 $500$ 多行代码;其次,这种评分在中间位置还好,一旦到了边界,它就会在一些已经不可能形成五连的无意义点落子。

五元组评分算法:所谓五子棋,就是要五子连成线才取得胜利,正规比赛以及我们该比赛的棋盘都是 $15\times15$ 大小的,所以整个棋盘上有 $572$ 个五元组,每一个点都被包含在 $20$ 个五元组中(边界情况例外)。于是,对点的评分改为:已经被落子的点,直接赋值为 $-1$ ,对于没有被落子的点,计算包含它的所有五元组的情况,然后进行评分,评分方法很简单:看每个五元组里面有几个自己的子以及对手的子,然后给分,不用去管具体位置是什么样的。

算法就是这样。

下面,是我的评分表,我直接把头文件黏贴过来:

#ifndef MY_HEAD_H
#define MY_HEAD_H

#define SIZE 15

#define PLAYER1 1
#define PLAYER2 2

#define FIRST_PLAYER 1
#define SECOND_PLAYER 2

#define M1 35
#define M2 800
#define M3 15000
#define M4 800000

#define O1 20
#define O2 500
#define O3 4000
#define O4 300000

#define VO 7
#define PU 0
#define NO 0

#endif

说明一下,只看 M1 到 M4 和 O1 到 O4 以及最后三个。

Mi表示该五元组上有 $i$ 个自己的子;

Oi 表示该五元组上有 $i$ 个对手的子;

VO 表示该五元组上没有子,为什么没有子分不是 $0$ ,因为还有更坏的情况:PU 表示五元组上既有自己的子,又有对手的子,所以这时该五元组已经被 污染,不可能再形成五连;

NO 表示不存在五连,这是考虑边界情况,这样定义,方便函数的实现和调用。

个人觉得,该评分已经比较完美,也许会有更好的评分。

当然,如果要进行多层搜索的话需要对全局进行评分,试探落子,然后计算所有五元组得分之和,多步试探,最后还是要用到博弈树算法,还不懂具体怎么实现,等到假期再来研究。

$C$ 语言实现的五子棋代码在 $GitHub$ 上:https://github.com/ucasFL/Gomoku/

0%