EGTB value

[bob]

...my intent is going to be to remove all the EGTB code since it is not providing any Elo boost, unless I happen to find some setting/limit that does improve results.

I just don't believe that only probing at root can do anything but help. Maybe you should start at that end.

The problem is you are already "there". We would prefer to search a large tree and choose the path that takes us to a win, vs to a draw. As you reduce that tree, you reduce your ability to have lots of choices. You might win one game extra out of a thousand, maybe. But that's not going to be an elo-booster.

Here's the current results using no egtbs (23.4) vs egtbs + probe up to max iteration depth, but not beyond (extensions drive the search much deeper than this):

Code: Select all

    Crafty-23.4R09       2620    4    4 17616   54%  2593   27% 
    Crafty-23.4          2619    4    4 17611   54%  2593   27% 

[Dirt]

...my intent is going to be to remove all the EGTB code since it is not providing any Elo boost, unless I happen to find some setting/limit that does improve results.

I just don't believe that only probing at root can do anything but help. Maybe you should start at that end.

The problem is you are already "there". We would prefer to search a large tree and choose the path that takes us to a win, vs to a draw. As you reduce that tree, you reduce your ability to have lots of choices. You might win one game extra out of a thousand, maybe. But that's not going to be an elo-booster.

Here's the current results using no egtbs (23.4) vs egtbs + probe up to max iteration depth, but not beyond (extensions drive the search much deeper than this):

Code: Select all

    Crafty-23.4R09       2620    4    4 17616   54%  2593   27% 
    Crafty-23.4          2619    4    4 17611   54%  2593   27% 

I don't trust my intuition that much. It might be one in a thousand, but that would show up in your testing. It might be more or less, though. Have you ever tested it?

[Dann Corbit]

Since we probe Nalimov compressed files randomly, on disks, I don't see why the same idea would not work for bitbases, and thought that was already done. Only issue is the computational cost of the decompression. If you take a typical EGTB that has only 1 byte values, you should be able to compress a 1.5 bit value (w/l/d) and get maybe 5 of those in a byte. So doing some ugly rounding, our 7.5 gigs of 3-4-5 piece Nalimov tables turns into maybe 1.5g of bitbase data? In theory this might compress better, I am not sure. 1gb is certainly doable. And I was thinking that current bitbase implementations were already doing this, but I am not sure.

Certainly one can easily derive a full set of bitbase values from the Nalimov files, rather than having to generate them...

You could start with Nalimov 5-men and derive bitbases from them, I don't think there's any problems with the 50-move rule in those. If I were doing it myself I'd want to write my own DTZ50 generator first (which is probably why I've been thinking about it for at least 10 years and still havent done it...) Once you have the bitbases, the interesting research project would be to figure out how to represent them more cheaply.

By "less entropy", I meant that the DTM / DTC / DTZ50 databases consist of entries like "Win in 21", "Win in 17", "Win in 41", "Win in 20", "Win in 19", "Draw", "Draw", "Lose in 4", "Win in 36", "Draw" ....

And the matching bitbase would contain: W,W,W,W,W,D,D,L,W,D, ...
So its probably easier to compress.

Especially if you can get that 1.5 bits down to 1 bit for some of them: "Win" and "Everything else" then use some smaller secondary lookup to figure out the everything else. Secondary lookups on disk are too slow, but if the whole thing fits in RAM it would be fine.

Darkthought had 4-man bitbases in about 15 MB, *uncompressed*. Of course a full set of 5-man bitbases would be much bigger, but if you had a good compressed representation supporting random access, setting aside a big chunk of ram to cache them (like 500+ MB) might be reasonable.

You do not want to compress bitbases in memory because it takes time to decompress a block just to pick one entry. And you do not want to have them all in memory, because that memory is more useful to be used as hashtable. IMHO, the best solution is to have them uncompressed in an efficient cache. It is also a waste to have bitbases and tablebases. But if you cache the EGTB info as bitbase information, you accomplished the goals of both formats. In addition, having a common interface, allows you to solve some positions with just heuristics, saving huge amount of time of HD access. This is the philosophy of the Gaviota format.

Miguel

Perhaps order preserving compression can be of some use.
http://portal.acm.org/citation.cfm?id=653274

[michiguel]

Since we probe Nalimov compressed files randomly, on disks, I don't see why the same idea would not work for bitbases, and thought that was already done. Only issue is the computational cost of the decompression. If you take a typical EGTB that has only 1 byte values, you should be able to compress a 1.5 bit value (w/l/d) and get maybe 5 of those in a byte. So doing some ugly rounding, our 7.5 gigs of 3-4-5 piece Nalimov tables turns into maybe 1.5g of bitbase data? In theory this might compress better, I am not sure. 1gb is certainly doable. And I was thinking that current bitbase implementations were already doing this, but I am not sure.

Certainly one can easily derive a full set of bitbase values from the Nalimov files, rather than having to generate them...

You could start with Nalimov 5-men and derive bitbases from them, I don't think there's any problems with the 50-move rule in those. If I were doing it myself I'd want to write my own DTZ50 generator first (which is probably why I've been thinking about it for at least 10 years and still havent done it...) Once you have the bitbases, the interesting research project would be to figure out how to represent them more cheaply.

By "less entropy", I meant that the DTM / DTC / DTZ50 databases consist of entries like "Win in 21", "Win in 17", "Win in 41", "Win in 20", "Win in 19", "Draw", "Draw", "Lose in 4", "Win in 36", "Draw" ....

And the matching bitbase would contain: W,W,W,W,W,D,D,L,W,D, ...
So its probably easier to compress.

Especially if you can get that 1.5 bits down to 1 bit for some of them: "Win" and "Everything else" then use some smaller secondary lookup to figure out the everything else. Secondary lookups on disk are too slow, but if the whole thing fits in RAM it would be fine.

Darkthought had 4-man bitbases in about 15 MB, *uncompressed*. Of course a full set of 5-man bitbases would be much bigger, but if you had a good compressed representation supporting random access, setting aside a big chunk of ram to cache them (like 500+ MB) might be reasonable.

You do not want to compress bitbases in memory because it takes time to decompress a block just to pick one entry. And you do not want to have them all in memory, because that memory is more useful to be used as hashtable. IMHO, the best solution is to have them uncompressed in an efficient cache. It is also a waste to have bitbases and tablebases. But if you cache the EGTB info as bitbase information, you accomplished the goals of both formats. In addition, having a common interface, allows you to solve some positions with just heuristics, saving huge amount of time of HD access. This is the philosophy of the Gaviota format.

Miguel

Perhaps order preserving compression can be of some use.
http://portal.acm.org/citation.cfm?id=653274

Thanks, I saved it and I will read it.

Miguel

[bob]

...my intent is going to be to remove all the EGTB code since it is not providing any Elo boost, unless I happen to find some setting/limit that does improve results.

I just don't believe that only probing at root can do anything but help. Maybe you should start at that end.

The problem is you are already "there". We would prefer to search a large tree and choose the path that takes us to a win, vs to a draw. As you reduce that tree, you reduce your ability to have lots of choices. You might win one game extra out of a thousand, maybe. But that's not going to be an elo-booster.

Here's the current results using no egtbs (23.4) vs egtbs + probe up to max iteration depth, but not beyond (extensions drive the search much deeper than this):

Code: Select all

    Crafty-23.4R09       2620    4    4 17616   54%  2593   27% 
    Crafty-23.4          2619    4    4 17611   54%  2593   27% 

I don't trust my intuition that much. It might be one in a thousand, but that would show up in your testing. It might be more or less, though. Have you ever tested it?

No. The reason I don't like the idea is that you are either in the EGTB or not, you don't have any say-so about how you get in, you can just accept the score you get by playing one of the root moves, or else choose to play a root move that is not a capture so that you don't reach an EGTB position. Not much flexibility.

[bob]

I stopped the previous test after over 17,000 games per version, with identical Elos at that point. I have started a test with a version that only probes when ply <= iteration_depth>>1, (or ply <= iteration_depth / 2).

so far:

Code: Select all

   2 Crafty-23.4R09       2616    4    4 17890   54%  2590   27% 
   3 Crafty-23.4R10       2616   10   10  2770   54%  2592   28% 
   4 Crafty-23.4          2616    4    4 17895   54%  2590   27% 

[bob]

Another update. Looks like the probing below iteration-depth / 2 is no improvement nor no worse:

Code: Select all

   2 Crafty-23.4R09       2616    4    4 17890   54%  2590   27% 
   3 Crafty-23.4          2616    4    4 17895   54%  2590   27% 
   4 Crafty-23.4R10       2615    6    6  7187   54%  2590   27% 

R10 only probes if ply <= iteration_depth / 2

Looks like no significant difference between any of 'em

I may run some 10m+10s games for a final confirmation, but my conclusion, at least for Crafty, is that EGTBs have no significant effect, good or bad... Will try to experiment with bitbases next...

[Dann Corbit]

Another update. Looks like the probing below iteration-depth / 2 is no improvement nor no worse:

Code: Select all

   2 Crafty-23.4R09       2616    4    4 17890   54%  2590   27% 
   3 Crafty-23.4          2616    4    4 17895   54%  2590   27% 
   4 Crafty-23.4R10       2615    6    6  7187   54%  2590   27% 

R10 only probes if ply <= iteration_depth / 2

Looks like no significant difference between any of 'em

I may run some 10m+10s games for a final confirmation, but my conclusion, at least for Crafty, is that EGTBs have no significant effect, good or bad... Will try to experiment with bitbases next...

This is in line with every other experiment I have ever seen.

I do expect you will see a boost in Elo from bitbases.

I would ask you not to simply remove the EGTB support, though. It is very useful for special analysis purposes. Since there is no harm to it either, it seems to be neutral in effect. There is value for the end users in that they can get perfect analysis for difficult (for us humans) endgame positions.

As an example, thorough analysis of difficult MES positions with EGTB support is more likely to produce a correct analysis than without the support. So, even though crafty may not play with more strength, it still makes crafty a more useful tool for certain special purpose tasks.

[jwes]

...my intent is going to be to remove all the EGTB code since it is not providing any Elo boost, unless I happen to find some setting/limit that does improve results.

I just don't believe that only probing at root can do anything but help. Maybe you should start at that end.

The problem is you are already "there". We would prefer to search a large tree and choose the path that takes us to a win, vs to a draw. As you reduce that tree, you reduce your ability to have lots of choices. You might win one game extra out of a thousand, maybe. But that's not going to be an elo-booster.

Here's the current results using no egtbs (23.4) vs egtbs + probe up to max iteration depth, but not beyond (extensions drive the search much deeper than this):

Code: Select all

    Crafty-23.4R09       2620    4    4 17616   54%  2593   27% 
    Crafty-23.4          2619    4    4 17611   54%  2593   27% 

I don't trust my intuition that much. It might be one in a thousand, but that would show up in your testing. It might be more or less, though. Have you ever tested it?

No. The reason I don't like the idea is that you are either in the EGTB or not, you don't have any say-so about how you get in, you can just accept the score you get by playing one of the root moves, or else choose to play a root move that is not a capture so that you don't reach an EGTB position. Not much flexibility.

The other options are either continue to use EGTBs deeper in the tree or arrive at the same root positions and frequently misplay them.

[Dirt]

No. The reason I don't like the idea is that you are either in the EGTB or not, you don't have any say-so about how you get in, you can just accept the score you get by playing one of the root moves, or else choose to play a root move that is not a capture so that you don't reach an EGTB position. Not much flexibility.

Actually, I was suggesting even less flexibility by not even looking until the root position was in the EGTBs. I think that has to help, even if it's too small to measure. I'm sure you can do better than that, but it's not clear to me exactly how.