Data Structures - Chapter 14 - Programming Assignment Ideas
Games for the Game Class

Data Structures and Other Objects Using C++
Second Edition
by Michael Main and Walter Savitch
ISBN 0-201-70297-5, Softcover, 816 pages

---

The Game Class

Section 14.3 of the textbook provides an abstract base class called game. The game class provides a framework for two-player games such to be implemented as derived classes. Within the framework, the human user will be one player in the game and the computer will be the other player (using a game strategy called minimax with alpha-beta pruning. The textbook describes the game class in detail and also provides a derived class to play Connect4. Here are the relevant files:

• Our game header file, game.h
• Our game class implementation file, game.cxx
• Header file for the derived connect4 class
• Implementation file for the derived connect4 classe
• Short program that uses the connect4 class

Writing Other Derived Classes

There are many other derived classes that you might write for two-player games. Here are some hints on selecting games that may work well as a derived class:

1. The game should have two players whose positions are symmetric. This means that generating the list of possible moves for one player is no different than generating the list of possible moves for the other player. In general, the games that are easiest to implement are the games where it is relatively easy to write a function that can generate the list of possible next moves for a player. For example, generating such a list is much easier for Connect4 than for chess, so that implementing a derived chess class will take more work than implementing the derived connect4 class.
2. All information about the current state of the game should be available to both players. This eliminates many card games (where you can see your own cards, but not your opponent's cards).
3. The game should not involve randomness such as dice or selecting a card from a pile of shuffled cards. Such games can fit into a modified version of the minimax strategy, but our implementation of the base game class does not allow randomness.
4. When you are writing the evaluate function for your derived class, you should concentrate on having a quick evaluation function rather than a complicated function that attempts to anticipate the consequences of subsequent moves. The anticiaption of subsequent moves is already built into the minimax strategy of the base game class, and the evaluation function that you write for the derived class is never used until the base class has already traversed several layers down the tree of possible moves.

Some Possible Games

If you come up with a good game that can be written using the base game class, I would like to hear about it. So far, I have implemented:

• Connect 4 (implementation given by the links above).
• Othello (described in the textbook).
• Tic-Tac-Twice (invented by Andrzej Ehrenfeucht and Pat Baggett). (See www.cs.colorado.edu/~main/projects/tictactwice.html.)

---