Archive for the 'Tutorial' Category

Game Artificial Intelligence using the Minimax Algorithm

Saturday, 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.