Rein Halbersma wrote:
I would be interested in learning why DTW computations for checkers are inherently more complicated than for say chess. Can you elaborate?

The details emerge once you are actually writing the code and getting results. You soon find out that "chess logic" for DTW does not apply to checkers. Not only that, once you figure out the checkers logic, it's not apparent if your routine will ever terminate. Then, finally, the "light bulb moment" occurs, and everything falls into place.

In chess, for example, you place the pieces on every possible square, and look for checkmates for the side to move. Every such position is a "loss in 0." Next, every move possible by the side-not-to-move must create a "win in 1." I am oversimplifying, leaving out illegal "still in check" moves and the fact that the mated side might also have winning chances, etc. This process repeats for loss in 2, win in 3, loss in 4, etc.

In checkers, you have to look at every position with each iteration, and not just "increment" the win/loss ply counters.

Example from the 9-piece database:

Here the red checker starts at the bottom and crowns to a king on squares 29, 30, 31, or 32. It must travel up the board.

You can see if it were white to move, 16-12 threatens to win the checker on square 8 trivially. One might then think 8-12 is forced for red to move, keeping the red checker safe. Recall an iterator only sees 1-move ahead at a time, and the values written are a function of the number of times a position is visited.

The correct winning move for red is 21-25! which can ignore 16-12? since that in turn loses to 25-22! which is a killer shot. It seems to throw away material pointlessly, but red wins after either 12x3 1-6! 18x25 6-10 14x7 2x11x18 and white to move loses in 28-ply, or 18x25 1-6 12x3 6-10 14x7 2x11x18.

So all this turmoil must first be examined, iteration after iteration, and we still don't have the optimal response for white to move after 21-25!

In chess endgames you don't have to deal with this.[/img]