Gaviota tablebases, probing code v0.3.2 (UPDATE)

[michiguel]

Nothing spectacular to report, but the code has been substantially modified.
https://sites.google.com/site/gaviotach ... e/releases

1) **Many** small clean up changes to silence all compiler (GCC and Intel) warnings in a very strict mode. I think that developers who turn their warnings to be really picky will appreciate this.

2) tb_indexmemory() function implemented. It returns how much memory has been allocated to be used in indexes. The engine may like to know this in order to allocate resources more efficiently. If all the 5 -piece TBs are loaded, the memory is slightly below 10 MB.

Just in case, the previous code (v0.3.0.1) is still in the download section.

Miguel

[Houdini]

Miguel,

Thank you.
During the integration of the Gaviota code in Houdini 1.5 I had a number of ideas/suggestions.

1) Houdini doesn't require the end user to specify which compression level is used. It scans the folder for files 'kqkr.gtb.cpX' (X from 1 to 4) to decide which compression to use. Maybe this behaviour could be made standard for Gaviota?

2) Multi-threaded performance is problematic. The current code uses critical sections, when multiple threads are running this is a very slow solution. This is especially hurtful for soft probing, it prevents the soft probes from being used close to the leaves of the search. Ideally the soft-probing should return immediately when the synchronization object is set.

3) For Houdini the potential strength improvement comes from a very limited number of table bases like KQPKQ and KRPKR. It would be interesting to have these tables permanently available in memory as WDL tables.
The process could be as follows:
- convert some of the gtb files to WDL files
- load these files at program start-up - the engine would specify which files are needed
- keep the files permanently in memory, separated from the dynamically loaded table bases
- as the files are permanently available in memory, they can be accessed simultaneously by several threads

Any comments?

Robert

[michiguel]

Miguel,

Thank you.
During the integration of the Gaviota code in Houdini 1.5 I had a number of ideas/suggestions.

1) Houdini doesn't require the end user to specify which compression level is used. It scans the folder for files 'kqkr.gtb.cpX' (X from 1 to 4) to decide which compression to use. Maybe this behaviour could be made standard for Gaviota?

2) Multi-threaded performance is problematic. The current code uses critical sections, when multiple threads are running this is a very slow solution. This is especially hurtful for soft probing, it prevents the soft probes from being used close to the leaves of the search. Ideally the soft-probing should return immediately when the synchronization object is set.

3) For Houdini the potential strength improvement comes from a very limited number of table bases like KQPKQ and KRPKR. It would be interesting to have these tables permanently available in memory as WDL tables.
The process could be as follows:
- convert some of the gtb files to WDL files
- load these files at program start-up - the engine would specify which files are needed
- keep the files permanently in memory, separated from the dynamically loaded table bases
- as the files are permanently available in memory, they can be accessed simultaneously by several threads

Any comments?

Robert

I think I can do something about point 1 w/o much trouble. Point 2 is not trivial, but maybe I can do some sort of a lockless mechanism for soft probes.

Point 3 is problematic. I understand perfectly what you mean and I thought about it, but it is a lot of memory to commit permanently. The point is that most likely that memory could yield better results if it is used to increase the regular hashtable size. OTOH, as memory becomes cheaper, this could be an option...

What I certainly plan to do, is to calculate most WDL internally with functions and rules. In other words, when you probe you try first to see whether a function could return a WDL result, if not, you go to cache, if not, you probe HD. For most of the TBs, results could easily be determined with rules (KQQQK for instance if it is white's turn). Some are simple, some are more complicated. In this way, the cache could be used more efficiently, and the functions do not need to be in critical sections. This will relieve the problem in SMP engines too.

Note that the functions do not need to be complete. In fact, I do not even need to have them all. I could be coding them little by little and making them more and more thorough. The nice thing is that it is very easy to debug! I can check them with the actual TBs!

Miguel

[mcostalba]

What I certainly plan to do, is to calculate most WDL internally with functions and rules.

This could be an interesting idea, but instead of returning win/draw/lost position using rules I'd suggest to simply return "unknown" (also in known win cases) and let the engine search.

This IMHO should allow to greatly simplify rules and _quickly_ cut out a lot of positions where the usual search can easily get to the point anyway.

Of course the same logic could be implemented in the engine through a function

Code: Select all

bool EGBTprobable(const Position& pos);

that returns true _only_ in the cases that could actually make a difference in a real games with a real search as a fallback solution.

[zamar]

Hi Miguel!

What I certainly plan to do, is to calculate most WDL internally with functions and rules.
Miguel

I'm afraid that is a dead end road. It's very easy underestimate the complexity of such functions. Based on experience I'd say that complex 4 pieces endgame functions (like KBPK or KNKP) take at least 2000 code lines each. Complex 5 pieces endgame functions take at least 10000 code lines each.

Some time ago, I tried to walk that way and implemented a lot of internal WDL rule functions for stockfish. The result was very disappointing: +- 0 ELO !!

Anyway if you are still interested going ahead, I can send you a dead branch from my private repo where are perfect rules for following endgames:

KK, KQK, KRK, KBK, KNK, KPK, KQQK, KQRK, KQBK, KQNK, KQPK, KRRK, KRBK, KRNK, KRPK, KBBK, KBNK, KNNK, KQKR, KQKB, KQKN, KBKB, KBKN, KNKN

But as I said, SF didn't get any stronger... Around 2000 extra code lines was added. Some of the remaining twelve 4-piece endgames are extremely difficult, so I think it would take sth around 10000 code lines and around 3-6 months of full time work to get everything right for 4-piece endgames!

So, I don't recommend the way, but if you really want to start walking it I can send you the branch, so that you don't need to reinvent everything... Just contact me by e-mail or send a pm.

[Houdini]

Miguel,

I think I can do something about point 1 w/o much trouble. Point 2 is not trivial, but maybe I can do some sort of a lockless mechanism for soft probes.

I'm ready to help, if you would find that useful.

Point 3 is problematic. I understand perfectly what you mean and I thought about it, but it is a lot of memory to commit permanently. The point is that most likely that memory could yield better results if it is used to increase the regular hashtable size. OTOH, as memory becomes cheaper, this could be an option...

Memory has become very cheap, and as hash sizes usually are confined to powers of 2, there's a lot of excess memory available. For example on a 4 GB system the 2048 MB main hash can very well be accompanied by a 512 MB table base cache.

What I certainly plan to do, is to calculate most WDL internally with functions and rules.

I'm not sure whether that will actually be useful. This approach would be most successful for trivial endings like the KQQQK example you give, but engines probably don't need the Gaviota probing code for these anyway. The endings that matter most (KQPKQ, KRPKP etc) are not trivial.

Robert

[michiguel]

Hi Miguel!

What I certainly plan to do, is to calculate most WDL internally with functions and rules.
Miguel

I'm afraid that is a dead end road. It's very easy underestimate the complexity of such functions. Based on experience I'd say that complex 4 pieces endgame functions (like KBPK or KNKP) take at least 2000 code lines each. Complex 5 pieces endgame functions take at least 10000 code lines each.

I was not thinking of doing it thoroughly. I was thinking to have the type of rules that would cover the most cases with the less code possible and stop there. Maybe what I am saying is silly because I did not even try, but if I could write not many lines of code on average to cover 50% of cases, it would mean that 50% of the cases do not go to cache, effectively increasing its efficiency (2x).

Some time ago, I tried to walk that way and implemented a lot of internal WDL rule functions for stockfish. The result was very disappointing: +- 0 ELO !!

Anyway if you are still interested going ahead, I can send you a dead branch from my private repo where are perfect rules for following endgames:

KK, KQK, KRK, KBK, KNK, KPK, KQQK, KQRK, KQBK, KQNK, KQPK, KRRK, KRBK, KRNK, KRPK, KBBK, KBNK, KNNK, KQKR, KQKB, KQKN, KBKB, KBKN, KNKN

But as I said, SF didn't get any stronger... Around 2000 extra code lines was added. Some of the remaining twelve 4-piece endgames are extremely difficult, so I think it would take sth around 10000 code lines and around 3-6 months of full time work to get everything right for 4-piece endgames!

So, I don't recommend the way, but if you really want to start walking it I can send you the branch, so that you don't need to reinvent everything... Just contact me by e-mail or send a pm.

Thanks, if I decide to go that way, I will let you know. But I certainly appreciate the warning. Time is important.

Miguel

[michiguel]

Miguel,

I think I can do something about point 1 w/o much trouble. Point 2 is not trivial, but maybe I can do some sort of a lockless mechanism for soft probes.

I'm ready to help, if you would find that useful.

Point 3 is problematic. I understand perfectly what you mean and I thought about it, but it is a lot of memory to commit permanently. The point is that most likely that memory could yield better results if it is used to increase the regular hashtable size. OTOH, as memory becomes cheaper, this could be an option...

Memory has become very cheap, and as hash sizes usually are confined to powers of 2, there's a lot of excess memory available. For example on a 4 GB system the 2048 MB main hash can very well be accompanied by a 512 MB table base cache.

My point is that I still think (though unproven) that it would be better (as long as the engine allows it) to have a 2560 MB hash.

What I certainly plan to do, is to calculate most WDL internally with functions and rules.

I'm not sure whether that will actually be useful. This approach would be most successful for trivial endings like the KQQQK example you give, but engines probably don't need the Gaviota probing code for these anyway. The endings that matter most (KQPKQ, KRPKP etc) are not trivial.

Robert

The idea is that it would help indirectly, diverting a number of hits with functions and leaving the cache for more important endgames.

Coming back to you suggestion, it may an option to load those selected bitbases in a compressed form. You will have the overhead of decompressing, but you will save a lot of memory. Decompression could be quite fast if the blocks are not big. If done properly, probing a position this way, may be the equivalent of searching ~50 nodes. In critical positions like KQPK it may be worth it.

Anyway, regardless of the implementation, acknowledging that some endgames are more critical than others and that they deserve a special treatment is a valid concept.

Maybe I should run statistics about how many times a search will return a wrong value, compared to EGTBs, for each of the TBs. Maybe Marco is right and the ones with best ratio may not even worth probing (KQQQK). Some will be critical and deserve special treatment.

Miguel