华容道游戏的人工智能搜索解法

1华容道游戏的计算机搜索求解1.绪论“华容道”有几十种布阵方法，如图1给出的“横刀立马”、“层层设防”、“过五关”、“水泄不通”、“峰回路转”等等玩法。棋盘上仅有两个小方格空着，玩法就是通过这两个空格移动棋子，用最少的步数把曹操移出华容道。这个玩具引起过许多人的兴趣，大家都力图把移动的步数减到最少。图（1）2.计算机搜索的算法2.1盘面的表示方法在编写程序之前，首先要确定华容道每个盘面在计算机内存中的存储格式。由上面的介绍看到，华容道的盘面为五行四列，棋子分为五种（把空白处也视为棋子），所以可将盘面的棋子进行编号后存储在一个5×4的二维数组中。在不同的开局中，可能会有多种“关羽”或者多种“张飞”，编号时只要棋子的形状相同就采用相同的编号，具体编号方式如图2。这样，“横刀立马”开局就可存储成图3的方式。31111231321413322图（2）图（3）在给定盘面中寻找下一步有哪些走法时，首先要确定当前盘面中空白处的位置，然后判断与空白位置相邻的棋子能否向空白位置移动。在程序中若要得到当前盘面的下一个盘面，首先要找到两个0的位置，再看这两个0的四周的棋子中有那些可以向0移动。还以“横刀立马”开局为例，显然两个0分别在下标为[4][1]和[4][2]的存储单元中，周围共有四个4可向0移动，即有四种走法。2.2搜索方法的选择解决华容道问题就是要在给定开局盘面的情况下，按照棋子的移动规则，最终将曹操移动至最下方的出口位置，而移动的步数越少越好。将华容道游戏中每一个盘面视作一个节点，采用广度优先搜索（BFS）的方式，这样第一个找到的解一定是最佳解。为了避免搜索进入循环以致无法继续搜索下去，在每次展开儿子节点时都检查此儿子节点之前有无出现过，仅保存之前没有出现过的儿子节点。另外，在搜索到目标节点后，还要能够找出从初始节点通往目标节点的通路，这是一个回溯的过程。所以，每次由当前节点生成儿子节点时，还要给儿子节点标记上父亲节点的位置。这样就可以从最终找到的目标节点回溯到初始节点，从而找到初始节点与目标节点之间的通路。2.3主要变量数组history：存储由初始向量展开的解空间；数组start：存储初始节点；数组connection：存储解空间中每个节点生成子节点的方式，其中每一行记录下一步移动的棋子和棋子的坐标以及移动方向等信息；数组father：存储解空间中每个节点的父亲节点的位置；数组width：存储解空间每一行的宽度；3121223132443240043数depth：存储解空间的深度3.程序执行结果程序在一台普通的笔记本电脑上执行：IntelCorei3M370处理器，主频2.4GHz，1.86GB可用内存。使用MSVisualStudio2010的C语言环境，源程序代码约210行，以下为程序在开头给出的八种开局为例分别得出的运行结果。表1给定不同开局下的程序运行结果开局名称所用步数耗时（s）打开盘面个数横刀立马11616.82909359层拦叠障7727.508058187层层设防13825.299075476水泄不通1144.533051979过五关460.192011514峰回路转17945.2070111059一路进军8113.684016153井中之蛙8815.2580559804.反思与展望4.1程序的改进由于时间仓促，程序中有很多需要改进的地方，主要有以下几方面：改进搜索方法。如在节点开展程度较深时（如100层以上），改用深度优先搜索以节约搜索时间和存储空间。还可以采用A*算法提高搜索效率。改进判断重复的方法。因为华容道棋盘左右对称，如果开局时的棋子布局也左右对称（如“横刀立马”开局），可将左右对称的节点看作是重复节点不予展开，从而大为减少搜索在时间和空间上的消耗。优化存储。可以将每个盘面进一步缩减到更小存储格式中去；优化解空间的存储。在本程序中定义的history[200][3000][5][4]浪费了大量的存储空间，可改用形如history[N][5][4]这样的线性的空间存储各节点。4.2将来需要研究的问题在本程序的基础上，可以进一步研究以下问题：华容道问题一共有多少种开局，其中有解开局有哪些，每种有解开局的最佳解，最难的开局是什么。4附录：全部程序代码和程序运行结果截图（以“横刀立马”为例）#includestdio.h#includemath.h#includetime.h#includestdlib.hstaticintx,y,route[200][5][4]={0},branch_num[200][3000],depth,father[200][3000];staticinthistory[200][3000][5][4]={0},connection[300][3000][8][8]={0};staticinttemp[5][4];staticlongwidth[200]={0};intform_connection();voidblock_nearby_single(intm,intn,intdir);voidblock_nearby_bouble(intx1,intx2,inty1,inty2);voidwrite_block_nearby(inta,intb,intx1,intx2,inty1,inty2,intdir,inth);voidprint_history(intp,intq);voidprint_connection(intp,intq);voidmove(intt);intcompare_temp_and_history();voidwrite_temp_to_history(intx1,inty1);voidprint_route(intp);voidwrite_route(intp,intq);voidmain(){inti,j,t,q,p,m=0,l,s;longplot_sum=-1;typedeflongclock_t;clock_tstartt,finisht;doubleduration;startt=clock();intstart[5][4]={31,11,12,31,32,14,13,32,31,21,22,31,32,4,4,32,4,0,0,4};//横刀立马//intstart[5][4]={31,11,12,4,32,14,13,4,21,22,4,4,31,21,22,31,32,0,0,32};//层拦叠障//intstart[5][4]={31,11,12,31,32,14,13,32,4,21,22,4,4,21,22,4,0,21,22,0};//层层设防//intstart[5][4]={4,11,12,31,4,14,13,32,21,22,21,22,21,22,21,22,4,0,0,4};//水泄不通//intstart[5][4]={4,11,12,4,4,14,13,4,21,22,21,22,21,22,21,22,0,21,22,0};//过五关//intstart[5][4]={4,4,4,31,11,12,31,32,14,13,32,31,0,21,22,32,0,4,21,22};//峰回路转//intstart[5][4]={31,11,12,4,32,14,13,4,31,31,31,4,32,32,32,4,0,21,22,0};//一路进军//intstart[5][4]={4,21,22,4,31,11,12,31,32,14,13,32,4,21,22,4,0,21,22,0};//井中之蛙/*initialize*/for(i=0;i=4;i++)for(j=0;j=3;j++)history[0][0][i][j]=start[i][j];print_history(0,0);x=0;y=0;while(1){printf(x=%dwidth=%d\n,x,width[x]);for(y=0;y=width[x];y++){t=form_connection();for(p=0;pt;p++){move(p);if(compare_temp_and_history()==0){write_temp_to_history(x+1,width[x+1]);father[x+1][width[x+1]]=y;width[x+1]+=1;}if(history[x+1][width[x+1]-1][4][1]==14){5printf(x=%dwidth=%d\n,x+1,width[x+1]-1);finisht=clock();for(s=0;s=x+1;s++)plot_sum+=(width[x]+1);printf(win,耗时：%7f秒展开盘面总数y=%d\n,duration=(double)(finisht-startt)/CLOCKS_PER_SEC,plot_sum);getchar();for(p=x+1,l=width[x+1]-1;p=0;p--){write_route(p,l);l=father[p][l];}getchar();for(p=0;p=x+1;p++){printf(第%d步：\n,p);print_route(p);}return;}}}x++;depth++;}getchar();}intform_connection(){intx1=0,y1=0,x2=0,y2=0;//0的坐标inti,j,p,q,flag=0;branch_num[x][y]=0;//findoutthelocationof0for(i=0;i=4;i++)for(j=0;j=3;j++){if(history[x][y][i][j]==0){x1=i;y1=j;gotoanother_zero;}}another_zero:for(i=0;i=4;i++)for(j=0;j=3;j++){if(history[x][y][i][j]==0&&(i!=x1||j!=y1)){x2=i;y2=j;}}//findblocksnextto0,directiontomove:up=1,down=3,left=2,right=4if(x1-1=0)block_nearby_single(x1-1,y1,3);if(x1+1=4)block_nearby_single(x1+1,y1,1);if(y1-1=0)block_nearby_single(x1,y1-1,4);if(y1+1=3)block_nearby_single(x1,y1+1,2);if(x2-1=0)block_nearby_single(x2-1,y2,3);if(x2+1=4)block_nearby_single(x2+1,y2,1);if(y2-1=0)block_nearby_single(x2,y2-1,4);if(y2+1=3)block_nearby_single(x2,y2+1,2);//thetwozerosnearbyif(abs(x1-x2)+abs(y1-y2)==1)block_nearby_bouble(x1,x2,y1,y2);return(branch_num[x][y]);}voidblock_nearby_single(intm,intn,intdir)6{if(history[x][y][m][n]==4)write_block_nearby(4,4,m,m,n,n,dir,0);if(history[x][y][m][n]==31&&dir==1)write_block_nearby(31,32,m,m+1,n,n,dir,0);if(history[x][y][m][n]==32&&dir==3)write_block_nearby(31,32,m-1,m,n,n,dir,0);if(history[x][y][m][n]