AI algorithm for "RaceTrack" game

Question

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

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.

Answer 1

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.

Usage

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

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.

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.

How it works

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 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.

Examples

stopwatch racetrack 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.

stopwatch racetrack 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.

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... :)

Answer 2

Others recommend A*, which is probably the way to go, but there is a problem with that approach. Let me first say that the 'cost' of going from one node to another is always 1, as you want to minimize the number of steps, there simply is not other cost involved.

But the important point I want to make is that a location (x,y) is not a unique node in the search graph of A*! The node is characterized by x and y, but also by the x and y coordinates of the node the car is coming from(or by the velocity components vx and vy if you will). So you cannot just traverse the A* algorithm over a 2 dimensional grid; it should actually be 4-dimensional. That said, A* is probably still the way to go.

As for the heuristic, you could get really creative about that one, but I suggest something like distance to finish minus current velocity, where the distance is precalculated for each point in the regular 2D grid(use a Dijkstra algorithm for that). This makes the A* algorithm search first towards the finishline and preferably as fast as possible. I believe such an algorithm would do very well to calculate the entire route immediately.

One problem though, is that A* will always yield the optimal route, so an AI using such an algorithm wouldn't be fun to play against, as it would always win(assuming the startingpositions are fair).