Programming Assignment
Purpose: This assignment will give experience in the implementation of a tree data structure. It will also review recursion and introduce some simplistic AI concepts as they apply to two-player, zero-sum games.
Description: You will build an "intelligent" game program that will allow a user to play against the computer, insuring that the computer always makes a "good" move. You have a choice to either implement the game Othello or Critical Mass (to be described in class). The intelligence of your choices for the computer's moves will be implemented via a game tree, a generalized tree that represents options for some number of successive moves of the computer and the other player. The game tree is generated based upon the current state of the game board and then evaluated to determine which next move should be made. In the event that more than one move would have the same "value", a random choice of move should be made. Once the next move is determined, the move should be enacted according to the rules of the game and the play pass to the user.
This assignment will require a lot of planning because of its various aspects. There is the need to represent the game board in its current state to the user. There is the need to implement the mechanics of a move based upon the rules of the game. The game tree must be built, with each node in the game tree holding a different configuration of the game board based upon a specific choice that could be made. Finally, there must be a way to determine the "value" of a particular configuration so that a choice between board options can be made in an advantageous way.
There are several things you will want to understand prior to tackling your program:
• Of course, the rules of the game you choose to implement
• How to build a game tree
• Evaluation of a game tree using the minimax algorithm
The game trees for both Othello and Critical Mass in their entirety are huge - too huge to build and evaluate because of time constraints. Consequently, you should build a game tree of height no more than 4 (unless you want to do some additional research into optimizing evaluation approaches - but this would be very time consuming so I would discourage it).