TypeButton}">
这里我们把这个Style称为Style1。
界面逻辑上，将是否开始、是否禁手和是否电脑先行
作为两个全局变量的布尔型值，通过设置和判断bool型值进行逻辑上的控制。
中间的棋盘是个canvas，一个15*15的Grid放满Button并将每个Button应用Style1开始时候透明度设为0，也就是根本看不到，在下棋的时候改变Button的背景和透明度，实现落子
的效果，因为Grid的位置关系，所以可看起来好像是下在横竖的交线处。
第三步，进行输赢判断：
因为规则不同，“无禁手”和“有禁手”的输赢判断自然不同。
先看无禁手：
这个比较简单，遍
历每个位置，然后从这个位置开始，分别判断它的四个方向：
即横、竖、左上到右下、左下
到右上。
每个方向从中间点开始，往两边数连子数，然后将两个方向的连字数加和再加一
（中
间的棋子）。
如果得到大于等于
5，那么就说明下子方赢棋。
对于有禁手的五子棋，输赢判断还需要判断禁手，禁手的判定较为复杂。
将待判断点放入黑
棋子。
然后搜索待判断点周边棋盘；还原棋盘；利用搜索结果依次对各方向进行分析，
判断
黑棋放入后所产生的棋型是否形成长连或形成某种四连或三连的的棋型。
若形成长连，判定
为禁手，返回长连禁手标识。
若形成某种四连或三连的棋型，该棋型统计数加
1，再对下一
个方向进行判断，直到各个方向分析结束。
若四连棋型或三连棋型的统计数大于１，
则返回
为禁手。
其余情况返回非禁手。
第四步：
构造棋型估分
“有禁手”规则比较复杂，涉及到比较多下棋方面的技巧，而且对算法的思路没有丝毫影响，
所以下面我们主要考虑无禁手规则下的AI设计。
若设计好无禁手AI，只需要让AI执黑时
坚决不下到禁手点，就可以很快构造有禁手的AI。
虽然这种方式没有利用有禁手规则下的技巧，但这些技巧只需要修改下面所讲到的估分函数即可。
我们可以将五子棋的连珠可以分为以下几种：
成5：
即构成五子连珠
活4：
即构成两边均不被拦截的四子连珠。
死4：
一边被拦截的四子连珠
活3：
两边均不被拦截的三字连珠
死3：
一边被拦截的三字连珠
活2：
两边均不被拦截的二子连珠
死2：
一边被拦截的二子连珠单子：
四周无相连棋子
根据五子棋的技巧，可以将五子棋的棋型用连珠进行分类，分类过后我们按照威力给每种棋型打分。
因为五子棋一次只落一子，因此很容易理解，双活三和三活三的威力是一样的，类
似情况不多做解释。
程序中，我以100分为满分，对棋型进行了以下打分：
成5,100分
活4、双死4、死4活3，90分双活3，80分
死3活3，70分
死4，60分
活3，50分
双活2，40分死3，30分
活2，20分
死2，10分单子0分
有了估分方法，就有了五子棋AI的基础，接下来就是一些博弈的方法了。
第五步：
得到位置估分
AI
单纯应用棋谱以及对五子棋当前局势的分析，对每步进行估分，程序中做如下工作：
将每个
位置进行分析，假设AI落子在该位置，用以上打分规则为AI打分,并将得到的分数加一。
然后，假设玩家落子在该点，为玩家打分，然后将所有的分值汇总。
取最高分作为这个位置
的估分，接下来就是取分数最高的位置下棋了。
“位置估分”，下棋的时候，既可以考虑到自
己攻击对手，又能考虑到对对手的防御，可以说，很多时候可以顶上考虑两步的AI。
作实
验，从网上下载了一个用博弈做的AI，和“位置估分”对下，结果是一胜一负。
谁先子，谁
赢得胜利。
而且一步估分毫无疑问是最快的，即使遍历所有位置，也能很快的做出决策。
第六步：
应用博弈树，提高
AI
智能
做五子棋的博弈，自然会用到博弈树，这里我说下自己的思路。
在对弈中,根据下一步由谁
来走,AI对任何一个局面根据前面估分方法给出一个分数,我们把这个估分方法汇总成一个
评估函数，并返回分值。
据此来选择下一步的走法。
由于人和AI是轮流落子，可以将人的
估分也算入，并将前面加负号。
那么，估值越大表明对AI越有利，估分越小则表明对AI
越不利。
那么每次AI选择都是从它可能的走法树的某层节点，返回评估值中最大点。
而用
户总是从走法树的某层节点中选择最小点，从而形成一棵极大极小搜索树，然后根据深度优
先搜索，可以最后得到固定搜索深度下的一个最好的走法。
我做了下试验，单纯应用博弈树，
可以在100ms之内让AI考虑完整的两步，由于组合爆炸，当需要考虑三步的时候，就需
要6s左右，4步就需要1分钟。
拿两步来和一步估分作比较，虽然比较慢，但是确实有了一定智能。
第七步：
考虑层数，提高
AI
智能
上面的设计对于返回值是统一处理的,但是，层数是个很重要的信息.因为下棋时如果能2步
获胜,不应选择4步获胜。
对于输的棋型层数就更重要,AI必须尽可能拖延输的时间，就有
更大的可能让AI化险为夷。
这样，可以通过设置一个dep值。
深度约浅，dep越大，用
dep和得到的得分相乘，得到搜索节点的得分，再进行以上算法，进一步提高AI的智能。
第八步：
应用α-β剪枝，提高AI速度
在搜索博弈树的过程中，实际上搜索有很多点是多余的，例如下图
图中，方形框节点是该
AI走,圆形框节点是该人走.比如C节点,它需要从E
和F当中选取
最大的值。
目前已经得出
E为2,当搜索F节点时,因为F是人走的节点，那么
F需要从KL
M中选取最小的，因为
K已经是1，也就是说F<=1，那么L，M就不需要搜索，因此就
发生了α剪枝。
然后看A节点，该人走了，需要从C和D中选取最小值，因为C节点是2，
而G是7，那么D至少是7。
因此，D的其他节点不必再考虑，就发生如上图所示的β剪
枝。
总结上面规律，我们可以得到剪枝方法如下：
当前为AI下棋节点：
α剪枝：
如果当前节点的值不比父节点的前兄弟节点的大值大
则舍弃此节点。
β剪枝：
如果当前节点子节点的值不比当前节点的前兄弟节点中的最小值小
则舍弃该子节
点和该子节点的所有后兄弟节点。
当前为用户下棋节点：
α剪枝：
如果当前节点的某子节点的值不比当前节点的前兄弟节点中的最大值大
则舍弃该
子节点和该子节点的所有后兄弟节点。
β剪枝：
如果当前节点的子节点的值不比当前的父节点的前兄弟节点中的最小值小则舍弃此节点。
经过α-β剪枝，可以极大的减少搜索的数量，很多时候，能把几十亿的搜索数量，缩小到
几亿，那么，就可以把搜索深度增1。
第九步：
应用下棋范围，提高
AI
速度
当前节点的子节点的数量和排列顺序对于搜索的速度起着至关重要的影响。
根据五子棋的特点,可以产生一个棋面搜索范围。
记录当前棋面所有棋子的最左最右最上最下点构成的矩形我们认为下一步棋的位置不会脱离这个框3步以上。
这样在棋子较少的时候，搜索节点的数量大大减少。
可以将AI的速度提高一倍左右。
第十步：
利用棋型得分，提高
AI
速度
因为每种下法都对应一种得分，所以，可以每次只考虑当前得分前十的节点进行下一步搜索大大减少了搜索范围，可以进一步增加搜索的深度。
，
第十一步：
利用置换表，提高
AI
速度
我们一般用递归的方法实现博弈树，但是，递归的效率是低的，而且很明显，有很多重复搜索的节点，所以，我们可以用一个表，记录下所有搜索过节点的情况，然后只要遇到搜索到
的节点，就可以直接得到结果。
置于这个“表”是什么，就是一个置换表，利用Zobrist算法，
进行Hash处理，使在表中查找的时间大大缩短，这样AI的速度又能提高一个数量级。
第十二步：
利用多线程，提高
AI
速度
我们其实可以利用多核技术，利用多个线程，让算法实现并行计算，提高AI的速度。
我们在第一层用一个线程分配器把第二层的候选节点分配给多个线程,每个线程包含着从第二层一个候选节点开始的搜索,然后等所有线程结束后,将所有线程的结果进行汇总,选出最大值。
并行的程序，可以将速度提高一倍左右。
第十三步：
利用随机化算法，让确定方法不能必胜
由于AI算法的固定性，所以一担玩家一次获胜，按照相同的走法，必然会再次获胜。
但除
了必杀招或者必防招,一个局面很多时候没有绝对最好的走法。
而是有一些都不错的走法,那
么可以把这些评分差不多走法汇集起来,然后随机选择它们中的一种走法,避免AI的走法的
固定.这样最简单的方法避免固定方法AI必输。
第十四步：
让
AI
自学习，不再同一个地方犯错
上面的算法还没有自学习的能力,这样AI在下棋时还可能会重蹈覆辙。
因此在每盘棋结束时
如果AI输，则进行大于搜索深度的步数回退。
可以把倒数为搜索深度数目的局面定为目标
局面，从倒数深度加一步局面进行预测,找到不会导出必败目标局面的局面。
然后记录下这
个局面和前面的局面，并据此修改评分函数。
这样AI就不会犯曾经犯过的错误，达到自学
习的效果。
做到以上十四步，一个拥有强大
AI
的五子棋游戏即可诞生！
五子棋算法可简可繁,要看你对自己五子棋程序智能的要求,人机对战的意思就是人和电脑
下,也就是说电脑会思考如何下棋....其实这才是五子棋程序的核心.如果只实现人与人对战
的话,是一件很简单的事情,无非就是绘制棋盘,然后绘制下棋的效果,再写个下棋合法性判断,
胜负判断....大概就搞定了....所以核心其实是人机对战的电脑那部分人工智能.这东西吧,可
以研究的很多,不过主要的几个设计要点就是搜索算法和估值算法,这两个是最主要的,还有
提高电脑思考销率的方法就有多cpu的计算机多线程思考的设计....通过一些手段让电脑变
得更像人类棋手的,例如利用一些遗传算法之类的让电脑具有学习能力,可以在失败中吸取
教训,开局库,历史启发之类的一大堆......但是总而言之,这一系列算法的设计没有一个标准,
只要能让你的电脑下棋下的更聪明,更快那就是好算法.国内有一个叫王晓春的写过一本叫
<>的书,这是一本研究人机博弈程序很经典的书,书的后面还附了
一个五子棋的程序实例,你可以参考一下.下面是csdn的下载地址,你也可以自己去搜一下.
五子棋的核心算法
五子棋是一种受大众广泛喜爱的游戏，其规则简单，变化多端，非常富有趣味性和消遣性。
这里设计和实现了一个人机对下的五子棋程序，采用了博弈树的方法，应用了剪枝和最大最
小树原理进行搜索发现最好的下子位置。
介绍五子棋程序的数据结构、评分规则、胜负判断
方法和搜索算法过程。
一、相关的数据结构
关于盘面情况的表示，以链表形式表示当前盘面的情况，目的是可以允许用户进行悔棋、回退等操作。
CListStepList;
其中Step结构的表示为：
structStep
{
intm;//m,n表示两个坐标值
intn;
charside;//side表示下子方
};
以数组形式保存当前盘面的情况，
目的是为了在显示当前盘面情况时使用：
charFiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE];
其中FIVE_MAX_LINE表示盘面最大的行数。
同时由于需要在递归搜索的过程中考虑时间和空间有效性，只找出就当前情况来说相对比
较好的几个盘面，而不是对所有的可下子的位置都进行搜索，这里用变量CountList来表示当前搜索中可以选择的所有新的盘面情况对象的集合：
CListCountList;
其中类CBoardSituiton为:
classCBoardSituation
{
CListStepList;//每一步的列表
charFiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE];
structStepmachineStep;//机器所下的那一步
doublevalue;//该种盘面状态所得到的分数
}
二、评分规则
对于下子的重要性评分，需要从六个位置来考虑当前棋局的情况，分别为：
-,|,/,\,//,\\
实际上需要考虑在这六个位置上某一方所形成的子的布局的情况，对于在还没有子的地方
落子以后的当前局面的评分，主要是为了说明在这个地方下子的重要性程度，设定了一个简单的规则来表示当前棋面对机器方的分数。
基本的规则如下：
判断是否能成5,
如果是机器方的话给予
100000分，如果是人方的话给予－
100000
分；
判断是否能成活
4或者是双死4或者是死
4活3，如果是机器方的话给予
10000分，如果是
人方的话给予－10000分；
判断是否已成双活
3，如果是机器方的话给予
5000分，如果是人方的话给予－
5000
分；
判断是否成死3活3，如果是机器方的话给予
1000分，如果是人方的话给予－
1000
分；
判断是否能成死
4，如果是机器方的话给予
500分，如果是人方的话给予－
500分；
判断是否能成单活
3，如果是机器方的话给予
200分，如果是人方的话给予－
200
分；
判断是否已成双活
2，如果是机器方的话给予
100分，如果是人方的话给予－
100
分；
判断是否能成死
3，如果是机器方的话给予
50分，如果是人方的话给予－
50分；
判断是否能成双活
2，如果是机器方的话给予
10分，如果是人方的话给予－
10分；
判断是否能成活
2，如果是机器方的话给予
5分，如果是人方的话给予－
5分；
判断是否能成死
2，如果是机器方的话给予
3分，如果是人方的话给予－
3分。
实际上对当前的局面按照上面的规则的顺序进行比较，如果满足某一条规则的话，就给该
局面打分并保存，然后退出规则的匹配。
注意这里的规则是根据一般的下棋规律的一个总结，在实际运行的时候，用户可以添加规则和对评分机制加以修正。
三、胜负判断
实际上，是根据当前最后一个落子的情况来判断胜负的。
实际上需要从四个位置判断，以
该子为出发点的水平，竖直和两条分别为是否最后落子的一方构成连续五个的棋子，
45度角和135度角的线，目的是看在这四个方向
如果是的话，就表示该盘棋局已经分出胜负。
具
体见下面的图示：
四、搜索算法实现描述
注意下面的核心的算法中的变量currentBoardSituation，表示当前机器最新的盘面情况,
CountList表示第一层子节点可以选择的较好的盘面的集合。
核心的算法如下：
voidMainDealFunction（）
{
value=－MAXINT;//对初始根节点的value赋值
CalSeveralGoodPlace（currentBoardSituation,CountList）;
//该函数是根据当前的盘面情况来比较得到比较好的可以考虑的几个盘面的情况，可以根据
实际的得分情况选取分数比较高的几个盘面，也就是说在第一层节点选择的时候采用贪婪算
法，直接找出相对分数比较高的几个形成第一层节点，目的是为了提高搜索速度和防止堆栈溢出。
pos=CountList.GetHeadPosition（）;
CBoardSituation＊pBoard;
for（i=0;ivalue=Search（pBoard,min,value,0）;
Value=Select（value,pBoard－>value,max）;
//取value和pBoard－>value中大的赋给根节点
}
for（i=0;ivalue）
//找出那一个得到最高分的盘面
{
currentBoardSituation=pBoard;
PlayerMode=min;//当前下子方改为人
Break;
}
}
其中对于Search函数的表示如下：
实际上核心的算法是一个剪枝过程，其中在这个搜索过
程中相关的四个参数为：
（1）当前棋局情况；
（2）当前的下子方，可以是机器（max）或者是
人（min）；（3）父节点的值oldValue；（4）当前的搜索深度depth。
doubleSearch（CBoardSituation＆
board,intmode,doubleoldvalue,intdepth）
{
CListm_DeepList;
if（deptholdvalue））==TRUE）
{
if（mode==max）
value=select（value,search（successor
Board,min,value,depth＋1）,max）;
else
value=select（value,search（successor
Board,max,value,depth＋1）,min）;
}
returnvalue;
}
else
{
if（goal（board）<>0）
//这里goal（board）<>0表示已经可以分出胜负
returngoal（board）;
else
returnevlation（board）;
}
}
注意这里的goal（board）函数是用来判断当前盘面是否可以分出胜负，而当前的盘面从机器的角度进行打分。
evlation（board）是对
下面是Select函数的介绍，这个函数的主要目的是根据
PlayerMode
情况，即是机器还是用
户来返回节点的应有的值。
doubleSelect（doublea,doubleb,intmode）
{
if（a>b＆＆mode==max）||（areturna;
else
returnb;
}
五、小结
在Windows操作系统下，用VC＋＋实现了这个人机对战的五子棋程序。
和国内许多只是
采用规则或者只是采用简单递归而没有剪枝的那些程序相比，在智力上和时间有效性上都要
好于这些程序。
同时所讨论的方法和设计过程为用户设计其他的游戏（如象棋和围棋等）提供了一个参考。
大部分算法中，都要进行两步。
升级会员 