今天在做五子棋AI算法时，遇到了一个遍历棋盘的问题。如果按照从头开始遍历各坐标点的算法来循环，固然浪费了很多内存而又效率低下，因为很多点（比如(0， 0)）一般人是不会去落子的。如果从棋盘中间向四周这样遍历，或许几步就找到符合进攻条件的点并退出循环体了。在这种前提下，我想到了用一种半径法循环来提高遍历效率。
算法使用JavaScript语言描述，以19×19路的棋盘为例，以点(9， 9)为中心点，由中心点向外逐层进行循环，共循环360次。在加上中心点(9， 9)，共361个点，恰好等于19×19。下面来具体介绍一下。
这里可能有朋友会有疑惑：这套算法是用来进攻的还是防守的？是用来进攻的，对于如何落子防守，在我的五子棋展望算法里有更高效的循环办法（至少比循环棋盘上的空白点要高效）。但如果是要进攻的话，恐怕只能像这样寻找一个满足进攻条件的空白点来落子了，这就是这个算法的背景。
在制作算法之前，先应该观察一下棋盘的横纵点分布。因为横纵皆为19路，那么不难发现，棋盘是一个以中心点为对称中心的中心对称图形，中心点左右各有9路。我们假定“半径”是由中心点向外各层的伸长量，那么半径的取值应该是从1-9，其规律如下：
n： 1 2 3 4 5 6 7 8 9
x： 8 16 24 32 40 48 56 64 72
不知各位有没有理解。当半径为1时，形成的正方形各点是：(8， 9)，(8， 8)，(9， 8)，(10， 8)，(10， 9)，(10， 10)，(9， 10)，(8， 10)，共8个点，然后半径递增逐层向外循环。因为这样循环符合玩家落子的规律，那就是由“天元”开始，向外扩张。不难发现，上面数列符合这样一个通式：x = n × 8，这样，每一层循环的个数就确定了下来。
要根据每层循环的个数，来找到每次循环的点，这个问题是本算法的难点。首先要有一个基本思路，就是让一个变量进行“走环”，走一圈下来所有的点也就都遍历到了。先给变量赋一个初值，这个值是一个坐标点。比如当n=1时，这个初始点是(8， 9)，当n=2时，点是(7， 9)。然后每一次循环，要给这个变量一个行驶的路线。一个完整的走环过程应该是：向上、向右、向下、向左、再向上回到起点。再有就是要确定路线的步长：比如当n=1时，向上1步，向右2步，向下2步，向左2步，再向上0步，共7步，加上初始点(8， 9)，一共8步；当n=2时，向上2步，向右4步，向下4步，向左4步，再向上1步，共15步，加上初始点(7， 9)，一共16步。有了这些规律，最后只需要一个计数器变量就可以了。它的作用是，每走一步递增一次，如果达到了本次路线的步数（就是说下一步该转向时），则把路线数组和步长数组的第一个元素删除，这样下一次循环就进入到了下一条路线。
算法虽然只有二十几行，但是控制路线的思想还是体现的比较灵活。分享给大家：
点击下载
里面注释掉的那一行就是每一次循环的坐标点，各位可以在这一行对坐标点进行各种操作，完成自己的五子棋AI算法。
算法使用JavaScript语言描述，以19×19路的棋盘为例，以点(9， 9)为中心点，由中心点向外逐层进行循环，共循环360次。在加上中心点(9， 9)，共361个点，恰好等于19×19。下面来具体介绍一下。
这里可能有朋友会有疑惑：这套算法是用来进攻的还是防守的？是用来进攻的，对于如何落子防守，在我的五子棋展望算法里有更高效的循环办法（至少比循环棋盘上的空白点要高效）。但如果是要进攻的话，恐怕只能像这样寻找一个满足进攻条件的空白点来落子了，这就是这个算法的背景。
在制作算法之前，先应该观察一下棋盘的横纵点分布。因为横纵皆为19路，那么不难发现，棋盘是一个以中心点为对称中心的中心对称图形，中心点左右各有9路。我们假定“半径”是由中心点向外各层的伸长量，那么半径的取值应该是从1-9，其规律如下：
n： 1 2 3 4 5 6 7 8 9
x： 8 16 24 32 40 48 56 64 72
不知各位有没有理解。当半径为1时，形成的正方形各点是：(8， 9)，(8， 8)，(9， 8)，(10， 8)，(10， 9)，(10， 10)，(9， 10)，(8， 10)，共8个点，然后半径递增逐层向外循环。因为这样循环符合玩家落子的规律，那就是由“天元”开始，向外扩张。不难发现，上面数列符合这样一个通式：x = n × 8，这样，每一层循环的个数就确定了下来。
要根据每层循环的个数，来找到每次循环的点，这个问题是本算法的难点。首先要有一个基本思路，就是让一个变量进行“走环”，走一圈下来所有的点也就都遍历到了。先给变量赋一个初值，这个值是一个坐标点。比如当n=1时，这个初始点是(8， 9)，当n=2时，点是(7， 9)。然后每一次循环，要给这个变量一个行驶的路线。一个完整的走环过程应该是：向上、向右、向下、向左、再向上回到起点。再有就是要确定路线的步长：比如当n=1时，向上1步，向右2步，向下2步，向左2步，再向上0步，共7步，加上初始点(8， 9)，一共8步；当n=2时，向上2步，向右4步，向下4步，向左4步，再向上1步，共15步，加上初始点(7， 9)，一共16步。有了这些规律，最后只需要一个计数器变量就可以了。它的作用是，每走一步递增一次，如果达到了本次路线的步数（就是说下一步该转向时），则把路线数组和步长数组的第一个元素删除，这样下一次循环就进入到了下一条路线。
算法虽然只有二十几行，但是控制路线的思想还是体现的比较灵活。分享给大家：
点击下载
里面注释掉的那一行就是每一次循环的坐标点，各位可以在这一行对坐标点进行各种操作，完成自己的五子棋AI算法。
本文链接： http://wushen.biz/original/programs/index.jsp?id=1280563704000¤t=1 （复制）
阅读次数 ( 4806 )
下载次数 ( 38 )
1 #：
游客
2011-07-10 14:25:03
遍历棋盘?有这个必要么？效率有点低。
遍历棋盘?有这个必要么？效率有点低。
·回复：不遍历棋盘如何比较落子点？
2 #：
老吉
2010-08-03 17:28:09
我是太笨了，看不明白。我的思想是： 下一个棋子后 的坐标， 横向循环判断，竖向 循环判断，斜向判断，比如： 这个棋盘 下了点（9，9） 那么就从点（5，9） 横坐标循环到（13，9）这样 横向的坐标就判断好了；然后再竖向点（9，5） 到（9，13） 点竖向循环判断；再从斜向（5，5） 到点（13，13） 斜向循环判断； 再从点（5，13） 到点（13，5） 这样循环判断。结果4次每次至多9次循环判断后，找个计数n 来做判断就可以了。 这样把他们封装起来，做成一个类，PanDuan(char[][] qipan ，int x，int y) 。传递一个数组和 刚骡子的 坐标即可。我基本就是这样的思路，还请老毕同学给予评价 ，共同进步.
我是太笨了，看不明白。我的思想是： 下一个棋子后 的坐标， 横向循环判断，竖向 循环判断，斜向判断，比如： 这个棋盘 下了点（9，9） 那么就从点（5，9） 横坐标循环到（13，9）这样 横向的坐标就判断好了；然后再竖向点（9，5） 到（9，13） 点竖向循环判断；再从斜向（5，5） 到点（13，13） 斜向循环判断； 再从点（5，13） 到点（13，5） 这样循环判断。结果4次每次至多9次循环判断后，找个计数n 来做判断就可以了。 这样把他们封装起来，做成一个类，PanDuan(char[][] qipan ，int x，int y) 。传递一个数组和 刚骡子的 坐标即可。我基本就是这样的思路，还请老毕同学给予评价 ，共同进步.
·回复：嗯，我实际的类中，在此基础上又判断了每个方向敌方堵子的情况。
作者 & 技术支持： 毕飞 主题设计： mono-lab
版权所有 ICP备案号： 苏ICP备09065350号 在线 32 人
Author & Powered By： Bi Fei Theme Designed： mono-lab
Copyright © http://www.wushen.biz
Author & Powered By： Bi Fei Theme Designed： mono-lab
Copyright © http://www.wushen.biz