Kirill Kryukov wrote:
I'm not sure I follow here - in the usual retrograde analysis solving whenever you find a win, it's the shortest win for that position. When we are looking for wins in N we know that all wins in N-1 are already found and marked. What do you mean by "improving" the win? Is it something specific to checkers?
In checkers, when you have a position that was unknown but now a move you try leads to a win, it is not guaranteed to be the fastest win. Therefore, the Distance To Win will not correspond to the iteration number, and, therefore, you must revisit the position several times over before determining its "true" distance to win.
If you look at some of the data in my report.txt file you see things like this:
Code: Select all
Sunday, January 17, 2010 @ 22:34:34
DB 5, slice 7, (global slice 48): iteration 5 completed.
********************************************************
wins resolved this pass = 318705, losses resolved this pass = 29, draws resolved this pass = 1057.
win lengths improved this pass = 224711, loss lengths that changed this pass = 0.
total move pass wins = 2300954, total move pass losses = 713, total move pass draws = 70640.
cumulative win lengths improved = 574989, cumulative loss lengths that changed = 0.
In checkers, win lengths can be improved. Loss lengths can change as well. For this reason, it is possible to have your solver "loop forever" if you are not careful.
A diagram will show why this is the case.
From the position shown above, suppose it is examined for the first time. That is, the pieces were just placed on these squares, and the position is currently unknown. Let's say it is white to move. The white checker is one move away from crowning and becoming a king. It can crown onto 2 different squares, and both of those positions would be in the "2 kings vs. 1 king" database, which was already solved. The result can be queried, and sure enough, white wins, since red to move would lose in each case. White would then chose which move wins most quickly.
The move 8-4 leads to a red loss in 24 plies, so white appears to win in 25 plies.
The move 8-3 leads to a red loss in 24 plies also, so white thinks the position wins in 25 plies.
Next, the move 14-10 is tried. This move leads to the red king being jumped, easy enough for a human to see. But, on this first iteration, it will remain unknown. Why? The position for the other side to move after 14-10 has not been solved yet. It takes two iterations to resolve a win in 3 plies, and 14-10 is a win in 3 plies.
So, after this first iteration, the position is saved as a white win in 25 plies.
On the second iteration, it will be red to move. The position with the king on square 10 (instead of 14) will be set up. The red moves 2-7 would lead to a losing jump, as would 2-6, so that position can be resolved as a loss in 2 plies.
On the third iteration, the position in the diagram is reached. This time, when 14-10 is generated, the position is now known to be a 2-ply loss for red. The program can therefore change the status from "win in 25" to "win in 3."
Kirill Kryukov wrote:How large (approximatelhy, in number of positions) can be the largest single table in 10-piece checkers, 11-piece, 12-piece (if you know)?
The largest slice is typically the arrangement that has 1 fewer checker than "perfect symmetry" for at least half of the pieces being kings. Sometimes it is the most symmetrical arrangement with equal numbers of kings.
For the 10-piece database, one side has 5 pieces. If "at least half" were kings, it would be 3 kings + 2 checkers vs. 3 kings + 2 checkers for "perfect symmetry." For the distribution with 1 less checker for one side, it would be the slice with 3 kings + 2 checkers vs. 2 kings + 3 checkers.
How many positions are there?
(# of 3 checkers vs. 2 checkers positions) * (27 choose 3) * (24 choose 2) = (1018056)(2925)(276) = 821 876 608 800
Fortunately this number also matches Dr. Schaeffer's
http://webdocs.cs.ualberta.ca/~chinook/ ... piece.html
Look for the listing "3223" for this result.
For 11-pieces, 3 kings + 3 checkers vs. 3 kings + 2 checkers = 6 027 095 131 200
For 12-pieces, 3 kings + 3 checkers vs. 3 kings + 3 checkers = 36 652 173 958 400
Kirill Kryukov wrote:I tried the caching idea similar to what you describe. It performs great when the available RAM is slightly smaller than the actual amount required to keep the table being solved + required sub-tables. However when the difference becomes larger, solving slows down intolerably due to always needing new blocks from the disk. Perhaps you found some improvement.
Yes, I did. The improvement was in the area of "locality of reference", which describes how "far away" your "next" block is, compared to the one most recently accessed. I redesigned my indexing function to improve the locality of reference, so each time a piece "moves" the resulting index won't jump too far away. It took a lot of experimentation to do this, and even more math! But it was fun, and it made it worth it.