In this project, you will demonstrate your understanding of dynamic memory and linked data structures (Chapter 10) and extend your program design, testing, and debugging skills. You will also learn about Artificial Intelligence and tree search algorithms, and implement a simple algorithm for playing checkers.
Checkers, or draughts, is a strategy board game played by two players. There are many variants of checkers. For a guide to checker’s families and rules, see https://www.fmjd.org/downloads/Checkers_families_ and_rules.pdf. Your task is to implement a program that reads, prints, and plays our variant of the game.
Setup. An 8×8 chessboard with 12 black and 12 white pieces initially positioned as shown in Figure 1a.
Gameplay. Each player plays all pieces of the same color. Black open the game by making a move, then white make a move, and then players alternate their turns. In a single turn, the player either makes a move or capture. For example, the arrow in Figure 1a denotes an opening move of the black piece from cell G6 to cell F5.
Moves. A piece may move to an empty cell diagonally forward (toward the opponent; north for black and south for white) one square. The arrows in Figure 1b show all the legal moves of black and white pieces.
Towers. When a piece reaches the furthest row (the top row for black and the bottom row for white), it becomes a tower (a pile of pieces). The only move of the white piece at cell D7 in Figure 1b promotes it to the tower. A tower may move to an empty cell diagonally, both forward and backward, one square. The arrows in Figure 1c show all the legal moves of black and white towers.
Captures. To capture a piece or a tower of the opponent, a piece or a tower of the player jumps over it and lands in a straight diagonal line on the other side. This landing cell must be empty. When a piece or tower is captured, it is removed from the board. Only one piece or tower may be captured in a single jump, and, in our variant of the game, only one jump is allowed in a single turn. Hence, if another capture is available after the first jump, it cannot be taken in this turn. Also, in our variant of the game, if a player can make a move or a capture, they may decide which of the two to complete. A piece always jumps forward (toward the opponent), while a tower can jump forward and backward. The arrows in Figure 1d show all the legal captures for both players.
Game end. A player wins the game if it is the opponent’s turn and they cannot take action, move or capture, either because no their pieces and towers are left on the board or because no legal move or capture is possible.
Your program should read input from stdin and write output to stdout. The input should list actions, one per line, starting from the initial setup and a black move. The input of moves and captures can be followed by a single command character, either ‘A’ or ‘P’. Action should be specified as a pair of the source cell and the target cell, separated by the minus character ‘-’. For example, “G6-F5” specifies the move from cell G6 to cell F5.
The following file test1.txt uses eleven lines to specify ten actions, followed by the ‘A’ command.
Stage 0 – Reading, Analyzing, and Printing Input Data (8/20 marks)
The first version of your program should read input and print the initial setup and all legal actions. The first 42 lines that your program should generate for the test1.txt input file are listed below in the two left columns.
Lines 1–21 report the board configuration and specify the initial setup from Figure 1a. We use ‘b’ and ‘w’ characters to denote black and white pieces, respectively. Then, lines 22–42 print the first move specified in the first line of the input. The output of each action starts with the delimiter line of 37 ‘=’ characters; see line 22. The next two lines print information about the action taken and the cost of the board; see lines 23 and 24. The cost of a board is computed as b+3B−w−3W, where b, w, B, and W are, respectively, the number of black pieces, white pieces, black towers, and white towers on the board; that is, a tower costs three pieces. Then, your program should print the board configuration that results from the action. The complete output your program should generate in Stage 0 for the test1.txt input file is provided in the test1-out.txt output file.
If an illegal action is encountered in the input, your program should select and print one of the following six error messages. Your program should terminate immediately after printing the error message.
|1 ERROR: Source cell is outside of the board.
2 ERROR: Target cell is outside of the board.
3 ERROR: Source cell is empty.
|4 ERROR: Target cell is not empty.
5 ERROR: Source cell holds opponent’s piece/tower.
6 ERROR: Illegal action.