Game boards: Checkers

Submission time: Sunday, December 15th, by Ross closing time.

Aims:

Practice programming in C++: inheritance, referneces, operator overloading, and other features. Practice OOD.

Level:

Medium+ (As the 1st c++ exercise, we did most of the design for you. Once you understand this design, the implementation is simple.)

Description:

1. General:
In this exercise you will implement a generic board-game software, and implement a Checkers (a.k.a Damka) game over it. You will write a program that performs a Checkers game among 2 players on a n*m board. We give you some classes' interfaces you must use (some of them are abstract). Do not change any of the header files we provide you, unless specified otherwise.

2. The classes' header-files we provide you:
game.h:
This class represents a game played on a rectangular board. The game holds the board-game with the game-pieces on it and the rules of the game. The board can perform moves of the game-pieces, print the board etc.

board.h:
This class represents a board of a board-game. It can move/add/remove game-pieces in it. It holds the game pieces that are currently in the game. 

gameRules.h:
This abstract class encapsulates the rules of the game. It can initialize the board, determine the winner or the termination of the game, and decide who is the next team to play.
You will have to implement a subclass of the GameRules class, called CheckersRules (inside the file "checkersRules.cpp") , which will encapsulate the rules of checkers (see below). When using checkersFactory, you must still use the interface described in gameRules.h.

gamePiece.h:
This abstract class represents a game-piece in a game-board (for example, a knight in chess). Each game piece holds the type of the piece (e.g. "knight") and the team it belongs to (e.g. "White"). Each Game piece can tell if it can perform a certain move and tell what would be the changes on the board if the move was performed (performMove method).  Note that we might have in one game pieces from different games (e.g. Chess players vs. Checkers players).

checkersFactory.h:
This class is a factory for Checkers pieces. It can create pawns and queens by demand. The CheckersRules class that you will write should use this class for inserting the pieces to the game board.

changes.h:
In this file we describe a container class for the changes to be done on the board.
Note: you CAN add things to this header file (see instruction within), as long as you do not add/remove public data members (methods or variables) or friend functions/classes.

Note that the classes (except CheckersFactory) are generic, not Checkers-specific. To create a new game (e.g. chess), one should define the relevant sub-class for the GameRules class, and also define the game-pieces in the game.

See more details inside the header-files.

3. The checkers program:
The program (called "ex3") you should write, gets the board's size as argument (see format below), initializes a checkers board (see below), and then asks the players (types names must be "B" and "W" for black and white, respectively) for moves, and performs the moves. After the initialization, and after each move, the program prints the board to the standard output (see decription on the operator<< of the Board class). The program should use the interface described in game.h.

The usage of the program is as follows:
ex3 <width> <height>
For the Checkers game, both width and height must be at least 8 (print error message to the standard error otherwise).
For example, "ex3 8 10" will create a board of width 8 and height 10.

In Checkers, there are two kinds of game-pieces: a "Pawn" and a "Queen".
When printing your board to the standatd output (see operator << of Board class), the teams' types (i.e. the players) must be "W" and "B" for white and black. The pieces' types must be "P" and "Q" for pawn and queen, respectively.

Initialization: The first 3 rows  in a board will be initialized with the white player's pawns, on all entries with an even sum of indices (e.g. (0,0),(0,2) etc.). The last 3 rows are for the black player, again put pawns in squares with even sum of indices. The size of a row is the width of the board.

In each time you should ask the relevant player for a move: "B turn:\n" or "W turn:\n". (Exact format, no extra spaces or newlines.)
The user can move with the following format:
move (fromX,fromY) (toX,toY) \n
For example, if the user wants to move the piece in position (4,5) to position (8,8) she will write:
"move (4,5) (8,8)\n". The words can be separated with any number of spaces, according to the isspace function, but only one newline in the end of the command. If the player cannot perform this move, write "Illegal move\n" and ask him again to perform a move in the same way.

Termination: Upon termination the program should output the winner team to the standard output, and exit normally.
Format: <winner-team> wins
For example, "W wins\n". Do not write any more spaces in the output. In case of a possible tie, the output should be "Nobody wins\n". In situations when no player can move, it is considered a tie.

More commands: when any player writes the command "quit", the program should stop the game and exit normally.
When any player writes "new", the program should stop the game, and start new game from the beginning.
For both "quit" and "new" options, do NOT write anything to the stdout (except printing the board of the new game, of course).

4. Checkers rules (simplified):

1. Basic moves: A pawn can move only one square diagonally, towards the opponent (whites move up-rows, blacks move down-rows). (a player must move when he can. E.g, moving from a position to the same position is illegal.)
2. "Capture" opponent's pieces by pawns:
   if a square diagonally adjacent to a pawn is occupied by an opponent's piece (pawn or queen), and if the square beyond that piece in the same direction is empty, the pawn can "jump" over the opponent, and land on the empty square. The opponent's piece is "captured" and removed from the board. Note that a pawn can capture an opponent piece in any direction. 
3. Multiple captures: After capturing a rival piece (see previoes rule), the pawn can similarly go on eating as much as it can, on any direction. Note that even for the case of multiple captures, the user only sends 2 positions on board ("from" and "to") and the program performs the changes on the board by itself.
4. Becoming a queen: A pawn that reaches the last opposite row (i.e. the first row for the black player, the last for the white player) turns into a "queen". If during a multiple capture, the pawn steps on the last row (for him) and ends up in another row, this pawn will not turn into a queen (this is a simplification).
5. Queens: A queen can move in any diagonal direction, for any distance, as the limits of the board permits. The queen can jump over (i.e. capture) few (non-consecutive) opponent pieces at one move, but eventually it has to land in an empty space adjacent to the last opponent it captures (on the same direction). A queen cannot jump over pieces from its own team, nor jump over 2 or more consecutive opponents. Note that the queen cannot change its moving direction in case of multiple captures (unlike regular Checkers), i.e. the queen can move only on one diagonal in a single move (even when it captures opponent's pieces).
6. Termination: The game terminates when only pieces of one team remain on the game board. This team is announced the winner.
7. First move: The White player always has the first move.
8. No possible move cases: When there is no possible move for a team in its turn, its move should be skipped !
9. Unique rule 1: If there are two ways to move from point to point, always choose the way that moves to the west in ambiguous cases (i.e. to the lower columns of the board), or to the north (i.e. down rows) in cases were there is still an ambiguity. This is relevant for cases of multiple eating by a regular (i.e. non-queen) piece. For example, if a pawn can capture two opponent pieces in two possible routes that both ends-up in the same square, one starts with a move to the east, and another with a move to the west, it must do it with the route that initially goes west.
10. Unique rule 2: Unlike regular checkers, a player is NOT obligated to capture a rival piece when he can.

Compilation:

As before, you should compile your code using a makefile. The makefile should create a library named libcheckers.a and an executable named ex3. The library should contain only those object files required for the implementation of the Checkers game and the generic classes, but without the program that activates the game (i.e. the program with the "main" that reads input, make moves, write outputs etc.).
The makefile should be named "Makefile" (not makefile or MakeFile etc.). Note that we might test your classes directly (e.g. play chess with our own gamePiece classes, with your Board and Game, or replace one of your classes with ours).

Your makefile should have the following options:
1. make ex3 - create the executable ex3
2. make libcheckers.a - with the Checkers infrastructure.
3. make clean - clean (i.e. remove) all the object files, executables, and unix's temporary files (e.g. ex3.c~, #ex3.c#).
4. make tar - create a tgz file from the files you want to submit

Note that your makefile has to rebuild only the files which are not up-to-date.

Submission:

You should submit a tgz file called ex3.tgz (read here how to do it) with the needed code files (see above), including the ones we provided you, and:

1. A good way to debug this exercise is to play Checkers using it. Enjoy.
2. Note that we may test your code with our own code, e.g. play chess on your board.
   
3. You should implement this exercise with the c++ programming language. You must use the c++ syntax for the basic operation (IO, memory management, etc.). For example, use new/delete instead of malloc/free, use streams instead of printf. You are not allowed to use advanced c++ that haven't yet studied in class (such as templates, STL, exceptions, name spaces, etc.).
4. If you are not comfortable with the interface we defined, we encourage you to define your own graphic interface, such that playing Checkers with the program will be more convenient. However, you must submit a program with the exact interface we defined.
5. No need to submit a hard-copy.
6. Do not postpone the work on this exercise. As the 1st c++ exercise it might take more time than you initially expect.