五子棋ai如何判断棋型
五子棋ai如何判断棋型
五子棋ai如何判断棋型?下面学习啦小编给你介绍五子棋ai判断棋型的方法，欢迎阅读。
五子棋ai如何判断棋型
学习啦在线学习网 任何一种棋类游戏其关键是对当前棋局是否有正确的评分,评分越准确则电脑的AI越高。五子棋游戏也是如此，但在打分之前，我们先扫描
整个棋盘，把每个空位从八个方向上的棋型填入数组gStyle(2, 15, 15, 8, 2)，其中第一个下标为1时表示黑棋，为2时表示白棋，第二和第三
学习啦在线学习网 个下标表示(x,y)，第四个下标表示8个方向，最后一个下标为1时表示棋子数，为2时表示空格数，如：
学习啦在线学习网 gStyle(1,2,2,1,1)=3表示与坐标(2,2)在第1个方向上相邻的黑棋棋子数为3
学习啦在线学习网 gstyle(1,2,2,1,2)=4表示与坐标(2,2)在第1个方向上的最近的空格数为4
在定义方向时，也应该注意一定的技巧，表示两个相反的方向的数应该差4，在程序中我是这样定义的：
学习啦在线学习网 Const DIR_UP = 1
Const DIR_UPRIGHT = 2
Const DIR_RIGHT = 3
Const DIR_RIGHTDOWN = 4
学习啦在线学习网 Const DIR_DOWN = 5
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所以，只要我们把该点的对于黑棋和白棋的价值算出
来，然后我们就取棋盘上各个空点的这两个值的和的最大一点作为下棋的点。然而，对各种棋型应该取什么值呢?我们可以先作如下假设：
Fn 表示先手n个棋子的活棋型，如：F4表示先手活四
学习啦在线学习网 Fn'表示先手n个棋子的冲棋型，如：F4'表示先手冲四
Ln 表示后手n个棋子的活棋型，如：L3表示后手活三
学习啦在线学习网 Ln'表示后手n个棋子的冲棋型，如：L3'表示后手冲三
根据在一行中的棋型分析，得到如下关系：
L1'<=F1'
从这个关系包含了进攻和防守的关系(当然，这个关系是由我定的，你可以自己定义这些关系)。对这些关系再进一步细化，如在一个可下
棋的点，其四个方向上都有活三，也比不上一个冲四，所以我们可以又得到4*F3
到了下面各种棋型的分值，由C语言表示为：
F[2][5]={{0,2,5,50,16000},{0,10,30,750,16000}};
学习啦在线学习网 L[2][5]={{0,1,5,50,3750},{0,10,30,150,4000}};
F数组表示先手，第一个下标为0时表示冲型，第二个下标表示棋子数，则F2'对应F[0][2]L数组表示后手，第一个下标为0时表示冲型，第二
学习啦在线学习网 个下标表示棋子数，则L2对应F[1][2]Ok，棋型的分值关系确定好了以后，我们把每一个可下点的四个方向的棋型值相加(包括先手和后手的分
值)，最后选择一个最大值，并把这一点作为计算机要下的点就OK了:)。
后话：
1、得到最大值也许不止一个点，但在我的程序中只选择第一个最大点，当然你可以用于个随机数来决定
选择那一个最大值点，也可以对这些最大值点再作进一步的分析。
学习啦在线学习网 2、在这个算法中我只考虑了周围有棋子的点，而其它点我没有考虑。
学习啦在线学习网 3、可以再更进一步，用这个算法来预测以后的几步棋，再选择预测值最好的一步，这样电脑的AI就更高了
学习啦在线学习网 4、这个算法没有考虑黑棋的禁手(双3、双四和多于五子的连棋)。因为在平时我下的五子棋是没有这些
禁手的。
五子棋算法探讨
近来随着计算机的快速发展，各种棋类游戏被纷纷请进了电脑，使得那些喜爱下棋，又常常苦于没有对手的棋迷们能随时过足棋瘾。而且这类软件个个水平颇高，大有与人脑分庭抗礼之势。其中战胜过国际象棋世界冠军-卡斯帕罗夫的“深蓝”便是最具说服力的代表;其它像围棋的“手淡”、象棋的“将族”等也以其优秀的人工智能深受棋迷喜爱;而我们今天将向大家介绍的是五子棋的算法。
学习啦在线学习网 当我们与电脑对战时，您知道这些软件是怎样象人脑一样进行思考的吗?前不久我曾编写过一个五子棋的游戏，在这里就以此为例和大家一起探讨探讨。
总的来说(我们假定您熟悉五子棋的基本规则)，要让电脑知道该在哪一点下子，就要根据盘面的形势，为每一可能落子的点计算其重要程度，也就是当这子落下后会形成什么棋型(如：“冲四”、“活三”等)，然后通览全盘选出最重要的一点，这便是最基本的算法。当然，仅靠当前盘面进行判断是远远不够的，这样下棋很容易掉进玩家设下的陷阱，因为它没有考虑以后的变化。所以在此基础上我们加入递归调用，即：在电脑中预测出今后几步的各种走法，以便作出最佳选择，这也是我们下棋时常说的“想了几步”。如此一来您的程序便具有一定的水平了。什么?不信!过来试试吧!
学习啦在线学习网 总体思路弄清之后，下面进行具体讨论：
一：数据结构
学习啦在线学习网 先来看看数据结构，我们需要哪些变量?
学习啦在线学习网 首先得为整个棋盘建立一张表格用以记录棋子信息，我们使用一个15*15的二维数组 Table[15][15] (15*15是五子棋棋盘的大小)，数组的每一个元素对应棋盘上的一个交叉点，用‘0’表示空位、‘1’代表己方的子、‘2’代表对方的子;这张表也是今后分析的基础。
学习啦在线学习网 在此之后还要为电脑和玩家双方各建立一张棋型表Computer[15][15][4]和Player[15][15][4]，用来存放棋型数据，就是刚才所说的重要程度，比如用‘20’代表“冲四”的点，用‘15’代表“活三”的点，那么在计算重要性时，就可以根据20>15得出前者比后者重要，下子时电脑便会自动选择“冲四”的点。那为什么棋型表要使用三维数组呢?因为棋盘上的每一个点都可以与横、竖、左斜、右斜四个方向的棋子构成不同的棋型，所以一个点总共有4个记录;这样做的另一个好处是可以轻易判断出复合棋型，例如：如果同一点上有2个‘15’就是双三、有一个‘15’和一个‘20’就是四三。
怎么样!3个数组构成了程序的基本数据骨架，今后只要再加入一些辅助变量便可以应付自如了。应该不会太难吧?OK!有了这么多有用的数据，我们就可以深入到程序的流程中去了。
二：程序流程
我们主要讨论五子棋的核心算法，即：人工智能部分，而其他像图形显示、键盘鼠标控制等，因较为简单，所以就不作过多介绍了。
程序由六个基本功能模块构成，各模块的详细分析如下：
(1)初始化：首先，建立盘面数组Table[15][15]、对战双方的棋型表Computer[15][15][4]和Player[15][15][4]并将它们清零以备使用;然后初始化显示器、键盘、鼠等输入输出设备并在屏幕上画出棋盘。
(2)主循环控制模块：控制下棋顺序，当轮到某方下子时，负责将程序转到相应的模块中去，主要担当一个调度者的角色。
(3)玩家下子：当轮到玩家下时，您通过键盘或鼠标在棋盘上落子，程序会根据该点的位置，在Table[15][15]数组的相应地方记录‘2’，以表明该子是玩家下的。
(4)盘面分析填写棋型表：本程序核心模块之一，人工智能算法的根本依据!其具体实现方法如下：您在下五子棋时，一定会先根据棋盘上的情况，找出当前最重要的一些点位，如“活三”、“冲四”等;然后再在其中选择落子点。但是，电脑不会像人一样分析问题，要让它知道哪是“活三”、哪是“冲四”，就得在棋盘上逐点计算，一步一步的教它。
先来分析己方的棋型，我们从棋盘左上角出发，向右逐行搜索，当遇到一个空白点时，以它为中心向左挨个查找，如果遇到己方的子则记录然后继续，如果遇到对方的子、空白点或边界就停止查找。左边完成后再向右进行同样的操作;最后把左右两边的记录合并起来，得到的数据就是该点横向上的棋型，然后把棋型的编号填入到Computer[x][y][n]中就行了(x、y代表坐标，n=0、1、2、3分别代表横、竖、左斜、右斜四个方向)。而其他三个方向的棋型也可用同样的方法得到，当搜索完整张棋盘后，己方棋型表也就填写完毕了。然后再用同样的方法填写对方棋型表。
注意：所有棋型的编号都要事先定义好，越重要的号数越大!
OK! 怎么样?有点累了吧?不过千万别泄气!因为好戏还在后头。
学习啦在线学习网 Let's go!
学习啦在线学习网 (5)电脑下子：有了上面填写的两张棋型表，现在要作的就是让电脑知道在哪一点下子了。其中最简单的计算方法，就是遍历棋型表Computer[15][15][4]和Player[15][15][4]找出其中数值最大的一点，在该点下子即可。但这种算法的弱点非常明显，只顾眼前利益，不能顾全大局，这就和许多五子棋初学者一样犯了“目光短浅”的毛病。
要解决这个问题，我们引入‘今后几步预测法’，具体方法是这样的： 首先， 让电脑分析一个可能的点，如果在这儿下子将会形成对手不得不防守的棋型(例如：‘冲四’、‘活三’);那么下一步对手就会照您的思路下子来防守您，如此一来便完成了第一步的预测。这时再调用模块4对预测后的棋进行盘面分析，如果出现了‘四三’、‘双三’或‘双四’等制胜点，那么己方就可以获胜了(当然对黑棋而言‘双三’、‘双四’是禁手，另当别论);否则照同样的方法向下分析，就可预测出第二步、第三步……
等一等，要是盘面上没有对手必须防的棋型，哪该怎么办呢?进攻不成的话就得考虑防守了，将自己和对手调换一下位置，然后用上面的方法来预测对手的棋，这样既可以防住对手巧妙的攻击，又能侍机发动反击，何乐而不为呢!
但是必须告诉大家的是：预测法的运算量相当之大，据我的经验，用Pentium-100预测3步的走法平均需要15秒以上时间，所以建议预测量在5步以内。可别小瞧了这5步，有时它甚至会走出让您拍手叫绝的妙着呢!
学习啦在线学习网 (6)胜负判断：务须多言，某方形成五子连即获胜;若黑棋走出‘双三’、‘双四’或长连即以禁手判负。
到现在为止，整个五子棋软件就基本完成了，其水平大约在中级上下。当然，这种算法并不是最好的，但我相信它的基本思路是正确的。如果您有什么问题或好的想法，欢迎给我发E-mail: softboy@sina.com，我期待着您的见解。
五子棋禁手判定算法
学习啦在线学习网 禁手的判定较为复杂，设计一个判断禁手的算法既要分析构成它的棋型又要找到合适的搜索方法。
首先分析棋型。
先考虑构成长连禁手的棋型，构成长连的棋型较简单，可归纳为一种，即相连后形成六子或更多相连。一旦发现产生此棋型，即判为长连禁手。
再考虑构成四四禁手、三三禁手的棋型。要判断下某一子是否构成四四禁手(或三三禁手)，只需判断下这一子后是否产生两个或两个以上的冲四或活四(或活三)即可。所以归结起来，要正确判断四四禁手、三三禁手就是要正确判断冲四、活四和活三。
考虑冲四、活四和活三的定义。冲四是只有一个点可以成五的四，这里我们将那个点称为关键点。同样，构成活四的有两个关键点，构成活三的有一个关键点。如图11，a,b两点是其构成活四的关键点，又如图12，a点是其构成活三的关键点。
 图12 |
学习啦在线学习网 以下是对各棋型和关键点的分析。
1、活四：
学习啦在线学习网 归结起来构成活四的只有一种棋型,如图13
 图13 |
学习啦在线学习网 这种棋型真正构成活四的条件是左右两空位(即a,b点)必须是黑棋可下的点，也就是在a,b点下黑子后都不会构成禁手。
2、冲四：
学习啦在线学习网 形成冲四有两种棋型，如图14和图15
 图14 |  图15 |
学习啦在线学习网 这两种棋型真正构成冲四的条件是中间的空位(即a点)必须是黑棋可下的点，也就是在a点下子后不会构成禁手。
3、活三：
形成活三有两种棋型，如图16和图17
 图16 |  图17 |
学习啦在线学习网 其中，a点是关键点，b,c点可以是边界、无子或白色棋子，但不能是黑色棋子。
学习啦在线学习网 这两种棋型真正构成活三的条件是a点必须是黑棋可下的点，也就是在a点下子后不会构成禁手，m,n两点不用管是否构成禁手，因为当a点放入黑子后，不管在m点还是n点放黑子，就会形成五连，即获胜，不构成禁手。
所以我们要判断一种棋型是否构成冲四、活四或活三，需要在已判断它是可能的冲四、活四或活三的棋型的基础上判断它的关键点是否可落黑色棋子，也就是判断关键点是否不会构成新的禁手点，这一步在程序中可以用递归实现。
棋型分析完成，我们就要据此考虑选择合适的算法。
基于禁手分析所需的精确度，我们在棋盘盘面搜索时，需要记录与待判断点相邻的连续黑色棋子数，并记录之后的连续空子数，并记录再之后的连续黑子数，和再之后的连续空子数，以及再之后的连续黑子数。所以可以说搜索的深度要达到5层。
学习啦在线学习网 在判断关键点的可下性时，选用递归的方法来判断其是否不是禁手点。
学习啦在线学习网 于是最后我们可以得出禁手判定算法的思路。
第一步：将待判断点放入黑棋子;
学习啦在线学习网 第二步：搜索待判断点周边棋盘;
第三步：还原棋盘;
第四步：利用搜索结果依次对各方向进行分析，判断黑棋放入后所产生的棋型是否形成长连或形成可能构成活四、冲四、活三的棋型。若形成长连，判定为禁手，返回长连禁手标识。若形成可能是活四、冲四、活三的棋型，判断关键点是否可下，若不可下，该棋型统计数加1，反之，则对下一个方向进行判断，直到各个方向分析结束。
第五步：若活四、冲四棋型的统计数大于1，返回四四禁手标识，若活三棋型的统计数大于1，返回三三禁手标识。其余情况返回非禁手标识。
源代码:
