Master Baboon The sea of the simulation

3May/092

My AI reads your mind and kicks your ass (part 2)

Get Adobe Flash player

In the last post I discussed how it is possible to program a game Artificial Intelligence to exploit a player's unconscious biases using a simple mathematical model. In the karate game above, the AI uses that model in order to do the largest amount of damage. Give it a try! You get 10 points if you hit your opponent with a punch or a kick, 0 points if you miss, and 5 points if you block your opponent's move. As you play, the AI learns your strategy and adapts to knock you down as often as possible.

How does it work? According to decision theory, we need to maximize the expected score. To compute the expected score for an action 'x' (e.g., 'punch'), one needs to consider all possible player's moves, 'y', and weight the possible outcome with the probability of the player doing that move, i.e.

E[score for x] = sum_y P(y) * Score(y,x)

where P(y) is the probability of the player choosing action 'y' (obtained using last post's model), and Score(y,x) gives the score of responding 'x' to 'y'.

For example, in the karate game using a low kick has a priori the highest chance of success: you score in 3 out of 4 cases, and only lose 5 points if the opponent decides to block your kick. This is why, at the beginning, the AI tends to choose that move. However, if you know that the AI uses that move often, you will choose the kick-blocking move more often, increasing P(kick-block). This change will make the punch more likely to score points. As you play, the optimal strategy changes and the AI continues to adapt to your style.

With a bit of practice, you'll notice that you can compete with the AI and sometimes even gain the upper hand over it. This shows that you are in turn forming an internal model of the computer's strategy. I think that the game dynamics that results from this interaction makes the game quite interesting, even though it is extremely simple. Unfortunately, it's very rare to see learning AIs in real-life video games...

As always, you can download the code here.

Update: Instead of always making the best move, the AI now selects the move with a probability related to its score, which makes it less predictable. More details in the next post...

[ad#adpost]

23Apr/093

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

Get Adobe Flash player

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]

14Feb/096

Guess 2/3 game: sending data from Flash to a remote database

I wrote a simple game to learn how to store on and retrieve data from a server-side database. The rules are simple: you have to guess 2/3 of the average of the guesses of all the players. So, for example, if you think that the other players guessed on average 100, your guess should be 67. The 2/3 rule is there to avoid the trivial strategy of  submitting the same number over and over again. According to game theory, the game has a Nash equilibrium at 0, which in this case does not correspond to a rational strategy. Wikipedia has some information and links about the game. Give it a try:

Get Adobe Flash player

The score you see after submitting is the distance from your guess to the true 2/3 of the average. Since you get some information about your and others' score, it should be possible to find a strategy to win in a small number of trials... Let me know if you find one!

Communicating with the server

To implement the game, I created a MySQL table in a database on the server that is used to store the players' name and guess. The database is accessed by calling a server-side PHP script from the game Actionscript client.

The PHP script gets the player's information and stores it in the database; then it computes the 2/3 of the average of all entries, and returns the score and rank of the current player, along with the top scores in the database. The script receives the data as a HTTP request (the ?var1=value1&var2=value2 thing you see in many dynamical web pages), and returns an XML fragment.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
\n";
// top scores
while (($row = mysql_fetch_array($hit)) && ($currentrank==0 || $rank<=$ntop)) {
  if ($rank<=$ntop) {
    print "
\n";
    print "
\t{$row['name']}\n";
    print "
\t{$row['diff']}\n";
    print "
\n";
  }
  if ($row['time'] == $time) {
    $currentrank = $rank;
    $currentscore = $row['diff'];
  }
  $rank = $rank + 1;
}

// current score
print "
\n\t{$name}\n\t{$currentscore}\n";
print "


\n";

mysql_close();

?>

Calling the script from AS3 is relativelty easy. The remote call is done by a URLLoader object; the actual request is stored in a URLRequest object, and the request variables are wrapped in a URLVariables instance. I had an annoying problem with testing the code: for some reason, Flash always caches the requests. I looked around and it seems that the only workaround is to add a dummy variable to the request with a value that changes constantly, e.g., the current time.

This is the code for the communication with the server:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public function submitGuess(name:String, guess:uint, ntop:int):void {
    var request:URLRequest = new URLRequest("http://www.masterbaboon.com/php/guess23/guess23submit.php");
    var httpHeader : URLRequestHeader = new URLRequestHeader("pragma", "no-cache");
    request.requestHeaders.push(httpHeader);

    // request variables: name of player, guess, number of top scores to return
    var vars:URLVariables = new URLVariables();
    vars.name = name;
    vars.guess = guess;
    vars.ntop = ntop;
    // this is to trick AS3 into not caching the URL request
    vars.nocache = Number(new Date().getTime());

    request.method = URLRequestMethod.GET;
    request.data = vars;

    // send to server and call loadingComplete when complete
    var loader:URLLoader = new URLLoader();

    // the results of the request is not returned immediately, but
    // we can monitor the COMPLETE event dispatched by the loader
    loader.addEventListener(Event.COMPLETE, loadingComplete);
    try {
        loader.load(request);
    } catch (e:Error) {
        trace("An error has occurred while communicating with the server.");
        trace(e);
    }
}

public function loadingComplete(e:Event):void {
    // this is how to access the data returned from the request
    data = XML(e.target.data);
    // switch frame
    gotoAndStop("highScoreFrame");
}

You're welcome to download the whole code.

[ad#adpost]

7Feb/094

Simulated evolution

Here's another classic from the 80's: an artificial life simulation, where bugs move on a virtual Petri dish, hunting for bacteria. If they manage to survive until adulthood, and accumulate enough energy from bacteria, the bugs reproduce and generate two copies of themselves. In the reproduction process, the genetic code undergoes small mutations, so that the baby-bugs are not exact copies of their mother.

Get Adobe Flash player

The genetic code of bugs determines the way they move around. It consists of six numbers that give the probability that the bug will move  in one of six directions (forward, soft/hard right, backwards, soft/hard left) at any point in time. For example, a bug with code [5, 0, 5, 0, 0, 0] would move forward 50% of the time (relative to his current direction), and for the rest of the time it would take a hard turn right (120 degrees on its right) and move. Mutations change one of the numbers in the code by +/- 2.

Individual with a genetic code unfit to deal with competition for food eventually die away, and by the law of natural selection the population of bugs adapts to efficiently navigate their environment to collect bacteria. The optimal strategy will depend on the environment: if the bacteria are randomly scattered around, the optimal behavior is to "slide" forward for some time before taking a turn. If instead bacteria are concentrated on a small patch, a surer way for a bug to survive is to rotate on itself, to make sure not to get too far.

This idea was described by A.K. Dewdney in in the article "Simulated evolution: wherein bugs learn to hunt bacteria" in 1989  in Scientific American (May, pp. 138-141). The flash application above is my version of Dewdney's simulation, implemented in ActionScript 3 (click here to download the code). It is based on the SpatialDatabase class described in the previous post, so you might want to have a look at the code if you're curious about how it can be used in practice.

As you might have guessed, the yellow circles are bacteria, while the green ones are bugs. Bugs start to fade when their energy is low; if they don't find food fast enough, they eventually disappear into nothing. The button "Garden of Eden" activates a small region with high bacterial growth, you can switch it on to see how fast the bugs adapt to the new environment. It usually takes around 20 generations for them to show a highly specialized behavior.

Have fun!

[ad#adpost]

1Feb/095

2D Cellular Automata

I decided to get my feet wet with Flash + ActionScript programming with a classic of the 80's: 2-dimensional Cellular Automata!

A 2D CA is a grid of cells, each of which can be in either an "alive" or "dead" state. The state of each cell evolves in time, according to simple update rules based on the number of alive neighbors (each cell has 9 neighbors). Briefly:

  • The update rule defines the overall behavior of the CA, and is given by two lists of numbers, S for "Survival" and B for "Birth"
  • If the cell is alive and the number of active neighbors is not on the S list, the cell dies
  • If the cell is dead and the number of active neighbors is on the B list, the cell becomes alive

The standard notation for the rules is S/B. For example, 23/3 (S=[2,3], B=[3]) corresponds to the celebrated Game of Life by Conway, that produces ever-changing patterns of activity. The reason CAs are so famous is because they are a perfect example of how simple, local rules can produce complex, global behavior.

In the Flash application below, you can experiment with different rules by (un)checking the checkbox on the right side. This wikipedia page has a list of rules known to produce interesting behavior.

Get Adobe Flash player

Short instructions: click on the grid elements to switch them between dead and alive states. On the right side, you can add numbers to the Survival and Birth list, clear the CA to a blank state, or set the cells to a random state.

Actionscript notes

You can download the AS3 and the Flash library here. This is my first ActionScript project, so everything was new to me. The hardest part for me was to figure out how to link the interface I designed in the Flash IDE with the AS3 classes. I think I found a decent solution in the end, but let me know if you have suggestion to improve the code.

The BinaryCA class is an independent class to manage 2D CAs. To store the CA cells I based the core on the Array2 class from polygonal labs' AS3DS data structures library.

Cellular Automata...  so retro!

[ad#adpost]