C语言编程实现的五子棋程序源代码可运行

回复于：2001-08-10 20:40:08

dot99  转

五子棋算法探讨

--------------------------------------------------------------------------------

　　近来随着计算机的快速发展，各种棋类游戏被纷纷请进了电脑，使得那些喜爱下棋，

又常常苦于没有对手的棋迷们能随时过足棋瘾。而且这类软件个个水平颇高，大有与人

脑分庭抗礼之势。其中战胜过国际象棋世界冠军-卡斯帕罗夫的“深蓝”便是最具说服力

的代表；其它像围棋的“手淡”、象棋的“将族”等也以其优秀的人工智能深受棋迷喜

最基本的算法。当然，仅靠当前盘面进行判断是远远不够的，这样下棋很容易掉进玩家

设下的陷阱，因为它没有考虑以后的变化。所以在此基础上我们加入递归调用，即：在

电脑中预测出今后几步的各种走法，以便作出最佳选择，这也是我们下棋时常说的“想

了几步”。如此一来您的程序便具有一定的水平了。什么？不信！过来试试吧！

　　总体思路弄清之后，下面进行具体讨论：

　　一：数据结构

先来看看数据结构，我们需要哪些变量？

首先得为整个棋盘建立一张表格用以记录棋子信息，我们使用一个 15*15 的二维数组

Table[15][15]  (15*15 是五子棋棋盘的大小)，数组的每一个元素对应棋盘上的一个交叉

点，用‘0’表示空位、‘1’代表己方的子、‘2’代表对方的子；这张表也是今后分析

4 个记录；这样做的另一个好处是可以轻易判断出复合棋型，例如：如果同一点上有 2 个‘15’

就是双三、有一个‘15’和一个‘20’就是四三。

怎么样！3 个数组构成了程序的基本数据骨架，今后只要再加入一些辅助变量便可以应付自如

了。应该不会太难吧？OK！有了这么多有用的数据，我们就可以深入到程序的流程中去了。

　　二：程序流程

　　我们主要讨论五子棋的核心算法，即：人工智能部分，而其他像图形显示、键盘鼠标控制

等，因较为简单，所以就不作过多介绍了。

　　首先，请仔细阅读图 1：

　　我们看到本程序由六个基本功能模块构成，各模块的详细分析如下：

（1）初始化：首先，建立盘面数组 Table[15][15]、对战双方的棋型表 Computer[15][15][4]和

（4）盘面分析填写棋型表：本程序核心模块之一，人工智能算法的根本依据！其具体实现方法

     如下：您在下五子棋时，一定会先根据棋盘上的情况，找出当前最重要的一些点位，如“

     活三”、“冲四”等；然后再在其中选择落子点。但是，电脑不会像人一样分析问题，要

     让它知道哪是“活三”、哪是“冲四”，就得在棋盘上逐点计算，一步一步的教它。

先来分析己方的棋型，我们从棋盘左上角出发，向右逐行搜索，当遇到一个空白点时，以它为中

心向左挨个查找，如果遇到己方的子则记录然后继续，如果遇到对方的子、空白点或边界就停

止查找。左边完成后再向右进行同样的操作；最后把左右两边的记录合并起来，得到的数据就是

该点横向上的棋型，然后把棋型的编号填入到 Computer[x][y][n]中就行了（x、y 代表坐标，n=0、

1、2、3 分别代表横、竖、左斜、右斜四个方向）。而其他三个方向的棋型也可用同样的方法得

到，当搜索完整张棋盘后，己方棋型表也就填写完毕了。然后再用同样的方法填写对方棋型表。

Let 's  go！

（5）电脑下子：有了上面填写的两张棋型表，现在要作的就是让电脑知道在哪一点下子了。其

中最简单的计算方法，就是遍历棋型表 Computer[15][15][4]和 Player[15][15][4]找出其中数值

这就和许多五子棋初学者一样犯了“目光短浅”的毛病。

要解决这个问题，我们引入‘今后几步预测法’，具体方法是这样的：首先，让电脑分析一个

可能的点，如果在这儿下子将会形成对手不得不防守的棋型（例如：‘冲四’、‘活三’）；那

4 对预测后的棋进行盘面分析，如果出现了‘四三’、‘双三’或‘双四’等制胜点，那么己方

等一等，要是盘面上没有对手必须防的棋型，哪该怎么办呢？进攻不成的话就得考虑防守了，将

自己和对手调换一下位置，然后用上面的方法来预测对手的棋，这样既可以防住对手巧妙的攻击，

但是必须告诉大家的是：预测法的运算量相当之大，据我的经验，用 Pentium-100 预测 3 步的走法

　　到现在为止，整个五子棋软件就基本完成了，其水平大约在中级上下。当然，这种算法并不

是最好的，但我相信它的基本思路是正确的。如果您有什么问题或好的想法，欢迎给我发

E-mail:  wj77@990.net，我期待着您的见解。

--------------------------------------------------------------------------------

softboy(汪疆)

金点时空2000/2/12 

===========================================================

==================

五子棋算法

网址：http://tyhweb.163.net

邮箱：tyhweb@163.net

===========================================================

==================

    任何一种棋类游戏其关键是对当前棋局是否有正确的评分,评分越准确则电脑的 AI 越高。五子棋游戏也是

如此，但在打分之前，我们先扫描整个棋盘，把每个空位从八个方向上的棋型填入数组

(x,y)

    gStyle(1,2,2,1,1)=3 表示与坐标(2,2)在第 1 个方向上相邻的黑棋棋子数为 3

    在定义方向时，也应该注意一定的技巧，表示两个相反的方向的数应该差 4，在程序中我是这样定义的：

    Const  DIR_DOWNLEFT  =  6

    Const  DIR_LEFT  =  7

    Const  DIR_LEFTUP  =  8

    ---------

    ---------

    ---oo----

    -ox*xx---

    ---------

    ---------

    图中的*点从标为(4,4),（打*的位置是空位）,则:

    gStyle(2,4,4,1,1)=1 在(4,4)点相邻的上方白棋数为 1

    gStyle(2,4,4,1,2)=2 在(4,4)点的上方距上方白棋最近的空格数为 2

    gStyle(1,4,4,3,1)=2 在(4,4)点相邻的右方黑棋数为 2

    gStyle(1,4,4,3,2)=1 在(4,4)点的右方距右方黑棋最近的空格数为 3

    一旦把所有空点的棋型值填完，我们很容易地得出黑棋水平方向上点(4,4)的价值，由一个冲 1（我把有界

的棋称为冲）

和活 2（两边无界的棋称为活）组成的。对于而白棋在垂直方向上点(4,4)的价值是一个活 1，而在/方向也是活 1

作为下棋的点。

    然而，对各种棋型应该取什么值呢？我们可以先作如下假设：