Catcha Mouse如何实现老鼠逃跑算法的优化？

Question

在一个可以由多个六边形组成的地图中，有一只老鼠，可以向六个方向（上、下，左上，左下，右上，右下）移动，同时，某个或者多个六边形被定义为地洞。游戏开始，人可以在地图上任何一个六边形中放置捕鼠夹；然后，老鼠会以最短路径方式向最近地洞逃逸，每次移动一格；老鼠移动之后，人可以放置下一个捕鼠夹，由此人机次第进行游戏。老鼠每一次移动时，会重新计算最短路径（因为捕鼠夹相当于障碍，会使最短路径改变）。直至：
1 老鼠没有任何机会进入地洞，则人获胜；
2 老鼠最终进入地洞，则电脑获胜。基础AI是老鼠每次找最近的洞...用广搜做完了...要提高AI的话，都能有些什么策略呢？谢谢

Answer 1

最短路径问题——Dijkstra算法？

Answer 2

我觉得不能使用最短路径的方式，应该找到一条路径，它上面有一个点，老鼠可以有多个选择入洞，比如老鼠现在在A点，   老鼠在A点可以选择往B点（洞口），C（洞口）逃跑，由于玩家一次只能放置一个鼠夹，所以老鼠才有机会入洞。所以老鼠能够到达A点的话它就可以获胜了，这类算法我觉得使用回溯能解决，

Answer 3

可以尝试一下全局搜索最优。
当前位置可以有m个节点可以走(0 < m <= 6),对于某个可行节点N，求取其到各个洞口i的最短路径Li：
建立一个费用函数Fi = exp(1 - Li).那么节点N的费用为：F(N) = sum(Fi);选取费用最大的节点作为下一步。

Answer 4

最短路径Li指的是可行节点N距洞口i之间的节点数吗？

Answer 5

由于楼主是做手机开发，AI往往是通过一次搜索来完成。
我不大清楚楼主手机的计算能力，如果能采用multi-level search，可能效果会更好。
就像下棋一样，算一个"胜率"，像这种大小的矩阵，可以提前算出3步的话，基本就可以稳赢了。

Answer 6

纠正一下，应该不是说稳赢。应该是知道是否能“赢”，因为mouse的初始位置、hole的初始位置是有一定随机性的，这直接影响最终的结果。有点类似残局一样，基本上下不赢，能下赢的话可能也是自古华山一条道。