## My AI reads your mind (part 1)

I regularly read about people complaining that AI in games should be improved. I definitely agree with them, but here's a argument why pushing it to the limits might not be such a good idea: computers can easily discover and exploit our unconscious biases.

Magic? ESP? More like a simple application of decision theory. In order to make an unbeatable AI one needs two steps: 1) build a model of a player's response in order to predict his next move, and 2) choose actions that maximize the expected score given the prediction of the model.

The basic idea behind 1) is that even if we try to be unpredictable, our actions contain hidden patterns that can be revealed using a pinch of statistics. Formally, the model takes the form of a probability distribution: P(next move | past observations).

Try it out: In the Flash example below, you can type in a sequence numbers 1-4, and the AI will try to predict your next choice. If your choices were completely random, the AI would only be able to guess correctly 25% of the time. In practice, it often guesses correctly 35-40% of the numbers! (It might take a few numbers before the AI starts doing a decent job.)

In this example I used a 2nd order Markov model, i.e., I assumed that the next number, n(t+1), only depends on the past 2 choices: P(n(t+1) | past observations) = P(n(t+1) | n(t), n(t-1)). The rest is just book-keeping: I used two arrays, one to remember the past 3 numbers, and one to keep track of how many times the player chose number 'k', given that his past two moves were 'i' and 'j':

1 2 3 4 5 | // last 3 moves public var history:Array = [1, 3, 2]; // transition table: transitions[i,j,k] stores the number // of time the player pressed 'i' followed by 'j' followed by 'k' public var transitions:Array; |

When the player makes a new choice, I update the history, and increment the corresponding entry in the transition table:

1 2 3 4 5 6 7 | /* * Update history and transition tables with player's move. */ public function update(move:int):void { history = [history[1], history[2], move]; transitions[history[0]][history[1]][history[2]] += 1; } |

The probability that the next choice will be n(t+1), is given by the number of times the player pressed n(t+1) after n(t) and n(t-1) before, normalized by the number of time the sequence n(t-1), n(t) occurred in the past:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | /* * Return probability distribution for next move. */ public function predict():Array { // probability distribution over next move var prob:Array = new Array(4); // look up previous transitions from moves at time t-2, t-1 var tr:Array = transitions[history[1]][history[2]]; // normalizing constant var sum:Number = 0; for (var k:int = 0; k < 4; k++) { sum += tr[k]; } for (k = 0; k < 4; k++) { prob[k] = tr[k] / sum; } return prob; } |

The best prediction is given by the choice with maximum probability. You're welcome to have a look at the code!

In the next post, I'll show how the AI can choose the best actions in order to maximize its expected score in a Virtual Karate game.

[ad#adpost]

ChiJune 15th, 2010 - 21:01

sorry to bother you, i’m right now writing a flash game, maybe later i’m gonna bother you to ask you to teach me something. but even though you’re not going to help me, i still want to say that your site is really really great, i can learn a lot from every single post. thanks for sharing your knowledge! seriously

masterbaboonJune 16th, 2010 - 09:02

@Chi: I’m glad you like the blog! Don’t worry about asking, I’ll try and answer if I can.

NghiaJuly 26th, 2012 - 08:04

can you convert your code into java code, I got some issue of misunderstanding