AI algorithm for “RaceTrack” game

Question

Does anyone knows (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, brute-force is getting very expensive even if you can rule out some choices because of the 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

The racetrack is a game classically played with pen and paper, but there are also video game implementations of it. The game is played on a track drawn on a grid. The track is the racetrack that the cars are supposed to stay inside.

The path shown in the track is a player’s race path.

To find a path from the goal to start the game shall use a genetic algorithm. Our AI is supposed to learn by generating individuals that are run through a racetrack and evaluated according to some fitness function.

The primary advantage of genetic algorithms comes from the crossover that combines two independent states into one. This makes the algorithm converge towards a good solution quickly.

In our algorithm the agent has three sensors; ahead, right and left (see figure 5). Each sensor returns either near, normal or far, indicating the distance to the nearest wall in the given direction. Because the thresholds of these sensor levels really are dependent on the track (how narrow the track is for example), they are specified by the sensor_near and the sensor_normal attributes in the .lvl-files. 

You can refer the following link for complete strategy given by the generic algorithm:

http://www.csc.kth.se/utbildning/kandidatexjobb/datateknik/2011/rapport/olsson_robert_OCH_tarandi_andreas_K11062.pdf

If you want know about Artificial Intelligence and Deep Learning then you can watch this video:

Learn more about Artificial Intelligence in this insightful Artificial Intelligence Online Course now!