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