For your second assignment, create a computer opponent that uses mini-max with alpha-beta pruning to play the Plus-Minus game with a human opponent. You will need to write a program for your task and implement it in some programming language (Lisp, C++, Pascal, Prolog, etc.). You may work with a partner, if you wish. However, each partner will need to submit a separate written report.
You may use the Lisp code on the CIS 479 web page as the basis of your mini-max algorithm, or the demonstration programs (Pascal or C++) on the CIS 479 web page. You will need to devise experiments to demonstrate that your algorithm with alpha-beta pruning does indeed output perform ordinary min-max.
In the Plus-Minus game, players take turns inserting a “+” or “-“ in a blank space between any pair of successive numbers. When all blank spaces are filled the expression is evaluated. If the resulting value is odd the human wins if not then the computer wins. Your program should be able to handle up to 6 or 8 digit numeric sequences.
Start: 1 2 3 4
Human: 1 + 2 3 4
AI: 1 + 2 - 3 4
Human: 1 + 2 - 3 - 4
Sum is not odd, so computer wins
You will need to turn in a well-commented program listing, sample runs (with neatly organized output), and a memo discussing your solution. In your memo, you should describe what makes your algorithm "smart" (ie. from what knowledge source does it derive its power). You need to turn in the output from your experiments showing that the alpha-beta cutoffs are occurring. You need to discuss the results of your experiments and determine the work saved by alpha-beta pruning. To help you determine how much work your algorithm is doing, you may wish to display some of your internal data structures during program execution.
Assigned: 5-14-08
Date due: 6-02-08