Search Algorithm

[BertTuyt]

Below a 12-man capture in one of the zillion of random games .

Bert

Code: Select all

1. 34-30  18-23  
  2. 32-28  23x32  
  3. 38x27  20-24  
  4. 42-38  17-21  
  5. 40-34  21x32  
  6. 38x27  16-21  
  7. 27x16  15-20  
  8. 45-40  19-23  
  9. 30x28  13-19  
 10. 33-29  12-18  
 11. 29-24  19x30  
 12. 35x15   8-12  
 13. 34-30  11-17  
 14. 31-26   6-11  
 15. 40-34   3- 8  
 16. 50-45  17-22  
 17. 28x 6  18-23  
 18. 26-21   8-13  
 19. 30-24   7-11  
 20.  6x28   1- 7  
 21. 43-38   9-13  
 22. 37-32  13-18  
 23. 38-33  14-19  
 24. 24x22   4- 9  
 25. 15x13   5-10  
 26. 49-43   7-12  
 27. 36-31  10-15  
 28. 47-42   2- 7  
 29. 16-11  

[Rein Halbersma]

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

If you also impose some reasonable left/right balance constraint (e.g. 6 pieces left and right), you get (13! / (6! 7!))^2 * (12! / (6!)^2)^2 = 2.5 e12, so factor of 10 smaller. And if you continue down to a 7x7 database with left/right balance + own terrain, you have only 24e9 positions. Now that might be within reach now.

[Walter]

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

If you also impose some reasonable left/right balance constraint (e.g. 6 pieces left and right), you get (13! / (6! 7!))^2 * (12! / (6!)^2)^2 = 2.5 e12, so factor of 10 smaller. And if you continue down to a 7x7 database with left/right balance + own terrain, you have only 24e9 positions. Now that might be within reach now.

I am not too sure about own terrain as a constraint. For instance, all attacking positions with a white piece on 24 or a black piece on 27 would be excluded. In classical positions a white piece on 25 or black piece on 26 are common, but would be excluded. Of course you can make exceptions for such common positions but that would increase the number of positions again! To overcome this problem it could be useful to use tempi and tempi balance as additional constraints.

For instance, for 12x12 the absolute min tempi would be 21 (e.g. black pieces on 1-10 and two on row 11-15). That is not a very likely practical position. Combined with a tempi difference of +2 that would force all white pieces to be in a fairly similar position at the opposite end. Even more unlikely.

With 8 pieces the '30-stelling' (27,28,32,33,34,37,39,44) is considered an excellent placement of the pieces. So you could slice the problem by generating partial databases for all positions with a white tempi / black tempi = 30/30, then 30/29, then 30/28, then 31/30, then 32/30 etc.

Maybe from the Turbodambase database some reasonable tempi boundaries can be determined for 7x7, 8x8, 9x9 etc.?

Walter

[MichelG]

I think you can indeed limit the list of positions by finding some statistical useful properties of the positions.

Tempo and left right balance are good examples, and there may be more. (common patterns) These properties can be determened by random gameplay.

Basically, with current technology, you can work your ways up from 5-5 to 8-8 and from 20-20 down to 18-18. The middle game area, with between 18 and 35 pieces on the board will be the hardest though, but they will also be the most useful.

If (ram) memories keep increasing, eventually this will create draughts programs so strong to the point they are very unlikely to ever lose again. [and all games will be draw...]

Michel

[BertTuyt]

After the theoretical exercise to determine the maximum number of 20-20 positions (which was around 3G ), I have played a short ( 89 games) DXP Match against Kingsrow (10 min game each side).
In Damage i have now re-implemented a "learn" function which can store unique positions.
After the 89 games Damage had found around 4.6M unique 20-20 positions (so basically I could stop the DXP game after 1 capture, but it is always interesting to observe such a match).
Damage did not use a opening-book.

I dont believe that this figure of 4.6M will dramatically explode (maybe 10M as a max?) , as I believe to already see some first signs of saturation.
So considering the permutation/combination figure where I started with of around 10^19, the real (still to be proven) value of 3G, and now the actual number of nodes encountered of 4M-5M.
I also believe that the only interesting nodes/positions which need to be kept to have an impact, is the non-capture positions, and where the static evaluation is significant different from a dynamic search.

It might be that in the end "only" 100K (or something like that) 20-20 positions are really required.
But as stated before the real interesting area is most likely 8 - 12 man each.......

Bert

[Rein Halbersma]

I think you can indeed limit the list of positions by finding some statistical useful properties of the positions.

Tempo and left right balance are good examples, and there may be more. (common patterns) These properties can be determened by random gameplay.

Basically, with current technology, you can work your ways up from 5-5 to 8-8 and from 20-20 down to 18-18. The middle game area, with between 18 and 35 pieces on the board will be the hardest though, but they will also be the most useful.

If (ram) memories keep increasing, eventually this will create draughts programs so strong to the point they are very unlikely to ever lose again. [and all games will be draw...]

Michel

with Killer draughts the margin for error is much smaller, I don't expect flawless play there to be as easy to achieve as in regular draughts

[Walter]

Basically, with current technology, you can work your ways up from 5-5 to 8-8 and from 20-20 down to 18-18.

Michel

In combination with search you might not have to do them all to get a measurable impact on engine strength. The relatively small number of 4M-5M unique 20x20 positions that Bert reported for his match must be related to the natural reduction of the number of men during the game. So generating a 20x20 database might be unnecessay if you can assume the search in 20x20 positions will be deep enough for most leaf nodes that need to be evaluated to be in the 19x19 database. Hence, you might skip a 20x20 database and only build a 19x19 database. I guess that a reduction in men can assumed to occur within about 10 plies. So if the search can be assumed to reach about 20 plies within reasonable time, then you might want to skip the 18x18 database and only build a 17x17 database etc.

I think that 5x5 is in the near term reach of endgame databases. Again, it might be unnecessary to generate a 6x6 database if the search in 7x7 positions would normally hit the 5x5 endgame database with high frequency.

All in all with constraints on the number of positions such a left/right balance, tempi, tempi difference and skipping some database based on the search depth it should be possible to generate midgame databases that increase the engine strength.

Ps. I agree with Rein that for computer draughts (and less urgently human draughts) to remain interesting we would have to move to Killerdraughts soon.

Ps. Bert was asking for 1 million cores. The new Chinese Tianhe 2 supercomputer has 3,120,000 cores (384,000 Ivy Bridge + 2,736,000 Xeon Phi cores). Maybe if interest in draughts continues to grow in China Bert can borrow their machine for a few months.

Regards,
Walter

[BertTuyt]

So after 81 games 36.5M unique 19-19 positions in a match against Kingsrow.
Think this number will further increase, so I think I will modify the learn function to stop a DXP-games if a minimum piece-count is reached, and continue to 158 games.
For those interested, game time was 10 min, and 1 core only.

Match result (perspective Damage) 5 win, 1 lost, 75 draw.
Attached the pdn file.

Bert

[BertTuyt]

Herewith an overview of unique X-X positions (20-20 --> 10-10) ""found" during DXP games against Kingsrow.
Damage took 10 seconds search-time for every move.
The game was stopped when the material was not sufficient to add more X-X positions.
On the horizontal axis number of games, vertical number of positions ( so maximum between 50M - 60M ).

I thing this graph might contains some interesting clues......
Although due to the limited games & positions one should be careful with preliminary conclusions.

I'm also preparing a .xls file with all the underlying data (and more.. )

Bert

LearnX_10s.png (36.85 KiB) Viewed 8923 times

[MichelG]

Herewith an overview of unique X-X positions (20-20 --> 10-10) ""found" during DXP games against Kingsrow.
Damage took 10 seconds search-time for every move.
The game was stopped when the material was not sufficient to add more X-X positions.
On the horizontal axis number of games, vertical number of positions ( so maximum between 50M - 60M ).

I thing this graph might contains some interesting clues......
Although due to the limited games & positions one should be careful with preliminary conclusions.

I'm also preparing a .xls file with all the underlying data (and more.. )

Bert

Those graphs don't look like they are reaching a saturation point soon...

What you really want to know is how big a hashtable you need in order to hit it frequently. I am working on that right now and i will provide an accurate value for that later.

At the moment, extrapolation of early results indicate that for noncapture, 15 man vs 15 man, you need only 4 billion positions in your table to reach a 63% hitrate. (1-1/e = 1-1/2.71828 = 63%) I think is a surprisingly low number.

It is based on random sampling of about 10 million games and a database of 2 billion positions.

[Rein Halbersma]

Those graphs don't look like they are reaching a saturation point soon...

What you really want to know is how big a hashtable you need in order to hit it frequently. I am working on that right now and i will provide an accurate value for that later.

At the moment, extrapolation of early results indicate that for noncapture, 15 man vs 15 man, you need only 4 billion positions in your table to reach a 63% hitrate. (1-1/e = 1-1/2.71828 = 63%) I think is a surprisingly low number.

It is based on random sampling of about 10 million games and a database of 2 billion positions.

Creating the hash table should not be the problem, filling it with useful information seems much harder. You need 34 * N core years if you want to search 2 billion positions for N seconds each. Even with 12 cores it takes 3 years to fill such a hash table with 1 second searches. You also will need some serious cluster to get anywhere.

[BertTuyt]

Those graphs don't look like they are reaching a saturation point soon...

What you really want to know is how big a hashtable you need in order to hit it frequently. I am working on that right now and i will provide an accurate value for that later.

At the moment, extrapolation of early results indicate that for noncapture, 15 man vs 15 man, you need only 4 billion positions in your table to reach a 63% hitrate. (1-1/e = 1-1/2.71828 = 63%) I think is a surprisingly low number.

It is based on random sampling of about 10 million games and a database of 2 billion positions.

Creating the hash table should not be the problem, filling it with useful information seems much harder. You need 34 * N core years if you want to search 2 billion positions for N seconds each. Even with 12 cores it takes 3 years to fill such a hash table with 1 second searches. You also will need some serious cluster to get anywhere.

Rein, with 31.560.000 seconds a year ( 365 * 24 * 60 * 60 ), i think it should be around 64 core-years for every search-second based on 2.000.000.000 positions .

I guess this would be abolutely doable, if we split the work amongst the Draughts computer programmers...

For me the most important thing to prove (or to make plausible) is the assumption which we discussed the last weeks(s) , that the actual number of Draughts board postions is much smaller than we thought before, and the practical number which you need to really improve programs (or as Michel stated to realize a high hash hit-rate) is even an order of magnitude lower than that.

It might be not practicale in the next 5 years, but it migth provide a roadmap for the longer term future.

Im also working on random games and hash-hit-rates (as Michel posted), and I will also share some findings this week.

Bert

[Rein Halbersma]

Rein, with 31.560.000 seconds a year ( 365 * 24 * 60 * 60 ), i think it should be around 64 core-years for every search-second based on 2.000.000.000 positions .

em, yes, off-by-factor-of-two here. I wrote 2^30 / (365 * 24 * 60 * 60) in my calculator, instead of 2^31.

[Walter]

Rein, with 31.560.000 seconds a year ( 365 * 24 * 60 * 60 ), i think it should be around 64 core-years for every search-second based on 2.000.000.000 positions .

em, yes, off-by-factor-of-two here. I wrote 2^30 / (365 * 24 * 60 * 60) in my calculator, instead of 2^31.

Instead of a fixed x-seconds (or x-depth) search you could attempt to make this dynamic based on hit rate. You could start with calculating the static evaluation value for each of the 2.000.000.000 positions. After that every position that gets actually hit might be flagged as work for the 1 second search to improve the evaluation accuracy. If a position has been hit 100 times, then it might be flagged as work for a 10 seconds search to improve the evalution score further.

[MichelG]

Instead of a fixed x-seconds (or x-depth) search you could attempt to make this dynamic based on hit rate. You could start with calculating the static evaluation value for each of the 2.000.000.000 positions. After that every position that gets actually hit might be flagged as work for the 1 second search to improve the evaluation accuracy. If a position has been hit 100 times, then it might be flagged as work for a 10 seconds search to improve the evalution score further.

Finding the required hashtable size proves harder to find than i thought. The problem is that the samples from the random games seem not as random as i would like. Other methods point to about 50-100 billion positions for 15vs15. I'll try and investigate more.

Anyway, with estimates between 4 and 100 billion (and that's 15v15 only!), 1 second searches are not going to be realistic unless you borrow Bert's 1 million core computer for a while Maybe you can set your GPU to work though.

Michel