Introduction

The objective of this assignment is to let you practice the use of 2- D arrays (and optionally pointers)

in C++. You are to write a program to simulate a classic board game known asReversi(a.k.a. Othello).

Reversi is a two-player game which is played on a square uncheckered board with some game pieces. A piece is a disc with two sides in black and white colors respectively. At the beginning of a game, there are four pieces placed on the board as shown in Figure 1. We use a dot '.' to denote an empty cell in the board, the character 'X' to denote a black piece, and the character 'O' to denote a white piece. To denote a position in a game board, we use a coordinate system similar to a spreadsheet program, e.g. "A2" refers to the cell in the first column and the second row. Suppose that a C++ array arr is used to represent the game board, cell address "A2" will be mapped to arr[1][0].

A     B     C     D      E      F     G     H

Figure 1: Initial configuration of the game board

The two players, namely "Black" and "White" make moves in turns by putting a disc of their color on an empty cell of the board. Black plays the first move. A move cannot be made arbitrarily to any of the empty cells. As a valid move, the newly placed disc must be in a position such that it forms at least one straight (horizontal, vertical, or diagonal) occupied line between the new piece and another piece of the same color, with one or more contiguous pieces of the opposite color between them. After the move, those contiguous pieces will all be flipped to become the color of the new piece. Figure 2shows an example move made by White. Note that a move can simultaneously form more than one straight line. In such a case, the sandwiched pieces on all the lines formed will be flipped.

Figure 3shows such an example.

Figure 2: An example move by White ('O') at position D7, forming a vertical occupied line from D7 to D2. Four

black ('X') pieces are “clipped” by two white pieces at both ends and are flipped.

Figure 3: An example move by Black at F5, forming three occupied lines (i) F5 to F3, (ii) F5 to D5, and (iii) F5 to

D3. All sandwiched pieces of white are flipped to black.

A game is over when either the board is full or both players have no valid moves. The player having more  pieces of  his/her  color than the opponent wins the game.  If  both  players  have the same number of pieces, the game draws.

To add more challenges to the game, this assignment will extend the original Reversi game with an additional feature: some “blocks” can be added to the game board, preoccupying some cells so that both players cannot place a disc onto such positions. Blocks are added before the game begins. For example, Figure 4 shows a board with cells A1, A2, B1, B2, G5, G6, G7 and F7 initialized as blocks. Let’s call them “block cells” . Then players cannot make a move to such positions. Apart from fewer choices for making a move and greater likelihood that the players run out of valid moves before the board becomes full, the overall rules of the game stay the same as in the case without block cells.

7

8

Figure 4: Initial configuration of the game

A     B     C     D      E      F     G     H

board with blocks (grey areas) added

Program Specification

Game board

You must use a two-dimensional array of char type to represent the game board. For example, you may define the following in your main() function:

char board[N][N];

Note that defining the board array as a global variable is forbidden and will invite mark deduction if you do so. You should also avoid declaring it in a hard coded manner like char board[8][8];

Make sure your program can support array sizes other than 8. We demand that the array size should be defined as a global constant in a header file to make it easily scalable.

const int N = 8;         // board size

When grading, we may change N to a different value (basically between 4 and 12) for more thorough testing of your code. Please follow the above constant definition exactly, i.e., declaring a constant of int type and naming it with a single capital letter 'N' to facilitate our marking process.

Game Flow

•    The  program  needs to set  up the game  board first.  Before  a game  begins, the  program will prompt the user to enter the number of block cells to add to the board. It can be zero or up to half of the board’s area at most. For example, if N (board size) = 8, the  maximum number of block cells allowed would be (8 * 8) / 2 = 32. This ensures that the board still has enough empty cells for making moves. It is illegal to set any of the initial four pieces central in the board as a block. Entering a cell address that refers to a block already defined or a cell out of the board’s size range is illegal too. If the user enters an exceedingly value for N or any illegal cell addresses, the program repeats prompting until valid inputs are received.

•    Then the game starts with round 1 on the board initialized with the first four discs as shown in Figure 1and optionally with block cells. Black moves first.

•    Black and White make moves alternately. For each move, the program should prompt the player to enter the cell address of the intended move, e.g. "D3", and it will convert the characters into two integer values (x, y) that represent the column and row indexes, respectively, to access the corresponding element of the array board[y][x].

•    You should check whether a player’s input refers to a valid move. If the input position is not valid (either because the input coordinate is out of bounds of the board or because the input position cannot flip any opponent’s pieces), the player should be prompted again for a valid move.

o  In fact, it can happen that the board with empty cells has really run out of positions for a player to make a valid move. Thus, your program needs to check whether there still exists at  least  one  empty  cell  that  allows  the  current  player  to  make  a  valid  move  before prompting  him/her for  entering  a  cell  address. This  involves  scanning the  whole  game board for any cells for a valid move per round before prompting .

o  In case of no possible valid moves, the player’s round will be “passed” to the opponent.

•    If a valid move is made, all relevant pieces should be flipped to the opposite color.

•    The game should end when either (1) the board is full, or (2) two consecutive passes are made (i.e. Black passes to White but White immediately passes back to Black since both of them have no valid moves to make). If Black wins, the message “Player X wins!” should be printed; if White wins, the message “Player O wins!” gets printed; and if the game is a draw, “Draw game!” should be printed.

•    Your program should be reasonably decomposed into different functions for various tasks such as printing the game board, initializing the board, adding blocks, checking if a move is valid, and updating the board to realize a move, etc. The game board array and other data like the input coordinate values can be passed between the functions.

Provided and Required Functions (reversi.cpp and reversi.h)

Your  program  must  contain  the  following  functions. Some of them are written for you already (Provided) and you shall not modify their contents. The others will be written by you (Required). These functions shall be implemented in a source file reversi.cpp with the function prototypes in a header file reversi.h. These functions shall be called somewhere in your program. You must not modify the prototypes of all these functions. You can design extra functions if you find necessary.

Besides, all the required functions below will be graded individually. That is, we shall connect your reversi.cpp with another source file with our testing code to call the functions one by one for grading. So your code for each function shall implement the description of that function only. You shall not write any code in a function that is beyond that function’s description.

(Provided) void print_board(char board[][N]);

Print the game board to the screen using the format in Figure 1.

(Provided) bool cin_failed();

Return true if console input fails (e.g., the user enters alphabets while an integer is expected.) or false otherwise. This function bypasses any weird input by skipping to the next newline and clearing the  error flag  on  the  cin  object.  Upon  receiving true, the  caller  of this function  may  execute  a continue statement, say, to skip to the next iteration