Home arrow Practices arrow Page 7 - Solving Problems with Recursion

The Minimax Method - Practices

Recursion is a way to solve a problem by...reducing it to the same problem. What? It may be counterintuitive, but many turn-based games (including chess) use exactly this technique to make a computer player "think." Mohamed Saad explains the concept, along with when (and when not) to use recursion in your programming. Check out the Connect4 example!

TABLE OF CONTENTS:
  1. Solving Problems with Recursion
  2. The Plot Thickens
  3. First Programming Example
  4. The Flood Fill Algorithm
  5. How it Works
  6. Connect 4 AI program
  7. The Minimax Method
  8. Placing Pieces
  9. Trying it Out
  10. Two More Tips
By: Mohamed Saad
Rating: starstarstarstarstar / 54
November 17, 2004

print this article
SEARCH DEV SHED

TOOLS YOU CAN USE

advertisement

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.



 
 
>>> More Practices Articles          >>> More By Mohamed Saad
 

blog comments powered by Disqus
escort Bursa Bursa escort Antalya eskort
   

PRACTICES ARTICLES

- Calculating Development Project Costs
- More Techniques for Finding Things
- Finding Things
- Finishing the System`s Outlines
- The System in So Many Words
- Basic Data Types and Calculations
- What`s the Address? Pointers
- Design with ArgoUML
- Pragmatic Guidelines: Diagrams That Work
- Five-Step UML: OOAD for Short Attention Span...
- Five-Step UML: OOAD for Short Attention Span...
- Introducing UML: Object-Oriented Analysis an...
- Class and Object Diagrams
- Class Relationships
- Classes

Developer Shed Affiliates

 


Dev Shed Tutorial Topics: