Felicity EGTB generators and probers

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

Dave Gomboc
Posts: 13
Joined: Sun Aug 15, 2021 12:22 am
Full name: Dave Gomboc

Re: Felicity EGTB generators and probers

Post by Dave Gomboc »

noobpwnftw wrote: Mon Jul 01, 2024 12:15 pm Practically one would use various in RAM bitmaps to track "to do" positions and memory map the fat ply counting ones backed with files on disk, random access is likely inevitable but not too heavy with the help of those bitmaps.

Overengineering the indexing scheme is of little value, as we are already ahead of our times in terms of feasibility with common hardware. Nothing much has changed to make building 7-man chess tablebases any easier compared to a few years ago, while for xiangqi I'm still looking at a few years of compute into generating tablebases before available RAM runs out(there are much more combinations to work on).

Dealing with xiangqi rules involves multiple extra labeling passes during genration, it was quite an adventure: trial and error over multiple years to come across some bugs or corner cases. Code has been available for your reference, just FYI.
Could you please provide a link to your Xiangqi endgame table reference code?
User avatar
phhnguyen
Posts: 1484
Joined: Wed Apr 21, 2010 4:58 am
Location: Australia
Full name: Nguyen Hong Pham

Re: Felicity EGTB generators and probers

Post by phhnguyen »

I am happy to say that the issue of Chinese chess perpetual rules has been solved completely, both theoretically and practically. It took me a lot of time and labour but now I'm almost done. I have been still verifying the code and improving its speed, as well as writing documents. All will be released soon.

The below image is a position with a perpetual chase move (the one marked with a circle in purple)

Image
https://banksiagui.com
The most features chess GUI, based on opensource Banksia - the chess tournament manager
User avatar
phhnguyen
Posts: 1484
Joined: Wed Apr 21, 2010 4:58 am
Location: Australia
Full name: Nguyen Hong Pham

Re: Felicity EGTB generators and probers

Post by phhnguyen »

The statistics of an endgame looks like:

Code: Select all

Name                        : krkcn
Total positions             : 32805000
Legal positions             : 36856968 (56%) (2 sides)
Total draws                 : 812263, 2% of total legal
Max DTM                     : 116
White to move (WDL)         : 97%, 0%, 0%
 Perpetual checks (WL)      : 30521, 45
 Perpetual chases (WL)      : 766, 6
Black to move (WDL)         : 13%, 3%, 80%
 Perpetual checks (WL)      : 710, 6
 Perpetual chases (WL)      : 34065, 45
Total perpetuations         : 664527, 81% of draws. #checks: 31282, #chases: 34882
Leading perpetuation max    : 46
Total leading perpetuations : 598363, #wins: 79086, #losses: 519277


Samples with max DTM:
9/3k5/9/9/9/9/6n2/5K3/9/1R2c4 b 0 1
9/3k5/9/9/c8/9/6n2/5K3/9/1R7 b 0 1
9/9/R2k5/9/4c4/9/6n2/5K3/9/9 b 0 1
9/3k5/9/9/c8/9/6n2/5K3/R8/9 b 0 1
9/3k5/9/9/4c4/8n/9/1R3K3/9/9 b 0 1
1R1k5/9/9/9/4c4/9/6n2/5K3/9/9 b 0 1
R8/3k5/9/9/9/9/6n2/5K3/4c4/9 b 0 1
R8/3k5/9/9/4c4/9/9/5K2n/9/9 b 0 1
R8/3k5/9/9/4c4/8n/9/5K3/9/9 b 0 1
R2k5/9/9/9/4c4/9/6n2/5K3/9/9 b 0 1


Samples of perpetual checks:
9/4c4/5k3/9/9/9/9/3K5/1n7/4R4 w 0 1
9/9/5k3/9/9/9/8c/3K5/6n2/3R5 b 0 1
9/9/5k3/9/9/7c1/5n3/3K5/9/3R5 w 0 1
9/7c1/5k3/9/9/9/9/3K5/6n2/3R5 b 0 1
9/5k3/5c3/9/9/9/5n3/3K5/9/3R5 w 0 1
9/9/4k4/9/9/9/9/1n1K5/6c2/3R5 b 0 1
4k4/9/9/9/9/2n6/9/3K5/9/1c1R5 w 0 1
5k3/3c5/9/9/9/9/3n5/3K5/9/2R6 w 0 1
9/9/5k3/3c5/9/9/3n5/3K5/9/1R7 w 0 1
4k4/9/9/9/9/2c6/4n4/3K5/9/1R7 b 0 1


Samples of perpetual chases:
4c4/4k4/9/9/n8/1R7/9/3K5/9/9 b 0 1
4c4/4k4/9/2n6/9/1R7/9/9/3K5/9 w 0 1
4c4/4k4/9/9/9/9/9/2R6/n8/3K5 w 0 1
4c4/9/4k4/2n6/9/1R7/9/9/3K5/9 w 0 1
9/4k4/4c4/9/3R5/5n3/9/9/5K3/9 w 0 1
4c4/4k4/9/2n6/9/1R7/9/9/9/3K5 w 0 1
4c4/4k4/9/9/n8/1R7/9/9/9/5K3 b 0 1
4c4/4k4/9/9/n8/1R7/9/9/9/3K5 b 0 1
4c4/4k4/9/9/9/9/9/2R6/n8/5K3 w 0 1
4c4/4k4/9/9/n8/2R6/9/9/9/5K3 w 0 1


Samples of max leading perpetuations:
9/4k4/4c4/9/9/9/9/1n1K5/1R7/9 b 0 1
9/4k4/4c4/1n7/9/9/9/3K5/1R7/9 b 0 1
9/4k4/4c4/9/9/9/9/1n1K5/R8/9 b 0 1
9/4k4/4c4/9/9/9/4n4/3K5/R8/9 b 0 1
9/4k4/4c4/9/4n4/9/9/3K5/1R7/9 b 0 1
9/4k4/4c4/9/9/9/n8/3K5/R8/9 b 0 1
9/4k4/4c4/9/4n4/9/9/3K5/R8/9 b 0 1
9/4k4/4c4/9/9/9/4n4/3K5/1R7/9 b 0 1
9/4k4/4c4/9/n8/9/9/3K5/1R7/9 b 0 1
9/4k4/4c4/1n7/9/9/9/3K5/R8/9 b 0 1
A perpetual chase game:

Code: Select all

[Event "FelicityEgtb"]
[Site "banksiagui.com"]
[Date "2024.10.01"]
[Time "21:31:18"]
[Round "*"]
[White "hm::White"]
[Black "hm::Black"]
[Result "*"]
[PlyCount "51"]
[Variant "xiangqi"]
[FEN "9/4k4/4c4/9/4n4/9/9/3K5/1R7/9 b - - 51 25"]
[SetUp "1"]

1...e5c4 2.d2e2 c4e5 3.e2f2
e5g4 4.f2f1 g4e3 5.f1f0
e3g2 6.b1g1 g2f4 7.g1g8
e8e9 8.g8g7 e9e8 9.f0f1
f4e6 10.g7f7 e6d4 11.f1f2
d4e6 12.f7f8 e8e9 13.f8f6
e6d4 14.f6d6 d4f5 15.d6e6
e9e8 16.e6e5 f5g3 17.e5e3
g3f5 18.e3e6 f5d4 19.e6e4
d4b3 20.f2f1 b3d2 21.e4e2
d2b3 22.e2e5 b3d2 23.f1f0
d2c4 24.e5e4 c4d2 25.e4e3
d2c4 26.e3e4 c4d2
https://banksiagui.com
The most features chess GUI, based on opensource Banksia - the chess tournament manager
noobpwnftw
Posts: 614
Joined: Sun Nov 08, 2015 11:10 pm

Re: Felicity EGTB generators and probers

Post by noobpwnftw »

It doesn't seem right beyond "Legal positions".
User avatar
phhnguyen
Posts: 1484
Joined: Wed Apr 21, 2010 4:58 am
Location: Australia
Full name: Nguyen Hong Pham

Re: Felicity EGTB generators and probers

Post by phhnguyen »

noobpwnftw wrote: Tue Oct 01, 2024 2:44 pm It doesn't seem right beyond "Legal positions".
Can you say more clearly? What is wrong? What are your correct stats?

I have been working to twist, verify and correct the program. All ideas/data will help. Thanks
https://banksiagui.com
The most features chess GUI, based on opensource Banksia - the chess tournament manager
noobpwnftw
Posts: 614
Joined: Sun Nov 08, 2015 11:10 pm

Re: Felicity EGTB generators and probers

Post by noobpwnftw »

Code: Select all

wtm win: 16623945
wtm lose: 116185
wtm draw: 98756
wtm longest: 2c6/3nk4/9/5R3/9/9/9/9/3K5/9 w
wtm max dtm: 48

btm win: 2740562
btm lose: 16727069
btm draw: 550451
btm longest: 3c5/4k4/9/9/8R/9/9/3K5/4n4/9 b
btm max dtm: 28
Your legal count appears to be correct, what is wrong appears to be 1) how double perpetuals are adjudicated and 2) how perpetuals are counted towards dtm. Appearently the winning side can force perpetuals in order to reach shorter dtm.
phhnguyen wrote: Tue Sep 17, 2024 2:07 pm I am happy to say that the issue of Chinese chess perpetual rules has been solved completely, both theoretically and practically.
Bold claim, I may have no other ideas to provide.
User avatar
phhnguyen
Posts: 1484
Joined: Wed Apr 21, 2010 4:58 am
Location: Australia
Full name: Nguyen Hong Pham

Re: Felicity EGTB generators and probers

Post by phhnguyen »

noobpwnftw wrote: Tue Oct 01, 2024 4:37 pm

Code: Select all

wtm win: 16623945
wtm lose: 116185
wtm draw: 98756
wtm longest: 2c6/3nk4/9/5R3/9/9/9/9/3K5/9 w
wtm max dtm: 48

btm win: 2740562
btm lose: 16727069
btm draw: 550451
btm longest: 3c5/4k4/9/9/8R/9/9/3K5/4n4/9 b
btm max dtm: 28
Your legal count appears to be correct, what is wrong appears to be 1) how double perpetuals are adjudicated and 2) how perpetuals are counted towards dtm. Appearently the winning side can force perpetuals in order to reach shorter dtm.
Do you use normal (DTM) scores for perpetual positions?

In my EGTB, I use two metrics. One is normal DTM. The other one is perpetual metric. Those metrics distinguish each other by their score ranges. The main reason for creating a new metric (perpetual one) is that perpetuations are undetermined (for a given perpetual position and without extra information, say, history moves, we cannot know exactly how long to win/lose). That is not good to replace or mix with DTM - a determined one. We create two special scores: PERPETUAL_SCORE_CHECK and PERPETUAL_SCORE_CHASE to mark perpetual positions. Besides them, we have some leading/toward scores, used for ancestor positions leading to perpetual ones.

The algorithm to detect perpetual positions knows and counts the shortest paths to win anyway.
noobpwnftw wrote: Tue Oct 01, 2024 4:37 pm
phhnguyen wrote: Tue Sep 17, 2024 2:07 pm I am happy to say that the issue of Chinese chess perpetual rules has been solved completely, both theoretically and practically.
Bold claim, I may have no other ideas to provide.
Advertising should always be loud. What I say is always biased to me! ;)

To refuse my claim, you and other people need to point out what is wrong with that! ;)

BTW, all of my methods, documents and code will be published soon. I keep nothing for myself or in secrets. Please join to develop, and verify them if anyone can.
https://banksiagui.com
The most features chess GUI, based on opensource Banksia - the chess tournament manager
noobpwnftw
Posts: 614
Joined: Sun Nov 08, 2015 11:10 pm

Re: Felicity EGTB generators and probers

Post by noobpwnftw »

How to count them in DTM is appearently the million dollar question.

Obviously whether one side should commit to a perpetual is dependent on the game outcome, therefore if they are not considered together then adjudication will be wrong in some mutual check or chase cases. They can be nested, some more complicated ones are not seen until there are more pieces on board. You might not know the upperbound of the actual distance to mate due to how many repetitions happened in history or about to happen, but there is certainly a determistic lowerbound before which no mate is possible with perfect play, all things considered.

Bottom line is it at least needs to be consistent with game outcome, you have more draws than mine, and I told you why.
User avatar
phhnguyen
Posts: 1484
Joined: Wed Apr 21, 2010 4:58 am
Location: Australia
Full name: Nguyen Hong Pham

Re: Felicity EGTB generators and probers

Post by phhnguyen »

noobpwnftw wrote: Tue Oct 01, 2024 4:37 pm

Code: Select all

wtm win: 16623945
wtm lose: 116185
wtm draw: 98756
wtm longest: 2c6/3nk4/9/5R3/9/9/9/9/3K5/9 w
wtm max dtm: 48

btm win: 2740562
btm lose: 16727069
btm draw: 550451
btm longest: 3c5/4k4/9/9/8R/9/9/3K5/4n4/9 b
btm max dtm: 28
I have been testing and verifying my tools. Any chance to verify will be good for me.

Look into your stats, there is something quite different from mine. For example, your max DTM is 48, mine is 116. I guess yours is a number of full moves (2 x plies = 2 x 48 = 96) when mine is in plies. Seriously, they are not matched with a big gap. My max DTM does not count perpetual positions thus your number should be similar to or larger than mine if you count perpetuations.

I have several FEN samples for max DTM in my stats. From one of them, I got the game below with 116 plies. Can you check if there is any wrong? What is the game extracted by your EGTB for that FEN?

Note again, it is a pure DTM position, without perpetuation involved.

Code: Select all

[Event "FelicityEgtb"]
[Site "banksiagui.com"]
[Date "2024.10.03"]
[Time "00:50:33"]
[Round "*"]
[White "hm::White"]
[Black "hm::Black"]
[Result "1-0"]
[TimeControl "40/300+1"]
[PlyCount "116"]
[Variant "xiangqi"]
[FEN "9/3k5/9/9/9/9/6n2/5K3/9/1R2c4 b - - 2 58"]
[SetUp "1"]

1...e0e5 2.b0b5 e5e6 3.b5b6
e6e7 4.b6b8 d8d9 5.b8b7
g3f5 6.b7b9 d9d8 7.b9f9
f5d6 8.f9e9 d6f5 9.f2e2
f5d4 10.e2e1 d4f3 11.e1e0
f3g1 12.e0f0 e7f7 13.e9f9
g1e2 14.f0f1 f7d7 15.f9e9
e2d0 16.f1e1 d0c2 17.e1e0
c2d4 18.e9e8 d8d9 19.e8e5
d9d8 20.e5d5 d4e2 21.e0e1
e2c3 22.d5d4 c3b5 23.d4d3
b5c7 24.e1f1 c7b5 25.f1f2
b5c7 26.d3d6 c7b5 27.d6c6
d8d9 28.c6c5 b5a3 29.f2e2
d9d8 30.e2d2 d7d6 31.c5c6
d8e8 32.d2d1 a3b5 33.c6c5
b5a3 34.c5c8 e8e9 35.c8b8
a3c2 36.b8b6 d6d7 37.b6e6
e9f9 38.e6e7 d7d6 39.e7d7
c2e3 40.d1d0 e3c4 41.d0e0
f9f8 42.e0e1 d6f6 43.d7d8
f8f9 44.d8d4 c4b2 45.e1f1
f9e9 46.d4e4 e9d9 47.e4b4
b2c0 48.f1f2 d9e9 49.b4e4
e9d9 50.f2e2 f6d6 51.e4d4
d6d8 52.d4c4 d8e8 53.c4c0
e8e6 54.c0c6 e6e7 55.c6c7
e7e8 56.c7g7 d9d8 57.g7g8
e8f8 58.g8f8 d8d9 59.e2e1
 1-0
https://banksiagui.com
The most features chess GUI, based on opensource Banksia - the chess tournament manager
noobpwnftw
Posts: 614
Joined: Sun Nov 08, 2015 11:10 pm

Re: Felicity EGTB generators and probers

Post by noobpwnftw »

They are of course counted in plies while I don't count perpetuals. Actual mate sequence can only be longer, regardless of how the winning side played.

What you should try to find is, can a shorter than metric distance be achieved by a perfect player.

https://www.chessdb.cn/query/?9/3k5/9/9 ... /9/1R2c4_b

In my opinion, when you use my moves to play white and yours black, if it ended up not lasting 116 plies or more, then there are some problems to solve.