Tag Archive for ‘game’ at Master Baboon

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…

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:

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.

Master Baboon