In this assignment, you will write a program that plays the game of Hex, in order to attempt optimal or near-optimal play.
You will be implementing agents for two variants of the game:
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).
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.