# Checkers AI Algorithm

I am making an AI for my checkers game and I'm trying to make it as hard as possible. Here is the current criteria for a move on the hardest difficulty:

1: Look For A Block: This is when a piece is being threatened and another piece can be moved in behind it to protect it. Here is an example:

Black Moves
|W| |W| |W| |W| |
| |W| |W| |W| |W|
|W| | | |W| |W| |
| | | |W| | | | |
| | | | |B| | | |
| |B| | | |B| |B|
|B| |B| |B| |B| |
| |B| |B| |B| |B|

White Blocks
|W| |W| |W| |W| |
| |W| | | |W| |W|
|W| |W| |W| |W| |
| | | |W| | | | |
| | | | |B| | | |
| |B| | | |B| |B|
|B| |B| |B| |B| |
| |B| |B| |B| |B|

2: Move pieces out of danger: if any piece is being threatened, and a piece cannot block for that piece, then it will attempt to move out of the way. If the piece cannot move out of the way without still being in danger, the computer ignores the piece.

3: If the computer player owns any kings, it will attempt to 'hunt down' enemy pieces on the board, if no moves can be made that won't in danger the king or any other pieces, the computer ignores this rule.

4: Any piece that is owned by the computer that is in column 1 or 6 will attempt to go to a side. When a piece is in column 0 or 7, it is in a very strategic position because it cannot get captured while it is in either of these columns

5: It makes an educated random move, the move will not indanger the piece that is moving or any piece that is on the board.

6: If none of the above are possible it makes a random move.

This question is not really specific to any language but if all examples could be in Java that would be great, considering this app is written in android. Does anyone see any room for improvement in this algorithm? Anything that would make it better at playing checkers?

• (On a Checkers-specific note, IIRC being on the edge isn't necessarily the advantage you make it out to be; such pieces have no mobility, since they only have one move available, and are easier to trap and capture.) – Steven Stadnicki Jun 3 '12 at 19:11
• Just in case you weren't aware checkers is a solved game, and if played perfectly the result is always a draw. chessbase.com/newsdetail.asp?newsid=3997 – Adam Jun 4 '12 at 12:01

If you're trying to make a good AI for your checkers program, then the first place to look is what's known as Alpha-Beta game tree search. The short version is that any AI that only takes into account static features of the current position is bound to run into trouble, especially in the early-to-mid game, because it simply can't understand what's presently happening in the game and what the threats are. Instead, what you want to do is to write an algorithm that searches all possible moves-and-replies for some number of moves ahead (5 to 10 would be typical), evaluates the position at the end of each branch of this move-and-reply tree (in terms of 'how many pieces ahead or behind am I?), and then makes the move that gives it the best chance - in other words, the move that maximizes its possible value, where the possible value is calculated as the minimum possible value across all of your opponent's replies (assuming, in other words, that they'll make the move that's best for them), etc. - this is why this algorithm is often called the Minimax algorithm.

What you'll find is that many of the elements you're talking about - moving pieces to the side, moving pieces out of danger, etc. - will become elements of the positional evaluation function of the game tree search. Essentially, instead of asking the simple question 'how many pieces ahead is one side or the other?', you'll say 'what is the value of this position?' and then give point values to various features of the board (e.g., whether a piece is on the side, whether it's vulnerable, etc.) in terms of partial pieces - for instance, you might decide that the difference between an edge and a center piece is worth possibly .1 piece, so in a position where you're a man behind but have an extra edge piece the overall value to you will be -0.9.

One critical advanced notion for checkers AI specifically is the concept of Quiescence search: imagine that you go down six moves into your tree, and at the tail end your opponent has just made a capture where your (forced) reply is an immediate recapture. Unfortunately, the positional evaluation function can't see the recapture, so it evaluates the position as being a piece up for your opponent even though you're about to regain parity. Quiescence search is an attempt to solve this problem by forcing the evaluator to go down into a branch until all possible forced captures have been made, and only then evaluate the position.

This may all sound fairly complicated, but I think you'll find it's more straightforward than it looks - once you write your evaluator function, the tree search is relatively easy; there are a lot of smart concepts (things like transposition tables) that you can apply to it, but it should be easy to get something working and then continue to improve it. For more details, I suggest searching on pretty much any of the key terms (alpha-beta search, minimax, quiescence search, game tree, etc); there's plenty of good information on all of these concepts out on the web.

• Thanks for your answer, I've thought about doing this before but I always thought my way was more effective, but the way you describe it sounds like it would be more effective but a lot more work. I'm going to be making an AI for a chess game soon, and I think it would be less work and more effective to do it your way. If the computer has a bunch of different choices to choose from, and it narrows them down to a couple that all have good outcomes, how can it lose? Thanks for the detailed answer! – John Jun 3 '12 at 21:13
• I would still recommend you try Steven's method, as it would be significantly easier to implement minimax in checkers than chess, and in fact, it would be significantly easier to implement minimax in checkers than you might realize. I wrote a (non-ab-pruned) minimax algorithm for Connect Four in a couple hundred lines. It's all fairly straightforward if you're willing to put in the time and energy to improve your skills. – SomeGuy Jun 3 '12 at 21:47
• I'd like to point out that since Steven's answer, MTCS has become hugely popular as an alternative to Alpha/Beta. That's also worth looking into, especially because MTCS is an anytime algorithm. – Tobia Tesan Oct 22 '17 at 6:21
• @TobiaTesan I presume you mean MCTS (Monte Carlo Tree Search)? It has, to be sure, but MCTS is substantially trickier to implement than a basic Alpha-Beta algorithm and I'd definitely encourage implementing A-B first, not least because it's a good base from which to implement MCTS. – Steven Stadnicki Oct 22 '17 at 6:25
• @StevenStadnicki Mind you, I wasn't trying to criticize in any way your excellent answer (which I upvoted). I concur that classical methods like A/B are always worth learning first, in particular because Minimax is a powerful theoretical framework; however, MTCS really didn't strike me as hard to implement; the tricky part IMHO is that quite a few pseudocode versions out there are a bit on the low-level side, in particular (e.g. Gelly 2011) they like to express the algorithm through side effects on a global state [board] which get reversed as recursive calls are popped. – Tobia Tesan Oct 22 '17 at 10:38