CIS300 Spring 2005: Assignment 5

15 points; due Wednesday, March 16, at 10:00pm

You must write a program that plays ``baby checkers.''

``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 C

At 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 ! C

Here, 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.

Implementation

A demo version of the two-player checkers game has been built, where a human player competes against a computer player (algorithm). You can find the game at http://www.cis.ksu.edu/~schmidt/300s05/Assign/Assn5 Using the command window, the human views the board and enters each move, where a move is coded with the usual x,y-coordinates one uses to denote the cells of a two-dimensional array. Here is how to start and play a first move of a 3-by-3 game:

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.

`public class SmartComputerPlayer implements Player`

Your implementation of class SmartComputerPlayer must implement a criterion of your choosing for judging the favorability of a checker board. The criterion might be based on the number of the computer's pieces left on the board, the difference of the computer's pieces minus the human's, the danger of possible capture, the forwards location of the computer's pieces, etc.

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.

What to Submit

Your assignment will be saved in a folder named Assign5, and you will submit Assign5.jar. Within the folder, you will place

package GamePieces, which holds the codings for the checker board and game controller. Do not alter this package.
Other packages that you use, e.g., package Queue.
package Game, in which you include your coding of class SmartComputerPlayer implements Player. Revise class Start to use your SmartComputerPlayer.
The javadoc-generated documentation for the classes you write.
A file, strategy.txt, which is a detailed, English explanation and rationale of the search strategy you implemented in your coding of the computer player. (Your explanation must consist of at least 6 grammatically correct English sentences. Supporting diagrams and examples of the computer player's play are welcome.)

Submit Assign5.jar at http://www.cis.ksu.edu/~schmidt/300s05/Assign/submit.html