Project 1 — Reversi
| Assigned | Monday, September 22nd |
|---|---|
| Program Due | Wednesday, October 1st by 11:59pm |
| Weight | 7% |
| Updates: |
|
Objectives
To gain experience:
- Designing, writing, and compiling a substantial C++ program
- Defining and calling functions
- Performing console input/output
- Working with arrays
- Working with both pass-by-value and pass-by-reference parameter-passing
- Documenting functions
Project Policy
This project is considered an OPEN project. Please review the open project policy before beginning your project. Note: even for OPEN projects, you are not allowed to ever share code!
Project Analysis
Time permitting, code from this project might be reviewed in class. If you would like your code to be used for this purpose, please contact your instructor. Your name will be held in strict confidence. This practice has worked extremely well in the past. It is a wonderful way to compare and contrast the different designs that people have used.
Reversi
We will be programming up a simple version of an old game called "Reversi". The rules of the traditional game, and the variant sold as "Othello", are available here. A quick description: two opponents play on a square grid, taking turns placing pieces of their respective color on empty squares on the board. The goal is to see who has the most pieces of their color when the board is filled. This seems like a dumb game, since it seems like both players will put down exactly half the pieces, except for one thing...
The game is called "Reversi" because of this rule: if you put a piece down on a square such that the new piece, and another of your pieces already on the board, bracket one more more of your opponent's pieces with no gaps, those pieces of your opponent's get turned into your pieces. (It was called "Reversi" because the pieces were actually all the same, with black on one side and white on the other, so each player just played the piece with their own color facing up, and capturing your opponent's pieces consisted of merely flipping, or "reversing" your opponent's pieces to your own color.)
Note that only pieces directly affected by your newly-placed piece are reversed: the reversing effect does not then chain outwards. In other words: if one of the reversed pieces happens to cause other pieces to be bracketed by your pieces, the reversing effect does not cascade and reverse those other pieces. (See the example below.)
The entire game will be texted based, with players taking turns entering moves. The two players will be represented by 'X' and 'O' (the letter "Oh", not the number "zero"), with 'X' always going first.
Your program should first get the size of the board from the
command-line arguments. Since the board is always square,
there will only be one argument used. Since command-line
arguments are always C-strings, you must use something like
atoi() to convert it into an int. There are
three restrictions on the size: it must be an even number
(that's the traditional board), and it must be at least 4
squares on a side, and should be less than or equal to 10
(these should be defined constants in your code).
You should check for these constraints, and exit
with an error message (sent to "cout") if the user violates
this rule.
We are making a simplification to the game's rules: there is no preset board layout. In other words, at the start of the game, players get to play anywhere on the empty board. (The usual game starts with four pieces in the middle before the first player takes a turn.)
On each turn, you will prompt with:
Player X's move:or:
Player O's move:You will then read row and column numbers from the user. the numbers will be 1-origin, with row 1, column 1 being the top-left corner. The row will always be specified first, and the two numbers will always be on the same input line,
Based on the user's move request, you will check several things:
- Is the move legal, i.e., on the board?
If not, you should print an error message, and then reprompt for a move (see e.g. below). - Is the space free?
If there is a piece already there, you should print an error message, and then reprompt for a move (see e.g. below). - Does the move cause any pieces to be reversed?
You must check for this and update the pieces. - Is the game over?
If every square is filled, you should print the results and exit the game (more detail below).
After each player's successful turn, you should print out the current state of the board, using 'X' or 'O' depending on who's piece is there, or '-' (a hyphen) if the square is empty. This includes printing out the final board one last time after the game-ending move, before printing out the summary. However, if the use gave an invalid move, you must not print the board: just reprompt for a move.
Other than the errors we specifically mention your having to handle above, we promise that we user will always give reasonable input. For example, while you must check that the board size is within bounds, you can trust that the command-line argument will always exist, and will be a string representing an integer. For the turns, the user will always give exactly two numbers on the same line separated by whitespace, but the numbers might be invalid, as described above.
For example:
% ./Proj1.out 2 The board must be an even size between 4 and 10. % ./Proj1.out 7 The board must be an even size between 4 and 10. % ./Proj1.out 4 Welcome to Reversi! Player X's move: -1 7 "-1 7" is not on the board! Player X's move: 2 3 ---- --X- ---- ---- Player O's move: 2 3 "2 3" has already been played! Player O's move: 2 4 ---- --XO ---- ---- Player X's move: 3 3 ---- --XO --X- ---- Player O's move: 4 3 ---- --XO --X- --O- Player X's move: 2 2 ---- -XXO --X- --O- Player O's move: 2 1 ---- OOOO --X- --O-Note that on the last move shown above, when 'O' played {2, 1}, it reversed the 'X's at {2,2} and {2,3} to 'O's. However, the new 'O' at {2,3} does not then cascade to reversing the 'X' at {3,3}, even though it is now between two 'O's.
Assume the players made the following subsequent moves:
X: 1,3
O: 1,4
X: 1,2
O: 1,1
X: 4,4
O: 4,2
X: 4,1
O: 3,4
X: 3,2
The end of the game should look like this:
Player O's move: 3 1 OOOO OOOO OOOO XXXX The game is over. Player X controls 4 squares. Player O controls 12 squares. Player O wins!
[ADDED:]
In the case where the two players control the same number of squares,
you should print out:
The game is over. Player X controls 8 squares. Player O controls 8 squares. The game is a tie!
We will be automating much of the grading for this project. Please note that your program must follow this format exactly to get any credit. Programs that do not use these symbols and spacing will receive a grade of zero.
How to Test Your Project
You should throughly test your program for all typical, edge, and error cases. The main example above does some of this. You should check every direction of flipping. The following examples test each of the 8 directions (they will work on any-sized board):- X flips to left of last piece, O flips to right:
{1,1} {3,3} {3,2} {1,2} {1,3} {3,1} - X flips upwards from last piece, O flips downwards:
{1,1} {3,3} {2,3} {2,1} {3,1} {1,3} - X flips to upper-left of last piece, O flips to lower-right:
{1,1} {4,3} {3,2} {2,2} {3,3} {2,1} - X flips to lower-left of last piece, O flips to upper-right :
{4,1} {1,3} {2,2} {3,2} {2,3} {3,1}
How to Start
For this project, you will be creating several source files:
Proj1.cpp, which contains your main() function, as well as
one or more other files containing the other functions you will be writing.
You should also create a makefile.
You should be adhering to all of the usual design goals that you were taught in prior courses, including writing small, well-modularized functions, using proper variables and function parameters, documenting all of your functions, etc..
The usual top-down design criteria should hold: you would probably want to start with main(), and lay out what the major blocks should be:
- Getting configuration parameters (here, the board size)
- Initializing the proper data structures.
- Running the main game logic
- Handling the end-of-game tasks
For the board and other such data structures, you are allowed to use fixed-size arrays dimensioned to the maximum board size (10 here). However, the usual advice about using named constants (e.g., MAX_GAME_SIZE) instead of magic numbers ("10") applies.
The most complex part will obviously be the game-playing logic. We would advising further decomposing this into a number of functions, at multiple levels. At the top, it should be structured as a main loop, alternating turns between the two players, testing for the termination condition. Each turn should consist of getting the move position from the user, testing it for validity, then placing the move. It is important to remember here that the user is inputting moves in a 1-origin coordinate system, while C++ arrays are all 0-origin, so you must remember to convert coordinates.
At the next lower level, the hardest task is propagating the reversals that a move may cause. Try to think about this in a modular fashion, also. A new piece might cause flips in any of (and possible more than one of) 8 directions: UP, DOWN, LEFT, RIGHT, UP_AND_LEFT, DOWN_AND_LEFT, UP_AND_RIGHT, and DOWN_AND_RIGHT. For each direction, you need to know how to compute coordinates for successive squares in that direction from where the new piece was played. For each successive position, you need to test if the next square is the opponent's piece, and if so, to keep scanning. The scan can end in one of only three ways:
- You hit an empty square;
In this case, you don't have to reverse anything. - You hit the edge of the board;
In this case, again, you don't have to reverse anything. - You hit a piece of your own color;
In this case, you reverse all the pieces in between.
Additional Requirements
One additional requirements it is mandatory that you create and use the following function (this is to ensure that you display your knowledge of passing arguments to functions by-reference):
void GetNextMove(char playerSymbol, int &row, int &col);
This function takes a symbol to use to print the personalized prompt for the two players (either 'X' or 'O'), and two by-reference parameters that are used to pass back the user's inputs. Note that this function does not do any error-checking on the input; that is the job of the caller.
Grading
See the course website for a description of how your project will be graded.
Project Submission
Before submitting your project, be sure to compile and test your code on the GL system. See the Project Compilation section of the course Projects page for details on how to compile and execute your project on GL.
Assuming you’ve used the specified file names, submit your project by typing the command
submit cs202 proj1 Proj1.cpp Proj1.h Proj1Aux.cpp Proj1Aux.h Makefile
See the Project Submission page for detailed instructions.
You may resubmit your files as often as you like, but only the last submittal will be graded and will be used to determine if your project is late. For more information, see the Projects page on the course web site.
Remember — if you make any change to your program, no matter how insignificant it may seem, you should recompile and retest your program before submitting it. Even the smallest typo can cause errors and a reduction in your grade.