有谁知道（或可以建议）用于RaceTrack铅笔纸游戏的 AI 的好算法？
由于您在每个步骤中有 9 种可能的选择，并且您需要至少提前 6-10 步才能决定一个好的策略，因此即使您可以排除一些选择，因为与边界相交，暴力破解也变得非常昂贵。
目前我正在尝试为每个选择分配一些质量值，以便决定排除哪些选择 - 但我还不知道如何分配这样一个质量值的良好规则。
问问题
6914 次
8 回答
14
我制作了一个 C++ 求解器，它有点太长（187 行），无法舒适地放在这里，所以我把它放在了 pastebin 中：http://pastebin.com/3G4dfTjR。该程序要么计算一个最优（最小可能的移动次数）解决方案，要么报告一个不可能的解决方案。
用法
以racetrack startX startY goalX goalY [circleX circleY radius]运行程序。
该程序假定一个 100x100 的网格，可以选择包含一个圆形障碍物，其中心和半径由您指定。您必须另外指定汽车的初始位置和单个目标位置。尽管这些约束有些限制，但看一下代码应该可以明显看出它们并没有限制一般的算法——所有相关的逻辑都封装在isMoveValid()andisGoalState()例程中，所以如果有人可以实现更通用的版本这些例程（例如，允许用户指定网格位置的位图，和/或允许多个目标位置）然后可以毫无困难地合并。
唯一的小麻烦是让目标位置与起始位置相同（或接近，但“在另一侧”），如果您希望您的赛道成为赛道，这就是您所需要的。在这种情况下，为了避免求解器只是让汽车掉头或立即停止，您需要指定一条不可见的“起始线”，并更改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 上...... :)
于 2011-07-06T14:43:55.230 回答
5
其他人推荐 A*，这可能是要走的路，但这种方法存在问题。首先让我说，从一个节点到另一个节点的“成本”始终为 1，因为您想最小化步骤数，根本不涉及其他成本。
但我想说的重要一点是，位置 (x,y) 不是 A* 搜索图中的唯一节点！节点的特征是 x 和 y，但也有汽车来自的节点的 x 和 y 坐标（或者速度分量 vx 和 vy，如果你愿意的话）。所以你不能只在二维网格上遍历 A* 算法；它实际上应该是 4 维的。也就是说，A *可能仍然是要走的路。
至于启发式方法，您可以对此非常有创意，但我建议使用诸如完成距离减去当前速度之类的方法，其中为常规 2D 网格中的每个点预先计算距离（为此使用 Dijkstra 算法）。这使得 A* 算法首先向终点线搜索，并且最好尽可能快。我相信这样的算法可以很好地立即计算出整个路线。
但一个问题是，A* 总是会产生最佳路线，因此使用这种算法的 AI 对抗起来不会很有趣，因为它总是会赢（假设起始位置是公平的）。
于 2011-07-05T23:42:01.403 回答
5
到目前为止，我认为没有人解决您问题的关键点：您如何提出一个好的“质量价值”？在 AI 中，您所指的质量值通常称为“启发式”。理想情况下，在给定当前位置/速度的情况下，您的启发式算法会准确地告诉您到达终点所需的最少移动次数。实际上，我们必须满足于更容易计算的东西。
一个重要的指导原则是一个好的启发式应该是可以接受的；也就是说，它永远不应该高估达到目标的成本（在你的情况下，达到终点的移动次数）。A* 算法依赖于具有可接受的启发式。
提出可接受的启发式的常用技术是放松原始问题。在游戏中，您通常可以通过改变游戏来做到这一点，使其变得更容易（例如通过删除规则）。例如，在 RaceTrack 中，您可以理顺赛道以使其成为更轻松的游戏。在直线轨道上，最好的策略显然是不断加速。因此，一个可接受的启发式方法是计算从当前位置到终点的距离（即拉直轨道的长度），然后在假设加速度恒定的情况下计算行进该距离所需的移动次数。
您可以通过放宽不同的规则来提出其他启发式方法，但通常需要在启发式方法的准确性和所需的计算量之间进行权衡。
于 2011-07-06T00:10:23.150 回答
4
本文档可能对您有所帮助
于 2011-07-06T03:06:52.093 回答
1
您提到“为每个选择分配一些质量值”的想法 - 这称为启发式函数。许多 AI 算法（例如其他人提到的 A* 和 alpha-beta 剪枝）仅与您插入其中的启发式函数一样好。
但是，如果您确实设法创建了一个好的启发式函数，那么这些算法将自动“免费”执行得更好 - 所以花一些时间来开发一个好的算法是非常值得的。
另一个角度是尝试从一开始就预先计算你的整个比赛。然后是最小化越过终点线的转弯次数的问题。一种方便的求最小值算法是模拟退火。
除此之外，看到像这样的游戏的一些遗传算法解决方案也很酷。不确定它是否非常合适，但我可以想象创建一个接受各种输入的“大脑”——未来几圈与墙壁的预期距离、速度、与其他赛车手的距离等——并发展其逻辑大脑与遗传算法。诀窍是将问题分解成可以有意义地变异的部分。
实际上，您甚至可以将它们结合起来，并使用遗传算法。开发插入标准 AI 搜索算法的启发式函数。
老实说，蛮力可能会在受约束的轨道上正常工作，因为如果您崩溃，您可以抛出一个子树（并且崩溃对于坏路径很常见）。
于 2011-07-05T23:11:42.697 回答
1
我建议你从扭转问题开始。假设你是唯一的玩家，使用逆行分析（就像他们在国际象棋残局中所做的那样http://en.wikipedia.org/wiki/Retrograde_analysis）从最后开始向后计算，看看需要多少步才能越过终点线，给定位置和速度。如果我的想法是正确的，那么计算它的时间应该在位置数量上是线性的。应该很快。
这不是绝对的真理，因为你有竞争对手干扰你的路径，但它会给你一个很好的启发式搜索算法。
于 2011-07-06T09:06:30.707 回答
1
虽然它不会立即适用于 RaceTrack，但您可以从A* 寻路算法中学到一些东西。它被用于许多游戏中，以帮助 AI 弄清楚如何尽快从 A 点到达 B 点。
于 2011-07-05T22:57:26.383 回答