Faculty of Applied Science and Engineering, University of Toronto
CSC181: Introduction to Computer Programming

Sample Design for Connect Four Program

Introduction

This document outlines a sample design for a Connect Four program. You are free to use this design however you wish. It is geared towards a C++ implementation, but it can easily be adapted to a C or Java implementation.

This design decomposes the Connect Four program into three modules:

• TextUI: The game's text-based user interface.
• Board: Represents the game board.
• Player: Represents a player (human or computer).

Users set up and play a game of Connect Four through the TextUI module, which takes care of registering players (creating a computer opponent if necessary) and initializing the game board. Once the game is started, the TextUI is responsible for maintaining the game board, carrying out the players' moves and notifying them when the game is over.

The base requirements are addressed here. Enhancements will be (partially) addressed in a separate document.

TextUI

Overview

A text interface for the Connect Four game. The interface takes care of setting up a board and registering the two players (Red and Black), asking the user whether they would like to play a human vs. human or human vs. computer game.

If the game is played between a human user and the computer, the interface should ask the user to pick one of two playing schemes for the computer:

• Random play: Under this scheme, the computer chooses moves at random. The user must specify a seed, which is used to generate the random moves.

• Minimax play: Under this scheme, the computer determines its moves using the minimax algortihm. The user must specify how many moves ahead the computer can think (thus supplying a cutoff depth for minimax).

Once the game is started, the TextUI carries out the players' moves (maintaining the board as appropriate) and notifies them when the game is over.

Methods

Board

Overview

The Board type represents Connect Four boards. Each instance of this type is initialized with two players (Red and Black) and an empty board, and can subsequently be used to record the placement of their pieces on the board.

Implementation

The board is implemented using a two-dimensional array of Player pointers. Assuming that this array is named board, then board[r][c] represents the square at row r, column c, and can take on one of three values:

• A pointer to the Red player, indicating that a red piece occupies that square.

• A pointer to the Black player, indicating that a black piece occupies that square.

• A null pointer, indicating that neither Red nor Black occupies that square.

The columns of the board take on indices from 0 (the leftmost column) to NUM_COLUMNS-1 (the rightmost column), where NUM_COLUMNS is seven for a conventional game. The rows of the Connect Four board take on indices from 0 (the bottommost row) to NUM_ROWS-1 (the topmost row), where NUM_ROWS is six for a conventional game. This indexing scheme can be visualized as follows:

 +-+-+-+-+-+-+-+
5| | | | | | | |
 +-+-+-+-+-+-+-+
4| | | | | | | |
 +-+-+-+-+-+-+-+
3| | | | | | | |
 +-+-+-+-+-+-+-+
2| | | | | | | |
 +-+-+-+-+-+-+-+
1| | | | | | | |
 +-+-+-+-+-+-+-+
0| | | | | | | |
 +-+-+-+-+-+-+-+
  0 1 2 3 4 5 6

In order to determine a winner, the board looks at each winning line, i.e. each row, column or diagonal of NUM_TO_CONNECT connected squares, where NUM_TO_CONNECT is four for a conventional game. If all of the squares in a winning line are occupied by Red's pieces, then Red has won; similarly, if all of the squares in a winning line are occupied by Black's pieces, then Black has won. Since the positions of these winning lines are known well in advance, a table containing all of the winning lines could be constructed at the beginning of the program's execution for faster lookup.

Related Constants

Constructors

Methods

Player (HumanPlayer, MinimaxPlayer, RandomPlayer)

The Player type represents a Connect Four player. There are three subtypes of Player:

• HumanPlayer, which represents a human player.
• MinimaxPlayer, which represents a computer player that uses the minimax algorithm to choose its moves.
• RandomPlayer, which represents a computer player that chooses its moves randomly.

All of these subtypes share a common interface, consisting of one virtual function, suggestMove, which asks the player what move they want to make.

MinimaxPlayer Implementation

As shown in class, minimax is essentially a search through a tree. The root node of this tree represents the current game state, and the rest of the nodes represent all the game states that are reachable from the current game state. It is not essential, however, that an actual tree data structure be used; we can rely on the properties of recursion to generate--and restore--game states.

HumanPlayer constructor

MinimaxPlayer constructor

RandomPlayer constructor

Methods

Last updated on 2000-11-25 by Ray Ortigas.