Felicity EGTB generators and probers

[phhnguyen]

We have restarted Felicity’s EGTB project. The plan is to rewrite all code, to create EGTB (Endgame table base) generators and probers for chess, Xiangqi and Jeiqi.

Creating a new EGTB may be controversial at the moment, in the time of machine learning/neural networks. On one hand, we know EGTBs don’t bring much strength to chess. 6-men Syzygy EGTB just contributed under 3 Elo for Stockfish 15. With NNUE technology Stockfish can learn automatically a lot of techniques to win endgames. On the other hand, we guess EGTB may contribute much more strength to Xiangqi engines. That guess is based on the fact that Xiangqi endgames are typically much more complicated than chess ones since it has so many tricks and exceptions to win or draw. It is not easy for humans to study so it is for machines to learn, even with some latest techniques. One of my friends – a Xiangqi engine programmer estimated that EGTB brought at least 50 Elo to his strong Xiangqi engine. We need to verify that estimate with some open data and testing.

This project focuses on Xiangqi and Jeiqi. However, we support chess (orthodox chess variant) too. That could help us to compare code, verify, and get ideas and tests from many sources.

This is a long journey. The work is a hobby, mainly for fun and enjoyment as well as for contributing to the community.

All information is published on the GitHub repository and in the BanksiaGUI forum.

We will sometimes update here too.

------------
Brieft after first 7 attempts:

We concluded by using the mailbox technique for board representation for the EGTB project because of some advantages:
- simple: all code is short, clear, easy to understand and maintenance
- easy to support different chess variants, from small to huge boards
- fast (for basic functions such as in/out, move generators, make, takeback, incheck...) enough for chess, be faster than ones with bitboards for bigger boards (such as Xiangqi)



BanksiaGUI is working with both local and online EGTBs

[hgm]

I am also interested in generation of Xiangqi EGT. This is not nearly so trivial as generating EGT for Chess, though, because of the ban on perpetual checking and chasing. Xiangqi also has some features unparallelled in Chess, which would allow you to use EGT with a smaller number of pieces directly for an end-game with more pieces; in particular, Advisors and Elephants of the winning side can be ignored when they are not 'in the way' (and are not needed as Cannon mount). For my own Xiangqi engine I generated some such 'partial EGTs'.

[Ajedrecista]

Hello:

[...]



[...]

I do not understand the relation between score and comment: some of the moves have an offset of 20000 (Rg7g4, Ng8f6 and Ke6e7) while the rest have an offset of 30000. The offset of 20000 means cursed wins due to the fifty-move rule?

I also see that the circles in the board have different colours, even if they have the same info (e.g. M-1 at b7 and c7 squares).

Thank you in advance.

Regards from Spain.

Ajedrecista.

[phhnguyen]

I am also interested in generation of Xiangqi EGT. This is not nearly so trivial as generating EGT for Chess, though, because of the ban on perpetual checking and chasing. Xiangqi also has some features unparallelled in Chess, which would allow you to use EGT with a smaller number of pieces directly for an end-game with more pieces; in particular, Advisors and Elephants of the winning side can be ignored when they are not 'in the way' (and are not needed as Cannon mount). For my own Xiangqi engine I generated some such 'partial EGTs'.

I used to invert a lot of time and effort in a similar direction. However, I concluded that in the best-case scenario, we could save about 10% of the total EGTB size, not important nowadays when there are many serious drawbacks. The main drawback is that you have to write a specific code for each endgame. It is not as easy as typical endgame coding, especially when Xiangqi has too many tricks and exceptions.

For example, KRKAAEE (a rook vs a full defence) and KRAKAAEE look similar since A (Advisor) of the Rook side could be considered completely redundant: it may contribute nothing to the effort to win. However, in many cases A may block the King to control a column or to move sideways. You may move A away/under the King but with one or two extra moves, the strong side may lose already the chance to win!

It’s somewhat similar to EGTB of chess, we may save some sizes by removing some sure/easy win endgames such as KRK, KQK… but not much and maybe not worth creating more trouble.

BTW, even if you want to write some code for Xiangqi endgames, you need to understand their methods to win. Different from chess, Xiangqi has a complicated set of methods to win endgames. The known set is typically not enough or clear or does not cover all cases, and there are so many special/exceptional cases. To learn those methods to code as well as verify their correctness, it’s much better if you have a full Xiangqi EGTB first

[phhnguyen]

I do not understand the relation between score and comment: some of the moves have an offset of 20000 (Rg7g4, Ng8f6 and Ke6e7) while the rest have an offset of 30000. The offset of 20000 means cursed wins due to the fifty-move rule?

I don't understand either

I have just followed the API description of chessdb.cn when querying and managed to display as much information as possible as well as explain known ones such as translating scores into mate scores to display on bubbles. The meaning of those comments is a mystery to me.

I also see that the circles in the board have different colours, even if they have the same info (e.g. M-1 at b7 and c7 squares).

Thank you in advance.

Regards from Spain.

Ajedrecista.

Those bubbles (circles) are semi-transparent. If a square has several bubbles, their backgrounds are combined and look stronger than the ones alone.

[hgm]

I used to invert a lot of time and effort in a similar direction. However, I concluded that in the best-case scenario, we could save about 10% of the total EGTB size, not important nowadays when there are many serious drawbacks. The main drawback is that you have to write a specific code for each endgame. It is not as easy as typical endgame coding, especially when Xiangqi has too many tricks and exceptions.

For example, KRKAAEE (a rook vs a full defence) and KRAKAAEE look similar since A (Advisor) of the Rook side could be considered completely redundant: it may contribute nothing to the effort to win. However, in many cases A may block the King to control a column or to move sideways. You may move A away/under the King but with one or two extra moves, the strong side may lose already the chance to win!

It’s somewhat similar to EGTB of chess, we may save some sizes by removing some sure/easy win endgames such as KRK, KQK… but not much and maybe not worth creating more trouble.

I guess it gave huge savings for me, because I only generated the end-games where the weak side was stripped to King + defenders, with the minimal number of attackers to beat a 'full house' (so R, HH or PPP). The indexing I used distinguished 119 Palace states and 29 Elephant states. (I made no effort to remove the broken states where an Elephant collided with a King, as these make up only 112 out of 3451 K-A-E constellations.) When there is no obstruction by the defenders of the strong side, this reduces to 3 essentially different constellations (the files where the King can be).

Provided the attacking pieces are across the River there are 792 K-A-E constellations that can be reduced to these three.

The idea was even if there would be obstruction, it would only take very few moves to get the obstructing defenders out of the way, and that I could leave it to the search to find these few moves. (The heuristic evaluation of my engine was such that it would award doing so if the opponent had no attacking pieces, and it had no Cannons itself.) In the same spirit I only tabulated positions where the attacking pieces were across the River, so that they could not be obstructed by any surplus defenders.

This did not work out very well for KRxKAAEE, though. I got the impression that this end-game, when won, contains a long cycle of forced Rook-only moves in order to prevent the losing player to reorganize his defense to reach a draw, and that this cycle leaves one move where the Rook doesn't have to act, which can then be used to make progress in 'liberating' the attacking King.

The main challenge is to do end-games where the losing player also has attacking material, though. For those the generator has to deal with the ban on perpetuals.

The number of combined defender constellations is already 12M, with two-fold symmetry only, so comparable to a 4-men Chess end-game with Pawns. And every additional man would bring a factor 100 instead of 64. How far do you intend to go with this? Will you do 2-vs-1 attacker?

[phhnguyen]

And every additional man would bring a factor 100 instead of 64.

Did you mean 90?

If you add a Pawn or a similar attacker (say, RR) their factors will be significantly smaller.

How far do you intend to go with this? Will you do 2-vs-1 attacker?

Sure! I have already code to generate 2vs1. However, I need to rewrite/verify it. The problem is that the size of 2vs1 with some defences becomes too huge to generate or use. One of the main reasons I want to review and rewrite all my code is to reduce EGTB size in general and sizes of multi-attackers in particular. I guarantee it is a… very hard battle with a huge chance of losing

[hgm]

Sorry, I meant indeed 90. So for 2 vs 1 (all different) and potentially full defence that would make 4.3T positions. I suppose doing this with full defense on both sides would hardly ever be necessary, though.

The biggest problem I see is "one check, one chase" defensive strategies. These could be successful with a Rook defender if the winning player has no King castle at all. But perhaps two Elephants or a single Adviser would already be enough to thwart any such defense strategy.

A single Knight as defender is probably harmless in the counter attack, due to the ban on perpetuals. Used for counter attacking it could at most delay the progress by a number of pointless checks.

[phhnguyen]

To be realistic, I think it’s a success if we can generate all two attackers (1 vs 0, 2 vs 0 and 1 vs 1) with full defenders (12 men). The rule for perpetual chases/checks for 1 vs 1 is not hard to implement and could be ignored for x vs 0.

I still hope if we work hard and get lucky enough we may reduce the sizes of EGTBs to 2 - 3 times (compared with my previous work) thus we can generate all 2 attackers quicker, easier and cheaper (my friends have to use some expensive computers to generate them).

Even with that lucky, we still have too much trouble to generate all 3 attackers. Thus I think we will generate some of them only, mostly for studying.

[hgm]

I did 3 vs 0 for three pawns quite some time ago, so it cannot be that hard on modern hardware. I am a bit out of touch, so are there any other 3 vs 0 end-games that are of interest? Perhaps H+2P and C+2P?