IZ IN UR BASE KILLIN UR D00DZ - Lolcat

June 22nd, 2007

This morning I made this Lolcat of my cat Dante.

IZ IN UR BASE KILLIN UR D00DZ - Lolcat

Game Artificial Intelligence using the Minimax Algorithm

June 9th, 2007

Version 1.0

Prerequisite knowledge

Obviously you must know how to program in the chosen language.
How stack and heap memory work for your language (if it has it).
Recursion.

Helpful knowledge

How to debug your code and view the call stack.
By reference and by value parameters.
CSharp / JAVA

Whats next (Part 2 - Increasing performance)

Using a code profiler to tweak the algorithm and your code.
Alpha-beta pruning to increase search time.

Introduction

This tutorial will show the reader through explanations and code examples how to implement the Minimax Algorithm for Artificial Intelligence for the turn based computer game of their choice.

Before we begin I suggest the reader takes a look at the Minimax wiki artical
to understand some of the concepts involved with this algorithm which I will be talking about.

It doesn’t matter if you don’t understand much on that article yet (I didn’t until I worked on this).

Also I suggest you get some experience programming and debugging recursion before you try to implement Minimax into the game of your choice.

Level of difficulty: Hard to learn at first, but easy to do once understood.

Examples are done in Csharp, it was the only suitable language I had a compiler for where I wrote this.
If you know JAVA the code is accentually the exact same other than writing to the console.

What is Minimax?

Minimax is a computer algorithm which looks at all the possible outcomes of a situation and decides which is the best decision to take. This makes it perfect for turn based computer games.

It works on the principle of ‘Maximizing’ the chances of its self (the AI) winning while at the same time ‘Minimizes’ the chances of the other players winning.

The concept is actually extremely easy to understand.

The game which will use Minimax

In this tutorial I will be designing Minimax for a ‘pick up stick game’. The rules of this game are simple which makes it easy to explain and are as follows.

- The ‘pick up sick game’ is a game played by two players.
- The game starts with a number of sticks (Ill be using 10 in this example).
- Players take turns of either picking up 1,2 or 3 sticks.
- The player to pick up the last stick looses.

The game tree

The ‘Game Tree’ which is all possible game out comes of the game can be seen in the image below.

For ease of understanding I have shown the tree as if the game was from six sticks onwards. Ie, player one takes 1 sticks and player two takes 3 sticks 10 – (1+3) = 6; then the next move is player one’s in the game tree.

Now remember if there is 1 stick left and its your turn, you have to pick that stick up which means you loose.

Note: A player cannot make a loosing move on purpose and this is not shown.

Minimax game tree for 'pick up sticks' game

How to interpret the ‘Game tree’ diagram

Each player takes a turn at making a move. Players take alternate turns. This is shown to the right (P1 / P2).

The game ends once there are no sticks left. If you add up all the ‘Leaf’s ‘ of a game branch it will add up to be 6.

A branch is a possible way the game could play. In the diagram from 6 sticks left onwards the game can end in 10 different ways. Hence there are 10 branches.

Branches where blue wins are circled in blue and branches where red wins in red.

Leafs are shown in Orange, Purple and Green. They represent how many sticks will be picked up if that branch or fork of the game is taken.

Familiarize yourself with the game tree. I will refer to it thought the tutorial.

What the game tree shows us.

The game tree can be used to find the best possible move. For example, in the diagram when there are 6 sticks left and its player one’s turn it would be better for the player to pick up 1 stick this is because it results in a more likely chance of winning then picking up 2 or 3 sticks.

Picking up 1 stick results in a 3 to 1(66.67%) chance of winning where as 2 or 3 sticks results in a 1 to 1 and a 2 to 2 chance (50%).

Writing the code

So now how do we write code to search through the game tree to find the best possible move at any give point in the game?

A 2 player version

First you need to set up the rules of the game I suggest you write the game if you were writing 2 human player version first.

[csharp]
//The number of starting sticks
private static int NoSticks = 10;

//Max number of sticks a player can pick up at a time
private const int MAXPICKUP = 3;

//Holds the amount specified by the player to pickup
private static int PickUpAmount = 0;

//Holds which players turn it is
private static bool player1 = true;
[/csharp]

We set up values to hold how many sticks are left, we define the maximum pick up amounts and a value to hold which players turn it is (which will act as a switch between the players)

[csharp]
static void Main(string[] args)
{
//Let the game run while there is atleast one stick to pickup
while(NoSticks >= 1)
{

/*Prompt player one how many sticks they would like to pick up
*when its their turn. And prompt player two when its theirs.*/
if (player1)
{
Console.Write(”How many sticks would you like to pick up player1? :”);
}
else
{
Console.Write(”How many sticks would you like to pick up player2? :”);
}

//Read in the amount of sticks to pick up specified by the player
try{
PickUpAmount = Int32.Parse(Console.ReadLine());
} catch (System.FormatException ex) {
PickUpAmount = 0;
}

//Only make a the move if the pick up amount is valid
if (PickUpAmount < 4 && PickUpAmount > 0)
{
NoSticks = NoSticks - PickUpAmount;
Console.WriteLine(”Number of sticks left ” + NoSticks);
player1 = !player1;
}else{
Console.Write(”You can only pick up between 1,2 or 3 sticks”);
}
}

/*When there are no sticks left, the game is over.
*who ever picks up the last stick looses*/
showWinner();
}

[/csharp]

Next we write code to run the game until the game is over.

[csharp]
///
/// Shows which player has won the game.
///

private static void showWinner()
{
if(player1)
{
Console.WriteLine(”Player 1 wins”);
}
else
{
Console.WriteLine(”Player 2 wins”);
}
}
[/csharp]

Show which player has won the game.

Summary

If you wish to see how the 2 player version game runs download the source code and comment out the line that has ’showPlayerBestMove();’ in the file MainClass.cs

The AI version

The following code will go in a static class called ‘AI’

[csharp]
public static int three = 0,two = 0,one = 0;
[/csharp]

In the AI class we need to set up variables to hold how important the AI picks the corresponding amount sticks.
Because in the ‘pick up sticks’ game you can pick up one, two or three sticks we have values representing these choices.

For other games: This would be a list of every posible move in the game at any one time.
as you could imagine some games have thousands of choices a player can make
and this list can be quite large and will likely be an array of choices.

[csharp]
public static void runMinimax(int sticksLeft,bool playerAI,int noSticksToPickUp,ref int rootPickup)
{
int maxPickup = 3;

//Make the move
sticksLeft -= noSticksToPickUp;

//If after the pickup is made the game is over (no sticks are left) switch the turn
//to the other player.
if(sticksLeft == 0)
{
playerAI = !playerAI;
}

//Test to see if it was a lossing move
if(sticksLeft <= 1)
{
//'Max' has lost - Min has won (BAD)
if (playerAI)
{
if(rootPickup == 1) one- -;
if(rootPickup == 2) two- -;
if(rootPickup == 3) three- -;
}
//'Min' has lost - Max has won (GOOD)
else
{
if(rootPickup == 1) one+ +;
if(rootPickup == 2) two+ +;
if(rootPickup == 3) three+ +;
}
return;
}

//Start move logic using game rules

//If there is less sticks left then the maximum pick up amount then set
//the maximim pickup amount to the number of sticks left.
if (sticksLeft < maxPickup)
{
maxPickup = sticksLeft;
}

//Start the recursion which runs through all the posible moves at this current level

for (int i = 1;i <= maxPickup;i++)
{
runMinimax(sticksLeft,!playerAI,i,ref rootPickup);
}
return;
}
[/csharp]

runMinimax is basically the recursive method which runs the Minimax logic to find out how many sticks to pick up at the current point in the game. The amount calculated is the ultimate best choice to pick up.

For other games: Runs the Minimax logic to find out the best move at the current point in the game. The move calculated is the ultimate best move.


    parameter - sticksLeft

The number of sticks left avaliable to pick up. It is ‘the current state of the game’. In other games such as chess this would be the current board state. Ie, what pices are on the board and their positions.


    parameter - playerAI

Holds which players turn it is. If it is the AI’s turn (playerAI is true),
we are maximizing the chances of the AI winning. If it is the players turn, we
are minimizing the chances of the player winning.


    parameter - noSticksToPickUp

The number of sticks to pick up from the current game.


    parameter - rootPickup

This holds the value that we increment (the ‘root pickup amount’/'game move’ results in a win for the AI when the game is over on the current game branch) or decrement (result is oposite of increment). Think of it as the origonal move made by the AI that started the Minimax recursion. It is the value passed to the minimax algorithum method on the bottom of the call stack.
If we want to test how good picking up 3 sticks at the current point in the game, we pass it 3.
If we want to test how good moving king from A3 to A4 is we pass this logic.

[csharp]
public static int getNoSticksToPickUp()
{

//Find highest value logic
if(one > two && one > three)
{
return 1;
}

if(two > one && two > three)
{
return 2;
}
if(three > two && three > one)
{
return 3;
}
return 0;
}
[/csharp]

To finish of the AI class we need a method to find and return the best move.

Other games: This may be a loop that loops through all posible moves and returns
the highest move.
It is returning the maximum (best) move.

Implementing the AI into our original 2 player game.

Finally we need to take our AI code and implement it the origonal 2 player game. We do this by adding logic to start the algorithum

[csharp]
///

/// Shows which player has won the game.

///


private static void showPlayerBestMove()
{

int maxPickup = MAXPICKUP;

//If there is less sticks left then the maximum pick up amount then set

//the maximim pickup amount to the number of sticks left.

if (NoSticks < maxPickup)

{

maxPickup = NoSticks;

}

//Start the recursion which runs through all the posible moves at the root level

for (int i = 1;i <= maxPickup;i++)

{
AI.runMinimax(NoSticks,player1,i,ref i);

}

//Get the number of sticks to pick up as calculated from the AI

Console.WriteLine("You should pickup " + AI.getNoSticksToPickUp() +
" sticks");

//Resets all the moves. All moves will now be equally important
//until AI is run again
AI.resetCount();
}

}
[/csharp]

And finally add a line to run it all. Replace your player 2 logic with the call to start the AI

[csharp]
//call AI logic

showPlayerBestMove();
[/csharp]

Sumary

In summary I would like to share a few things I have learnt while doing Minimax.

- You still need to add your game specific logic. The code shown above will be similar for every game though you will still need to add your own game specific logic for things like making the move.
-Dont try to make your code perfect the first time around. Write the logic for understandability you can fix things latter (part 2).
-Its a very good idea to know how heap / stack works and how by reference and by value parameters works if you dont know these two things well you will never get anywhere.
-Know how to debug your code and how to set break points where certain conditions are meet. Know how to step into and over methods. Make sure you watch the call stack while debugging. Debugging recursion is always intense.

Source code / Program downloads / Other

I suggest you take a look at the full copy of the tutorials source code and run the compiled program (.net/Monno enviroment needed). Both source and binary can be found here.

Please leave questions and comments.

If you wish you can convert this tutorial into another language (programming or spoken) and I will put it here.

I dedicate this to Cocco.

Shoutoutz

May 4th, 2007

Ok its time I thanked a few of my Internet brothers.

Firstly Pauly over at unpointless.com for the FREE hosting! The service provided is simply amazing, huge disk space, huge file transfer and ssh (IRC,VIM,GNU Compilers) which allows me to do things like the Full metal Racket steam recording. Also thanks for being there with web-dev help.

Secondly Phranticsnr, my older bro who resides up North at phranticsnr.wordpress.com thanks for being my top referral behind the search engines. Thanks for the tour of Brisbane and the in-sight into technology and gadgets.

And last but not least, Orbitor who chills (literally) south of heaven down at cradanka.yi.org who hooked my up with some html layout (pictured below) which I use in the images and programs section of the site. He probably dosnt even remember doing this but thanks anyway. He also tries to provide a public e-service and rid the Internet of idiots, we should all thank him for this.

555.png
Theres more of you. You know who you are…

Peace

Full metal racket mp3’s

May 2nd, 2007

I have set up a process to record the weekly Australian heavy metal radio ‘Full metal racket” on JJJ which also broadcasts over the internet. I did this using Cron, Bash scripting, Mplayer using the -streamdump switch and PHP. Then I host the Mp3 files on my site for download on IPods or portable mp3 players for listening at our own leisure.
For those that are interested this is the bash script called DownloadFMR.sh:

1) #!/bin/sh
2) mp3filename=Full_Metal_Racket-`date +%y%m%d`
3) /home/slith/apps/MPlayer-1.0rc1/mplayer http://202.6.74.107:8060/triplej.mp3 -dumpstream -dumpfile /home/slith/emkay.unpointless.com/FMR/${mp3filename}.mp3

Here is my crontab; maybe theres a better way of stoping the recording than killing all instances of mplayer. Does anyone know?

0 5 * * 2 /home/slith/scripts/DownloadFMR.sh > /home/slith/mylogs/FMR.log
0 8 * * 2 kill -9 `ps -ef | grep DownloadFMR.sh | grep -v grep | awk ‘{print $2}’`
0 8 * * 2 kill -9 `ps -ef | grep mplayer | grep -v grep | awk ‘{print $2}’`

If all you care about is downloading the shows in Mp3 format you can find these here.

Full metal racket Slayer

Cobol

April 26th, 2007

Cobol - Code Only (no comments because even the programmers have no idea what its doing) Business Oriented Language.
COBOL hurts my head. No more please.
I think its funny that in 25 years programmers will probably go ‘oh no not C#’ (if their not already doing it now).

That is all.

Mobile app - Geek tools

April 13th, 2007

This weekend I have finished programming my first mobile application. It actually wasnt the first one I have finished but it was the first one I started.

Basically the idea behind Geek tools was to create a set of useful and fun tools for mobile that only geeks would have a need for.

Features:

Prime number checker: Can check a 64-bit integer for primality.

This may come in use some day. Maybe if you only place bets on horses which have only primes as their number.

Al bhed translator: Al bhed is a language spoken by a race in the game Final Fantasy 10. This tool allows you to convert from Al bhed to English and vice versa. The code that does this is very generic so it could be done to any other language and I am open to suggestions. Eg, Elvish.

Binary / Hex / Octal / Decimal / ASCII convertor: So far this is the ‘killer app’ of the tool set. I havnt seen any other J2ME apps with this capability so it may be the first! It can convert between any of the formats to any other format or base.

Some advice when using this; know the capability of your phone and dont give it something insane to convert to all other formats or it can take a while.

If you wish you can download it here http://jwhatson.googlepages.com/GeekTools.zip

Im very open to suggestions and ideas so please let me know if you want a feature added to Geek tools. Also like all of my phone apps im interested how it works on your phone.

Heavy metal reviews [Slayer - Christ Illusion]

April 13th, 2007

Ive been able to listen to allot of metal albums these days. My daily trip from my house to Sydney CBD allows allows me to listen to albums from start to finish with no interuptions.

This is how I have always thought albums should be listned to.

Here are my thoughts on what I have recently been listening to.

Christ Illusion

Review - God HATES us all! Firstly I want to talk about the song Black Serenade. I find this one of their most disturbing songs lyrically. Although I look at the funny sides of necrophilia so on second thought this song is killer rape hardcore! This song features a catchy heavy riff, perfectly timed guitar leads and a ideal contrast of tempo and ‘heavyness’.

One thing I noticed is Slayer albums feature no ‘filler songs’ or annoying interlude’s to waste time. Christ Illusion follows suit.

‘Eyes of the Insane’ is basically about how war makes a solider insane. It makes me understand how much you would see death and think about death. Your job is to take the life of the enemy, you will die also.

Now the most controversial song of the album - ‘Jihad’. This song is about the 9/11 attacks from the point of view of the ‘terrorists’ or ‘holly warriors’ depending which side you are on. Tom Araya’s vocals are peaty awesome to keep up with the tempo and I would like to see him pull this of live. The song ends with a extract from motivational letter used before the attacks and is tremendously effective.

I also love Skeleton Christ. Its about how Christianity is used to control people. Its about how Christianity black mails you into things that aren’t true. This song is awesome, its not like Decides rebellion. Its just saying that religion is stupid, you need to make up your own morals. Figure out for self whats right and wrong. Hail Satan! or F*ck Satan! It dosnt matter its all BS.

Overall this album features melodic solos which arn’t in the older Slayer albums. The album is well produced and refined compared to older stuff. It shows the band is still full of creativity in their older age. Its weird because this album is different though you can still decently tell it is Slayer. There is no band to being anything like Slayer.

4 out of 5 Pentagrams

Windows commands for UNIX freaks

March 24th, 2007

Ok, when I have a choice I will use a *NIX OS. I prefer to use *NIX because among other things the amount of power given over the OS at the command terminal.
Unfortunately 99% of the world uses Windows and when at work or school the systems admin would have a nervous breakdown if one day you just replaced the OS on your work pc, sure you may be 300 times more productive but, UNIX is evil isn’t it? Hence having no place on corporate computer equipment.

Heres where my problem starts. Well I take that back it’s more an personal announce…

I am constantly typing the ‘ls’ command in the Windows Command-prompt and as we know the equivalent to this command is actually ‘dir’ under Windows.

I literally do this every time I want a directory listing! It annoys me so much.

Today I had a few hours spare and thought I would figure out how to change this… Heres how.
First we use the doskey command, which will now alias ‘ls’ as ‘dir’ so know we can type ls command and the corresponding dir command will be executed.
Command Syntax - doskey ls=dir

The problem is the alias is lost every time we reboot or run a new command-prompt instance.
To fix this we need to add a registry key, which will set up our alias every time the command line is starts.

To do this we need to add a new registry key located under HKEY_CURRENT_USER\Software\Microsoft\Command Processor with the name ‘AutoRun’ and the value doskey ‘ls=dir’.

So now we are 33% more productive in listing directories! (3 letter command VS 2 letter)

Windows errors on the way to work

March 6th, 2007

Today as I was rushing to catch a train to work and noticed a crowd of people looking confused at one of the train departure screens. On closer inspection I realized it was a classic Windows error message. The crowd looked even more confused as I laughed at it while taking a photo with my phone.

Well here it is, sorry for it being blurred I was in a rush to a train that didnt even turn up.

The message box said there was a video driver error.

I hope its there tomorrow so I can get a better shot and put it on http://www.windowscrash.com/modules.php?name=gallery

*Edit*

OMG its still there, today after this edit being the 7th! It seems they cant get rid. Maybe they should drag it to the bottem corner? Or reboot? Or not use Windows?

Ohh no’s I forgot how to get home…

February 11th, 2007

So today I was driving with Mum and 5 minutes from home she asked me to get rid of a ant which she had found on her arm.
I picked the ant up and rolled down the window and placed him out side. This then got me thinking what will he do? Where will he go?

Will he..

A - Try to find his way home.

B - Join another local ant colony.

C - Start his own ant colony.