# ICS 171: Homework #8

1. (100). Create a heuristic and all other functions necessary to allow the computer to play connect four against you. You will use the board manipulation and functions developed in HW 6. One possible heuristic is to

• 1. For each player, give points for every possible line of length 4
• 1. If the opposing player has any pieces in the line, 0 points
• 2. If there are all blanks in the line, 0 points
• 3. If there is one of this player's piece, and 3 blanks, 1 point
• 4. If there are two of this player's piece, and 2 blanks, 2 points
• 5. If there are 3 of this player's piece, and 1 blank, 4 points
• 6. If there are 4 of this player's piece, 1000 points
• 2. Subtract the score of the opponent from that of the player.

The code for alpha-beta Minimax search is in minimax.lisp. Use a depth limit of 4 for your search. That is, stop searching when the depth is greater than or equal to 4.

Suggestions: Debug your code with a depth limit of 1 or 2 first.

If you implement connect four like I did at first, you found all legal moves by doing something like (loop for i from 0 to 6 do <make-move i>). Alpha-beta works better if you try the moves in a different order, such that the better moves are tried first. In connect four, you are more likely to win if your moves are close to the center of the board. Have your move generator to generate better moves first, and to make the worse moves last.

Extra credit: Try some other game, such as 3 dimensional Tic Tac Toe or Othello. Choose another game if I approve, but avoid chess, checkers, and go.

Back to http://www.ics.uci.edu/~pazzani/171-p.html (text only) or http://www.ics.uci.edu/~pazzani/171.html .

Michael Pazzani
Department of Information and Computer Science,
University of California, Irvine
Irvine, CA 92717-3425
pazzani@ics.uci.edu