Checkers AI Algorithm

Question

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?

Answer 1

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.