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]

21Feb/095

Advanced math functions for AS3

Did you ever need to sample from a Dirichlet distribution in Actionscript 3.0? What about computing a value of the Gamma function? Probably not ūüėČ In case you did, I wrote a class with a few math methods:

  • a function to sample from multinomial distributions; this is useful if you need to choose randomly from a set of elements, each with a different probability;
  • functions to draw samples from the Dirichlet and Gamma distribution;
  • the Gamma function
  • a factorial function that works even for large values (using the identity n! = Gamma(n+1))
  • other utility functions, e.g. to compute mean and variance of an array, or add two arrays together

You can download the AdvancedMath class here, it includes AsUnit tests.

This is an example of how to use the AdvancedMath class to simulate a rigged dice: the code below throws the dice 1000 times, and keeps a count of how many times one gets the different faces.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import com.masterbaboon.AdvancedMath;

// probability of the faces; 6 is about twice more likely to appear
var p:Array = [0.14, 0.14, 0.14, 0.14, 0.14, 0.3];
           
// count the number of times a face appears
var count:Array = AdvancedMath.zeros(6);
           
// throw dice 1000 times
var face:int;
for (var i:int = 0; i < 1000; i++) {
    face = AdvancedMath.sampleMultinomial(p);
    count[face]++;
}
           
// show how many times we got which face
trace(count);

[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)) &amp;&amp; ($currentrank==0 || $rank&lt;=$ntop)) {
  if ($rank&lt;=$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();

?&gt;

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]

7Feb/092

Spatial database for collision detection

In games and other graphical applications one has to keep track multiple sprites and detect collisions between them. A naif approach would loop over all sprites and check for collision with *every other sprite*. This is, of course, terribly inefficient and can be very slow even for a small number of sprites.

One way out of this nightmare  is to register the sprites in a spatial database that stores them according to their position, and is able to determine which of them is close to a given point. As a result, one only needs to check for collision between neighboring sprites. There are many implementations of spatial databases, some of which are quite sophisticated. In this post I'm going to describe an ActionScript 3 implementation of a grid-based spatial database, that can be used for simple flash games.

Grid: 2D Array with neighborhood

A Grid is a two-dimensional array with a concept of neighborhood. In addition to be able to store and retrieve information on the 2D grid, one can request neighboring elements of a given array element.

For example, let's create a simple 4x4 grid, and store at each point an increasing number:


1
2
3
4
5
6
7
var grid:Grid = new Grid(4, 4);
var k:int = 1;
for (var i:int = 0; i &lt; 4; i++) {
    for (var j:int = 0; j &lt; 4; j++) {
        grid.set(i, j, k++);
    }
}

This image shows the resulting grid, with small numbers indicating grid coordinates and large, bold ones the stored values:

grid11

We can now query the grid to get neighbors of a given position: For example, the following code


1
2
3
4
var neighbors:Array = grid.getNeighbors(1, 1);
trace(neighbors);
neighbors = grid.getNeighbors(1, 3);
trace(neighbors);

displays 1, 2, 3, 5, 7, 9, 10, 11 and 3, 4, 7, 11, 12, respectively, as shown here:

grids2and3

Note that, by default, the neighbors stop at the border. It is possible to work on a "toroidal" grid, meaning that the opposite borders of the grid are connected:

grid4


1
2
3
grid.setToroidal(true);
neighbors = grid.getNeighbors(1, 3);
trace(neighbors);

which prints 3,4,1,7,5,11,12,9 .

I added two functions that simplify working with neighbors. The first, mapOnNeighbors(x, y, fct), applies a function fct to all neighbors of (x,y). Let's  see which of the neighbors of (1,3), are even numbers, just for fun:


1
2
3
function isEven(x:int):Boolean { return (x % 2 == 0); }
var neighborsAreEven:Array = grid.mapOnNeighbors(1, 3, isEven);
trace(neighborsAreEven);

This gives false,true,false,false,false,false,true,false. There are several interesting uses of this method: collecting information from elements in a region of the grid, activating neighboring elements, ...

The second function, reduceOnNeighbors(x, y, fct), is a bit more difficult to explain, but equally useful: it returns a single value constructed by iterating over the neighbors of (x,y) and calling fct(a, b) on the first two items of the sequence, then on the result and the next item, and so on. We can use this function to compute the sum of all neighbors:


1
2
3
function sum(x:Number, y:Number):Number { return x + y; }
var sumOfNeighbors:Number = grid.reduceOnNeighbors(1, 1, sum);
trace(sumOfNeighbors);

prints 48 = 1+2+3+5+7+9+10+11 . This function could have been used for example in the previous post in the Cellular Automaton code, to compute the number of alive neighbors for every cell of the CA.

SpatialDatabase

The SpatialDatabase class registers sprites in a Grid with coarser resolution. For example, a Shape at position (31, 23) on the stage would be stored in element (3,2) if the resolution of the grid is 10 pixels.

That's basically all there is to it! For collision detection, we can query the spatial database for sprites registered at neighboring elements in the grid:


1
2
3
4
5
6
7
8
9
10
// Check collision with shape:Shape
// 1. get neighbors
var neighbors:Array = spatialDatabase.getAllNeighbors(shape.x, shape.y);
// 2. loop over all neighbors and check collision
for each (var s:Shape in neighbors) {
    // check collision
    if (checkCollision(shape, s)) {
        // do something (bounce, explode, ...)
    }
}

A higher resolution gives an optimal performance. Just keep in mind that the grid size should be larger than the size of the largest sprite, otherwise some collisions may go undetected.

There exist much more sophisticated methods to improve the efficiency of collision detection (see for example this post and the excellent tutorial at metanet software). However, this simple grid-based approach can be *very* efficient for many applications!

You can grab the code for the Grid and SpatialData`base classes here (including AsUnit tests for the Grid class). I have a nice example of this class at work, but this post is already long enough, have a look at the next one!

[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]