For your second
assignment, create a computer opponent that uses mini-max with alpha-beta
pruning to play the Fif 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.
You may use the Lisp
code on the CIS 479 web page, the sample programs from the Turbo Pascal
Gameworks toolbox
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 Fif players take
turns selecting numbered squares. Players mark their moves by writing their
initials in the empty squares. The first player that can form a triplet (exactly
3) of numbers that sums to fifteen wins. A player cannot win with fewer than
three squares chosen and can use more than three squares to win. This example
shows a win for B.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
A |
B |
B |
A |
A |
B |
B |
A |
|
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) and also discuss the results of your experiments to
determine the work saved by alpha-beta prunig. 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-17-06
Date due: 6-05-06