By adding the depth parameter to our function, we’ve prevented it from spending days trying to reach the end of the tree. But we still have a problem: our evaluation function doesn’t know what to do if we’re not at a leaf. Right now, we’re returning positive infinity if Player 1 has won, negative infinity if Player 2 has won, and 0 otherwise. Unfortunately, since we’re not making it to the leaves of the board, neither player has won and we’re always returning 0. We need to rewrite our evaluation function.
Writing an evaluation function takes knowledge about the game you’re playing. It is the part of the code where a programmer can infuse their creativity into their AI. If you’re playing Chess, your evaluation function could count the difference between the number of pieces each player owns. For example, if white had 15 pieces, and black had 10 pieces, the evaluation function would return 5. This evaluation function would make an AI that prioritizes capturing pieces above all else.
You could go even further — some pieces might be more valuable than others. Your evaluation function could keep track of the value of each piece to see who is ahead. This evaluation function would create an AI that might really try to protect their queen. You could even start finding more abstract ways to value a game state. Maybe the position of each piece on a Chess board tells you something about who is winning.
It’s up to you to define what you value in a game. These evaluation functions could be incredibly complex. If the maximizing player is winning (by your definition of what it means to be winning), then the evaluation function should return something greater than 0. If the minimizing player is winning, then the evaluation function should return something less than 0.
Instructions
Let’s rewrite our evaluation function for Connect Four. We’ll be editing the part of the evaluation function under the else statement. We need to define how to evaluate a board when nobody has won.
Let’s write a slightly silly evaluation function that prioritizes having the top piece of a column. If the board looks like the image below, we want our evaluation function to return 2 since the maximizing player ("X") has two more “top pieces” than "O".
For now, inside the else statement, delete the current return statement. Create two variables named num_top_x and num_top_o and start them both at 0. Return num_top_x - num_top_o.
Before this new return statement, loop through every column in board. Inside that loop, loop through every square in column. You’re now looking at every square in every column going from top to bottom.
If square equals "X" add one to num_top_x and then break the inner for loop to go to the next column.
If square equals "O" add one to num_top_o and then break the inner for loop to go to the next column.
We’ve imported three boards for you to test this function. We should first get an understanding of what these three boards look like.
Note that these boards aren’t game states you’d find in real games of Connect Four — "X" has been taking some extra turns. Nevertheless, we can still evaluate them!
Call print_board once per board — board_one, board_two, and board_three. What should the evaluation function return for those three boards?
Call evaluate_board once on each board and print the results. Did we trick you with board_three?