| Instructions |
The applet supports 1-player and 2-player mode, and also 0-player (computer vs. computer). Move a piece by clicking on it. It will be backlit in orange, and then click on the target square. If there is a forced capture elsewhere, then the piece will be backlit in blue.
You can set the search depth, which is counted in ply, or half-moves. If you bring up the Java console, you can see the evaluation of the position. Positive scores favor Black, with one checker worth 100, and a king worth 200. Positional considerations are also taken into account. Look at the source code of the engine to see the (mild) tweaking.
Recommended search depths is 4 to 6, which should allow for a playable game for novices. If you are willing to wait for up to a minute per move, you can try the higher search depths. As usual, Internet Explorer and Netscape Communicator users can expect faster responses due to JIT compilers.
The features of this applet include:
Don't forget to see the rest of the site!
| Standard Checkers |
We implemented forced and multiple captures because this is how checkers is played seriously. Leaving these features out would be like coding a chess program without allowing pawns to be pushed two spaces, en passant and underpromotion. The game may look the same in the beginning, but play is highly crippled. This made for most of the problems in the implementation, since bugs were difficult to find. We are very proud of the fact that we implement forced captures for the player, and that the game engine makes captures when they are possible.
Also, in the case of multiple captures, the interface is intuitive for the player, since he will be able to click on all the intermediate squares. The background color of the checker after one capture allows him to see easily that a further capture is possible. Some implementations we have seen require right clicks of the mouse which is difficult for the player to keep track of.
The computer will only consider moves to be complete in the case of multiple captures if the 'active' checker, that is, the checker that has already captured, has no further captures. Therefore it will not terminate multiple captures halfway because that would be illegal.
| Minimax algorithm with alpha-beta pruning |
We have described the algorithm in great detail in our research page.
What we do is create a Vector of all the possible moves, and then consider these moves, calling the Minimax method recursively. The move consideration has all the checking inlined and does not consider spurious moves. Illegal moves are, as far as possible, detected early and rejected. Whenever possible, we have streamlined the engine. For example, redundant checking was present in the code to catch bugs, but these were later removed. Therefore, when the computer considers a position to generate a Vector of moves, it only looks once for forced captures, instead of doing so for every single considered walking move.
Forced move deepening helps prevent the dreaded horizon effect, which occurs when the computer sees a move (say in 4 ply) that is very good for the player. An example of this may be crowning a new king, or the capture of two checkers. It sees that by forcing the player to make some other move, say by giving up one of its other checkers, it can forestall the first eventuality. This pushes the first eventuality past the horizon of the search, so the computer plays this. However, the original threat still exists beyond the horizon. Forced move deepening lets the computer see further when it tries to give away a checker, so that it doesn't push the threat beyond the horizon.
Forced moves at depth 0 are played immediately by the computer without thinking at all, since it has no choice. This saves some time since the information is not stored. If you bring down the Java console, some statistics of every move will be printed.
| Evaluation function |
Evaluation is basically counting material and then adding positional considerations. In checkers, positional considerations are not as obvious as they are in chess, but thankfully they are much simpler. We implement quadratic scoring for checker rank, and discourage placing kings on edges.
The rank is how many rows a checker is from the bottom of the board. Evaluation of a board position is based on counting pieces, with checkers worth 100 + rank*rank, and kings worth 200. The quadratic scoring for checkers encourages advance of checkers that are already far down the board, to encourage crowning of kings.
Trapping enemy kings on the edge is a great way to force the opponent into a lost position when the opponent is down on material. It serves as an intermediate goal while the other enemy king is being trapped, in the common 3 on 2 endgame. Therefore, in the evaluation function, kings on edges are worth 20 points less. Kings in corners are worth 40 points less.
| Interface |
The interface is easy to use, and the controls respond well. However, Unix implementations of Netscape have problems with multithreading. This is not a defect of our implementation!
We've succeeded in preventing the board display from lagging by explicitly calling the update method instead of repaint. The toMove label sometimes gets a little lagged, though.
| Automatic Search Deepening |
This is an idea that Feng-Hsiung Hsu, creator of world chess computer champion Deep Thought, implemented. He first envisioned it in the case of forcing moves in chess, whereby variations in which the number of good moves is limited are searched deeper.
The proportion of bad moves to good moves in chess is much higher than in checkers. Also, seeing which moves are 'good' introduces state-dependence into the Minimax algorithm. We decided to implement a much simpler variant, which increases search depth by 1 ply when there is a forced move. This is useful since a forced move implies a forced capture, or the approach of a loss. Also, analysis of the forced move was essentially free, since there was no branching. We can thus search one ply deeper, thus adding about 7 nodes, without greatly overgrowing the number of nodes in the search tree.
| Source Code |
ZIP of the source code (download and compile!).
This code is very old: the game was written in Java 1.0 circa 1997.
It is also a very good example of how not to program, because we had to really cut a few corners in order to finish on time.
Please do not redistribute or make available modified code.
If you do improve the game, please send us a copy, we'd be very interested
in it.
Checkers.java Board.java Move.java Engine.java
| Randomization of Moves |
With every board evaluation, we add a small random weighting. This allows pseudorandom play on the part of the computer, and prevents repetition of games.
| Slide Show |
We had a rudimentary slide show that we could present to the CS20 class.
| Contact us |
Feel free to write to the authors.