HomePractices 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!

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 it’s the human's pieces it returns -100.