Felicity EGTB generators and probers

[Dave Gomboc]

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.

I am currently conducting some research regarding the construction and use of endgame tables using Chess. It might be interesting to attempt to apply the techniques that my collaborators and I are exploring to Xiangqi and Jeiqi also. Unfortunately, I do not know Mandarin, Cantonese, or any other Chinese language or dialect. Can you point me and other readers of this thread to any English-language official rule set for these games, if such a thing exists?

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

Is your BanksiaGUI with UCI support on Linux also open source? https://github.com/nguyenpham?tab=repositories shows an iOS-specific version, but I'm wondering about something that can be used with Linux. The description of https://github.com/nguyenpham/Banksia doesn't indicate that the GUI is included as part of that code.

[hgm]

My program prints out the index size for rn vs n with full defenders (run the program as: fegtb -n rn-n -subinfo)

Code: Select all

...
450) krnaabbknaabb  805'180'500'000

Its index space is about 800 G, or 10 times as small as yours. I think it has one of the most compact index space systems.

My size estimates also include all incomplete Palace and Elephant constellations. As I usually generate those at the same time. For the defending Palace these positions are usually on the path to any forced win. For the winning player's defenders this can indeed be contested; even though his defenders could be captured in 2-vs-1 end-games there probably will be winning strategies that avoid this. Nevertheless, to get accurate DTM the successor end-games due to loss of white defenders would have to be calculated as well.

This is why I was calculating with a Palace size of 119 = 70 + 40 + 9 instead of 70 for kaa, and 29 = 21 + 7 + 1 instead of 21 for ee. With two sets of defenders that already explains a factor ~5. I usually ignore collisions between K and E. There are only 16*7 = 112 of those amongst the 119*29 = 3451, and saving 3% of space is usually not worth the hassle of complicating the index calculation.

So when I say KRHAAEEKHAAEE I really mean KRHdKHd, with d = AAEE, AEE, AAE, AA, AE, EE, A, E, or -. Anyway, whether 8000G or 800G, they are too large for comfort, and if an equivalent table could be made with 1.2G positions I think it would be a worthwile development.

As for 3 vs 0: I really don't think these are problematic if you stick to the liberated King (i.e. KxyzKd). Even if you would like to have xyz on both sides of the River, the attacking King could still be represented by its file for xyz being on the 90% of the squares outside their own Palace (without Cannons).

I think it would be a mistake to consider the EGTs as monolithic entities, which have to be done completely or not at all. If 10% of the positions in a certain end-game would be 1000 times more difficult to do than the other 90%, and therefore beyond handling, that should not be a reason for shying away from doing those 90%. An EGT that covers only pieces across the River would have 3*119*29*45*45*45 = 900M positions.

[hgm]

I am currently conducting some research regarding the construction and use of endgame tables using Chess. It might be interesting to attempt to apply the techniques that my collaborators and I are exploring to Xiangqi and Jeiqi also. Unfortunately, I do not know Mandarin, Cantonese, or any other Chinese language or dialect. Can you point me and other readers of this thread to any English-language official rule set for these games, if such a thing exists?

I tend to use this one: https://www.clubxiangqi.com/rules/asiarule.htm

Note there exist two rule sets: "China-mainland rules" and "Asia rules". These differ in the details of what counts as 'perpetual chasing', and the Asia rules are considered a simplification that can be more easily handled by computers. (E.g. delivering a mate-in-1 threat would be considered a chasing move in China-mainland rules, but not in Asia rules.) Internationally Asia rules are used.

[phhnguyen]

I am currently conducting some research regarding the construction and use of endgame tables using Chess. It might be interesting to attempt to apply the techniques that my collaborators and I are exploring to Xiangqi and Jeiqi also. Unfortunately, I do not know Mandarin, Cantonese, or any other Chinese language or dialect.

Many of us (me, I guess Muller as well as some other chess programmers) don't know Chinese either. Recognising all Chinese characters printed in Xiangqi pieces perhaps is all my ability to read that language But we still love Xiangqi and can program it!

Can you point me and other readers of this thread to any English-language official rule set for these games, if such a thing exists?

The official publication of the rules is here. The other thing Mullter has mentioned already. We all (outside China) use those rules.

https://www.asianxiangqi.org/English/AXFrulesEng.htm

Is your BanksiaGUI with UCI support on Linux also open source? https://github.com/nguyenpham?tab=repositories shows an iOS-specific version, but I'm wondering about something that can be used with Linux. The description of https://github.com/nguyenpham/Banksia doesn't indicate that the GUI is included as part of that code.

There are actually three Banksia programs:
- Banksia: open-source. C++. It is a tournament manager for chess. It is a console program (no GUI). It is the core of Banksia GUI too. You can compile it for almost all OSs, including Linux
- BanksiaGUI for iOS: open-source. Swift. It is a chess game human vs engines with some pre-installed chess engines. It uses a different programming language but it has the same core/design as Banksia and BanksiaGUI. As its name, it is for iOS only
- BanksiaGUI: freeware but not open-source at the moment (I will publish its source code later). It is a tournament manager and also a basement for tools/utilities for chess. It has published with binaries already for main OSs, including Linux

If you prefer a chess GUI for Xiangqi/Jeiqi, you may wait a bit for a modified version of Banksia GUI to support those chess variants.

[phhnguyen]

Attempt 12: generate all 5-men endgames for chess

We generated all endgames 5-men (3 attackers + 2 Kings) for chess. The estimated size was about 10 GB, very small relatively compared with Xiangqi 2 attackers thus it is a much easier and quicker task. By doing that we could fix, and verify the new generator, trying some ideas. Furthermore, we could measure some stats as a baseline and compare our work with some existing EGTBs.

In this attempt, the generator uses the forwarding method for the move generator. The compress library is LZMA from the 7zip library, compressed by blocks of 4 KB. It ran an old computer AMD Ryzen 7 1700 8-Core 16 threads, 16 GB RAM, ran with 12 threads and took about 85% of the computer's power.

The generator took about 3 days and 15 hours to generate. If we add the time for verification, compressing and saving down it took almost 4 days to generate all 5-men endgames.

The size of all endgames is 8.8 GB, better than the estimation of 10 GB. However, it is noticeably larger than the Gaviota one (about 7.03 GB or 25% larger) and the Nalimov one (about 7.1 GB or 24% larger).

The bad thing is that our EGTB is larger/worse in size than all popular ones.

The good thing is that our code works fully!

[hgm]

If I calculated right that is 75 2-vs-1 plus 35 3-vs-0 = 110 5-men end-games in 87 hours, of 47 min per end-game.

That is not very fast. Fairygen calculates a typical 5-men end-game like KBB-KN in 75 sec. But that is without compression. It calculates a 4-men like KBN-K in 1.1 sec. And the 'pretty fast' algorithm by Marcel van Kervinck did that in under 0.1 sec.

Perhaps speed is irrelevant here, because the EGT need only be calculated once. At least for 5-men Chess EGT. But for the larger EGT it might start to hurt; you would not want it to take 10 years when it could be done in 1 month.

[phhnguyen]

Wow, your generator works so fast!!!

I agree, my one is too slow.

[phhnguyen]

Attempts 13 & 14: generate all 5-men endgames for chess with the backward method

We use a retro move generator to detect and work with only necessary positions, avoiding checking and updating all as the forwarding method. That caused a significant speed improvement.

The total generating time for 5-man chess is almost 17 hours (not including time for verifying, compressing and saving into hard drivers). Compared to 3 days and 15 hours (87 hours) of the forwarding method in the previous attempt, that is 5 times as fast.

The GitHub's code and documents are updated!

[hgm]

Can your generator handle KRC-KR?

[Dann Corbit]

What is the maximum number of chessmen on the board that are possible to generate a tablebase for?