五连珠问题_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
五连珠问题
上传于||暂无简介
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩9页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢　　这是我两年前完成的一个小项目，它基于我开发的。五子棋算法网上随便一搜到处都是，不过值得自豪的是，我在2KB内存的单片机上不仅跑上了我自制的嵌入式OS，还能同时跑五子棋。这是界面截图：
&以下是它的功能和特性：
内存占用极低，约600byte
执行一次迭代过程，算法在初级水平（同学，这是单片机，不是电脑！）
在8MHz的MSP430上算法执行时间不超过0.3s
支持人机对战，双人对战和无线对战（通过NRF24L01实现）
嵌入式彩屏GUI实现
支持陀螺仪体感旋转放置棋子
& & 与XMOVE手持终端相关的介绍文章列表如下:
　　下面我将简要的介绍系统实现过程，同时附上源代码。不过因为我系统对低内存平台做了特别的优化，如果你要纯粹往PC上移植的话，可能还不如去PUDN上面下代码来得快。当然参考一下设计思路也是有价值的。
二. 分析和数据结构定义
　　我们要重点分析以下几个问题：
如何精简内存占用
　　为了简化代码，我做了如下的定义：
　　#define unsigned char u8 //8bit
&&&&& #define unsigned intu16 //16bit
　　对于2KB内存的单片机，已经有将近1KB用于系统本身，可供使用的应用内存不超过1KB。如果不做优化，内存必然不够用。可以简单做个计算，五子棋盘大小15*15，每格存在三种情况，黑子，白子，无子，若用byte型存储，就需要225byte,若加上中间迭代过程是完全不够的。
　　因此我做了如下简化：每个子只占用两个bit,因此总共225个点，采用16bit的unsigned int存储，仅仅需要29大小的数组
　　做了这样的简化，必须提供读取或写入某点是何情况的接口函数：
　　PS:大三写的C代码，有点丑陋，大家随便看看吧
//x,y是横纵坐标，Data是数组
//返回0：无子，1 ：黑子，2：白子
u8 ReadData(u8 x,u8 y,u16
u8 t=y+x*15;
u16 temp=0x03;
temp=temp&&2*(t%8);
return ((Data[t/8]&temp)&&(2*(t%8)));
//x,y是横纵坐标，Data是数组
// dat 0：无子，1 ：黑子，2：白子
void WriteData(u8 x,u8 y,u16 Data[29],u8 dat)
u8 t=y+x*15;
u16 temp=0x03;
temp=temp&&2*(t%8);
temp=0xffff-
Dat=Dat&&2*(t%8);
Data[t/8]=(Data[t/8]&temp)|D
　　2. 判断胜负
　　系统在任意一方下棋之后，需要检测该方是否获胜，很简单，我们检测横竖，左斜和右斜四种情况是否满足五子连珠即可：
u8 ResultCheck(u16
Data[29],u8 color)
//成功测试 返回值：0：不成功，1 白方， 2黑方
// 判断横向
for ( y = 0; y & 15; y++ )
for ( x = 0; x & 11; x++ )
if ( color ==ReadData(x,y,Data)
color == ReadData(x+1,y,Data) &&
color == ReadData(x+2,y,Data)
color == ReadData(x+3,y,Data)
color == ReadData(x+4,y,Data)
// 判断纵向
for ( y = 0; y & 11; y++ )
for ( x = 0; x & 15; x++ )
if ( color ==ReadData(x,y,Data) &&
color ==ReadData(x,y+1,Data) &&
color == ReadData(x,y+2,Data) &&
color ==ReadData(x,y+3,Data) &&
color == ReadData(x,y+4,Data) )
// 判断"\"方向
for ( y = 0; y & 11; y++ )
for ( x = 0; x & 11; x++ )
if ( color == ReadData(x,y,Data)&&
color == ReadData(x+1,y+1,Data) &&
color ==ReadData(x+2,y+2,Data)&&
color ==ReadData(x+3,y+3,Data)&&
color == ReadData(x+4,y+4,Data) )
// 判断"/"方向
for ( y = 0; y & 11; y++ )
for ( x = 4; x & 15; x++ )
if ( color ==
ReadData(x,y,Data) &&
ReadData(x-1,y+1,Data) &&
ReadData(x-2,y+2,Data) &&
ReadData(x-3,y+3,Data) &&
ReadData(x-4,y+4,Data) )
// 不满足胜利条件
& 3. 核心算法
　　如前所述，由于单片机的硬件和内存限制，我们需要在算法实现上做一些必要的妥协：
　　按盘面分析填写棋型表：本程序核心模块之一，人工智能算法的根本依据。其具体实现方法如下：在下五子棋时，一定会先根据棋盘上的情况，找出当前最重要的一些点位，如&活三&、&冲四&等；然后再在其中选择落子点。但是，电脑不会像人一样分析问题，要让它知道哪是&活三&、哪是&冲四&，就得在棋盘上逐点计算，一步一步的教它。　　先来分析己方的棋型，我们从棋盘左上角出发，向右逐行搜索，当遇到一个空白点时，以它为中心向左挨个查找，如果遇到己方的子则记录然后继续，如果遇到对方的子、空白点或边界就停止查找。左边完成后再向右进行同样的操作；最后把左右两边的记录合并起来，得到的数据就是该点横向上的棋型，然后把棋型的编号填入到Computer[x][y][n]中就行了（x、y代表坐标，n=0、1、2、3分别代表横、竖、左斜、右斜四个方向）。而其他三个方向的棋型也可用同样的方法得到，当搜索完整张棋盘后，己方棋型表也就填写完毕了。然后再用同样的方法填写对方棋型表。　　注意：所有棋型的编号都要事先定义好，越重要的号数越大。经过我的测试，从0子到四子连珠的评分标准可以用这个数组来表达：long MarkTransform[5]={0,100,400,};
　　于是，电脑在下棋时，仅仅需要计算哪个点的评分最大，就在这点下棋。
&4. 核心算法实现和内存优化
　　如果大家仔细的看了第三部分的内容，就不难得到算法核心了，但问题也来了。我们要存储Computer和人这两个巨大的三维数组。所以必须制定自己的一套内存分配规则，来尽可能减小内存占用花销。
　　每个空子的位置，从左右方向的己方的子不会超过5种，所以，我们可以用4bit来存储（它可以储存8种情况）。 对每一方，例如计算机方，我们定义一个数组u16 Data[8][29]， u16 和29的来源在第一节就已经讲过，是225个点的存储。至于前面的8的来源：上下左斜右斜攻击四类情况，每类需要2bit，所以要定义8这样的大小。如下图：
　　 以下是计算整个棋盘每个点的评价值，存储在Data的临时数组当中， a,b,c,d四个寄存器，分别存储x,y坐标，向左和向右两个方向的判断步数（最多到4）,以及该空点在该线的连子数目。
//Data：棋型表
TotalCheseData当前全局的棋盘数据void CalGameSatus(u16 Data[][29],u16 TotalCheseData[29],u8 mood)
//mood=2黑方判断，mood=1；白方判断
u8 a,b,c,d;
for(a=0;a&15;a++)
for(b=0;b&15;b++)
if(ReadData(a,b,TotalCheseData)==0)
for(c=1;c&5;c++)
if(ReadData(a-c,b,TotalCheseData)!=mood||a-c==0)
for(c=1;c&5;c++)
if(ReadData(a+c,b,TotalCheseData)!=mood||a-c==14)
WriteData(a,b,Data[0],d%4);
//写入横向数据
WriteData(a,b,Data[1],d/4);
for(c=1;c&5;c++)
if(ReadData(a,b-c,TotalCheseData)!=mood||b-c==0)
for(c=1;c&5;c++)
if(ReadData(a,b+c,TotalCheseData)!=mood||b+c==14)
WriteData(a,b,Data[2],d%4);
//纵向数据
WriteData(a,b,Data[3],d/4);
//纵向数据
for(c=1;c&5;c++)
if(ReadData(a-c,b-c,TotalCheseData)!=mood||b-c==0||a-c==0)
for(c=1;c&5;c++)
if(ReadData(a+c,b+c,TotalCheseData)!=mood||b+c==14||a+c==14)
WriteData(a,b,Data[4],d%4);
//左斜数据
WriteData(a,b,Data[5],d/4);
for(c=1;c&5;c++)
if(ReadData(a-c,b+c,TotalCheseData)!=mood||a-c==0||b+c==14)
for(c=1;c&5;c++)
if(ReadData(a+c,b-c,TotalCheseData)!=mood||a+c==14||b-c==0)
WriteData(a,b,Data[6],d%4);
//右斜数据
WriteData(a,b,Data[7],d/4);
　　获取以上的评价规则后，我们得到对某一方的最核心的计算下子位置的函数：
　　在形参表中x,y通过指针的形式返回真正的计算结果， u16 Data1和 Data2分别是己方和对方的棋型表， TotalCheseData则是整个棋盘当前局势。算法挨个遍历每个点，计算该点在四个方向上的权值之和。分别计算己方和对方的值，最大评分点就是下子点。
　　其实完全可以这么理解，若己方的最大值大于对方的最大值，这显然对己方是有利的，己方应该进攻大于防守； 反之，对方已占先机，我方应该放手大于进攻。
CalPushPosition(u8 *X, u8 *Y,u16 Data1[][29],u16 Data2[][29],u16 TotalCheseData[29])
long TotalMark,MaxMark=0;
long MarkTransform[5]={0,100,400,2000,10000};
u8 m,n,p,M
CalGameSatus(Data1,TotalCheseData,1);
for(m=0;m&15;m++)
for(n=0;n&15;n++)
TotalMark=0;
for(p=0;p&4;p++ )
//对四个方向，看连子的数目，总评价分由这四个方向的值之和所决定
Mark=ReadData(m,n,Data1[2*p])+4*ReadData(m,n,Data1[2*p+1]);
//读取在x,y坐标下，连子的数目，其存储过程见棋型表存储结构
TotalMark+=
MarkTransform[Mark];
if(TotalMark&MaxMark)
*X=m,*Y=n;
MaxMark=TotalM
CalGameSatus(Data2,TotalCheseData,2);
for(m=0;m&15;m++)
for(n=0;n&15;n++)
TotalMark=0;
for(p=0;p&4;p++)
ReadData(m,n,Data2[2*p])+4*ReadData(m,n,Data2[2*p+1]);
TotalMark+=MarkTransform[Mark];
if(TotalMark&MaxMark)
*X=m,*Y=n;
MaxMark=TotalM
三. &其他模块的简单介绍
　　要实现五子棋，除了核心算法还有其他外围模块作为支持，有以下的函数：
画棋盘，选择框
无线对战（省略）
　　考虑到不同平台和硬件环境下，这些功能的实现可能完全不同，所以我仅仅贴一些示意性代码：
其他模块的实现（仅供参考）
void DrawDesk()
Clear_Screen();
SetPaintMode(0,COLOR_Black);
Rectangle(23,28,205,210,1);
SetPaintMode(0,COLOR_Yellow);
Rectangle(20,25,202,207,1);
SetPaintMode(0,COLOR_Black);
for(m=0;m&15;m++)
Line(20,25+13*m,200,25+13*m);
for(m=0;m&15;m++)
Line(20+13*m,25,20+13*m,207);
//Lcd_disp(240,12,"五子棋");
//Lcd_disp(65,36,"赵一鸣之作");
void Drawchess(u8 x,u8 y, u8 mood)
if(mood==2)//黑方
SetPaintMode(0,COLOR_Black);
Circle(20+13*x,25+y*13,5,1);
//Rectangle(2+x*4,1+y*4,4+x*4,3+y*4,1);
else if(mood==1)
SetPaintMode(0,COLOR_White);
Circle(20+13*x,25+y*13,5,1);
SetPaintMode(0,COLOR_Black);
Circle(20+13*x,25+y*13,5,0);
void PushChess(u8 x,u8 y,u16
Data[29],u8 mood)
Drawchess(x,y,mood);
WriteData(x,y,Data,mood);
u8 DrawKuang(u8 *x,u8 *y,u16
u8 func_state=0;
u8 GyroKey,myK
while(func_state==0)
SetPaintMode(0,COLOR_Black);
Rectangle(14+*x*13,19+*y*13,26+*x*13,31+*y*13,0);
if(GyroControlEN==1&&back_light&1&&GyroMenuEN)
delay_ms(200);
L3G4200DReadData();
L3G4200DShowData();
delay_ms(200);
InputControl();
GyroKey=GyroKeyBoardInputMethod(0,0,300,300);
if(GyroKey!=KEYNULL)
myKey=GyroK
myKey=key_
GyroKey=KEYNULL;
SetPaintMode(0,COLOR_Yellow);
Rectangle(14+*x*13,19+*y*13,26+*x*13,31+*y*13,0);
SetPaintMode(0,COLOR_Black);
PutPixel(20+(*x)*13,19+(*y)*13);
PutPixel(20+(*x)*13,(*y)*13+31);
PutPixel(14+(*x)*13,(*y)*13+25);
PutPixel(26+(*x)*13,(*y)*13+25);
switch(myKey)
case KEYENTER_UP
if(ReadData(*x,*y,Data)==0)
func_state=1;
case KEYCANCEL_UP
FourDirectionInputMethod(myKey,1,1,1,1,0,14,0,14,0,0, x,y);
myKey=KEYNULL;
四. &算法主流程（简化版）
　　流程因为很简单，所以就不画了。
while(OS_func_state==0)
//OS_func_state==0是正常的下棋状态
{if(func_state==0)
//我方下棋
if(DrawKuang(&XAxi,&YAxi,TotalCheseData))
PushChess(XAxi,YAxi,TotalCheseData,2);
OS_func_state=10;
if(ResultCheck(TotalCheseData,2)==2)
//胜利，跳出到成功界面
OS_func_state=5;
func_state=1;
//让给对方下棋
//对方下棋
GameSatusInit(myGameSatus);
GameSatusInit(itGameSatus);
CalPushPosition(&XAxi,&YAxi,myGameSatus,itGameSatus,TotalCheseData);
PushChess(XAxi,YAxi,TotalCheseData,1);
if(ResultCheck(TotalCheseData,1)==1)
OS_func_state=5;
func_state=0;
&五. 总结和改进
　　实现五子棋的算法有很多选项，比如基于博弈树的剪枝算法，和我这种比较简化的靠遍历评分的算法。这个算法来自于网上，水平仅仅算是初级，缺点也很明显，　　　　&&
&&&&& 只顾眼前利益，不能顾全大局，这就和许多五子棋初学者一样犯了&目光短浅&的毛病。要解决这个问题，我们引入&今后几步预测法&，具体方法是这样的： 首先， 让电脑分析一个可能的点，如果在这儿下子将会形成对手不得不防守的棋型（例如：&冲四&、&活三&）；那么下一步对手就会照您的思路下子来防守您，如此一来便完成了第一步的预测。这时再调用模块4对预测后的棋进行盘面分析，如果出现了&四三&、&双三&或&双四&等制胜点，那么己方就可以获胜了（当然对黑棋而言&双三&、&双四&是禁手，另当别论）；否则照同样的方法向下分析，就可预测出第二步、第三步&&
　　不过，我做过实际的测试，加上两步迭代以后，计算时间变为原来的10倍左右（确实是指数级的），但此时内存是不够用的。考虑到是2KB内存的超低功耗单片机，实现更复杂的算法勉为其难，我也就没有在上面实现迭代，有兴趣的同学们可以尝试实现之，其实不难，用个好点的CPU，比如STM32,（用电脑就别用我这个算法了），稍微改改代码就可以。这种情况，电脑的水平在中级左右。
　　系统没有随机性，换句话说，如果你每次下子的方式是一样的，那么系统演化的形式完全一致。
　　顺便提一下，自从学习了C#编程以后，看了两年前写的C代码，真是不堪入目。不过，在单片机上实现的东西，效率比可读性和结构性更重要吧。
　　有任何问题，欢迎随时交流。　　
阅读(...) 评论()
$(function(){ $("input[name=article_support]").click(function(){ $("textarea[class=comment_textarea]").val("文章不错，支持一下！"); ; }); $("input[name=article_pass]").click(function(){ $("textarea[class=comment_textarea]").val("飘过~~"); ; }); </script吴昊品游戏核心算法 Round 5 —— （转载）十四步实现拥有强大AI的五子棋游戏 - 吴昊系列 - 博客园
唯有真实的苦难，才能消除那些罗曼蒂克的幻想苦难
十四步实现拥有强大AI的五子棋游戏
博主按：在看到这篇文章的时候有很深刻的体会了，毕竟我的大学第一个C语言作品就是五子棋，时隔十多年我用Java在Android重新设计了手机版五子棋游戏，这篇文章对于五子棋算法的分析有很强的实用性，有点相见恨晚的感觉啊，我要接着改进AI了。
想做个好的人机对弈的五子棋，可以说需要考虑的问题还是很多的，我们将制作拥有强大AI五子棋的过程分为十四步，让我来步步介绍。
第一步，了解禁手规则
做 一个五子棋的程序，自然对五子棋需要有足够的了解，现在默认大家现在和我研究五子棋之前了解是一样多的。以这个为基础，介绍多数人不大熟悉的方 面。五子棋的规则实际上有两种：有禁手和无禁手。由于无禁手的规则比较简单，因此被更多人所接受。其实，对于专业下五子棋的人来说，有禁手才是规则。所 以，这里先对&#8220;有禁手&#8221;进行一下简单介绍：
五子棋中&#8220;先手必胜&#8221;已经得到了论证，类似&#8220;花月定式&#8221;和&#8220;浦月定式&#8221;，很多先手必胜下 法虽然需要大量的记忆，但高手确能做到必胜。所以五子棋的规 则进行了优化，得到了 &#8220;有禁手&#8221;五子棋。五子棋中，黑棋必然先行。因此&#8220;有禁手&#8221;五子棋竞技中对黑棋有以下&#8220;禁手&#8221;限制:&#8220;三三禁&#8221;:黑棋下子位置同时形成两个以上的三；&#8220;四 四禁&#8221;:黑棋下子位置同时形成两个以上的四；&#8220;长连禁&#8221;:六子以上的黑棋连成一线。黑棋如下出&#8220;禁手&#8220;则马上输掉棋局。不过如果&#8220;连五&#8221;与&#8220;禁手&#8221;同时出 现这时&#8220;禁手&#8221;是无效的。所以对于黑棋只有冲四活三（后面会有解释）是无解局面。反观白棋则多了一种获胜方式，那就是逼迫黑棋必定要下在禁点。
为了迎合所有玩家，五子棋自然需要做出两个版本，或者是可以进行禁手上的控制。
第二步，实现游戏界面
这里，我制作了一个简单的界面，但是，对于人机对弈来说，绝对够用。和很多网上的精美界面相比，我的界面也许略显粗糙，但，开发速度较高，仅用了不到半天时间。下面我们简单看下界面的做法。
界面我采用了WPF，表现层和逻辑层完全分开，前台基本可以通过拖拽完成布局，这里就不做过多介绍。根据界面截图简单介绍
1 处实际上市两个渐变Label的拼接，2、3是两个label，4、5实际上是两个Button，但是没有做事件响应。通过按钮6、7、8、9 的控制，修改label和Button的Content属性。也许有人会奇怪，为什么Button会丝毫看出不出有Button的影子，这里战友 whrxiao写过一个Style如下&Style&x:Key="ButtonStyle1"&TargetType="{x:Type&Button}"&&Setter&Property="Template"&&Setter.Value&&ControlTemplate&TargetType="{x:Type&Button}"&&Grid&&ContentPresenter&HorizontalAlignment="{TemplateBinding&HorizontalContentAlignment}"&VerticalAlignment="{TemplateBinding&VerticalContentAlignment}"&SnapsToDevicePixels="{TemplateBinding&SnapsToDevicePixels}"&RecognizesAccessKey="True"/&&/Grid&&/ControlTemplate&&/Setter.Value&&/Setter&&/Style&这 里我们把这个Style称为Style1。界面逻辑上，将是否开始、是否禁手和是否电脑先行作为两个全局变量的布尔型值，通过设置和判断bool 型值进行逻辑上的控制。中间的棋盘是个canvas，一个15*15的Grid放满Button并将每个Button应用Style1开始时候透明度设为 0，也就是根本看不到，在下棋的时候改变Button的背景和透明度，实现落子的效果，因为Grid的位置关系，所以可看起来好像是下在横竖的交线处。
第三步，进行输赢判断：
因 为规则不同，&#8220;无禁手&#8221;和&#8220;有禁手&#8221;的输赢判断自然不同。先看无禁手：这个比较简单，遍历每个位置，然后从这个位置开始，分别判断它的四个方向： 即横、竖、左上到右下、左下到右上。每个方向从中间点开始，往两边数连子数，然后将两个方向的连字数加和再加一（中间的棋子）。如果得到大于等于5，那么 就说明下子方赢棋。
对于有禁手的五子棋，输赢判断还需要判断禁手，禁手的判定较为复杂。将待判断点放入黑棋子。然后搜索待判断点 周边棋盘；还原棋盘；利用搜索结果依次 对各方向进行分析，判断黑棋放入后所产生的棋型是否形成长连或形成某种四连或三连的的棋型。若形成长连，判定为禁手，返回长连禁手标识。若形成某种四连或 三连的棋型，该棋型统计数加1，再对下一个方向进行判断，直到各个方向分析结束。若四连棋型或三连棋型的统计数大于１，则返回为禁手。其余情况返回非禁 手。
第四步：构造棋型估分
&#8220;有禁手&#8221;规则比较复杂，涉及到比较多下棋方面的技 巧，而且对算法的思路没有丝毫影响，所以下面我们主要考虑无禁手规则下的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分
有了估分方法，就有了五子棋AI的基础，接下来就是一些博弈的方法了。
第五步：得到位置估分AI
单 纯应用棋谱以及对五子棋当前局势的分析，对每步进行估分，程序中做如下工作：将每个位置进行分析，假设AI落子在该位置，用以上打分规则为AI打 分,并将得到的分数加一。然后，假设玩家落子在该点，为玩家打分，然后将所有的分值汇总。取最高分作为这个位置的估分，接下来就是取分数最高的位置下棋 了。&#8220;位置估分&#8221;，下棋的时候，既可以考虑到自己攻击对手，又能考虑到对对手的防御，可以说，很多时候可以顶上考虑两步的AI。作实验，从网上下载了一个 用博弈做的AI，和&#8220;位置估分&#8221;对下，结果是一胜一负。谁先子，谁赢得胜利。而且一步估分毫无疑问是最快的，即使遍历所有位置，也能很快的做出决策。
第六步：应用博弈树，提高AI智能
做 五子棋的博弈，自然会用到博弈树，这里我说下自己的思路。在对弈中,根据下一步由谁来走,AI对任何一个局面根据前面估分方法给出一个分数,我们 把这个估分方法汇总成一个评估函数，并返回分值。据此来选择下一步的走法。由于人和AI是轮流落子，可以将人的估分也算入，并将前面加负号。那么，估值越 大表明对AI越有利，估分越小则表明对AI越不利。那么每次AI选择都是从它可能的走法树的某层节点，返回评估值中最大点。而用户总是从走法树的某层节点 中选择最小点，从而形成一棵极大极小搜索树，然后根据深度优先搜索，可以最后得到固定搜索深度下的一个最好的走法。我做了下试验，单纯应用博弈树，可以在 100ms之内让AI考虑完整的两步，由于组合爆炸，当需要考虑三步的时候，就需要6s左右，4步就需要1分钟。拿两步来和一步估分作比较，虽然比较慢， 但是确实有了一定智能。
第七步：考虑层数，提高AI智能
上面的设计对于返回值是 统一处理的,但是，层数是个很重要的信息.因为下棋时如果能2步获胜,不应选择4步获胜。对于输的棋型层数就更重要,AI必 须尽可能拖延输的时间，就有更大的可能让AI化险为夷。这样，可以通过设置一个dep值。深度约浅，dep越大，用dep和得到的得分相乘，得到搜索节点 的得分，再进行以上算法，进一步提高AI的智能。
第八步：应用&#945;-&#946;剪枝，提高AI速度
在搜索博弈树的过程中，实际上搜索有很多点是多余的，例如下图
图 中，方形框节点是该AI走,圆形框节点是该人走.比如C节点,它需要从E和F当中选取最大的值。目前已经得出E为2,当搜索F节点时,因为F是人 走的节点，那么F需要从K L M中选取最小的，因为K已经是1，也就是说F&=1，那么L，M就不需要搜索，因此就发生了&#945;剪枝。然后看A节点，该人走了，需要从C和D中选取最 小值，因为C节点是2，而G是7，那么D至少是7。因此，D的其他节点不必再考虑，就发生如上图所示的&#946;剪枝。总结上面规律，我们可以得到剪枝方法如下：
当前为AI下棋节点：
&#945;剪枝：如果当前节点的值不比父节点的前兄弟节点的大值大,则舍弃此节点。
&#946;剪枝：如果当前节点子节点的值不比当前节点的前兄弟节点中的最小值小,则舍弃该子节点和该子节点的所有后兄弟节点。
当前为用户下棋节点：
&#945;剪枝：如果当前节点的某子节点的值不比当前节点的前兄弟节点中的最大值大,则舍弃该子节点和该子节点的所有后兄弟节点。&
&#946;剪枝：如果当前节点的子节点的值不比当前的父节点的前兄弟节点中的最小值小则舍弃此节点。
经过&#945;-&#946;剪枝，可以极大的减少搜索的数量，很多时候，能把几十亿的搜索数量，缩小到几亿，那么，就可以把搜索深度增1。
第九步：应用下棋范围，提高AI速度
当 前节点的子节点的数量和排列顺序对于搜索的速度起着至关重要的影响。根据五子棋的特点,可以产生一个棋面搜索范围。记录当前棋面所有棋子的最左最
右最上最下点构成的矩形,我们认为下一步棋的位置不会脱离这个框3步以上。这样在棋子较少的时候，搜索节点的数量大大减少。可以将AI的速度提高一倍左右。
第十步：利用棋型得分，提高AI速度
因为每种下法都对应一种得分，所以，可以每次只考虑当前得分前十的节点进行下一步搜索，大大减少了搜索范围，可以进一步增加搜索的深度。
第十一步：利用置换表，提高AI速度
我 们一般用递归的方法实现博弈树，但是，递归的效率是低的，而且很明显，有很多重复搜索的节点，所以，我们可以用一个表，记录下所有搜索过节点的情 况，然后只要遇到搜索到的节点，就可以直接得到结果。置于这个&#8220;表&#8221;是什么，就是一个置换表，利用Zobrist算法，进行Hash处理，使在表中查找的 时间大大缩短，这样AI的速度又能提高一个数量级。
第十二步：利用多线程，提高AI速度
我 们其实可以利用多核技术，利用多个线程，让算法实现并行计算，提高AI的速度。我们在第一层用一个线程分配器把第二层的候选节点分配给多个线程, 每个线程包含着从第二层一个候选节点开始的搜索,然后等所有线程结束后,将所有线程的结果进行汇总,选出最大值。并行的程序，可以将速度提高一倍左右。
第十三步：利用随机化算法，让确定方法不能必胜
由 于AI算法的固定性，所以一担玩家一次获胜，按照相同的走法，必然会再次获胜。但除了必杀招或者必防招,一个局面很多时候没有绝对最好的走法。而 是有一些都不错的走法,那么可以把这些评分差不多走法汇集起来,然后随机选择它们中的一种走法,避免AI的走法的固定.这样最简单的方法避免固定方法AI 必输。
第十四步：让AI自学习，不再同一个地方犯错
上面的算法还没有自学习的能 力,这样AI在下棋时还可能会重蹈覆辙。因此在每盘棋结束时,如果AI输，则进行大于搜索深度的步数回退。可以把倒数为 搜索深度数目的局面定为目标局面，从倒数深度加一步局面进行预测,找到不会导出必败目标局面的局面。然后记录下这个局面和前面的局面，并据此修改评分函 数。这样AI就不会犯曾经犯过的错误，达到自学习的效果。
做到以上十四步，一个拥有强大AI的五子棋游戏即可诞生！
随笔 - 122
评论 - 112}