CPSC 453, Spring 2003
Sixth Assignment
The sixth assignment for this course is to implement the MiniMax game-playing algorithm with alpha/beta pruning. You can base your work on the Connect4 game that can be found in the directory /home/cs453/qt_connect4. You should copy this directory into your own home directory. The directory contains a GUI program that lets the user play Connect4 against the computer. However, the version in the program named game does not implement MiniMax and plays a very bad, almost random game. (The program named game-smart uses MiniMax, but the source code that is provided is for game only.) You have the option of implementing MiniMax for the Connect4 game or of writing a new game that uses MiniMax. If you do Connect4, you must work alone. If you write a complete, new game, you can (but are not required to) work with a partner.
The program is due on Friday, March 28.
In order to implement MiniMax, you should write the mutually recursive functions minValue and maxValue that were discussed in class. You should improve the static evaluation function. You will also have to modify chooseComputerMove so that it calls minValue instead of the static evaluation function. All the work that you need to do will be in the file game.cc.
If you want to write a new game, you will have to modify the file game.h as well as game.cc. In game.h, you will have to change at least the definition of the Move class and the variables in the Game class that encode the data about the board. You will have to change the definitions of most of the functions definitions in Game.cc. (Also: The name of the game, displayed in the window's title bar, is set in the constructor for class MainWin in file mainwin.cc, and the size of the drawing area is determined by the command setMinimumSize(400,400) in the constructor for class View in the file view.cc.)
The program uses the QT GUI Toolkit, but you won't need to know too much about it, and what you need to know you can probably figure out by reading Game.cc. You don't need to look at the other files, which contain most of the GUI-specific code. If you want to know more about QT, you can find on-line documentation at http://math.hws.edu/local/qt_docs/. (This link is for on-campus access only.) If you need to draw a different game board, you might want to look at the documentation for the QPainter class to see what other drawing commands are available.
A "Makefile" is included in the qt_connect4 directory. When you make any changes and want to re-compile the program just use the make command. This command will consult the Makefile to determine which files need to be compiled and linked. The name of the compiled program will be game.
If you are writing a new game, it will have to be a full-knowledge, two-person board game with no random factors.
One good possibility is Mancala, an ancient African game with many variations and many names, including Mankala, Kalah, Wari, and Oware. I suggest that you do a Google search for "mancala game" and find a set of rules that you like.
Othello, also known as Reversi is another possibility. The programming for this game is more difficult -- making a move or checking to see whether a move is legal is fairly complicated. Another choice could be Go-Moko, which is similar to tic-tac-toe, but played on a 9-by-9 (or larger) board, with the goal of getting 5 pieces in a row. If you are interested in doing either of these games, you should discuss it with me first.