问"RaceTrack“博弈的AI算法

EN

我已经做了一个太长(187行)的C++求解器，不适合这里，所以我把它放在粘贴箱中：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)的速度矢量，我们考虑通过一次移动就可以从s到达的所有9个状态。对于还没有看到的任何这样的状态t，这个到t的路径(即，通过s)被保证是最优的，因为BFS总是按照它们到根的最小距离的顺序访问节点。每当我们确定状态的最佳路径时，我们都会记录前置状态，从而能够在最后生成完整路径的回溯。

BFS比Dijkstra的算法或A* search更简单，因此可能更快，后者是更通用的算法，允许移动具有各种成本--我们这里不需要的灵活性。如果没有什么障碍来混淆它的启发式，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.

请注意，这里的最优解首先必须“加倍”，向上绕过，然后再向下移动，因为圆形障碍物一直延伸到网格的底部。

小错误:发布的代码将给出一个短的(但不是零长度的！)如果将目标位置设置为初始位置，请回答此问题。显然，这可以作为特殊情况进行检查，但当我意识到这一点时，我已经将代码放在了粘贴板上……:)

其他人推荐A*，这可能是可行的方法，但这种方法存在问题。首先让我说，从一个节点到另一个节点的“成本”始终是1，因为您希望最小化步骤数，所以根本不涉及其他成本。

但我想指出的重要一点是，位置(x，y)在A*的搜索图中不是唯一的节点！节点的特征是x和y，但也包括汽车所在节点的x和y坐标(或者速度分量vx和vy，如果你愿意的话)。因此，您不能只在2维网格上遍历A*算法；它实际上应该是4维的。也就是说，A*可能仍然是未来的发展方向。

至于启发式，你可以很有创意，但我建议使用距离来完成减去当前速度，其中距离是为常规2D网格中的每个点预先计算的(为此使用Dijkstra算法)。这使得A*算法首先向终结线搜索，并且最好尽可能快。我相信这样的算法可以很好地立即计算出整个路线。

然而，一个问题是，A*总是会产生最优路径，所以使用这样的算法的人工智能将不会有乐趣，因为它总是会赢(假设起始位置是公平的)。

到目前为止，我认为还没有人回答你问题的一个关键点:你是如何提出一个好的“质量价值”的？在人工智能中，你引用的质量值通常被称为“启发式”。理想情况下，在给定当前位置/速度的情况下，您的启发式方法将准确地告诉您达到终点所需的最小移动次数。在现实中，我们必须满足于更容易计算的东西。

一个重要的指导原则是，一个好的启发式应该是admissable；也就是说，它永远不应该高估达到目标的成本(在您的情况下，是到达终点的移动次数)。A*算法依赖于具有可接受的启发式算法。

提出可接受的启发式方法的一种常见技术是放松原始问题。在游戏中，你通常可以通过改变游戏来做到这一点，使游戏变得更容易(例如，通过丢弃规则)。例如，在RaceTrack中，你可以拉直赛道，让游戏变得更容易。有了直道，最好的策略显然就是不断加速。因此，一个可接受的启发式方法是计算从当前位置到终点的距离(即拉直的赛道长度)，然后在假设恒定加速度的情况下计算移动该距离所需的移动次数。

您可以通过放宽不同的规则来提出其他启发式算法，但启发式算法的准确性和所需的计算量之间往往存在权衡。