Project Plan

Our objective is to set up a checkers program strong enough to beat anyone in the CS20c class with a difficulty setting of (an average of) 1 minute of computing time per move. We may forseeably achieve a speed on the magnitude of 1000 positions per second. This will allow exhaustive 4-ply search and selective 10-ply search (a ply is one move by one player).

For this project, we will implement alpha-beta pruning in a minimax search in a Java applet. Java is eminently suitable for such a program because of the end product: an applet that may be easily downloaded off the web. Of course, it is also object-oriented.

The construction of the applet will be encapsulated so that other games may be implemented. Therefore it will be split into classes that handle

• Display, display and user interaction (by VH)
• Move, generation of legal moves (by VH), position evaluation (by SHH with heuristic weighting rules by VH)
• Engine, move search and selection (i.e., the game engine) (by SHH)

The representation of the checkers board is very compact. We have 32 squares which may be individually labeled. A move is represented as something like "0105" which means move from square 1 to square 5. Each square may be empty, contain a checker, or a king. A simple way to represent the board would be a string of 32 bytes. The evaluation of the position will be an integer (we use integer arithmetic for speed).

Here are the responsibilities of the classes:

Display	Sets up the board and handles user requests (new game, takeback). Maintains the current board position and historical move list. Accepts user input (moves), displays it, calls a ApplyMove method in the Move class, with board position and move made. If ApplyMove returns "illegal move", reject user move. Calls the BestMove method in the Move class. Takes move returned by BestMove method and displays it to the user. If BestMove returns "loss" then display lose message. Calls LegalMove to see if human has any moves left. If not, then display win message.
Move	ApplyMove Accepts a position and move and returns new position if move is legal, "FALSE" otherwise BestMove Accepts a position and player-to-move. Calls Minimax in Engine class Returns best move to Display GenerateMoves Accepts a position and player-to-move Generates a Vector of all legal moves (by calling ApplyMove) Evaluate Accepts a position (w/o player-to-move) and returns an integer (higher for positions good for white)
Engine	Minimax Accepts position, player-to-move, current depth, maximum depth. Calls GenerateMoves in Move to get a list of possible moves. For each move in the list, call ApplyMove to arrive at the new position. Call Evaluate to find score of this position. Based on best scores on each side, conduct alpha-beta pruning. If (depth < maxdepth), call itself with depth+1, based on the new position. Accept the chosen score and chosen move of the recursive call. Returns chosen score, chosen move.

Other than the standard Archetype document we found, we have included a few web pointers which may be found in the links page.