Can EGTB be improved upon?

[M ANSARI]

I am thinking of loading up the entire set of 6 piece EGTB, and that is a daunting 1.2 TB. This is quite a footprint and depending on the speed of the drive or drives it can have a debilitating effect on the strength of the engine using it. I am wondering if there is a better way of doing EGTB's ... maybe better compression or even a better and faster indexing scheme that would be much more passive and thus cause less of a burden on a system. I know that Google has some sort of free indexing code available for the Desktop that is quite powerful ... maybe that code could somehow be adapted for EGTB's. Nalimov EGTB have been around for some time and I am surprised that not more work on improving EGTB's is being done. I would think that with HDD technology improvement and the ubiquitous availability of the internet that it would be possible to have virtual EGTB out somewhere in cyberspace with merely an indexing footprint required on the local machine. The indexing would simply be a win - lose - draw index. There must be a better way somehow!

[Terry McCracken]

I am thinking of loading up the entire set of 6 piece EGTB, and that is a daunting 1.2 TB. This is quite a footprint and depending on the speed of the drive or drives it can have a debilitating effect on the strength of the engine using it. I am wondering if there is a better way of doing EGTB's ... maybe better compression or even a better and faster indexing scheme that would be much more passive and thus cause less of a burden on a system. I know that Google has some sort of free indexing code available for the Desktop that is quite powerful ... maybe that code could somehow be adapted for EGTB's. Nalimov EGTB have been around for some time and I am surprised that not more work on improving EGTB's is being done. I would think that with HDD technology improvement and the ubiquitous availability of the internet that it would be possible to have virtual EGTB out somewhere in cyberspace with merely an indexing footprint required on the local machine. The indexing would simply be a win - lose - draw index. There must be a better way somehow!

Of course there is, but someone will want money for all that service!

Terry

[hgm]

IMO the concept of using precalculated EGTBs is a dead-end strategy. As the number of men increases, both size and number of the needed EGTBs explodes. And in practice very few of them are useful in games. Only those with substantial numbers of Pawns occur frequently. E.g. 10-men end-games without Pawns will occur exceedingly rarely.

So I think the future will be in on-the-fly generation of EGTBs: just generate the (small fraction of) the one you need as you need it. By the time the number of pieces in the game has gone down to the level where EGTBs are possible, you know which combinations of pieces still can occur, and which Pawn structures are still reachable.

My aim is to work on this, but developing two engines at the same time leaves in practice too little time for my EGTB project to progress much.

[M ANSARI]

Yes that is an interesting proposal indeed ... maybe this can be generated by a daughtercard or even another independent computer that is somehow connected passively, and thus can start generating certain egtb's as the game progresses. Still there must be some sort of indexing that at least tells the engine if the position is won - drawn or lost. Those tables should not take so much space ... or at least would be much less of a footprint. Once a game reaches a stage where egtb hits are there the daughtercard or slave computer could start generating the endings. I think there exists a program called Freezer that follows on some sort of similar concept but am not sure how the inner workings work.

Still I think there should be an index of win - lost - drawn positions. This should not take as big a footprint as EGTB's. And if an engine is given that a position is won for example, it would have a setting that would tell it the win is there for the finding, and thus it will reset its parameters to find the win and search deeply. So again the indexing is what is needed. I am almost sure that with today's hardware and with 120/40 time control, most engines would be able to find a win in a 6 or even 7 egtb if they know the win is there and the engine switches into a different setting.

[hgm]

Well, to buid a bitbase requires 3-4 bits per position, (1 or 2 bits for each side to move). Building a DTM or DTC tablebase requires 8 bits. So the gain is there, but it is not dramatic.

Bitbases are very useful for probing to which end-games you can convert. Then the WDL info is really all you need. Only once you are in a won position of that end-game on the game board, you would have to start worrying about how to win it (i.e. know the DTx).

Calculating a (true) 4-men ending currently takes me 2 sec on a 1.3GHz Pentium M, for a 5-men typically 240 sec. But I designed a new algorithm that should reduce that about a factor of 10. That should allow on-the-fly generation of pawn-less 5-men EGTBs at all but blitz time controls.

[George Tsavdaris]

Calculating a (true) 4-men ending currently takes me 2 sec on a 1.3GHz Pentium M, for a 5-men typically 240 sec. But I designed a new algorithm that should reduce that about a factor of 10. That should allow on-the-fly generation of pawn-less 5-men EGTBs at all but blitz time controls.

Factor of 10? Wow nice.....
So forget about Joker and MicroMax for now and create these tablebase's generators....

All these are for Pawnless. What about with Pawns? How much time then it makes to generate 4 and 5?

What about 6 or 7 or 8? Any time estimation.....?
I guess having Pawns on an 7 piece position for example, is not so dramatic for the generation time because you will only generate those with the Pawns standing on their current file and that reduces considerably the positions needed for the calculation.
A very promising project is that you started. I'm looking forward....

[hgm]

Yes, with Pawns it is generally easier, as they can only access a very small fraction of the board. (They can access some more by straying off their file, but as they can only due that by capturing something, you will have one fewer piece on the board is such positions, which saves you a factor 64. You lose the symmetry factor, though, which multiplies the size (and time) by 8 compared to Pawnless end-games.

How much you save depends on the number of Pawns. E.g a 5-men end-game with a (white) Pawn on e4 would have 8*4=32 times as many positions in it as the corresponding Pawnless 4-men. (The Pawn could be only on e4,e5,e6,e7. Positions with the Pawn on the d or f file would be 1.5/64 as numerous.) This is about half of what a Pawnless 5-men would contain.

In a 5-men with 2 Pawns, say on d2 and d7, there would be only 28 possible Pawn structures. This would give 8*28 the size of the corresponding Pawnless 3-men, i.e ~4 times the size of a 4-men, or 1/16 the size of a Pawnless 5-men. So you see that for 2 or more Pawns it gets enormously easier.

It depends a lot on where the Pawns are positioned. A passer in its initial position contributes a factor 6 (+10/64 after a single capture). Two of them would contribute a factor 36. But two head-to-head Pawns only contribute a factor 10. A KRPPKRPP with Pawns on a2, e4 (W) and a3, e5 (B) would only contribute a factor 100 for the Pawns, and thus contain 800 times as many positions as KRKR. That is about 12.5 times as much as a Pawnless 5-men. This then should take about 300 sec. That would be not so bad for an 8-men. KRPPKRP with 2 locked Pawns and a passer would be about twice as fast.

For the promotion positions you can convert to, a bitbase might still be needed, to know which promotions are winning and which not. My feeling is, though, that such bitbases can be Quite small: for one, they can be highly compressed, as for an interesting end-game, almost all end-games with a Queen more are quite trivially won. And you would of course only need the positions from such a TB with the Queen on the 8th.

[M ANSARI]

Wow that is amazing indeed. 240 seconds / 10 gives around 24 seconds now take that this is on a 1.3 Pentium and say use a Quad core running 3.2 Ghz and that should bring it to at the most 6 seconds and more likely 4 seconds!!! I am ofcourse assuming that this code is MP capable. That would really be something. So if you have the indexing of win - draw - lose already on locally the actual looking up and finding of the win would be very quick. I guess this could be used to generate EGTB with many more pieces and would really be a tremendous analysis tool as well as giving additional ELO strength to today's engines.

What code are you using or what tool? Is this code available somewhere for download? It would be a good idea to implement such a product as a plugin for UCI engines if UCI supports something like that. By the way do you have an idea what the bit base footprint would be of say 7 piece EGTB if you include only indexed win - draw - lose indexing.

This seems exactly what EGTB's need ... a new way of dealing with the problem of EGTB's that can be much more useful as an analysis tool as well as improving endgame play of engines in general.