Introduction to Artificial Intelligence

Assignment 2


Programming assignment - games

In this assignment, you will write a program that plays the game of Hex, in order to attempt optimal or near-optimal play.

The rules of the game

You will be implementing agents for two variants of the game:

  1. The standard game: as in assignment 1, rules are in the Hexy web page.
  2. In addition, we will also use a variant where after each move (by either player), a tile of random color is deposited at random next to the last played tile, if there is such an empty space.

What to implement

You need to implement two agents, one that works with the standard Hex game, using game-tree search with alpha-beta pruning and A-B pruning, and another that uses search on the expecti-minimax tree of the modified game, and also performs both alpha-beta and A-B pruning, when appropriate. In addition, you should have the code allowing the user to be an agent (from the previous exercise), and for making the agent pay against a copy of itself.

For each agent, a useful static heuristic evaluation function should be implemented and used in the search (although this may be the same function for both games, if appropriate, which you must justify).

Deliverables

Electronic submission of source code and executables. A non-trivial example of the search capabilities of your program, and an explanation of the heuristics. Frontal grading and checking of the program(s).

Deadline: April 3, 2003.