人工智能算法和QUOT;赛马场及QUOT;游戏 [英] AI algorithm for "RaceTrack" game

问题描述

没有人知道（或者可以建议）一个好的算法，人工智能的的RaceTrack pencil-纸的游戏？

does anyone know (or can suggest) a good algorithm for an AI for the RaceTrack pencil-paper game?

因为你必须在每一步9个可能的选择，你需要看看，至少6-10步骤提前决定一个很好的策略，暴力破解越来越很贵，即使你能排除一些选择，因为路口的边界

since you have 9 possible choices in each step and you need to look at least 6-10 steps ahead to decide on a good strategy, bruteforce is getting very expensive even if you can rule out some choices because of intersection with the boundary.

目前我试图以决定排除其选择为每个选择一些优质的价值 - 但我不知道好规则尚未就如何分配这样的质量值

Currently I'm trying to assign each choice some quality value in order to decide which choices to rule out - but I don't know good rules yet on how to assign such a quality value.

推荐答案

我已经做了C ++解算器，这是一个有点长（187线），合身舒适在这里，所以我把它放在引擎收录，而不是：的http://pastebin.com/3G4dfTjR 。该方案无论是计算最优（招式最小可能数）的解决方案，或报告，没有任何可能。

I have made a C++ solver that's a bit too long (187 lines) to fit comfortably here, so I have put it in pastebin instead: http://pastebin.com/3G4dfTjR. The program either computes an optimal (minimum possible number of moves) solution, or reports that none is possible.

运行程序的跑道的 STARTX startY goalX goalY [circleX circleY半径] 的

Run the program as racetrack startX startY goalX goalY [circleX circleY radius].

该计划假定一个100x100的网格，其可任选含有一个圆形的障碍物，其圆心和半径指定。您必须另外指定汽车的初始位置，一个单一的目标位置。尽管这些限制是有些严格，一看code应该很明显，他们不限制的算法一般 - 所有相关的逻辑被封装在 isMoveValid（）和 isGoalState（）程序，因此，如果有人能打扰实施这些程序较为笼统的（例如允许用户指定格位置的位图，和/或允许多个目标位置），那么这可以被掺入没有困难。

The program assumes a 100x100 grid which may optionally contain a single circular obstacle whose centre and radius you specify. You must additionally specify the car's initial location, and a single goal location. Although these constraints are somewhat restrictive, a look at the code should make it obvious that they don't limit the algorithm in general -- all the relevant logic is encapsulated in the isMoveValid() and isGoalState() routines, so if someone can be bothered implementing more general versions of these routines (e.g. allowing the user to specify a bitmap of grid locations, and/or allowing multiple goal locations) then this can be incorporated without difficulty.

只有轻微的并发症是在获得目标位置是相同的（或接近，但上的另一边）的起始位置，这是你需要的，如果你希望你的轨道是一个电路。在这种情况下，为了避免求解简单地扭转了汽车或立即停药，你将需要指定一个无形的起跑线，并改变 isMoveValid（）来禁止跨越这条线倒退的运动。

The only slight complication would be in getting the goal location to be the same as (or near, but "on the other side of") the starting location, which is what you need if you want your track to be a circuit. In this case, in order to avoid the solver simply turning the car around or stopping immediately, you would need to specify an invisible "starting line", and alter isMoveValid() to forbid "backwards" movements across this line.

由于每次移动的成本正好是1，这是可以使用的广度优先搜索通过四维状态空间找到一个最佳的解决方案。每当我们访问一个给定的状态S，它由四元组（X，Y，DX，DY）与dx和dy是我们用来获取到（X，Y）的速度矢量，我们认为所有的9个国家，我们可以从s的单一举动到达。对于任何这样的状态t内尚未见到，这条道路为T（即通过S）保证是最优的，因为BFS总是访问，以便他们的最小的从根距离的节点。每当我们确定了一个状态的最佳路径，我们记录了predecessor状态，使全路径的追踪将在年底产生的。

Because each move costs exactly 1, it's possible to use a breadth first search through the 4D state space to find an optimal solution. Whenever we visit a given state s, which consists of a 4-tuple (x, y, dx, dy) with dx and dy being the velocity vector we used to get to (x, y), we consider all 9 states that we can reach from s with a single move. For any such state t which has not already been seen, this path to t (i.e. via s) is guaranteed to be optimal, since BFS always visits nodes in order of their minimum distance from the root. Whenever we determine an optimal path for a state, we record the predecessor state, enabling a traceback of the full path to be produced at the end.

BFS更简单，因此很可能更快，比Dijkstra的算法或A *搜索，这是更一般的算法，考虑将移动到具有各种成本 - 灵活性，我们并不需要在这里。 A *可以是，如果有较少障碍物混淆其启发式快，但在每一个步骤，它需要查找最低成本节点，它通常是采用一个堆，而对于BFS一个最低成本节点始终可用在前面的队列的

BFS is simpler, and thus probably faster, than Dijkstra's Algorithm or A* search, which are more general algorithms that allow moves to have various costs -- flexibility that we don't need here. A* may be faster if there are few obstacles to confound its heuristic, but at each step it needs to look up the minimum-cost node, which is usually done using a heap, whereas for BFS a minimum-cost node is always available at the front of the queue.

秒表赛道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.

注意如何最优解这里首先必须双背，上去和周围，然后再向下，由于圆障碍物延伸经过网格底部一路

Notice how the optimal solution here first has to "double back", go up and around and then down again, since the circular obstacle extends all the way past the bottom of the grid.

小错误：在code作为发布会给一个简短的回答，如果你设定的目标位置等于初始位置（但非零长！）。显然，这可以检查作为一个特例，但我已经把code对引擎收录，当我意识到这一点...：）

Small bug: the code as posted will give a short (but nonzero-length!) answer if you set the goal location equal to the initial location. Obviously this could be checked for as a special case, but I'd already put the code on pastebin when I realised this... :)

这篇关于人工智能算法和QUOT;赛马场及QUOT;游戏的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！