Search Algorithm

[MichelG]

Quite amazing that white can legally play 39 moves without any capture! Do you still have the list of moves that plays that?

Here is another approach to computing a lower bound on the number of practical positions; consider all positions with no kings, with 12 black man and 12 white man. Every black man is in the area 1-25 and every white one is in 26-50. I think many 12vs12 position in gameplay would fall in this category.

There are {25!/(12!*13!)}^2=25 trillion of these positions already. About half of them will be capture positions but this will still leave some trillions of more or less regular positions. That's why i think creating a big midgame book won't work for now.

Michel

[BertTuyt]

Michel, the program does not record moves.

It was already a challenge to get to this result with 12G Memory.
It is however possible to print the end positions and share it with you if you want.
Also if you are interested i could forward to you the algorithm, it would be good if the results mentioned could be confirmed.

I agree with your math, but I'm not convinced yet that all positions could be realized in practice, and also i think that a fraction of it is only needed to assist the search (i call this Book Assisted Search). But that is all gut-feel, and not backed up by real evidence (so far).

I expect (but any other guess is also valid) that we might need 10^12 positions in the end to assist the search.
With 32 Bytes for a Book entry ( 3 * 8-byte Bitboards, and some other 8 bytes for score, depth, count, flags, or whatever) this yields 32 TeraByte.
I guess not totally out of reach in the next 10-20 years. And for calculations, you only need 1M cores, and with 30 second for each position, the search-job can be done in 1 year

In actual game play so far only 76K unique 20-20 positions have been played so far (based on the 1997 TurboDambase, so somewhat more these days).
But i dont expect that this value will dramatically increase even if we continue with Draughts for the next zillion of years.
So most 20-20 positions are most likely "not practical", and I will do some tests to better understand this.

I'm now doing some tests to check (with random game-play) if all 1-1 , 2-2 and 3-3 positions can be realized in practice.
And then i need to think about 12-12 to 16-16 positions as I agree with you that I expect there the bulk of positions.

Bert

[BertTuyt]

Herewith some graphs related to 20-20 positions.
Below a comparison of the theoretical maximum with the "actual" number derived from a TurboDambase file (1997).
The vertical axis is the log10 of positions, the horizontal axis the depth.

Interesting to see that at level 2, 79 positions are detected (the famous 81 - 2), as we also use in DXP matches (2 positions lead to an immediate loss of 1 man).

The next lines are presented in the graph (see also attached excel file).
- Blue line, cumulative theoretical maximum
- Red line, theoretical maximum for every depth ( so depth 0 = 1 (initial), depth 2 = 9, depth 3 = 81 ..... )
-Green line, cumulative position count based on Turbodambase (Mega1997.pd)
- Purple line, position count for every depth also based on TurboDambase.

Bert

[BertTuyt]

Herewith 1 of the 6 20-20 man positions at depth 77 (black to move).



The other 5 (including this one) in the doc attached.

Bert

[ildjarn]

I assume you don't have the moves that lead to this position?

[MichelG]

I expect (but any other guess is also valid) that we might need 10^12 positions in the end to assist the search.
With 32 Bytes for a Book entry ( 3 * 8-byte Bitboards, and some other 8 bytes for score, depth, count, flags, or whatever) this yields 32 TeraByte.
I guess not totally out of reach in the next 10-20 years. And for calculations, you only need 1M cores, and with 30 second for each position, the search-job can be done in 1 year

That no-capture position looks quite amazing

I have been thinking further on the midgame table, and i think it will become feasible the next 5-10 years. First the bad news: my current estimate suggests you need about 2*10^13 positions to dominate a program without such a table.

There are 2 different approaches:
1) The DOE approach: make a table of every position you encounter when white plays the best move and your opponent plays any move.
The problem with this is that you need a deep search on all of these trillions of positions
2) Make a table of any position you might encounter in a game, and precompute a shallow (0.1 millisecond) search of these positions. It's kind of endgame tablebases, but based on heuristics.

I think approach 2 will be easier. There is a detailed plan in my brain to make it, but hardware is not good enough yet to do it.

As for the storage requirements, you don't need 32 bytes to store a position. 4-8 bits should suffice with some methods. (e.g. endgame tables use less than a single bit/position) The challenge will be in generating 10^13 shallow searches and having enough ram in your computer to access it during the search.

Michel

[Rein Halbersma]

I assume you don't have the moves that lead to this position?

black's previous move was either 8-13 or 4-10, but other than that...

[BertTuyt]

I assume you don't have the moves that lead to this position?

black's previous move was either 8-13 or 4-10, but other than that...

Rein, in the position I provided, it is black turn.
I logged the positions which were created the last 2 iterations (for the others the number explodes).
The last 2 moves are 8-13 41-37 or 8-13 16-11

I need to re-think how I can extract the complete move-sequence...

Bert

[ildjarn]

black's previous move was either 8-13 or 4-10, but other than that...

Rein, in the position I provided, it is black turn.

Even with white moving last, black made a previous move too. And it must've been 8-13, because 9 couldn't get there with 3 and 4 both present.

[BertTuyt]

Code: Select all

 1. 35-30  16-21  
  2. 31-27  21-26  
  3. 27-21  17-22  
  4. 21-16  11-17  
  5. 32-28  22-27  
  6. 30-25  17-21  
  7. 37-32  19-24  
  8. 34-29  26-31  
  9. 28-23   6-11  
 10. 32-28  21-26  
 11. 40-34  11-17  
 12. 41-37  17-21  
 13. 28-22  24-30  
 14. 22-17  30-35  
 15. 33-28  13-19  
 16. 39-33  19-24  
 17. 28-22   9-13  
 18. 44-39  24-30  
 19. 17-11  35-40  
 20. 22-17  13-19  
 21. 33-28   4- 9  
 22. 11- 6  19-24  
 23. 38-33  18-22  
 24. 17-11  12-17  
 25. 43-38   9-13  
 26. 49-43  40-44  
 27. 23-18  13-19  
 28. 18-13  30-35  
 29. 37-32  35-40  
 30. 13- 9  24-30  
 31. 46-41  19-24  
 32. 41-37   8-12  
 33. 47-41  12-18  
 34. 28-23   7-12  
 35. 32-28   2- 8  
 36. 37-32  30-35  
 37. 11- 7  24-30  
 38. 16-11   8-13  
 39. 41-37

Bert

[Rein Halbersma]

Code: Select all

 1. 35-30  16-21  
  2. 31-27  21-26  
  3. 27-21  17-22  
  4. 21-16  11-17  
  5. 32-28  22-27  
  6. 30-25  17-21  
  7. 37-32  19-24  
  8. 34-29  26-31  
  9. 28-23   6-11  
 10. 32-28  21-26  
 11. 40-34  11-17  
 12. 41-37  17-21  
 13. 28-22  24-30  
 14. 22-17  30-35  
 15. 33-28  13-19  
 16. 39-33  19-24  
 17. 28-22   9-13  
 18. 44-39  24-30  
 19. 17-11  35-40  
 20. 22-17  13-19  
 21. 33-28   4- 9  
 22. 11- 6  19-24  
 23. 38-33  18-22  
 24. 17-11  12-17  
 25. 43-38   9-13  
 26. 49-43  40-44  
 27. 23-18  13-19  
 28. 18-13  30-35  
 29. 37-32  35-40  
 30. 13- 9  24-30  
 31. 46-41  19-24  
 32. 41-37   8-12  
 33. 47-41  12-18  
 34. 28-23   7-12  
 35. 32-28   2- 8  
 36. 37-32  30-35  
 37. 11- 7  24-30  
 38. 16-11   8-13  
 39. 41-37

Bert

Nice find, Bert, you should also post this in the general forum. I think problem composers would like it. I think there was also once a "curiosa" thread on this forum, where someone showed how both black and white could make 20 kings starting from the initial position. Took 389 moves.

[BertTuyt]

Rein, I dont post outside the computer forum .
But feel free to share it......

Bert

[ildjarn]

Bert,

Is it possible to find the deepest position that can be reached with a unique move sequence?

And: viewtopic.php?f=65&t=276&start=225#p99885

[BertTuyt]

Bert,

Is it possible to find the deepest position that can be reached with a unique move sequence?

And: viewtopic.php?f=65&t=276&start=225#p99885

Thanks for posting...

I think it is possible, however I dont have a simple algorithm which does not explode in time.
The result as posted is based on backtracking from the final positions (in total 6).
So basically I need to check if all moves are unique, and if not move to another position on the same depth.
And if all fail, than go to a ply lower level, ..........
I didn't gave it much more thoughts, so there might be a better and faster way.
If you want I can calculate which moves in the example presented are unique.

Bert

[BertTuyt]

As also posted before I am working with random games to determine if all end-games (like 1-1, 2-2, 3-3) are really possible.
Initially I observed asymptotic convergence in a too early stage, which most likely was related to the use of the C random function. For this reason I implemented the Mersenne Twister, which has a far better random reputation.
During these games (as an extra bonus) I also included the max capture so far encountered (see below output).
Interesting result was a 12-capture,which to my knowledge was not "constructed" from the initial opening so far.
Need to add some code to output the move-list for this ultra-capture( and to be sure that this isn't a bug , or whatever).

Will keep you posted,

Bert

Code: Select all

0.65 Perft, Game = 0, Depth = 0, XCapture = 0
 0.65 Perft, Game = 0, Depth = 1, XCapture = 0
 0.65 Perft, Game = 0, Depth = 2, XCapture = 0
 0.65 Perft, Game = 0, Depth = 3, XCapture = 0
 0.65 Perft, Game = 0, Depth = 4, XCapture = 0
 0.65 Perft, Game = 0, Depth = 5, XCapture = 0
 0.65 Perft, Game = 0, Depth = 6, XCapture = 0
 0.65 Perft, Game = 0, Depth = 7, XCapture = 0
 0.65 Perft, Game = 0, Depth = 8, XCapture = 1
 0.65 Perft, Game = 0, Depth = 9, XCapture = 1
 0.65 Perft, Game = 0, Depth = 10, XCapture = 1
 0.65 Perft, Game = 0, Depth = 11, XCapture = 1
 0.65 Perft, Game = 0, Depth = 15, XCapture = 1
 0.65 Perft, Game = 0, Depth = 17, XCapture = 2
 0.65 Perft, Game = 0, Depth = 19, XCapture = 2
 0.65 Perft, Game = 0, Depth = 28, XCapture = 2
 0.65 Perft, Game = 0, Depth = 46, XCapture = 2
 0.65 Perft, Game = 0, Depth = 58, XCapture = 2
 0.65 Perft, Game = 0, Depth = 60, XCapture = 2
 0.65 Perft, Game = 0, Depth = 70, XCapture = 2
 0.65 Perft, Game = 1, Depth = 37, XCapture = 4
 0.65 Perft, Game = 3, Depth = 45, XCapture = 4
 0.65 Perft, Game = 4, Depth = 48, XCapture = 4
 0.65 Perft, Game = 4, Depth = 56, XCapture = 4
 0.65 Perft, Game = 5, Depth = 71, XCapture = 5
 0.65 Perft, Game = 19, Depth = 65, XCapture = 5
 0.65 Perft, Game = 43, Depth = 59, XCapture = 6
 0.65 Perft, Game = 89, Depth = 56, XCapture = 6
 0.65 Perft, Game = 114, Depth = 55, XCapture = 6
 0.65 Perft, Game = 161, Depth = 41, XCapture = 6
 0.66 Perft, Game = 334, Depth = 67, XCapture = 6
 0.66 Perft, Game = 454, Depth = 55, XCapture = 6
 0.66 Perft, Game = 462, Depth = 60, XCapture = 6
 0.66 Perft, Game = 650, Depth = 54, XCapture = 6
 0.66 Perft, Game = 692, Depth = 110, XCapture = 6
 0.66 Perft, Game = 758, Depth = 44, XCapture = 6
 0.66 Perft, Game = 785, Depth = 57, XCapture = 6
 0.66 Perft, Game = 1069, Depth = 44, XCapture = 6
 0.67 Perft, Game = 1483, Depth = 66, XCapture = 6
 0.67 Perft, Game = 1511, Depth = 33, XCapture = 6
 0.67 Perft, Game = 1653, Depth = 72, XCapture = 6
 0.67 Perft, Game = 1852, Depth = 87, XCapture = 6
 0.67 Perft, Game = 1990, Depth = 72, XCapture = 6
 0.67 Perft, Game = 1997, Depth = 73, XCapture = 6
 0.68 Perft, Game = 2236, Depth = 43, XCapture = 6
 0.68 Perft, Game = 2359, Depth = 31, XCapture = 6
 0.68 Perft, Game = 2628, Depth = 25, XCapture = 6
 0.68 Perft, Game = 2729, Depth = 48, XCapture = 6
 0.68 Perft, Game = 2865, Depth = 69, XCapture = 7
 0.69 Perft, Game = 3229, Depth = 90, XCapture = 7
 0.69 Perft, Game = 3806, Depth = 58, XCapture = 7
 0.69 Perft, Game = 4057, Depth = 70, XCapture = 7
 0.71 Perft, Game = 5425, Depth = 45, XCapture = 7
 0.72 Perft, Game = 6543, Depth = 63, XCapture = 7
 0.72 Perft, Game = 6832, Depth = 45, XCapture = 8
 0.76 Perft, Game = 10902, Depth = 52, XCapture = 8
 0.94 Perft, Game = 29303, Depth = 69, XCapture = 8
 0.99 Perft, Game = 34189, Depth = 57, XCapture = 9
 1.20 Perft, Game = 54404, Depth = 39, XCapture = 9
 1.47 Perft, Game = 81838, Depth = 48, XCapture = 9
 1.59 Perft, Game = 93340, Depth = 46, XCapture = 9
 2.27 Perft, Game = 161370, Depth = 55, XCapture = 9
 2.33 Perft, Game = 166917, Depth = 51, XCapture = 9
 3.10 Perft, Game = 243397, Depth = 45, XCapture = 9
 3.11 Perft, Game = 244588, Depth = 93, XCapture = 9
 3.61 Perft, Game = 294296, Depth = 40, XCapture = 9
 4.06 Perft, Game = 339227, Depth = 74, XCapture = 9
 4.06 Perft, Game = 339457, Depth = 42, XCapture = 9
 6.68 Perft, Game = 601253, Depth = 54, XCapture = 9
 6.94 Perft, Game = 627570, Depth = 43, XCapture = 9
 7.16 Perft, Game = 649782, Depth = 53, XCapture = 9
 7.61 Perft, Game = 694238, Depth = 63, XCapture = 9
 7.72 Perft, Game = 705906, Depth = 52, XCapture = 9
 7.96 Perft, Game = 729633, Depth = 34, XCapture = 9
 8.50 Perft, Game = 783806, Depth = 83, XCapture = 9
 9.82 Perft, Game = 916422, Depth = 42, XCapture = 9
10.26 Perft, Game = 960501, Depth = 53, XCapture = 9
11.57 Perft, Game = 1091070, Depth = 79, XCapture = 9
11.61 Perft, Game = 1094598, Depth = 75, XCapture = 9
11.95 Perft, Game = 1129430, Depth = 78, XCapture = 9
13.21 Perft, Game = 1255417, Depth = 56, XCapture = 9
13.76 Perft, Game = 1310079, Depth = 63, XCapture = 9
14.45 Perft, Game = 1378698, Depth = 47, XCapture = 9
14.52 Perft, Game = 1385683, Depth = 76, XCapture = 10
21.17 Perft, Game = 2048509, Depth = 56, XCapture = 10
29.28 Perft, Game = 2858344, Depth = 49, XCapture = 10
39.56 Perft, Game = 3880021, Depth = 38, XCapture = 10
51.29 Perft, Game = 5051284, Depth = 57, XCapture = 11
152.98 Perft, Game = 15221492, Depth = 55, XCapture = 11
193.99 Perft, Game = 19315946, Depth = 88, XCapture = 11
290.67 Perft, Game = 28984924, Depth = 89, XCapture = 11
416.97 Perft, Game = 41594178, Depth = 57, XCapture = 11
551.36 Perft, Game = 55016018, Depth = 64, XCapture = 11
694.27 Perft, Game = 69323015, Depth = 53, XCapture = 11
704.89 Perft, Game = 70386589, Depth = 46, XCapture = 11
845.95 Perft, Game = 84498943, Depth = 72, XCapture = 11
914.10 Perft, Game = 91295952, Depth = 51, XCapture = 11
1256.99 Perft, Game = 125672441, Depth = 45, XCapture = 11
1392.57 Perft, Game = 139266081, Depth = 80, XCapture = 11
1410.71 Perft, Game = 141088376, Depth = 74, XCapture = 11
1489.59 Perft, Game = 148992927, Depth = 71, XCapture = 11
1596.11 Perft, Game = 159684573, Depth = 87, XCapture = 11
1618.93 Perft, Game = 161976180, Depth = 37, XCapture = 11
1623.75 Perft, Game = 162460710, Depth = 75, XCapture = 11
1665.77 Perft, Game = 166680333, Depth = 57, XCapture = 11
1858.41 Perft, Game = 185998335, Depth = 38, XCapture = 11
2299.06 Perft, Game = 230165822, Depth = 57, XCapture = 11
2364.03 Perft, Game = 236676185, Depth = 57, XCapture = 12
2441.26 Perft, Game = 244419684, Depth = 54, XCapture = 12
4255.84 Perft, Game = 426349593, Depth = 75, XCapture = 12
4727.14 Perft, Game = 473599913, Depth = 66, XCapture = 12
12980.64 Perft, Game = 1299733137, Depth = 77, XCapture = 12