Homework Assignment #3
1. (40 points) For this assignment I would like you to implement a computer
program to play Othello. I am giving you C code that implements a human vs.
human version of the game. I would like you to enhance the code (in C, or
you can port the game to C++ or Java) to allow a human to play a computer agent
or a computer agent to play against a computer agent. The computer agent will
use minimax to evaluate and select from possible moves. I would like you to
implement three options for the computer agent. These options can be selected
interactively, as command-line parameters, or as constants in the program (the
choice is up to you). The options are:
Option 1: alpha-beta pruning
The agent should have the choice of using alpha-beta pruning
to speed up the search.
Option 2: simple or complex SBE
The simple SBE calculates the difference between the
number of player 1's pieces and the number of player 2's pieces.
The complex SBE calculates the weighted difference, where
strategic locations (e.g., sides, corners) are weighted more
heavily than less-important locations.
Option 3: choice of ply values
Please turn in your source code, a sample run, and a short document.
The document should describe how to compile and run the program. It should
also show the results (in search time or search size space as well as value
of the final board) of the computer agent with and without alpha-beta pruning,
with the simple and complex SBE, and with at least two different ply values.
In each case you can compare the results to the simple agent (no alpha-beta
pruning, simple SBE, ply=3). Your program should run on one of the department
Linux machines.
2. (10 points) Consider the following database of facts and rules.
All people that are not sick and are smart are happy.
People that read are smart. Happy people have exciting
lives. Healthy people are not sick.
John is a person. John is healthy. Helen is a person.
Helen reads and is healthy.
1) Convert the statements given in the paragraph above into a
set of First Order Logic sentences.
For your sentences use the predicates person(x), sick(x), smart(x),
happy(x), read(x), exciting(x), and healthy(x).
2) Discuss whether exciting(John) or exciting(Helen) are entailed by
the database, and why or why not.
3. (5 points) Apply minimax to show which move Player 1 (MAX) will select for
the game tree below. Show which branches, if any, that would be cut off during
an alpha-beta search for the tree. Also show the backed-up minimax values
and indicate which move the player should make.
_____________________*__________________ MAX
/ / \ \
/ / \ \
/ / | \
/ / | \
/ / | \
/ / | \
| | | |
* * * ___*___ MIN
/|\ /|\ /|\ / /|\ \
/ | \ / | \ / | \ / / | \ \
| | \ | | \ / | \ / / | \ \
| | \ | | \ / | \ / / | \ \
| | \ | | \ / | \ / / | | \
| | | | | | | | | / | | | \
* * * * * * * * * * * * * * MAX
/ | /|\ /|\ | /|\ /|\ |\ /|\ / \ /|\ | /|\ /\ /\
| | | | | | | | | | | | / | | | | | | | | | | | | | / | | | | | |
| | | | | | | | | | | | / | | | | | | | | | | | | | / | | | | | |
4 21 6 3 2 8 9 4 3 8 5 3 13 1 5 7 7 4 5 3 19 27 3 2 1 50 99 4 5 3 8 11 3