Checkers?

[PK]

@hgm, "Your approach" referred to the author of this thread: "I have chosen the approach where each jump is treated like a different move where the side was not switched".

Pruning moves based on move hash gave me some speedup on top of transposition table, but this is language and implementation dependent. Making a move in checkers may take more actions than in chess.

[hgm]

That's right, especially moves that can be realized through different paths will be likely to have lots of victims. But it is still surprizing to me that this can measurably affect speed, as I would expect duplicat moves are very rare. So if you have to spend some calculational effort on every move to prevent them, this could very easily wipe out the advantage. Unless the first trial of the move would be lost from the hash table by the time you get to the duplicat, and it would really have to rediscover the entire search tree. But that points more to a problem with the hash table.

In the Interactive Diagram I have a JavaScript AI without hash table, and there it is a real problem. Since in the chess variants it can be configured for one often deals with move definitions that generate duplicats. For instance a Rook that can also jump to the 2nd square. If the 1st square is not blocked that would provide two ways to get to the 2nd square, and it is not easy to define a Rook move that can slide to all squares except the 2nd. So I do keep a map of target squares during generation of moves with the same piece, to see if multiple moves without side effects to the same destination occur. That solves most of the problem. But in Draughts-like games it is all about the side effects. How did you calculate the move hash? The bitboard of all victim squares multiplied by some magic constant?

[PK]

I used the same hash keys as usual: [color][piece][square], changing the key for each captured piece, for from square, for to square and for promotion, but not taking into account any squares touched by the moving piece in the meantime. Thus, such hash was useless for visualizing moves or for defining which squares should be clicked on the board to make the desired capture.

For visualization purposes, moves were translated into a list of "actions" (what piece moves, between which squares, what disappears from where and a few others). It was very verbose, as without that pieces would be teleported and the order of actions was of course important.

[hgm]

That has in any case the advantage you can also use this move key to update the total position key. I suppose the number of moves you can actually do when you can make a capture is typically very small, so it doesn't really matter how much effort it takes to determine their hash key.

[jaroslav.tavgen]

It seems my approach of treating each sub-jump as a separate move is not very comfortable once you start implementing minimax (it is okay though if all you need is an engine capable of making correct moves).

What is the best practice of generating moves in checkers? Because it's extremely complicated. Each king can move in four different directions and once you jump in any of those direction you have four different directions once again. And if I am not mistaken the king can make up to 12 jumps in a row. How to correctly code all this?

[jaroslav.tavgen]

Finally! I've implemented something! Here: https://jaroslavtavgen.com/

https://github.com/jaroslavtavgen/Perso ... e/checkers

I've stolen the algo from https://github.com/sramakrishnan247/Checkers-AI/ and rewrote it in JavaScript.

I've implemented the AI the way it was described in Arthur Samuel's paper "Some Studies in Machine Learning Using the Game of Checkers" under the headline "Ply limitations".

The most effective one, although quite detailed, is simple in concept and is as follows. The program always looks ahead a minimum distance, which for the opening game and without learning is usually set at three moves. At this minimum ply the program will evaluate the board position if none of the following conditions occurs: (1) the next move is a jump, (2) the last move was a jump, or (3) an exchange offer is possible. If anyone of these conditions exists, the program continues looking ahead. At a ply of 4 the program will stop and evaluate the resulting board position if conditions (1) and (3) above are not met. At a ply of 5 or greater, the program stops the look-ahead whenever the next ply level does not offer a jump. At a ply of 11 or greater, the program will terminate the lookahead, even if the next move is to be a jump, should one side at this time be ahead by more than two kings (to prevent the needless exploration of obviously losing or winning sequences). The program stops at a ply of 20 regardless of all conditions (since the memory space for the look-ahead moves is then exhausted) and an adjustment in score is made to allow for the pending jump.

Something is wrong either with this algorithm or my implementation since I manage to do a draw even at a significant material disadvantage (say, 2 kings versus 8 enemy pieces).