1 Playing board games on a computer is very common. We can use abstraction to aide in the design of a board game by separating the game logic from the actual user interaction required to play the game. No matter the type of user interface provided to play the game (i.e., text based, desktop windowing en- vironment, or web browser), the underlying logic remains the same. Consider the game of Reversi, which was invented in 1893 but has a more modern set of rules dating back to the 1970s. Reversi is played by two players on a game board divided into 64 squares arranged in 8 rows and 8 columns and a set of 64 chips. Each chip is painted a dark color on one side and a light color on the other, with each color belonging to one of the two players. The players place their chips on the board and ip the chips of their opponent with the goal of having the most chips of their color on the board at the end of the game. The game starts with a con_guration as shown in part (a) of Figure 2.16.
The players take turns placing chips on the board with their color facing up. A chip can only be played in a square that is adjacent to a chip of the other player and that forms a straight line of attack (vertical, horizontal, or diagonal). A line of attack is formed between two squares containing the player's own chips in which there is one or more of the opponent's chips in between the two. For example, if player 1 (black) goes _rst, he has four options as shown in part
(b). Suppose player 1 places a chip in the square marked with an x. After placing his chip, player 1 ips all of the chips of player 2 (white) that are in the line of attack. In this case, he ips the chip immediately below the new chip as shown in part (c). Player 2 then places one of her chips. She has three options from which to choose as shown by the dark squares in part (c). If player 2 places her chip in the square marked x, she ips the black chip below the new chip as shown in part (d). If there are multiple lines of attack that result from the placement of a chip, then all of the opponent's chips that are in all of the lines of attack are ipped. For example, suppose player 1 places a chip in the square marked with an x as shown in part (d). Then he ips both white chips, the one to the left and the one diagonally down to the left as shown in part (e). Play alternates between the players until all of the squares are _lled or neither player can move. If one player cannot move but the other can, play proceeds with the other player. The winner is the player with the most chips at the end of the game. Given the following description of the operations, provide a complete implementation for the Reversi Game Logic ADT.
_ ReversiGameLogic(): Creates a new instance of the Reversi game logic with the initial con_guration.
_ whoseTurn(): Returns the player number (1 or 2) for the current player or 0 if no player can move.
_ numChips( player ): Returns the number of chips on the board belonging to the indicated player. The value of player must be 1 or 2.
_ numOpenSquares(): Returns the number of squares still open and avail- able for play.
_ getWinner(): Returns the player number (1 or 2) for the player who has won the game or 0 if the game is not _nished.
_ isLegalMove( row, col ): Returns True or False to indicate if the cur- rent player can place their chip in the square at position (row, col).
_ occupiedBy( row, col ): Which player has a chip in the given square? Returns the player number (1 or 2) or 0 if the square is empty.
_ makeMove( row, col ): The current player places one of his chips in the square at position (row, col). All chips on the board that should be ipped based on the rules of Reversi are ipped.