Documentation for Checkers


The entire program is written in Java.

To make the program "think" I use a variant of the MiniMax algorithm, which is a standard algorithm in the area of computer game playing.

MiniMax algorithm

We represent the game as a (search) tree where the nodes represent the current position and the edges represent moves. Since players take turns, successive nodes represent positions where different players must move. We call the nodes MAX or MIN nodes depending of who is the player that must move at that node. We assume that the MAX player makes the first move.

The MiniMax Game Strategy for the MAX (MIN) player is to select the move that leads to the successor node with the highest (lowest) score. The computer takes the maximum when the node to which a score is being assigned is the point where the computer has the turn and minimum in the opposite case. Thus at some point the root node will be assigned a score that was backed up right from some leaf node through a continuous path through the tree. All leaves are boards and they are evaluated by an evaluation function that returns an integer signaling how good/bad a certain board is.

The MiniMax algorithm works on a already built game tree. However, to improve performance my implementation of the algorithm builds and evaluates the game tree concurrently.

The problem with the MiniMax algorithm is that it explores each node in the tree. We therefore need the Alpha-Beta Pruning technique.

   function MINIMAX(N) is
   begin
      if N is a leaf then
           return the estimated score of this leaf
      else
           Let N1, N2, .., Nm be the successors of N;
           if N is a Min node then
              return min{MINIMAX(N1), .., MINIMAX(Nm)}
	   else
	      return max{MINIMAX(N1), .., MINIMAX(Nm)}
   end MINIMAX;

The Alpha-Beta Pruning

Alpha-Beta cutoff is a method for reducing the number of nodes explored in the Minimax strategy. The algorithm eliminates branches of the tree which are not worth looking at. By using alpha-beta cutoff the Checkers program can search a game tree of depth 8 in a few seconds. Without the alpha-beta cutoff only a game tree of depth 5 can be searched in the same time. In general it can be shown that in the most favorable circumstances the alpha-beta search opens as many leaves as minimax on a game tree with double its depth. For a detailed description of the Alpha-Beta cutoff method please see: MiniMax with Alpha-Beta Cutoff and Programming Intelligence

The Evaluation function

The evaluation function of my Checkers program implements very simpel heuristics. An obvious way of improving the program is therefore to add more heuristics to the evaluation function. However, it is not trivial to find the right heuristics and the right weights of the heuristics in the evaluation function. A solution is to repeately let the program play against itself with different heuristics and weights and from the result of these games calculate a good evaluation function.

But the evaluation function should not be too complicated. A large game tree has a large number of nodes. Thus the program has to use the evaluation function very often. The more complicated an evaluation function becomes (making the evaluation function more accurate, which is good), the less time the computer has to generate an even deeper tree (which is bad). So there has to be a trade off between how accurate the evaluation function is and how deep the computer searches for the best moves in the tree.

One person who has developed a good evaluation function is Dr. Jonathan Schaeffer. He led a team of researchers of the Department of Computing Science at the University of Alberta, Canada in the development of in the most advanced Checkers program, Chinook. Chinook is the World Man-Machine Champion, the first computer program to win a human world championship.

Class diagram

Download the source code