TalkChess.com

Hi all,

I have designed and implemented a new Xiangqi egtb (named Felicity egtb) with DTM metric, focusing on reducing its size.

The main idea to reduce sizes is so simple: omit some pieces on some specific positions which effect minimum to results. The missing information could be retrieved later by using extra computing and / or by using cheap extra databases.

By omitting some pieces' positions (ignore them when creating indexes), some different chess positions could share same indexes. The properties of the new egtb differ from traditional ones. Below are interesting:

- one chess position could be indexed into one index only, but one index could be represented for multi chess positions (one to many)
- score of an index could be undetermined

That is why we call the new one as "undetermined" egtb.

For Xiangqi, at the moment the new design could apply for a special class of endgames in which one side has no attacking (but defending) pieces (such as KRK, KCAAEEKAAEE, KHPAAEEKAAEE).

I omit all positions of Elephants of the attacking side which are not in the King's palace. By that I could reduce the index space to 15 times (only 6.6% left) as well as data sizes.

A traditional egtb of all-one-attacker with all configurations of defender (KR*K*, KC*K*, KH*K*, KP*K* - total 324 endgames from 3 to 11 men) may take 3.8 GiB in uncompressed form. With the new design the egtb's size have been reduced to 256 MiB (uncompressed).

So far I have failed to use extra computing to retrieve missing information (took too much time) but succeed on using an extra database (lookup tables). Simply I stored all undetermined positions with their real (determined) scores into lookup tables.

By omitting only some pieces' positions which effect minimum to results, I can keep the size of the extra database be small enough. With lookup tables, instead of 15 times reducing now the egtb + lookup tables sizes are about 420 MiB, a reduction of 9 times in total.

To save more, I discarded data of one side. Thus the egtb + lookup tables could take about 200 MiB in memory (all in uncompressed form). That is just a small space for model computers, especially comparing with 3.8 GiB of the original one. It means you may probe the egtb anywhere in high speed.

By applying some compress methods, at the moment the new egtb takes only 14 MB - very easy to download. It could be easily released with or even embedded directly into engines.

The probing source code (using standard C++ 11) and all-one-attacker egtb (the egtb stored inside the project) could be download under MIT license (almost no restrictions) at:

https://github.com/nguyenpham/FelicityEgtb

Have fun,

/Pham

I am not sure what exactly you mean by "omitting all positions of Elephants of the attacking side which are not in the King's palace". In general there are 21 positions with 2 Elephants (15 with both outside the Palace, 6 with one inside), 7 with 1 Elephant (6 + 1), and 1 without Elephants. So there are 15 + 6 + 1 = 22 positions without Elephant in the Palace, and 6 + 1 = 7 with an Elephant in the Palace. Is the factor 15 you mention a rounded 14.5 that you get from going from 22 + 7 = 29 to just 2 positions?

In principle even an Elephant outside the Palace could obstruct the attacking piece, when that piece is still on its own side of the River. Does this give rise to the 'undetermined' positions?

I use 'partial' EGT, containing only positions with the attacking piece(s) on the enemy board half. This indeed makes any out-of-Palace Elephants of the attacker completely invisible. In KR*K* this gves the correct DTM for all positions in the EGT, as the Rook can use the 6th rank (counting 0-9) for lateral movement. So positons with an Elephant in the Palace or the Rook on its own half cannot be found in the EGT, and rely on search to move the Rook forward and the Elephant out of the way to get the first EGT hit.

Horses sometimes have to cross the River for the fastest win, however, even when they already are on the enemy half. So the DTM in the partial EGT are sometimes sub-optimal. What I see then is that the engine follows the line of the EGT, until the search finds a shortcut outside the EGT to enter it on a more favorable point, and the DTM suddenly drops. So eventually it plays the fastest line after all, it is just that initially it might report a DTM that is too high. It is hard to prove that no wins are shielded this way. The situation can be improved somewhat by extending the region where the Horses are allowed to go to 6 or even 7 ranks, assuming two Elephants are on 4th rank. You only have to do that during generation; positions with the Horses on 3rd or 4th rank don't really have to go into the EGT, as it is quite trivial for the search to find the required shortcuts.

Mapping all positions without Palace Elephants to the corresponding ones with both Elephants on 4th rank, and omitting those with a Palace Elephant, gives a size reduction of 29, and restricting the attacking piece to the enemy half a further reduction of a factor 2 per attacking piece.

That still leaves many constellations of the King and Advisers that are equivalent. There are 119 possible Palace states (70 KAA, 40 KA and 9 K), but when the King is in front of all Advisers they can be mapped on 3 positions only differing in King file. That reduces 36 of the 119 positions to just 3. I can make the EGT even more partial by only incorporating these 3 Palace states, an additional reduction of nearly a factor 40. This is important if you want to do 2 or 3 attacking pieces (e.g. I have KHH*K* and KPPP*K*). The drawback of course is that more search is required to 'liberate the King'. This can be helped to have an extra evaluation term only active in the end-games for which you have an EGT, but are not in the stored part, which encourages exposing the King (so that the moves that do this become PV even at low depth, rather than getting reduced).

A KR*K* reduced this way did not work entirely satisfactory, though. Although it just takes a few moves to liberate the King, it turns out there are KR*KEEAA positions that are just on the edge of being won, where wasting even a single tempo on exposing the King would give the defending side the opporunity to reorganize his defese, and achieve a draw. To win those you have to exert presure with the Rook preventing the reorganisation, until you manoeuvre the defender into a position where you can afford a Palace move. But then the defender renews the draw threat, and you have to repeat the Rook manoeuvre to get back to the constellation where you can afford a second Palace move, etc. With an unfavorable Palace constellation of the attacker (e.g. K on backrank EAA on 2nd rank) you have to repeat this many times before you start hitting the partial EGT that assumes a fully liberated King. And that is way too deep for the search.

So I am still toying with the idea to make a auxiliary EGT for that Rook manoeuvre. I.e. assume a fully hidden King, which takes multiple moves to liberate, and calculate a 'distance to liberation', i.e. how many moves you need to reach a position where you can afford to waste a tempo. The worst case of that, multiplied by the number of moves needed to completely liberate your King, could be added to the worst DTM with completely liberated King to get a (pessimistic) estimate of the total DTM for the positions not in the partial EGT.

OTOH, KR*K* is small, and any other additional attacker makes it a certain and easy win, so you don't need an EGT for those. There could be similar situations in KHPP*K*, though, and there a size reduction would be very welcome.

hgm wrote:I am not sure what exactly you mean by "omitting all positions of Elephants of the attacking side which are not in the King's palace". In general there are 21 positions with 2 Elephants (15 with both outside the Palace, 6 with one inside), 7 with 1 Elephant (6 + 1), and 1 without Elephants. So there are 15 + 6 + 1 = 22 positions without Elephant in the Palace, and 6 + 1 = 7 with an Elephant in the Palace. Is the factor 15 you mention a rounded 14.5 that you get from going from 22 + 7 = 29 to just 2 positions?

Correct!

hgm wrote: In principle even an Elephant outside the Palace could obstruct the attacking piece, when that piece is still on its own side of the River. Does this give rise to the 'undetermined' positions?

Not really. Since many chess positions could share a same index, that index (and all relative chess positions) may be still determined when all their scores are the same. However, if only one of those scores differs from others, they all and their index are considered as undetermined. The positions of Elephants which I omitted may but not always lead an undetermined one.

In egtb files, if an index is determined I save its score as usual. If it is undetermined, I use two special values: WINNING (when all relative scores are winning) or UNKNOWN (when some are winning but others are draw).

The key of omitting those Elephants' positions is the low proportion of undetermined indices: they take only 5% in my EGTB.

hgm wrote: I use 'partial' EGT, containing only positions with the attacking piece(s) on the enemy board half. This indeed makes any out-of-Palace Elephants of the attacker completely invisible. In KR*K* this gves the correct DTM for all positions in the EGT, as the Rook can use the 6th rank (counting 0-9) for lateral movement. So positons with an Elephant in the Palace or the Rook on its own half cannot be found in the EGT, and rely on search to move the Rook forward and the Elephant out of the way to get the first EGT hit.

Horses sometimes have to cross the River for the fastest win, however, even when they already are on the enemy half. So the DTM in the partial EGT are sometimes sub-optimal. What I see then is that the engine follows the line of the EGT, until the search finds a shortcut outside the EGT to enter it on a more favorable point, and the DTM suddenly drops. So eventually it plays the fastest line after all, it is just that initially it might report a DTM that is too high. It is hard to prove that no wins are shielded this way. The situation can be improved somewhat by extending the region where the Horses are allowed to go to 6 or even 7 ranks, assuming two Elephants are on 4th rank. You only have to do that during generation; positions with the Horses on 3rd or 4th rank don't really have to go into the EGT, as it is quite trivial for the search to find the required shortcuts.

Mapping all positions without Palace Elephants to the corresponding ones with both Elephants on 4th rank, and omitting those with a Palace Elephant, gives a size reduction of 29, and restricting the attacking piece to the enemy half a further reduction of a factor 2 per attacking piece.

That still leaves many constellations of the King and Advisers that are equivalent. There are 119 possible Palace states (70 KAA, 40 KA and 9 K), but when the King is in front of all Advisers they can be mapped on 3 positions only differing in King file. That reduces 36 of the 119 positions to just 3. I can make the EGT even more partial by only incorporating these 3 Palace states, an additional reduction of nearly a factor 40. This is important if you want to do 2 or 3 attacking pieces (e.g. I have KHH*K* and KPPP*K*). The drawback of course is that more search is required to 'liberate the King'. This can be helped to have an extra evaluation term only active in the end-games for which you have an EGT, but are not in the stored part, which encourages exposing the King (so that the moves that do this become PV even at low depth, rather than getting reduced).

A KR*K* reduced this way did not work entirely satisfactory, though. Although it just takes a few moves to liberate the King, it turns out there are KR*KEEAA positions that are just on the edge of being won, where wasting even a single tempo on exposing the King would give the defending side the opporunity to reorganize his defese, and achieve a draw. To win those you have to exert presure with the Rook preventing the reorganisation, until you manoeuvre the defender into a position where you can afford a Palace move. But then the defender renews the draw threat, and you have to repeat the Rook manoeuvre to get back to the constellation where you can afford a second Palace move, etc. With an unfavorable Palace constellation of the attacker (e.g. K on backrank EAA on 2nd rank) you have to repeat this many times before you start hitting the partial EGT that assumes a fully liberated King. And that is way too deep for the search.

So I am still toying with the idea to make a auxiliary EGT for that Rook manoeuvre. I.e. assume a fully hidden King, which takes multiple moves to liberate, and calculate a 'distance to liberation', i.e. how many moves you need to reach a position where you can afford to waste a tempo. The worst case of that, multiplied by the number of moves needed to completely liberate your King, could be added to the worst DTM with completely liberated King to get a (pessimistic) estimate of the total DTM for the positions not in the partial EGT.

There are so many tempting solutions to reduce EGTB size (by creating undetermined EGTBs), its't it?

In contrast, I have been trying but seen so few ones for Western chess!

However it is a big challenge to make one of them work.

For the method of using extra database (as I have used in my EGTB) we should balance between gaining / reducing and paying back since aggressive solutions may pay badly by having larger extra databases. After trying many different solutions, I think the my current one (omitting some Elephants' positions) is one of the best for balancing.

For the method of using extra computing (searching), aggressive solutions may lead huger search trees. From my experience it is hard to make that method works in reasonable searching time. Even with my solution (not so aggressive) I have tried many ways to search, set out many thresholds (say, search tree should be under 10000 nodes), and so far I still fail (to create a good-enough search).

IMO, a bitbase (the egtb have used 1 or 2 bits per index for storing won/draw/loss) could be considered as an undetermined egtb (won/loss scores are not "real" values but undetermined). However searching with a bitbase should be much harder than our undetermined egtbs since the proportion of undetermined scores is much larger than our ones: all win/lose scores of a bitbase are undetermined and could take over 50% of all indices (in contrast, my egtb has only 5% undetermined scores). Thus bitbase's searching tree should be much larger and deeper. Logically, if Daniel of Scorpio could make his bitbase works, someone could do the same with Xiangqi egtbs. Keep working if you love this way!

hgm wrote:
OTOH, KR*K* is small, and any other additional attacker makes it a certain and easy win, so you don't need an EGT for those. There could be similar situations in KHPP*K*, though, and there a size reduction would be very welcome.

Agree, a Rook + any extra attacking pieces should be sure wins (so they are almost useless for having) for any defensive combinations. However a Rook alone could win in over 60% cases so you should solve your KR*K* first anyway.

My egtb can have huge gains for endgames of Pawns and Horses (any combinations such as KPPP*, KHH*, KHPP*) with reductions over 10 times. Logically you can see that those omitted Elephants won't affect them much since they work mostly above or could void those Elephants. However it could not gain much for combinations of Rooks (luckily as you have mentioned we don't need any combination of Rook and other attacking pieces) and Cannons. I have been working hard on that issue.