For your second assignment,creat a computer opponent that uses mini-max with alpha-beta pruning to play the Pathway 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.
The Pathways game is played on grid like the one shown below. Players take turns writing their initials in the empty squares. The first player to get a string of initials that cross completely from one side of the girds to the other wins. Initials must be horizontally or vertically next two one another. Diagonals initials are not part of the same string. You don’t need to worry about fancy graphical output.
|
|
W |
|
W |
|
|
M |
|
M |
|
M |
|
|
W |
|
W |
|
|
M |
|
M |
|
M |
|
|
W |
|
W |
|
Start state
|
M |
W |
M |
W |
W |
|
M |
W |
M |
M |
M |
|
W |
W |
W |
W |
M |
|
M |
M |
M |
W |
M |
|
|
W |
|
W |
W |
Win for W
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 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-18-05
Date due: 6-06-05