博弈大赛赛前培训六棋子程序的实现(整理)

《博弈大赛赛前培训六棋子程序的实现(整理)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

六子棋博弈(bóyì)程序唐志峰计算机博弈与人工智能(rénɡōnɡzhìnénɡ)协会://icga.bitss/计算机博弈(bóyì)与人工智能第一页，共39页。

1://icga.bitss/计算机博弈(bóyì)与人工智能本次(běncì)大赛通信协议博弈程序(chéngxù)整体设计思路博弈程序核心模块机器博弈交互平台本次大赛的一些相关说明讲解要点第二页，共39页。

2://icga.bitss/计算机博弈(bóyì)与人工智能机器(jīqì)博弈交互平台裁判系统棋盘(qípán)黑方程序白方程序1112334556第三页，共39页。

3://icga.bitss/计算机博弈(bóyì)与人工智能本次(běncì)大赛通信协议接受(jiēshòu)裁判系统信息：scanf("%s",Msg);传回裁判系统信息：printf("%s",Move);1.确定队名："name?“传回队名："nameBitStronger

4“2.开局："new"3.确定黑白方：黑方："black"白方："white"4.发送、接收招法//先横向坐标，后纵向坐标黑方第一步：moveX0Y0其他步数：moveX0Y0X1Y1第四页，共39页。

5://icga.bitss/计算机博弈(bóyì)与人工智能博弈程序整体设计(shèjì)思路实际(shíjì)问题数学建模算法编程、调试得到结果第五页，共39页。

6://icga.bitss/计算机博弈(bóyì)与人工智能棋盘(qípán)表示六子棋棋盘由19条横线和19条纵线组成。棋盘一共有19*19=361个交点。交点出现的可能情况：无子、黑子(hēizǐ)、白子棋盘：charposition[19][19];棋子：黑棋〔BLACK〕：0白棋〔WHITE〕：1无子〔NOSTONE〕：0xff第六页，共39页。

7例如(lìrú)代码宏定义：#defineGRID_NUM19//棋盘行数#defineGRID_COUNT361//可放棋子(qízǐ)总数#defineBLACK0//黑棋#defineWHITE1//白棋#defineNOSTONE0xff//无棋全局变量：BYTEposition[GRID_NUM][GRID_NUM];//棋盘STONEMOVEm_cmBestMove;//记录着法注:#include"windows.h"typedefunsignedcharBYTE://icga.bitss/计算机博弈(bóyì)与人工智能第七页，共39页。

8例如(lìrú)代码结构(jiégòu)定义：//棋子位置typedefstruct_stoneposition{BYTEx;BYTEy;}STONEPOS;//走法typedefstruct_stonemove{STONEPOSStonePos[2];//棋子位置intScore;//走法的分数}STONEMOVE;计算机博弈(bóyì)与人工智能://icga.bitss/第八页，共39页。

9例如(lìrú)代码主函数，程序的入口(rùkǒu)voidmain(){intChessmanType;//记录棋子颜色charMsg[500];//保存接收到的消息charname[]=“name中国深度

10";//队伍信息charMove[]="moveAABB

11";//走法intx0,x1,y0,y1;//坐标//初始化棋盘memset(position,NOSTONE,GRID_COUNT);://icga.bitss/计算机博弈(bóyì)与人工智能第九页，共39页。

12例如(lìrú)代码while(1){//循环接收裁判平台发送的消息，注意需要(xūyào)发送的字符串应该//以'

13'结束，裁判平台才会认为是一次完整的输入.//发送完需要(xūyào)调用fflush(stdout)清空输出缓冲区，使字符串//立刻输出到裁判平台memset(Msg,0,500);scanf("%s",Msg);if(strcmp(Msg,"name?")==0){printf("%s",name);fflush(stdout);continue;}://icga.bitss/计算机博弈(bóyì)与人工智能第十页，共39页。

14例如(lìrú)代码if(strcmp(Msg,“new〞)==0)//新开局{memset(position,NOSTONE,GRID_COUNT);//初始化棋盘scanf("%s",Msg);if(strcmp(Msg,“black〞)==0)//确定我方棋子的颜色{Sleep(50);//延迟一段时间发送，经测试，立即发送可//能造成平台(píngtái)无响应printf("moveJJ

15");position[9][9]=BLACK;fflush(stdout);ChessmanType=BLACK;continue;}://icga.bitss/计算机博弈(bóyì)与人工智能第十一页，共39页。

16例如(lìrú)代码else//if(strcmp(Msg,“white〞)==0){ChessmanType=WHITE;continue;}}//确定棋型颜色结束(jiéshù)if(strcmp(Msg,"move")==0){//接收对方的招法scanf("%s",Msg);://icga.bitss/计算机博弈(bóyì)与人工智能第十二页，共39页。

17例如(lìrú)代码if(Msg[2]==‘\0’)//接收(jiēshōu)黑方的第一着{//moveXX

18y0=(int)(Msg[0])-(int)('A');x0=(int)('S')-(int)(Msg[1]);position[x0][y0]=!ChessmanType;}://icga.bitss/计算机博弈(bóyì)与人工智能第十三页，共39页。

19例如(lìrú)代码else//接收对方的招法，一般(yībān)招法都是一着下两个子{//moveXYXY

20y0=(int)(Msg[0])-(int)('A');x0=(int)('S')-(int)(Msg[1]);y1=(int)(Msg[2])-(int)('A');x1=(int)('S')-(int)(Msg[3]);position[x0][y0]=!ChessmanType;position[x1][y1]=!ChessmanType;}://icga.bitss/计算机博弈(bóyì)与人工智能第十四页，共39页。

21例如(lìrú)代码if(SearchAGoodMove(position,ChessmanType)){//获得(huòdé)着法的坐标x0=m_cmBestMove.StonePos[0].x;y0=m_cmBestMove.StonePos[0].y;x1=m_cmBestMove.StonePos[1].x;y1=m_cmBestMove.StonePos[1].y;//将着法记录在棋盘中position[x0][y0]=ChessmanType;position[x1][y1]=ChessmanType;://icga.bitss/计算机博弈(bóyì)与人工智能第十五页，共39页。

22例如(lìrú)代码//将着法转换成要发送的字符(zìfú)形式y0=(char)((int)('A')+y0);x0=(char)((int)('S')-x0);y1=(char)((int)('A')+y1);x1=(char)((int)('S')-x1);//Move[]="moveAABB

23"//修改"AABB"并发送Move[5]=y0;Move[6]=x0;Move[7]=y1;Move[8]=x1;printf("%s",Move);fflush(stdout);://icga.bitss/计算机博弈(bóyì)与人工智能第十六页，共39页。

24://icga.bitss/计算机博弈(bóyì)与人工智能机器(jīqì)博弈交互平台裁判系统棋盘(qípán)黑方程序白方程序1112334556第十七页，共39页。

25计算机博弈(bóyì)的设计思路SearchAGoodMove(position,ChessmanType)如何根据已有的棋盘局面和我方子的颜色，来得到(dédào)我方下一步将要走的招法。://icga.bitss/计算机博弈(bóyì)与人工智能？？第十八页，共39页。

26穷举法穷举出下一步所有可能的招法，形成不同的局面。比较一下这些局面，选取出其中最好的〔对我方最有利〕局面，那么形成此局面对应的招法就是我方下一步“最正确〞的走法。所有可能的招法：招法生成比较：评估函数选取、最好的：搜索函数〔极大极小值搜索〕最正确：此时(cǐshí)对应的招法真的是最好的招法吗？://icga.bitss/计算机博弈(bóyì)与人工智能第十九页，共39页。

27://icga.bitss/计算机博弈(bóyì)与人工智能博弈(bóyì)程序核心模块搜索函数招法生成评估函数AI引擎(yǐnqíng)第二十页，共39页。

28招法生成(shēnɡchénɡ)招法生成：生成一个局面的所有可能招法〔合法招法〕。例如：象棋(xiàngqí)中的，象走田，马走日，兵可进不可退。六子棋的合法招法：任意空格点。思考：是不是所有招法都是我们需要考虑的？可不可以舍弃一些招法？速度与准确性的矛盾。://icga.bitss/计算机博弈(bóyì)与人工智能第二十一页，共39页。

29评估(pínɡɡū)函数评估函数：用以评价一个局面的好坏。计算机如何(rúhé)知道一个局面的好坏？局面的好坏实数思路：根据局面中的各方棋型，来具体分析局面好坏，给出各局面的分值。难点：1.查找棋型，保证速度与准确性。2.如何(rúhé)根据棋型给分值，分值如何(rúhé)确定。://icga.bitss/计算机博弈(bóyì)与人工智能第二十二页，共39页。

30六子棋的棋型长连：在棋盘的纵向、横向或斜向的任意一条线上，形成的7颗或7颗以上同色棋子不间隔地相连(xiānɡlián)。六连：在棋盘的纵向、横向或斜向的任意一条线上，形成的6颗同色棋子不间隔地相连(xiānɡlián)。长连和六连是规定时间内获胜的必要条件。://icga.bitss/计算机博弈(bóyì)与人工智能第二十三页，共39页。

31六子棋的棋型活五：在同一直线上的5颗同色棋子(qízǐ)，符合“对方必须用两手棋才能挡住〞的条件。“挡住〞是指不让另一方形成六连或长连。://icga.bitss/计算机博弈(bóyì)与人工智能第二十四页，共39页。

32六子棋的棋型眠五：在同一直线上的5颗同色棋子(qízǐ)，符合“对方用用一手棋才能挡住〞的条件。://icga.bitss/计算机博弈(bóyì)与人工智能第二十五页，共39页。

33六子棋的棋型活四：在同一直线上的4颗同色棋子(qízǐ)，符合“对方必须用两手棋才能挡住〞的条件。://icga.bitss/计算机博弈(bóyì)与人工智能第二十六页，共39页。

34六子棋的棋型眠四：在同一直线上的4颗同色棋子(qízǐ)，符合“对方用用一手棋才能挡住〞的条件。://icga.bitss/计算机博弈(bóyì)与人工智能第二十七页，共39页。

35六子棋的棋型活三：在同一(tóngyī)直线上的3颗同色棋子，符合“再下一手就能形成活四〞的条件。://icga.bitss/计算机博弈(bóyì)与人工智能第二十八页，共39页。

36六子棋的棋型眠三：在同一直线上的3颗同色棋子，符合“再下两手棋也只能形成(xíngchéng)眠四〞的条件。://icga.bitss/计算机博弈(bóyì)与人工智能第二十九页，共39页。

37六子棋的棋型活二：在同一直线上的2颗同色棋子，符合(fúhé)“再下两手棋就能形成活四〞的条件。://icga.bitss/计算机博弈(bóyì)与人工智能第三十页，共39页。

38六子棋的棋型眠二：在同一直线上的2颗同色棋子，符合“再下两手(liǎnɡshǒu)棋只能形成眠四〞的条件。://icga.bitss/计算机博弈(bóyì)与人工智能第三十一页，共39页。

39搜索(sōusuǒ)函数下一个最好的〔评估分值最高〕局面的对应的招法就是最正确招法吗？棋类高手(gāoshǒu)都能看很多步！当我方生成各种局面后，对方针对我方形成的每一种局面又同样会生成许多局面，我方再针对对方形成的每一种局面同样又会生成许多对应局面，这样循环往复，就形成了一个颗博弈树。://icga.bitss/计算机博弈(bóyì)与人工智能第三十二页，共39页。

40博弈(bóyì)树://icga.bitss/计算机博弈(bóyì)与人工智能博弈树一棵多叉树。六子棋博弈树的复杂度很高。每个局面对应(duìyìng)招法开始：360*359=129240结束〔设50步之后〕：310*309=95790设平均取105个节点。1层：1052层：105*105=10103层：1010*1010=1020……节点数随深度的增加以爆炸式方式增长第三十三页，共39页。

41博弈(bóyì)树提高时间效率一般一步能控制在半分钟内为宜。方法：减小博弈树的规模：1.降低搜索深度，但棋力提高有限。2.每个局面对应只生成(shēnɡchénɡ)少许有价值的节点，可能有漏选。运用高效的搜索算法，例如：α-β剪枝。提高各模块的效率，尤其是评估函数的效率。://icga.bitss/计算机博弈(bóyì)与人工智能第三十四页，共39页。

42极大(jídà)极小值搜索建立了博弈(bóyì)树，我们怎样找到我们需要的招法？搜索与回溯方式：因为：局面分值越高，对我方越有利，对于对方越不利。局面分值越低，对我方越不利，也就是对于对方越有利。所以：轮到我方走时，我方会选择使下一步局面分值最高的走法。此节点〔局面〕分值=MAX{所有子节点分值}轮到对方走时，对方会选择使下一步局面分值最低的走法。此节点〔局面〕分值=MIN{所以子节点分值}://icga.bitss/计算机博弈(bóyì)与人工智能第三十五页，共39页。

43计算机博弈(bóyì)与人工智能极大(jídà)极小值搜索局面（取极大值）局面（取极小值）RootRootMovesLeavesPly=0Ply=1Ply=2Ply=3Depth=3Depth=2Depth=1Depth=0图例：深度(shēndù)层数8151270167102034815207704874848://icga.bitss/第三十六页，共39页。

44思路(sīlù)总结://icga.bitss/计算机博弈(bóyì)与人工智能棋盘(qípán)信息搜索函数招法生成查找棋型评估函数最正确招法第三十七页，共39页。

45计算机博弈(bóyì)大赛1.自己个人(gèrén)能力的提高2.团队合作能力的提高3.初步了解软件工程与软件工程4.计算机博弈领域充满机遇与挑战5.我有可以吗？知识是靠自己学的。能力是从实践中锻炼出来的。://icga.bitss/计算机博弈(bóyì)与人工智能第三十八页，共39页。

46谢谢(xièxie)！！://icga.bitss/计算机博弈与人工智能(rénɡōnɡzhìnénɡ)协会第三十九页，共39页。