Faculty of Applied Science and Engineering, University of Toronto
CSC181: Introduction to Computer Programming
Due: Monday, 20 November by the start of tutorial
Announcements are available on the course Web site. It is your responsibility to keep up-to-date on these announcements.
The purpose of this assignment is to give you practice doing the following things:
This assignment will also prepare you for the next assignment, for which you will implement your design and test your implementation.
The game of Connect Four is played between two players, Red and Black, who each have a set of playing pieces they can place on a grid with 7 columns and 6 rows of squares. It is governed by the following rules:
Red and Black alternate moves (with Red starting) until one of them has won, or there are no more legal moves.
To move, a player chooses a column and drops one of their pieces in it; the piece drops to the lowest available row, above all other pieces already dropped in that column. Each square on the grid can hold only one piece, and no more pieces can be placed in a column if it is completely filled.
Over the next two assignments, you will design, implement and test a program for playing Connect Four, and in doing so, address:
A set of base requirements in order to qualify for a percentage (lower than 100%) of the available marks.
A combination of additional enhancements in order to qualify for more marks (the sum of which may create the possibility of a bonus).
For A4, in particular, you will write a report documenting your design and testing strategy for your Connect Four program. In doing this, you should:
Identify the program's modules, and briefly describe what they do.
Give an overview of the program by briefly describing how the modules interact.
Explain why you chose to break down the program into these modules.
Document the following items, for each module:
The important functions of the module's (public) interface.
The higher-level details of the module's implementation (e.g. the structures used to hold data, potential algorithms to be used, etc.), and the rationale for using said implementation.
The testing strategy you will carry out on the module (consisting of an overview and a table of test cases and expected results).
The base requirements, additional enhancements and marking scheme are described below.
The following base requirements qualify you for a percentage of the available marks:
The program should allow a legal game of Connect Four to be played according to the rules above. It should permit human vs. human and human vs. computer games, using some sort of text-based interface.
If the game is played between a human user and the computer, the computer should make moves using one of two strategies (which is specified by the user before the game is started):
Choose a move according to some pseudorandom sequence, which is determined by a specified seed.
Choose a move using the minimax algorithm, which searches the game tree up to a specified depth (the cutoff). Refer to the supplementary reading for the minimax pseudo-code.
You may address any combination of the following enhancements, each to qualify for a fixed percentage of additional marks:
Loading and saving of games: The user should be able to load a game state from and save a game state to a human-readable text file. You may design the format of the files however you wish. (Just make sure you can load the games you save!)
Undo/redo of moves: The user should be able to undo an unlimited number of moves (conceivably, all the way back to the initial game state). If the user undoes a move accidentally, they should be able to redo the move.
Minimax with game state caching: During the course of a minimax search, finding the successor of a game state may produce a board that was previously encountered, and therefore, a game state for which a score was calculated. If a record were kept of the game state and its score, then there would be no need to proceed further; the recorded score can just be used.
Minimax with alpha-beta pruning: This is another optimization of the minimax algorithm. Refer to the supplementary reading for the alpha-beta pruning pseudo-code.
If you think of an additional enhancement you would like to pursue, please e-mail rayo@dgp.toronto.edu to obtain the instructor's approval.
Content will count for 75% of the mark, with the remaining 25% allocated to style, grammar and spelling.
You should aim for as readable a document as possible; the more readable your document is, the better the marker can understand the content. To achieve this:
In short, use writing and formatting techniques to enhance readability.
You may do this assignment alone or in pairs, and will be evaluated accordingly:
If you do the assignment alone:
Addressing the base requirements qualifies you for 90% of the available marks.
For each enhancement you address, you qualify for an additional 10%.
If you do the assignment in pairs:
Addressing the base requirements qualifies you for 80% of the available marks.
For each enhancement you address, you qualify for an additional 10%.
In any case, clearly identify which requirements and enhancements you are addressing.
Above all, keep it simple.
Bind your report with a staple, place it in a 9" x 12" envelope with a completed assignment cover sheet (a blank one will be posted on the Web) taped to the front of the envelope, and give it to your tutorial leader. Do not seal the envelope.
For A5, you will implement and test the modules you designed in A4. More details to follow.
Last updated on 2000-11-07 by Ray Ortigas.