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

1、华容道游戏的人工智能搜索解法23华容道游戏的计算机搜索求解1.绪论华容道”有几十种布阵方法，如图 1 给出的 横刀立马” 层层设防” 过 五关”水泄不通” 峰回路转”等等玩法。棋盘上仅有两个小方格空着，玩法 就是通过这两个空格移动棋子，用最少的步数把曹操移出华容道。这个玩具引 起过许多人的兴趣，大家都力图把移动的步数减到最少。图（1）2.计算机搜索的算法2.1 盘面的表示方法在编写程序之前，首先要确定华容道每个盘面在计算机内存中的存储格式。 由上面的介绍看到，华容道的盘面为五行四列，棋子分为五种（把空白处也视 为棋子），所以可将盘面的棋子进行编号后存储在一个 5X4 的二维数组中。在不 同的开

2、局中，可能会有多种“关羽”或者多种“张飞”，编号时只要棋子的形状 相同就采用相同的编号，具体编号方式如图 2。这样，“横刀立马”开局就可存 储成图 3 的方式。31111231超司東苛忠:卒关羽卒1张飞张飞卒1 E卒卒层层设防巧术泄不谨“刃张卒关羽马黄忠赵云耳黄 起忠引卒一酹进蓝 L 町沖中之社越引4图（3）在给定盘面中寻找下一步有哪些走法时，首先要确定当前盘面中空白处的 位置，然后判断与空白位置相邻的棋子能否向空白位置移动。在程序中若要得 到当前盘面的下一个盘面，首先要找到两个 0 的位置，再看这两个 0 的四周的棋 子中有那些可以向o 移动。还以“横刀立马”开局为例，显然两个 0 分别在下

3、标 为41和42的存储单元中，周围共有四个 4 可向 0 移动，即有四种走法。 2.2 搜索方法的选择解决华容道问题就是要在给定开局盘面的情况下，按照棋子的移动规则， 最终将曹操移动至最下方的出口位置，而移动的步数越少越好。将华容道游戏 中每一个盘面视作一个节点，采用广度优先搜索（BFS）的方式，这样第一个找 到的解一定是最佳解。为了避免搜索进入循环以致无法继续搜索下去，在每次展开儿子节点时都 检查此儿子节点之前有无出现过，仅保存之前没有出现过的儿子节点。另外，在搜索到目标节点后，还要能够找出从初始节点通往目标节点的通 路，这是一个回溯的过程。所以，每次由当前节点生成儿子节点时，还要给儿 子节

4、点标记上父亲节点的位置。这样就可以从最终找到的目标节点回溯到初始 节点，从而找到初始节点与目标节点之间的通路。2.3 主要变量数组 history:存储由初始向量展开的解空间；数组 start：存储初始节点；数组 connection 存储解空间中每个节点生成子节点的方式，其中每一行记 录下一步移动的棋子和棋子的坐标以及移动方向等信息；数组 father:存储解空间中每个节点的父亲节点的位置；1112141332141332312122313244324004(2)曹操 二5数组 width：存储解空间每一行的宽度；数 depth：存储解空间的深度3.程序执行结果程序在一台普通的笔记本电脑上执

5、行： Intel Core i3M370 处理器， 主频 2.4GHz，1.86GB 可用内存。使用 MS Visual Studio 2010 的 C 语言环境，源程 序代码约 210行，以下为程序在开头给出的八种开局为例分别得出的运行结果。表1给定不同开局下的程序运行结果开局名称所用步数耗时（s）打开盘面个数横刀立马11616.82909359层拦叠障7727.508058187层层设防13825.299075476水泄不通1144.53305 佃 79过五关460.佃 2011514峰回路转17945.2070111059一路进军8113.684016153井中之蛙8815.258055

6、9804.反思与展望4.1 程序的改进由于时间仓促，程序中有很多需要改进的地方，主要有以下几方面：改进搜索方法。如在节点开展程度较深时（如100 层以上），改用深度优先搜索以节约搜索时间和存储空间。还可以采用A*算法提高搜索效率。改进判断重复的方法。因为华容道棋盘左右对称，如果开局时的棋子布局 也左右对称（如“横刀立马”开局），可将左右对称的节点看作是重复节点不予 展开，从而大为减少搜索在时间和空间上的消耗。优化存储。 可以将每个盘面进一步缩减到更小存储格式中去； 优化解空间 的存储。在本程序中定义的 history200300054浪费了大量的存储空间，可 改用形如historyN54这样的

7、线性的空间存储各节点。4.2 将来需要研究的问题在本程序的基础上，可以进一步研究以下问题：华容道问题一共有多少种 开局，其中有解开局有哪些，每种有解开局的最佳解，最难的开局是什么。6附录：全部程序代码和程序运行结果截图(以“横刀立马”为例)#include #inelude #inelude #include staticint x,y,route20054=0,branch_num2003000,depth,father2003000;staticinthistory200300054=0,c；onnection300300088=0;staticint temp54;staticlong

8、width200=0;int form_connection();voidblock_nearby_single(int m,intn, int dir);voidblock_nearby_bouble( int x1,int x2, int y1,int y2);void write_block_nearby(int a, int b, int x1, int x2, int y1, int y2, int dir, int h);void print_history( int p, int q);void print_connection(int p, int q);void move(

9、int t);int compare_temp_and_history();void write_temp_to_history( int x1, int y1);void print_route(int p);void write_route(int p, int q);void main() int i,j,t,q,p,m=O,l,s;long plot_sum=-1;typedef long clock_t;clock_t startt,fi ni sht;double duration;startt=clock();int start54=31,11,12,31,32,14,13,32

10、,31,21,22,31,32,4, 4,32,4,0,0,4 ;/ 横刀立马/i nt start54=31,11,12,4,32,14,13,4,21,22,4,4,31,21,22,31,32,0,0,32;层拦叠障/i nt start54=31,11,12,31,32,14,13,32,4,21,22,4,4,21,22,4,0,21,22,0;层层设防/i nt start54=4,11,12,31,4,14,13,32,21,22,21,22,21,22,21,22,4,0,0,4;水泄不通/i nt start54=4,11,12,4,4,14,13,4,21,22,21,22

11、,21,22,21,22,0,21,22,0;过五关/i nt start54=4,4,4,31,11,12,31,32,14,13,32,31,0,21,22,32,0,4,21,22;峰回路转/ int start54=31,11,12,4,32,14,13,4,31,31,31,4,32,32,32,4,0,21,22,0;/一路进军/i nt start54=4,21,22,4,31,11,12,31,32,14,13,32,4,21,22,4,0,21,22,0;/井中之蛙/*i nitialize*/for (i=0;i=4;i+)for (j=0;j=3;j+) history0

12、0ij=startij;pri nt_history(O,O);x=0;y=0;while (1)printf( x=%d width=%dn,x,width x);for (y=O;yv=widthx;y+)t=form_c onn ectio n();for (p=0;pt;p+)move(p);if (compare_temp_and_history()=O)write_temp_to_history(x+1,widthx+1); fatherx+1widthx+1=y;widthx+1+=1;7if (historyx+1widthx+1-141=14)printf( x=%d wid

13、th=%dn ,x+1,widthx+1-1);fini sht=clock();for (s=0;s=0;p-)write_route(p,l);l=fatherpl;getchar();for (p=0;p=x+1;p+) printf(第%步:n ,p);print_route(p);return ;x+;depth+;getchar();int form_connection() _int x1=0,y1=0,x2=0,y2=0;/0 的坐标int i,j,p,q,flag=O;bra nch_n umxy=0;/find out the locati on of 0for (i=0;

14、i=4;i+)for (j=0;j=3;j+)if (historyxyij=0) x1=i;y1=j;goto another_zero;ano ther_zero:for (i=0;i=4;i+)for (j=0;j=0)block_nearby_single(x1-1,y1,3);if(x1+1=0)block_nearby_single(x1,y1-1,4);if(y1+1=0)block_nearby_single(x2-1,y2,3);if(x2+1=0)block_nearby_single(x2,y2-1,4);if (y2+1y2) t=y1;y1=y2;y2=t;if (x

15、1+1=0) if (historyxyx1-1y1=21 &historyxyx2-1y2=22) write_block_nearby(21,22,x1-1,x2-1,y1,y2,3,1);if (historyxyx1-1y1=14&historyxyx2-1y2=13) write_block_nearby(14,13,x1-1,x2-1,y1,y2,3,1);_if (y 1=y2) / 纵连if (x1x2) t=x1;x1=x2;x2=t;if (y1+1=0) if (historyxyx1y1-1=12&historyxyx2y2-1=13) writ

16、e_block_nearby(12,13,x1,x2,y1-1,y2-1,4,0);if (historyxyx1y1-1=31 &historyxyx2y2-1=32) write_block_nearby(31,32,x1,x2,y1-1,y2-1,4,0);_void write_block_nearby(int a, int b, int x1, int x2, int y1, int y2, int dir,conn ecti on xybra nch_n umxy0=a;conn ecti on xybra nch_n umxy1=b;conn ecti on xybra

17、nch_n umxy2=x1;conn ecti on xybra nch_n umxy3=x2;conn ecti on xybra nch_n umxy4=y1;conn ecti on xybra nch_n umxy5=y2;conn ecti on xybra nch_n umxy6=dir;conn ecti on xybra nch_n umxy7=h;bra nch_n umxy+; void move( int t)int i,j,blk1,blk2,x1,x2,y1,y2,dir,h;for (i=0;i=4;i+)int h)9for (j=0；j=3；j+) tempi

18、j=history:xyij;blk1=co nn ectio n xyt0;blk2=co nn ectio n:xyt1;x1=co nn ectio nx yt2;x2=co nn ectio nx yt3;y1=co nn ectio n xyt4;y2=co nn ectio nx yt5;dir=c onn ecti on xyt6;h=c onn ecti on xyt7;/ 一次只占一个 0if (blk1=4)if (dir=1|dir=3) tempx1-(2-dir)y1=4;tempx1y1=0;if (dir=2|dir=4) tempx1y1-(3-dir)=4;t

19、empx1y1=0;if (blk1=31 &dir=1)tempx1-1y1=31;tempx1y1=32;tempx1+1y1=0;if (blk1=31 &dir=3)tempx2+1y2=32;tempx2y2=31;tempx1y1=0;if (blk1=21 &dir=2)tempx1y1-1=21;tempx1y1=22;tempx1y1+1=0;if (blk1=21 &dir=4)tempx2y2+1=22;tempx2y2=21;tempx1y1=0;/ 一次占用两个 0if (blk1=21 &blk2=22&(dir=1|

20、dir=3)tempx1-(2-dir)y1=21;tempx2-(2-dir)y2=22;tempx1y1=0;tempx2y2=0;if (blk1=31 &blk2=32&(dir=2|dir=4)tempx1y1-(3-dir)=31;tempx2y2-(3-dir)=32;tempx1y1=0;tempx2y2=0;if (blk1=11 &blk2=12&dir=1)tempx1-1y1=11;tempx2-1y2=12;tempx1y1=14;tempx2y2=13;tempx1+1y1=0;tempx2+1y2=0;if (blk1=14&

21、;blk2=13&dir=3)tempx1+1y1=14;tempx2+1y2=13;tempx1y1=11;tempx2y2=12;tempx1-1y1=0;tempx2-1y2=0;if (blk1=11 &blk2=14&dir=2)tempx1y1-1=11;tempx2y2-1=14;tempx1y1=12;tempx2y2=13;tempx1y1+1=0;tempx2y2+1=0;if (blk1=12&blk2=13&dir=4)tempx1y1+1=12;tempx2y2+1=13;tempx1y1=11;tempx2y2=14;temp

22、x1y1-1=0;tempx2y2-1=0;void print_history( int p, int q)int i,j;for (i=0;i=4;i+)for (j=0;j=3;j+) printf( %2d , historypqij);printf(n );printf(n);void print_connection(int p, int q)int i,j;prin tf( value x1 x2 y1 y1 dir hn);for (i=0;i8;i+)for (j=0;j8;j+) printf(%2d , connectionpqij);printf(n );printf(n);int compare_temp_and_history() -int i,j,n,m,flag=0;for (m=0;m=x+1;m+)for