Are Table Bases (always) useful?

[Anonymous]

> I don't think they are much use just at the root, it's going to be pure
> luck then if the engine ends up in a won TB position.

Sounds reasonable. Interestingly, tests show, that TBs, even when probed in the tree, don't help much. Some tests seem to indicate, they hurt. Nevertheless, the times I was at the PB tournament, all the authors installed TBs. So, is it stupid, that they do? Perhaps. Also, it would be rather frustrating, when the engine loses some half point, because it misplays a difficult TB position.

> About the OS swapping them out, that's fine as long as they aren't
> needed but what happens when suddenly they are needed...

In the case, that only at the root is probed, not much will happen. One memory page or the other will get swapped in again (perhaps one for each move, 40 moves * 4 kB is not much). Instead of using one m?lli second to end the game, the engine may use one second. Also note, that the memory is available now for certain, because you won't access the hash tables anymore.

When probing inside the tree, things are of course more complicated. The Nalimov code loads all available decompression indices into RAM. For example on my computer, when enabling 6-men TBs (I have a very few on disk), this is about 40 MB of RAM. From my observation, of those 40MB, only very few will be really accessed even in positions with heave TB-probing, so most of it can stay swapped out. After all, modern operating systems do give virtual memory to applications for a good reason, it is not bad to use it. (I am of course aware, that using it for normal hash tables makes no sense).

>I still maintain that it's not completely clear if the TBs are worth it if the
> engine is limited to a (small) total amount of memory.

If only probing at root - yes, it must be worth it. Only resource really needed is disk space. So they should be able to help (in those rare cases, where a difficult TB position is on the board).

>I hope Eugene will make some memory efficient 5-6 man bitbases at
> one point, perhaps after the 6-man set is complete?

Bitbases alone will not help at all. Uncompressed they will be about as big as compressed TBs. Compressed, they will need some sort of decompression indices. Or 2 disk accesses per probe (which could be avoided by a more sophisticated caching scheme). But this could be done with normal TBs already. Of course compressed bitbases will save disk space. But you will need the real TBs on disk anyway, because otherwise in many cases the engine will not be able to make progress in a won position.

Bitbases used in RAM should be a considerable advantage (at least in some cases), but they really cost resources, and 6-men bitbases in RAM will need an expensive computer ...

Regards,
Dieter

[Sune Fischer]

Hi Dieter,

I'm quite sure that, at least for my engine, probing only at the root is not the best setting. They do seem to help out the search whenever there is a relevant position on the board. This doesn't happen very often though and so the effect is hard to measure.
I get higher scores on endgame suites so they can't be all bad

If only probing at root - yes, it must be worth it. Only resource really needed is disk space. So they should be able to help (in those rare cases, where a difficult TB position is on the board).

Well perhaps, but if one does not probe only at the root...

Is it then worth spending 25 MB on TBs considering how infrequently they are used, or is it better to allocate 25 MB extra main hash which can be used for the _entire_ game?

Assuming you really have lots of memory, say 1 GB which is pretty standard these days, then you can probably afford the 25 MB for 5-man TBs better. But then, on a machine like that you aren't content with 5-man, you want 6-man of course So it will always be sort of a problem I think.

Of course compressed bitbases will save disk space. But you will need the real TBs on disk anyway, because otherwise in many cases the engine will not be able to make progress in a won position.

I'm hoping to do without the DTM tables entirely and use only bitbases, I think if you sort out the losing and drawing moves a the root, then the engine should be able to shorten the mate.
This might be problematic in a few RR-RN endgames, but I doubt these are common.

BTW, do you know how large 5 and 6 man bitbases will be?

-S.

[Tord Romstad]

Interestingly, tests show, that TBs, even when probed in the tree, don't help much. Some tests seem to indicate, they hurt.

The tests I have seen all have one big flaw: They have been done with strong programs, usually even with programs which are renown for being very good in the endgame (like Yace). I think the benefits of TBs are much bigger for weak to medium strong programs with limited endgame knowledge. I don't think adding TB support is the best way to go to improve such programs, but that's a different discussion.

Tord

[Laurens Winkelhagen]

My points exactly

(see one of the first posts in this thread)

-Laurens.

[Uri Blass]

Interestingly, tests show, that TBs, even when probed in the tree, don't help much. Some tests seem to indicate, they hurt.

The tests I have seen all have one big flaw: They have been done with strong programs, usually even with programs which are renown for being very good in the endgame (like Yace). I think the benefits of TBs are much bigger for weak to medium strong programs with limited endgame knowledge. I don't think adding TB support is the best way to go to improve such programs, but that's a different discussion.

Tord

I do not think that the benefit of tablebases is bigger for programs with limited knowledge.


perfect knowledge may be counter productive for programs with limited knowledge.

Take the KRKPP tablebases.

A program with rook against 3 pawns may lose the game instead of drawing it because it may refuse to capture a pawn because capturing leads to tablebase draw.

It is the case only for programs without knowledge about endgames.

programs with knowledge may know that the KRvs KPPP is better for the pawns thanks to evaluation so tablebases may not make them weaker
by not capturing a pawn to get a draw.

I also do not think that the advantage of yace in endgame relative to amateur of similiar level is thanks to better knowledge in the evaluation and I guess that the main advantage of it in simple endgame is thanks to superior search in this type of positions.

Uri

[Anonymous]

> I'm hoping to do without the DTM tables entirely and use only bitbases,
> I think if you sort out the losing and drawing moves a the root, then the
> engine should be able to shorten the mate.

Hmmm, yes, perhaps I was wrong. I am not sure. An example would be KQKR. Here bitbases would be totally useless. Only with knowledge, or TBs with some distance to win metric, an engine will be able to win it. I doubt, an engine will be able to win KNNKP with the bitbase only. It would be interesting to check some difficult KQPKQ position. There are positions, where the winning side needs over 30 moves, until he can advance a pawn (actually there are cases, where over 50 moves are needed). I have code for KQPKQ bitbase already. Perhaps I will try it. In most positions, bitbases may be enough. Probably no tables will be enough in most positions. Difficult to judge, how many critical positions there are, where bitbases alone will help to win a point, and how many, where bitbases alone will not be enough.

> BTW, do you know how large 5 and 6 man bitbases will be?

With the scheme I am using (it is slightly less efficient than the Nalimov scheme), it is rather easy to calculate.

For endgames with one pawn, for example KBPKN, it will be

1806*48*61*60/5

a bit more than 60 MB per side to move. 1802 are the number of different KK positions, with one mirror plane (no more symmetry, because of the pawn). 48 squares for the pawn, 61 for the bishop (3 squares are already taken) and 60 for the knight. Divide by 5, because in one byte, you can store 5 WDL results. Actually here WD would be enough, so devision by 8 could be possible. KRPKRP would be (ignoring ep) 1806*48*47*60*59/5. For TBs without pawns, use 462 instead of 1806 (due to the higher symmetry). For two pieces of one kind and same color, devide by 2, 3 pieces devide by 6. So KPPPKR: 1806*48*47*47*59/(5*6). When both sides have the same material constellation (KRPKRP for example), only one side to move is needed. Actually, always only one side to move could be enough. With the wrong side to move, one would need to search one ply more.

Eugene Nalimov's scheme saves a few percents from the above formulas, because it will avoid to allocate space for some illegal positions (where side not to move is in check).

Guido Antonelli (author of a TB library) did some years ago a calculation. I believe with the formulas, I used above, and also ignoring ep (it is no problem, to not have ep positions in the final TB, of course ep must be handled correctly during calculation of the tables).

---
For uncompressed endings I obtain these values:

No. men Different Space
Endings in Mb (1Mb = 1024^2)

2 1 ---
3 5 0.275 (kbk and knk excluded)
4 30 152.333
5 110 31,865.260
6 365 5,150,003.501
7 1001 611,686,390.198
8 2520 59,916,917,072.203

Values reported are the result of an exact calculation using double precision
floating point, but they_are_depending_on_the_indexing_scheme adopted.
So they can be larger or smaller of the correspondent values obtained by other
indexing scheme.
Of course if the program is correct ...
---

From http://chessprogramming.org/cccsearch/c ... _id=221160


I did not calculate the numbers myself, but I can at least confirm the number of different TBs for 6, 7 and 8 men. And the average size looks about right. Devide these numbers by 5, and you have the space for "stupid" WDL tables. Standard zip will compress my bitbases by 65%. I guess it will be more, for most of the 5/6-men.

Regards,
Dieter

[Sune Fischer]

Hi Dieter,

So if I understand that correctly uncompressed 5 man TBs are ~31 GB, compressed I know they are about 7 GB, a factor 4.4.

For 6 man uncompressed you need 5 TB, if they scale as 5 man they must be about 1.1 TB compressed.

You say bitbases save about a factor five, hence 5 man would need 1.4 GB and 6 man compressed would require ~228 GB?

-S.

[Anonymous]

Hi Sune,

> So if I understand that correctly ...

yes

> You say bitbases save about a factor five, hence 5 man would need 1.4
> GB and 6 man compressed would require ~228 GB?

Yes, if they compress about the same. I think, bitbases could compress better, at least with a specifically crafted compressor (zip does not do too well on the bitbases I have). But perhaps only the not so interesting TBs compress better. Say in KQQQK, DTM will have many mate in 1, 2, 3, which in bitbases are all simple won, acually only won with whtite to move. Nalimov TBs store specifically "broken". This is not needed, could be set to whatever compresses best (in KQQQK case won). Of course, kqqqk is not needed at all ...

Regards,
Dieter