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

While it won't be immediately applicable to RaceTrack, you may be able to learn something from the A* path-finding algorithm. It's used in a lot of games to help the AI figure out how to get from point A to point B as quickly as possible.

Answer 2

So far, I don't think anyone has addressed a key point of your question: how do you come up with a good "quality value"? In AI, the quality value you refer to is usually called a "heuristic". Ideally, your heuristic would tell you exactly the minimum number of moves required to reach the finish, given the current position/velocity. In reality, we have to settle for something that's easier to compute.

One important guideline is that a good heuristic should be admissable; that is, it should never overestimate the cost of reaching the goal (in your case, the number of moves to reach the finish). The A* algorithm depends on having an admissable heuristic.

A common technique for coming up with an admissable heuristic is to relax the original problem. In games, you can often do this by changing the game so that it becomes easier (e.g. by dropping rules). In RaceTrack, for example, you could straighten out the track to make it an easier game. With a straight track, the best strategy is clearly to just continuously accelerate. Thus, an admissable heuristic is to compute the distance from the current position to the finish (i.e. the length of the straightened-out track) and then compute the number of moves required to travel that distance assuming constant acceleration.

You can come up with other heuristics by relaxing different rules, but there is often a trade-off between the accuracy of the heuristic and the amount of computation required.

Answer 3

there are a few algorithms known in chess like alpha-beta pruning, move ordering etc.. maybe you have better luck if you search in chess context.

---

alpha beta, strategy

---

Edit: Those path finding algorithms only work if you don't have additional rules and conditions. For example if you also have velocity and centripetal forces you're out of luck. If you don't have those advanced conditions you're better off with a simple path finding algorithm as stated in other answers.

Answer 4

You mention the idea of "assigning each choice some quality value" - this is called a heuristic function. Many AI algorithms (such as A* and alpha-beta pruning, mentioned by others) are only as good as the heuristic function you plug into them.

However, if you do manage to create a good heuristic function, then these algorithms will automatically perform much better "for free" - so it is very much worth your while to invest some time in developing a good one.

Another angle is to try to pre-compute your entire race from the start. Then it is a question of minimization of number-of-turns to cross the finish line. One handy minimum-finding algorithm is simulated annealing.

That aside, it would also be cool to see some genetic algorithm solution to a game like this. Not sure if it's quite the right fit, but I could imagine creating a 'brain' that takes various inputs - expected distance from wall at a few turns in the future, speed, distance to other racers, etc - and evolving the logic of that brain with a genetic algorithm. The trick is to break the problem down into parts that can be mutated meaningfully.

Actually, you could even combine them, and use a genetic algo. to develop a heuristic function which is plugged into a standard AI search algorithm.

Honestly though, brute force would probably work fine on a constrained track, since you can toss out a subtree if you crash (and crashes are common for bad paths).

Answer 5

I'd propose that you start by reversing the problem. Use retrograde analysis (like they do in chess endgames http://en.wikipedia.org/wiki/Retrograde_analysis) to calculate backwards from the end, assuming you are the only player, to see how many steps are needed to cross the finish line, given a position and velocity. If my thinking is correct, the time to calculate this should be linear in number of positions. Should be very quick.

It will not be the absolute truth, since you have competitors disturbing your path, but it will give you a very good heuristic for your search algorithm.

Answer 6

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