Checkers AI

The most commonly used algorithm for having a computer play a two player game is minimax.

You write a function that looks at the board and the possible moves and determines which move is the best. To determine the value of each move, you can use the same function to evaluate how good the board resulting from each move is for the opponent. Your goal is to maximize the value, and the opponent's goal is to minimize the value. The opponent will choose the move that results in the lowest value. To find the value of each of those moves, we're back at the beginning trying to evaluate the player's position, and choosing the move that results in the highest value.

The recursion can continue all the way to the end of the game (assuming that you can detect infinite loops and/or there are rules that would prevent them). When the player wins the value is high, and when the opponent wins the value is low. For small games this approach creates a perfect player that looks at every possible move and finds a way to force a win whenever possible. For large games the game tree is too big so the recursion needs to be terminated before the end of the game. Usually a heuristic function can be used which tries to evaluate how good a board is, with better boards having higher values. The tree can then be searched to some limited depth.

There are some tricks to speed things up, like alpha-beta culling, and searching to a lower depth but expanding interesting positions further to focus the search on the more interesting possibilities. There are also hashing tricks to avoid having to compute a value for a state that has already been visited. There's plenty more information about this stuff on the internet.

Would you happen to know of any of these sites? I been looking around for some pseudocode or examples of a checkers AI.

Quote:

Original post by Warhell I was wondering if anyone knows of a good source or some good tips on programing AI for checkers? I would like to make an easy, medium, and hard AI.

AI for two-player games with perfect information (i.e. checkers or chess, but not poker or stratego) is typically implemented through variants of the minimax tree-search algorithm, so you want to start reading up on minimax (or one of its variants, such as alpha-beta search, MTD(f), etc).

If you want to go beyond the basics of implementing a bare-bones minimax search, you can start reading up on what others have done, in particular the publications on Chinook.

I will third the vote for minimax but would emphasize that the really hard part is evaluating the board. Each step of the minimax algorithm will require that you give the board a score which relates to its desireability for the player. This is not trivial, but you should be able to find plenty of possibilities in the literature. Try Google Scholar.

For those interested, I just recently saw a publication in which checkers was solved. Much too much number crunching for your purposes, but interesting nonetheless.

http://technology.newscientist.com/article/dn12296-checkers-solved-after-years-of-number-crunching.html

Also, Blondie24 is another interesting read. In this one, they developed a neural network that evaluated the board and that was used as the score for a minimax algorithm. The neural network was developed using an evolutionary computation appraoch. Again, probably not a solution for you, but interesting stuff. 8^)

http://www.amazon.com/Blondie24-Playing-Kaufmann-Artificial-Intelligence/dp/1558607838/ref=pd_bbs_sr_1/105-2475319-8502059?ie=UTF8&s=books&qid=1187194029&sr=8-1


-Kirk

Off the cuff, do you think the possibility space for checkers is small enough that you only need use the end game points? (i.e. +1/-1) I would suspect not since in the late game stages, you can do a lot of wandering around that doesn't move you toward the endgame. TTT forces you there since the possibility space continually shrinks.

The next possible cut would be based on the number of opponent pieces left. Or the delta between the two sides. Even that can be problematic, however, since there isn't a definative move toward a board state. If you each had two pieces left, perhaps only 5% of the moves would change the board state. That leads to a pretty large explosion of branches. Hmmm...

So what are the criteria for an advantageous board?

The basic heuristic for checkers is material count. Something like num_white_pawns-num_black_pawns + C*(num_white_kings-num_black_kings). You'll have to play with C to get good results. I think C should be around 3 for Spanish checkers (where kings move like bishops) and around 1.4 for what's usually played in the US (where kings move one square only).

On top of that you can add a piece-square table that will give a higher value to pawns in the center and in the back row. You may need the help of a good player to adjust those values. Then you can start defining patterns that are worth some points. A pattern is described by a mask indicating what part of the board has to be compared, plus a description of what should be in that part of the board in order to get a match. If you use bitboards, you can describe a pattern with 4 of them (mask, white_pieces, black_pieces, kings) plus the associated bonus score. You can probably get something faster using a decision tree.

With patience and an expert player to help you, you can get pretty far with this scheme. Of course you'll need a good search algorithm to go with it. I would start with alphabeta with transposition tables, and then try PVS and maybe even MTD(f) (although I've never managed to make MTD(f) work well). Then you'll need to generate an endgame database (essential in this game), so you can access the theoretical value of any position with less than N pieces with a simple lookup. You can also work on an opening book, or on some mechanism to remember scores of positions you have visited before.

This can keep you busy for several years, and it's a lot of fun. However, it would probably be better to try with a less-understood game, like go.

I would actually like to be able to implement this in a day or two, but from the looks of it, it's going to to me a lot longer then that. Since I have no experience with the minimax algorithm. It actually might make things very easy if I could find a full pseudo code for the algorithm. I have been looking around the net for a couple days, does anyone know of a good source that has the full pseudo code implementation of the minimax? I'm still having trouble conceiving in my head how I would actually implement this, let alone program it.

There's a few less-tricky things that you need to do before you can implement minimax. The basic ingredients are:
* A representation of the board
* A representation of a move
* A function that generates all the legal moves from a given position
* A function that gives you an idea of who is ahead. You can start with material difference and build from there

Once you have that, you can read what Bruce Moreland wrote about chess programming. Most of it applies to checkers directly. Two notable exceptions are the null-move heuristic, which doesn't work well in games like checkers where Zugswang is common, and the quiescence search, which is really essential to make a chess program, but in checkers can be substituted by the simple rule of not stopping the search after a capture (you could substitute that rule by "not stopping the search if a capture is possible", but it's probably harder to program).

If you find Bruce's pages too overwhelming, I can write some pseudo-code for you, with only the basic things that you can implement in a couple of days.