CSE 473 Introduction to Artificial Intelligence

Autumn 2001

Problem Set 3

Due October 29^th 2001

Modify your solution to problem set 2 to convert your Tic-Tac-Toe player into an Othello (Reversi) playing agent. This is a mini-project of sorts and you should work in groups of two.

1. Design a simple interface that will allow a user to play against your agent.

2. In order to modify your Tic-Tac-Toe program you will need to come up with

a. A state representation for the board positions.

b. A valid move generator.

c. An evaluation function for board positions.

3. Appropriate restrictions must be placed on either the search time or the look-ahead depth for each move so that only a reasonable time is spent between moves.

Here are some pointers to resources on Othello/Reversi.

1. http://www.vogclub.com/rules.phtml?sid=5&gtype=1 - rules of the game.
2. http://home.swipnet.se/~w-50714/othello/tutorial/intro.htm - basic strategies.
3. http://www.mathjmendl.org/reversi.html - more strategies and links
4. http://www.nada.kth.se/~gunnar/othello.html - detailed strategies.
5. Numerous Othello/Reversi online game sites, e.g. VOG, yahoo, …

For this project, the turn-in should include –

1. The source code – soft copy (according to instructions to be posted later).
2. Documentation that has compilation and user instructions.
3. A brief write-up that describes the overall design, and in particular the choice (with reasons) for the board representation, move generation, evaluation function, game-tree search strategy, etc.
4. In addition an analysis of intelligent search strategies employed (if any), other than those discussed in class, and their benefits, etc. will be for extra credit (5-10 points).

Tips

o Concentrate more on the evaluation function rather than the UI. The evaluation function is the key to an Othello game playing agent.

o Try out your strategy against other Othello agents on the web or otherwise.

Printable copy (ps) (pdf)

Earlier Assignments