Here's my online Checkers game with AI. Coded in C# and asp.net. Online Checkers It is hosted by my computer, so it might be a bit slow if many players are playing at once and occasionally it will be offline (when i'm sleeping) It uses Minimax (5-deep) with alpha-beta cut-offs. It rates a board according to: - number of pieces on the board (20 pts per piece) - number of kings on the board (30 pts per king) - number of allowed moves (1 pt per allowed move) - number of adjacent pieces (1 pt per adjacent piece or side, this way it preserves a little bit of cohesion) On this page there is also a Windows version available (and Linux if you have Mono). I'm thinking of implementing the following optimisations: - think deeper if opponent is allowed to make only 1 (or 2) move after moving a piece of your own. - cut-off branches which result in low score after 2-3 moves - Think deeper when there are less pieces on the board Has anybody made a Checkers AI before? Any suggestions / comments? Thanks, Edo

You could just have a time limit on the minimax search and increase the depth until you run out of time. Although this wastes some time, it's not as bad as it may seem, 1/2 in the worst case and a lot less in checkers.

Yeah already thought about the time limit, but it's not really an optimisation. What I want is a good formula for board rating and cut off branches in smart way, and think deeper when it's necessary.

Has nobody done this before?

I've done it in Spanish checkers. Iterative deepening (what the AP suggested) is a really good idea. If you use transposition tables, you can make it actually *faster* than fixed depth. And, at least in Spanish checkers, the difference in time to evaluate different positions at fixed depth makes that behaviour intolerable. Keep the moves at the root sorted. When you discover a better move than the current move, put it at the top of the list, so it is the first move explored on the next iteration.

Improve your move ordering. History heuristic seems to work just fine for checkers. It can be improved in several different ways.

For evaluation, use advice from masters if you have access to them, or try to learn how to play well yourself. Count material first(1 king = 1.35 pawns in checkers; it was 1king = 3 pawns in Spanish checkers), value pieces in the center of the board better than to the sides, value the squares in the first row more (except the corner). Then you can add detection for particular structures that happen all the time, with associated bonuses. This was very important in Spanish checkers to detect passed pawns, which doesn't matter much in checkers. It can also be used to keep good structures in the opening, and to give bonuses for one piece blocking two, or a trapped king.

Extend forced captures. That's about the most important extension you need. Also, don't stop the search in a position where a capture is possible.

Make a database of ending positions (see Chinook's website for this).

With those ingredients, you should have a pretty solid program. In general, you can apply most ideas from computer chess (and there is a lot of information on this). Don't even try the null-move heuristic, as it has no chance of working in this type of game.

To really improve your program, buy a commercial program and match your program against it. At the beginning it is frustrating to lose every game, so give yourself a huge handicap. For instance, you can run the professional program on a really slow computer, or at 1 second/move. Reduce the handicap as you progress.

Good luck!

Hmm... I got a few moves into a game, and now I can't move any more (I've got two available moves, both of which take a piece, and I can click and get the yellow 'moving this piece' marker but not actually move the piece).

[edit: OK, clicking on the AI Move button made it go again, despite it being my go. :) ]

I think you have to click three times: one the piece that you want to move, on the piece that you want to capture and on the square where you want to land. This interface should be improved.

Improved? It's the best I could think of. You click the piece to move, the pieces to be jumped, and the square to land on.
I thought I explained pretty well:

1. Click a piece to be moved
2. Click jumped piece(s) in the right order (if this applies)
3. Click an empty cell to land on

You can't just click start and end, because some jumps have same start and ending, but different jumped pieces. The windows version has an extended interface though, which feels a bit more natural.

BTW: Thanks alvaro for all the good suggestions!

Edo

You should make the move whenever you have enough information to determine what the move is. If there are two ways of capturing and I click on one of the pieces that can capture, I shouldn't have to click anywhere else. Especially if the webpage has to be loaded again each time (might be more tolerable locally).

Also, if a user just clicks the initial piece and then all the intermediate squares in order, it should work, because that's what most people will try the first time.

Yeah you're probably right, but I'm not going to fix it... my focus is on the AI. Sorry..

It's not THAT bad is it?

Nice checkers program.

I would recommend having a heuristic, which describes how good each square is. for eg. the center squares on the other side of the board, would be worth more then the squares you start on.

Also, make kings quite a bit more importaint. (in a few games, there is a piece which cuold be kinged in one move... and the ai's not taking it...)

Also put some shape recognition into it (bit boards! easy as 3.1415926535387932384626433). Recognisintg some basic shapes, such as a strait line, triangle, or a few others, would help its game immensly. (for a very small cost)

Also, some multi-peice tactics (even some basic ones), could make your ai's game soar... (after i've been clobbering it on endgames, time after time, after time, after time.)

Also, Conditional values, something like:
Holding on to the edge of line 4 has the value of 0.95 only if i am holding on to the edge of line 3.

You should also have it continually searching. (this will make your program a lot stronger, because now you get to search in the users time, and you have your own moves almost instantly, so you can run on any time control).
Just have it do its search continually, and whenever the user makes a move, remove the nodes which could not happen from the the search tree and flag it in the transposition table (a big flag saying you can overwrite me!).

A learnable opening book would be great to have, so that it can figure out the major openings which could beat it, and search for counterplays at a heigher depth then what was already searched.

Just some ideas for you.
From,
Nice coder