``Baby checkers'' is a simplified version of checkers, where a player's pieces can move one square left, right, or forwards (but not backwards). A piece is captured by an opponent if it is surrounded on two or more of its 4 sides by the opponent's pieces. (Unlike regular checkers, diagonal squares are not used here.)
Here are the first two moves of an example game, played on a 3-by-3 board. (Let C stand for ``computer'' and H for ``human.'')
0 Start: 1 Move: 2 Response: H H H H . H H . H . . . ==> . H . ==> ! H . C C C C C C . C CAt the Start, each player's pieces fill the back rows of the board. The Human moves first, and here, the human moved a piece from square 0,1 to 1,1. The Computer moves next, and the piece at square 2,0 is moved forwards to 1,0. At 1,0, the piece is surrounded by two opponent pieces, and it is captured and removed from the board (as noted by the !).
Of course, a capture can happen in the usual way: Say that the human makes a move like this one:
. . H . . H H H . ==> . H . . C C H ! CHere, the human's move from 1,0 to 2,0 captures the opponent piece at 2,1.
The game ends when a player cannot move (is out of pieces or blocked); the opponent wins.
java Game.Start 3 H H H . . . C C C Type x,y coordinates of piece to move (q to quit): 0,1 Type x,y coordinates of destination (q to quit): 1,1 H . H . H . C C C H . H . H . . C C Type x,y coordinates of piece to move (q to quit):Each round, the human sees the chosen move and the computer's response.
Here is a diagram of the program's structure:
The ComputerPlayer is simplistic, and a human easily beats it. Your job is to write a better computer player, which plays better than a human.
And, your implementation must employ a search of the search tree for the checkers game, starting from the current board configuration, searching at least 2 moves (the computer's next move and the human's response) into the future, generating the future board configurations, and selecting the next move that leads to the most favorable board configuration in the future.
You are encouraged to make the algorithm for the computer player as smart as possible; this is usually done by searching many moves into the future to resolve a choice between two next possible moves that appear to be similar in their initial benefits. This means your algorithm might do a shallow (2 move) search to locate the 2-3 best possible next moves and then do a deeper search to decide which of the remaining possibilities should be used as the next move. (This two-step process is called ``pruning the search tree.'')
It is best to use a queue to implement the bounded-depth search of the search tree.