For your second assignment, create a
computer opponent that uses mini-max with alpha-beta pruning to play the Date
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 Date game, players take turns
increasing either the month or the day, but not both. At any time, the evolving
date is required to be a valid date. The player to reach December 31 wins the
game. Here is first few moves of a game:
Start: Jan 06
Human: Jan 07
AI: Jan 20
Human: Feb 20
AI: Feb 21
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 discuss the results of your experiments to 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-16-07
Date due: 6-04-07