The full 8-piece draughts database is finished.

[Ed Gilbert]

Yesterday I finished building and verifying the 8-piece draughts WLD and MTC databases. More details are here: http://pages.prodigy.net/eyg/Checkers/8 ... hts_db.htm.

-- Ed

[FeikeBoomstra]

Congratulations,

Feike

[Ed Gilbert]

To exercise the new db, I set up this well known position from a Woldouby game last night, played white's best move 34-29 and the two forced captures, and then let it search overnight from there.

[FEN "W:W25,27,28,30,32,33,34,35,37,38:B12,13,14,16,18,19,21,23,24,26."]
1. 34-29 23x34 2. 30x39

This morning 8 hours later the search is returning a database draw. I had some time ago determined this position is a draw by playing down all the possible variations until a database result could be seen, but I was never before able to see the draw on a single search from this start position (although I'm not entirely sure that I had tried a search as long as 8 hours using the 'incomplete' databases).

-- Ed

[TAILLE]

Congratulation Ed., very good result endeed.
Now you will have a well-known and interesting problem to solve : how will you play a position for which you found a 8 pieces db draw ?
Gérard

[wellnesswrotter]

Isn't this simple?
The move that will gives the best chances to win, but will not lose.

[BertTuyt]

Ed, congratulations.

A new milestone in computer Draughts.
im still stuck at 7p generation, 5m - 2m only 1 single instance, as my program requires to much memory.

Thats basically my main question, which i will start to study in more detail during my vacation break.
im now in the process of changing my dbgenerate into a multicore program. im not sure but i prefer a parallel program over programs in parallel, mainly due to the fact that memory sharing could be much better.

To what extend it will scale with increasing cores remains to be seen.
Also with new developments on the way like 8 core 16-thread CPU's or 80-core gpu's where every core can run a different program (think it is called larabee but im not 100% sure).

I would like the opinion of the others here, what the most likely path forward is.

But in the mean time, I have deep respect for Ed's achievement.

Bert

[TAILLE]

Hi,

Isn't this simple?
The move that will gives the best chances to win, but will not lose.

I understand what a "not losing move" is but what do you mean by "the move that gives the best chances to win" ?

For a computer it is not a easy question.



Let's suppose a program having the 40 pieces endgame database and let's suppose that any of the 9 possible white moves leads to a draw. Which move will you choose ? The only chance to win is certainly to play 31-27 or 32-27 hoping black will play 16-21?? which, I suppose, will lead to a win for white
As you see this approach is a very poor way to play and such program will certainly never lose but also will almost never win!

What does mean "the best chance to win" for a program ?

[wellnesswrotter]

the best chance to win is to take variants of moves in where the opponent can make (difficult) mistakes

[TAILLE]

the best chance to win is to take variants of moves in where the opponent can make (difficult) mistakes

I agree entirely and the difficulty is then to recognise when the opponent can make a (difficult) mistake. The corresponding algorithm is not so easy to build and that is really my point.

Gérard

[Wieger Wesselink]

Congratulations Ed with this great achievement!

Although it's not that important, it might be that you are not the first one to have completed the 8 piece database. Long time ago two people working at at CWI (the dutch center for math and computer science) have used the spare cycles of a super computer to compute the 6 piece database. One of them was a draughts player, and the other a chess player. The latter one asked me to send him some positions to verify the result, and based on that I'm quite sure they were the first ones to complete the 6 piece database.

About 5 years ago I met this chess player again at my work, and then he claimed to have used the same program to compute the 8 piece database. But he only did this for testing purposes, and he never bothered to make the database available, although I tried to convince him to do so.

[Ed Gilbert]

Hi Gerard,

Now you will have a well-known and interesting problem to solve : how will you play a position for which you found a 8 pieces db draw ?

At the moment kingsrow does not distinguish between an 'easy' draw and a 'hard' draw. This is good for seach efficiency because a database draw generates an immediate cutoff, freeing cpu resources to search other non-drawing lines more deeply. OTOH you are right that it can result in not playing the most challenging game in drawn endgames. I think a simple improvement would be to use the heuristic eval to score database draws, but scale the values to perhaps a range of -3,-2,-1,0,1,2,3. Also, I might be wrong, but having observed very many automated games against programs with smaller databases, I don't see the present approach as causing kingsrow to miss very many winning opportunities. I think the best one could do would only have a small affect on match results. I could easily test this assumption using some long matches against Truus.

-- Ed

[Ed Gilbert]

Hi Weiger,

About 5 years ago I met this chess player again at my work, and then he claimed to have used the same program to compute the 8 piece database. But he only did this for testing purposes, and he never bothered to make the database available, although I tried to convince him to do so.

I expect that just having the databases by themselves is not very useful. You can lookup the value of some 8 piece positions but there is not a great deal of value in that. It's only when you couple the dbs with a strong program that you get to appreciate their full power.

Distributing large databases is something I have been doing for English checkers, and it is a bit of a PITA. I'm not surprised that someone wouldn't want to do it.

-- Ed

[Ed Gilbert]

Hi Bert,

Thats basically my main question, which i will start to study in more detail during my vacation break.
im now in the process of changing my dbgenerate into a multicore program. im not sure but i prefer a parallel program over programs in parallel, mainly due to the fact that memory sharing could be much better.

Of course either method should work. A nice advantage of running multiple instances of a single-threaded program is that you are not restricted to running it on one computer. In your case, for example, you have two quad core computers (I assume, unless you got rid of the Q6600 when you bought the I7), so you already have plenty of horsepower to build the 8pc db in just a few months. I will of course share the WLD counts with you and anyone else that needs them, and so you can skip the very time consuming self verify process.

-- Ed

[Ed Gilbert]

The position below has the longest moves to conversion of any in the 8-piece database. It is a black win (ignoring the 25-move rule), but if white defends correctly it requires 149 half-moves before a conversion move can occur. Along with the position I have pasted the correct moves to play at each turn, up to the first conversion move. I have noted in the few places where there is more than one possible correct move. If black plays anything other than the moves given, he either allows white to draw, or he allows it to move a greater distance from converting. If white deviates then it allows a conversion to occur in less than the maximum possible moves.

I cannot imagine that any human player can understand these moves. Even the kingsrow program makes many mistakes playing this out, either as white or black, if it is not permitted to use the 8-piece database. I view this position as being about as close as one can get to a drawn position without being a draw (again ignoring the 25-move rule).

-- Ed

[FEN "B:WK1,K7,48:BK8,15,K18,22,K33."]
18-4 2. 7-2 8-35 3. 2-16 35-44 4. 16-49 44-50 5. 1-12 33-24 6. 49-16 24-20 7. 16-49 20-3 8. 12-26 4-18 9. 26-37 3-26 10. 37-41 {37-14 equally good} 50-39 11. 41-19 {41-14 equally good} 39-25 12. 19-32 18-7 13. 49-35 26-3 14. 32-41 7-29 15. 41-32 25-39 16. 32-41 29-18 17. 35-49 3-25 18. 41-47 39-28 19. 47-24 {47-42 equally good} 25-3 20. 24-42 3-26 21. 42-24 18-9 22. 49-16 {24-2 and 24-35 equally good} 28-50 23. 16-49 9-20 24. 24-19 20-47 {26-31 equally good} 25. 19-14 26-3 26. 14-46 47-36 {3-25 equally good} 27. 46-37 50-45 28. 37-19 36-47 {45-1 equally good} 29. 19-30 45-1 30. 30-19 3-26 31. 19-14 47-36 32. 14-19 1-29 {1-7 equally good} 33. 19-32 {19-2 equally good} 29-7 34. 32-16 7-23 35. 16-2 23-46 36. 2-11 46-28 37. 11-2 26-17 38. 2-24 17-11 39. 24-42 11-2 40. 42-26 28-33 41. 49-16 33-47 42. 16-49 47-20 {47-29 equally good} 43. 26-3 20-33 44. 3-26 2-35 45. 49-32 33-29 {33-24 equally good} 46. 32-16 29-47 47. 16-49 47-20 48. 26-3 20-33 49. 49-16 33-28 50. 3-26 28-46 51. 16-49 46-5 52. 49-16 35-2 53. 26-12 5-37 54. 12-45 37-28 55. 45-50 {16-49 equally good} 2-30 56. 50-45 30-25 57. 45-40 25-3 58. 40-49 3-8 59. 49-43 {49-35 equally good} 8-2 {36-47 equally good} 60. 43-21 {43-34, 43-49, and 43-25 equally good} 36-47 61. 21-12 {21-3 equally good} 28-50 62. 12-26 47-20 63. 16-49 2-35 64. 49-16 50-45 65. 26-3 20-47 66. 3-26 47-24 67. 16-49 24-20 68. 26-3 20-25 69. 3-26 45-1 70. 26-37 25-20 {1-6 and 1-7 equally good} 71. 37-46 {37-5 equally good} 1-6 {20-47 equally good}
{At this point the MTC database does not have data for the next few moves because the depth to the next conversion is small. The remaining moves were determined by a search using heuristics. The heuristics consider more than just the distance to conversion so they are not optimal for that metric.}
72. 49-21 20-47 73. 21-3 22-27