用于"RaceTrack"游戏的AI算法

Question

有没有人知道(或可以建议)为RaceTrack铅笔纸游戏的AI算法？

因为你在每个步骤中有9个可能的选择,并且你需要至少看6-10步才能确定一个好的策略,即使你因为与边界相交而排除了一些选择,暴力也会变得非常昂贵.

目前我正在尝试为每个选择分配一些质量值,以决定排除哪些选择 - 但我还不知道如何分配这样的质量值的良好规则.

Answer 1

我已经制作了一个C++求解器有点太长(187行)以适应这里,所以我把它放在pastebin中:http://pastebin.com/3G4dfTjR.该程序要么计算最佳(最小可能的移动次数)解决方案,要么报告没有可能的解决方案.

用法

将程序作为racetrack startX startY goalX goalY [circleX circleY radius]运行.

该程序采用100x100网格,可选择包含一个圆形障碍物,其中心和半径指定.您还必须另外指定汽车的初始位置和单个目标位置.虽然这些约束是有些约束,看看代码应该使它明显,他们不限制的算法一般-所有相关的逻辑被封装在isMoveValid()和isGoalState()程序,所以如果有人可以打扰实现的更一般的版本这些例程(例如,允许用户指定网格位置的位图,和/或允许多个目标位置),然后可以毫无困难地结合这些例程.

唯一的轻微复杂因素是让目标位置与起始位置相同(或接近,但在"另一侧"),如果您希望您的轨道成为电路,则需要这个位置.在这种情况下,为了避免求解器简单地转动汽车或立即停车,您需要指定一条不可见的"起始线",并isMoveValid()改为禁止在此线上"向后"移动.

这个怎么运作

因为每次移动的成本恰好为1,所以可以使用广度优先搜索 4D状态空间来找到最佳解决方案.每当我们访问一个给定的状态s,其中包含一个4元组(x,y,dx,dy),其中dx和dy是我们用来得到(x,y)的速度向量,我们认为我们所有的9个状态都是可以通过一次移动从s到达.对于尚未看到的任何此类状态t,保证t(即通过s)的这条路径是最佳的,因为BFS总是按照它们与根的最小距离的顺序访问节点.每当我们确定状态的最佳路径时,我们就会记录前趋状态,从而在最后生成完整路径的回溯.

BFS比Dijkstra的算法或A*搜索更简单,因此可能更快,这是更通用的算法,允许移动具有各种成本 - 这里我们不需要灵活性.如果混淆启发式的障碍很少,A*可能会更快,但在每一步都需要查找最小成本节点,这通常使用堆来完成,而对于BFS,最小成本节点始终可用于队列的前面.

例子

秒表跑道30 3 90 10

Starting at (30, 3).
Goal is (90, 10).
Grid size is 100*100 (W*H).
No obstacle.
11-step solution:
(90, 10) (dx=10, dy=4)
(80, 6) (dx=9, dy=3)
(71, 3) (dx=8, dy=2)
(63, 1) (dx=7, dy=1)
(56, 0) (dx=6, dy=0)
(50, 0) (dx=5, dy=0)
(45, 0) (dx=5, dy=0)
(40, 0) (dx=4, dy=0)
(36, 0) (dx=3, dy=-1)
(33, 1) (dx=2, dy=-1)
(31, 2) (dx=1, dy=-1)
(30, 3) (dx=0, dy=0)
128113 states were examined in the process.
stopwatch: Terminated. Elapsed time: 343ms
stopwatch: Process completed with exit code 0.

秒表赛道30 3 90 10 50 20 25

Starting at (30, 3).
Goal is (90, 10).
Grid size is 100*100 (W*H).
A circular obstacle of radius 25 is centred at (50, 20).
22-step solution:
(90, 10) (dx=5, dy=-8)
(85, 18) (dx=5, dy=-7)
(80, 25) (dx=4, dy=-6)
(76, 31) (dx=4, dy=-5)
(72, 36) (dx=5, dy=-4)
(67, 40) (dx=6, dy=-3)
(61, 43) (dx=7, dy=-2)
(54, 45) (dx=8, dy=-1)
(46, 46) (dx=7, dy=0)
(39, 46) (dx=6, dy=1)
(33, 45) (dx=5, dy=2)
(28, 43) (dx=4, dy=3)
(24, 40) (dx=3, dy=4)
(21, 36) (dx=2, dy=5)
(19, 31) (dx=1, dy=6)
(18, 25) (dx=0, dy=6)
(18, 19) (dx=-1, dy=5)
(19, 14) (dx=-2, dy=4)
(21, 10) (dx=-3, dy=3)
(24, 7) (dx=-3, dy=2)
(27, 5) (dx=-2, dy=1)
(29, 4) (dx=-1, dy=1)
(30, 3) (dx=0, dy=0)
949565 states were examined in the process.
stopwatch: Terminated. Elapsed time: 3076ms
stopwatch: Process completed with exit code 0.

请注意,这里的最佳解决方案首先必须"双后退",然后向上和向下再向下,因为圆形障碍物一直延伸到网格的底部.

小错误:如果您将目标位置设置为等于初始位置,则发布的代码将给出一个简短(但非零长度!)的答案.显然这可以作为特殊情况进行检查,但是当我意识到这一点时,我已经把代码放在了pastebin上...... :)

Answer 2

其他人推荐A*,这可能是要走的路,但这种方法存在问题.我首先要说的是,从一个节点到另一个节点的"成本"始终为1,因为您希望最大限度地减少步骤数,因此不会涉及其他成本.

但我想说的重点是位置(x,y)不是A*搜索图中的唯一节点!节点的特征是x和y,但也可以通过汽车来自的节点的x和y坐标(或者如果你愿意,通过速度分量vx和vy).所以你不能只通过二维网格遍历A*算法; 它实际上应该是4维的.也就是说,A*可能还有很长的路要走.

至于启发式,你可以对这一点有所了解,但是我建议使用距离完成减去当前速度的距离,其中为常规2D网格中的每个点预先计算距离(使用Dijkstra算法).这使得A*算法首先朝向终点线搜索并且优选地尽可能快地搜索.我相信这样的算法可以很好地立即计算整个路线.

然而,一个问题是A*总是会产生最佳路线,因此使用这种算法的AI对于玩游戏并不会很有趣,因为它总是会赢(假设起始位置是公平的).

Answer 3

到目前为止,我认为没有人提出过你问题的关键点:你如何提出一个好的"质量价值"？在AI中,您所指的质量值通常称为"启发式".理想情况下,根据当前位置/速度,您的启发式操作会准确地告诉您到达终点所需的最小移动次数.实际上,我们必须满足于更容易计算的东西.

一个重要的指导原则是良好的启发式应该是可以接受的 ; 也就是说,它永远不应该高估达到目标的成本(在你的情况下,达到目标的动作数量).A*算法取决于具有可接受的启发式算法.

提出可接受的启发式的常用技术是放松原始问题.在游戏中,您通常可以通过更改游戏来实现此目的,以便更容易(例如,通过删除规则).例如,在RaceTrack中,您可以理顺赛道以使其更轻松.通过直线轨道,最好的策略显然是不断加速.因此,可接受的启发式算法是计算从当前位置到结束的距离(即,拉直轨道的长度),然后计算在假定恒定加速度的情况下行进该距离所需的移动次数.

您可以通过放宽不同的规则来提出其他启发式方法,但通常需要在启发式的准确性和所需的计算量之间进行权衡.

Answer 4

国际象棋中有一些已知的算法，例如 alpha-beta 剪枝、移动顺序等。如果您在国际象棋上下文中搜索，也许您会有更好的运气。

阿尔法贝塔,策略

编辑：这些路径查找算法仅在没有其他规则和条件的情况下才有效。例如，如果您还具有速度和向心力，那么您就不走运了。如果您没有这些高级条件，那么最好使用其他答案中所述的简单路径查找算法。