Learning Artificial Intelligence for Racing Games like Anki
Originally published by Christian Kramp on LinkedIn
Famous Anki Drive and soon Anki Overdrive is a toy for young and old. But what makes it different from old Carrera tracks? It is the fact that you don’t need a human counterpart for a thrilling race. AI racers are participating and racing against you. Even more interesting is that your AI counterparts are learning!
Now I asked myself: How does it work? How is the AI learning? Again my thoughts went to far and had crazy solutions. But it is easier and again we are using a lot of math and statistics. But at the beginning I explain my personal solution.
Let’s start with an image which shows the track and four cars on it. Every track piece is black and is limited on the left and the right with an orange border. As mentioned in articles in Wired or on Mashable (http://mashable.com/2015/07/21/anki-overdrive-racing-fun/) the cars use infrared-sensors for steering. This can also explain how AI drivers recognize the orange borders of the track.
Taking account that the AI cars are now able to measure the width of a track it can apply the given data for future analysis of battles for a position. Assume that a car describes the track ahead with 0 and 1. 0 means the track area is free while 0 means that something is ahead. Perhaps we add -1 to define the track border.
In the table above we reconstructed two length units and the track is free ahead of the car. But how does it learn?
Obviously it uses a mix of statistics/probability and commands. Commands because an AI driver isn’t driving around the track on the same virtual line but makes decisions and statistics and probabilities, because the sensors are recording and saving what is happening ahead, how other AIs and the players react. Every AI has the one target to win a race (or another game mode) so it has to record and compare every single maneuver and calculate the success based on the result or in other words speed-gain or speed-loss, successful overtaking or failed overtaking and more.
Here we have to choose a search-tree and apply A* search algorithm. What is it doing? It tries to reach a point M from A and want to avoid high costs. Additionally it applies a limited knowledge, the algorithm is fast and this is necessary for a racer. In our case the costs are factors mentioned above, e.g. speed-gain or loss. or in other words the probability to gain an advantage on track.
Let’s have a look on the following situation:
The AI car is on the second line from the left on the track-piece and a unit ahead is another car (1) we call Freddie. If the AI already got the chance to drive against another AI or human players it already collected data about the probability for a successful overtaking of the car ahead.
If Freddie isn’t smart, maybe really dumb, our AI would have great chances to overtake him through passing by on his left. But the average driver would try to block a competitor’s passing attempt while steering to the right could decrease the speed on the track and mean a disadvantage.
Thanks to the data collected in previous races our AI racer is able to make a decision.
In the situation above the success-rate for a passing-maneuver on the left is only 10% but 60% if you try to pass the competitor on the right. This would be an easy decision. Of course you can add more factors like the competitor’s speed, side changing pattern today and more. After the maneuver the result will be saved and changes the experience.
And even more interesting is the calculation if we are applying Bayes’ Theorem.
Let’s assume that I am the AI and racing on the track position mentioned before with a single free lane left from my rival ahead. We know that the probability of a successful takeover is 60% if there are two lanes free on the left (P(A1)), but the probability is only 13% if there is just a single lane left free (P(A2)). And we know that the when a racer called „Psycho“ is on the track the probability of a successful takeover is just 20% while the probability is 80% if we have another racer (Event B).
We want to know the probability of a successful overtaking-maneuver against „Psycho“ or P(A2 | B).
= P(A2) * P(B | A2) / P(A1)*P(B | A1) + P(A2) * P(B | A2)
= P(0.13)*(0.2)/[(0.13)*(0.2)+(0.6)*(0.8)]
= 0.0514
= 5.14%
If I didn’t make a mistake the chance of a successful overtaking on the left single free lane is 5% or: 5 of 100 tries will be successful. It depends on the AI characteristics if it’ll risk it. Characteristics by the way are important. Anki makers said every AI driver is different from each other. How are they doing it? If AI thinks logic it wouldn’t try to overtake Psycho. Here we have an eye on video games like MLB: The Show. Every player on the field has skill values. To simplify the whole process a pro now has a skill-value called Hit. It shows how well he hits the ball thrown by the pitcher. Simple again, if the value is 70 we could say that there is a 70%-chance for the batter to hit the ball. There are a lot of options how to combine different skills (left- or right-hand strength + coverage + vision etc.). Anki-AI-drivers may have characteristics like „taking risks in account“ or others.
What does it mean for the gaming experience? The game is steadily changing. Everybody’s Anki is different because everybody has an own driving style and uses different strategies.
And there is another instrument for decision making and analysis. We are talking about clustering. Clustering is a method to assign items to a group or to a pattern mirrored in values in a grid.
The example above is a very basic, not real example how a cluster could look like. As you can see there are four groups with higher concentrations. Each blue bubble represents a driver and now we could say that a cluster in the upper left is for careful drivers, the cluster in the upper right for safe but fast drivers, lower left for the reckless drivers and so on. The ability to assign a driver to a group can clarify which data the AI should use for decision making. If we are behind a careful driver it would be easier to pass by than if we are behind a reckless driver. Perhaps the last one would brake for surprise to stop us.
Of course every action changes the values and our AI reacts immediately on the new strategies.
I imagine that Anki developers are working with simple routines for track parts where AI drivers are alone. So you can imagine the process like this:
Driving — Scan: Nothing! — Driving — Scan: Nothing — Driving — Scan: DRIVER! — Ignition AI
The machine will easily master the track if there is no car next to it, but it must challenge others as soon as it faces them.
Conclusion
This was just a simple explanation about the machine learning behind Anki (as a popular example). Of course the software is more complex than what I have written and you need more information and the right technology to realize a project like this. Anki’s president Hanns Tappeiner wrote in a blog-post from August 23, 2013: „We spent the last five years writing the tens of thousands of lines of code that power Anki DRIVE, honing and perfecting the technology.“
