关于一个人机博弈游戏的算法

最近工作比较闲空，我就自己写一些东西做研究，我写了一个棋类游戏，目前碰到了困难，想向各位请教一下。

游戏的演示地址：http://u.115.com/file/aq7zi7ig


  这个游戏是这样的：
  1 有一个9x9=81格子的棋盘。

  2 玩家1的棋子位于棋盘从上往下数第一行的正中间，玩家2的棋子位于棋盘最底一行（即第九行）的正中间。

  3 游戏规则：先走到对方的底线的玩家获得胜利（比方说，玩家1的目标就是向下走到第9行，而玩家2的目标就是向上走到第1行）

  只要走到目标行即可，不管它处于目标行的哪一个单元格内。

  4 每个玩家都拥有10块挡板。挡板分为2种，一种为横挡板，一种为竖挡板，每个挡板的长度（或宽度）都是两个单元格。

  5 在使用挡板时，不能将对方或自己前往终点的路线堵死。

  6 每一步只能选择行棋或者放置挡板中的一种，如果走了棋子就不能放置挡板，放置了挡板就不能行棋。每回合棋子移动一格，每回合最多放置一个挡板。

  7 允许两方的棋子在单元格上重叠，互不干扰。

  规则大体如上 
   
  附件里附上我用VB 6.0写的一个简单人机对战（即Quoridor.rar)，用方向键控制棋子移动（控制下方棋子），用鼠标移动、点击来放置挡板。

以上是游戏介绍，下面是我的问题。  
这个游戏的算法涉及到两个方面：

  1 如何以最快的速度计算出棋子前往目标行的最短路径。与A*算法有所区别的是，该游戏并没有规定一个具体的单元格作为目标点，而是目标行的每一个单元格都有可能成为目标点，我分别用A*算法以及遍历的方法，发现二者速度差别不大（因为A*我必须把目标行上的单元格最短路径全部计算出来，然后再求一个最短值，这本身和遍历已经没有太多区别，甚至会更慢）

  2 人机博弈的计算量是相当大的。以该棋子为例，每一步的选择都有很多种（一共有144块挡板的安放方法，还要加上棋子的四个方向）,如果电脑需要至少思考3步，则经历的过程是 电脑--人--电脑--人--电脑一共五层递归，每一层都有100来种的可能性，其复杂度就是n的5次方。即使用了剪枝，速度也非常缓慢。
   
  我想了好久，都没有非常有效的加快速度的办法，目前只能通过一个函数来判断哪些挡板有可能会对局势起到作用，以削减每层递归时的计算量，但是减的狠了，电脑就显得很傻，减的少了，速度慢到难以忍受。

  在这个计算里，我测试寻找最短路径最多需要0.4ms，如果一个人对电脑行棋的时间忍受为20秒，这意味着电脑最多只能进行50000次循环，但是50000次循环无疑太少了，电脑根本还想不出太多有意义的步子来。


  请教各位算法达人，对于这样的游戏，如何进行有效的算法分析？

自己顶起来

支持原创