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