Faculty of Applied Science and Engineering, University of Toronto
CSC181: Introduction to Computer Programming
Due: Tuesday, 5 December by the start of lecture
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 implementing and testing a program with many modules, and documenting your implementation and testing.
Recall that for the previous assignment you designed a program for playing Connect Four, as well as a strategy for testing such a program. This assignment picks up where the previous assignment left off.
To recap, 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.
Implementation
For this assignment, you will implement 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).
Your implementation will be judged primarily on correctness. However, it is not sufficient for your program to just be correct; your correctness mark will depend largely on how well the marker can understand your documentation and testing. In other words: It is your job to convince the marker, through documentation and testing, that your program is correct. If you do not submit any documentation or testing, not only will you receive a zero for those items, but you also risk receiving a zero for correctness.
Documentation
In addition to the internal documentation you provide by commenting your code, you will also provide a report containing external documentation for your 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.
Document the following items, for each module:
The purpose of the module.
The data maintained by the module.
The functions of the module's public interface.
Testing
You will test your program and provide a report documenting the testing strategy and results. In doing this, you should:
Describe your testing strategy, and why it can adequately demonstrate that the program works as intended.
Outline, carry out and document the results of your test cases.
Document any bugs or missing features.
To facilitate the marker's understanding of your testing, split it into two parts: testing the program as a whole and testing the individual modules.
Style
Your code must conform to the style guide we provide you, which will be posted on the Web. If you follow every guideline, then you will receive full marks for style.
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 file, the name of which is specified by the user. The user should be able to load/save multiple games. You may design the format of the files however you wish; just make sure that it can be easily changed by a text editor, and that 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.
Correctness: 50%
Style: 10%
Documentation: 20%
Testing: 20%
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.
This assignment must be done in C, C++ or Java. It is your responsibility to ensure that your source files compile on ECF. You will submit a makefile which allows for automatic compilation of your source; instructions on how to create and edit makefiles will be posted on the Web.
Electronically submit your files to your Assignment 5 subdirectory under the CSC181 submit directory on the ECF server:
submitcsc181f 5 [filelist]
[filelist] is a space-separated list of the files you wish to
submit. Note that if you run this command again, it will overwrite your previous
submission.
You can check your submission using the following command:
submitcsc181f -l 5
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 the instructor. Do not seal the envelope.
Last updated on 2000-11-21 by Ray Ortigas.