Solving Problems with Recursion - The Minimax Method
(Page 7 of 10 )
What we have just created is called the minimax method. Let's see roughly how our code should look. I will try to keep things as simple as possible, so as not to distract you from the main idea. I will explain how to improve on it later.
class MoveValue
{//holds a score, column pair.
int Score;
int col;
MoveValue(int s,int c)
{
Score=s;
col=c;
}
MoveValue()
{
Score=col=0;
}
}
class Connect4
{
byte board[][]=new byte[8][7];
//the connect 4 board. 0 means empty, 1 means player 1 piece
//2 means player 2 piece
MoveValue bestMove(byte sideToMove,int depth,int maxDepth)
{//Finsd the best move for the side. Returns column and score pair
//depth specifies current level of depth (should be passed as 0)
//maxDepth specifies the maximum depth to search
//holds the best score
MoveValue best_score = new MoveValue(-100000,0);
if(depth%2==1)best_score.Score*=-1;
MoveValue mv=new MoveValue();
for (int i=0;i<7;i++)
{ //try putting a piece at each of 7 columns.
mv.col=i;
if(board[0][i]!=0)
continue; //if column is full ignore it.
//find the row to put this piece. x is the row
int x=0;
while(x<8&&board[x][i]==0)x++;
board[x-1][i]=sideToMove;
//find if it is a game over, don't search further if it is
//a score of 100 or -100 means a game over
MoveValue cur=new MoveValue();
cur.Score=value();
if(cur.Score==100||cur.Score==-100||depth==maxDepth)
mv.Score=cur.Score;
else //search further (this one is the recursive call)
mv.Score=bestMove((byte)(3-sideToMove),depth+1,maxDepth).Score;
//3-sideToMove, gives you the number of the opponent. If sideToMove is 1
//3-sideToMove will be 2. If sideToMove is 2, 3-sideToMove is 1
//if this move is better, use it instead
if(mv.Score>best_score.Score&&depth%2==0)
best_score=mv;
else if(mv.Score<best_score.Score&&depth%2==1)
best_score=mv;
//undo the move. Remove the piece you just put
x=0;
while(board[x][i]==0)x++;
board[x][i]=0;
}
return best_score;
}
}
This is the most complex piece of code we have written today. What does it do? Let me explain.
The code starts be defining a new class MoveValue, just to hold the value of a move, plus the column to play at. For example, if we discover that the best move is at column 3, which will give you a benefit of 90, the pair should hold the value (90,3).
Now, let's turn our attention to the code itself.
The basic idea is simple. Each move is assigned a score based on how good this move is for the player. We choose the best move for the player by choosing the move with the highest score.
The code first declares a MoveValue variable called best_score to hold the best move it can find.
If depth is odd it initializes the score to a very small negative number, or else it initializes it to a big positive number. Huh? Why? Remember when we said the computer, when it tries its moves, should take the best move for itself, and when it considers the opponent's move, it should take the worst move for itself. In other words, the best move for its opponent.
This is the reason behind those initial values. When depth is even, we are considering a move for the computer, so we initialize the score to a very small value so that the first possible move will be better than it. And when depth is odd, we initialize it to a very big number, so that any possible move will be worse than it.
Next: Placing Pieces >>
More Practices Articles
More By Mohamed Saad
/ 32 
