Home arrow Practices arrow Page 8 - Solving Problems with Recursion

Placing Pieces - 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

Now what? We make a loop over all 7 columns and try to put a piece in each place. We try to put a piece in column #i if it has an empty slot.

After trying to put a piece we call a function called value() to tell us about the value of this position. The function value(), which we are going to cover in a moment, is given the current situation, and gives us a score that tells us how well this position is for the computer--higher is better, of course.

We call this function first to check for a game over. If it returns +100 the computer has won, or if it returns -100 the human player has won (this is how we are going to program it). In both cases, we don't need to continue trying further moves. The game is over.

So, we check if the return from this function was +100 or -100 or if we have reached the end of our analysis (depth is equal to maxDepth) and we just take the value returned from the value() function.

If not, we recursively call the bestMove() function to continue digging deeper into the tree of possibilities.

In both cases, we check the return from the function against the best score found so far. If the new score is better than the best score found so far (i.e. it is larger than the best score if it is the computer's turn, or smaller than the best score if it is the human's turn), we replace the best score with the new score.

Finally, we return the board to what it was by removing the piece we just put. We repeat again for the next column and so on

The Value Function

Now, what about that value function? This function should tell us how good a position is from the point of view of the computer player. For the sake of simplicity, we will make a simple value function that just checks who is winning. Here it is

int value()
{//get the value of a position

 //check for 4 in a row
 for(int i=0;i<5;i++)
  for(int j=0;j<7;j++)
   if(board[i][j]!=0&&board[i][j]==board[i+1][j]&&
   board[i][j]==board[i+2][j]&&board[i][j]==board[i+3][j])
    if(board[i][j]==1)
     return 100;
    else return -100;
    
 //check for 4 in a column
 for(int i=0;i<8;i++)
  for(int j=0;j<4;j++)
   if(board[i][j]!=0&&board[i][j]==board[i][j+1]&&
   board[i][j]==board[i][j+2]&&board[i][j]==board[i][j+3])
    if(board[i][j]==1)
     return 100;
    else return -100;
    
 //check for 4 in a diagonal
 for(int i=0;i<5;i++)
  for(int j=0;j<4;j++)
   if(board[i][j]!=0&&board[i][j]==board[i+1][j+1]&&
   board[i][j]==board[i+2][j+2]&&board[i][j]==board[i+3][j+3])
    if(board[i][j]==1)
     return 100;
    else return -100;
   
 //check for 4 in the reverse diagonal
 for(int i=3;i<8;i++)
  for(int j=0;j<4;j++)
   if(board[i][j]!=0&&board[i][j]==board[i-1][j+1]&&
   board[i][j]==board[i-2][j+2]&&board[i][j]==board[i-3][j+3])
    if(board[i][j]==1)
     return 100;
    else return -100;
 return 0;
}

As you see, the function just checks if there are 4 pieces in a row, column or diagonal, and if it is the computer's pieces, it returns +100, and if its the human's pieces it returns -100.



 
 
>>> 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: