Felicity EGTB generators and probers

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

User avatar
phhnguyen
Posts: 1498
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 very happy that my new paper, "Chinese chess EGTB with perpetual check-chase rules," has been accepted for presentation at CG 2024 (Computers and Games 2024 conference, November 26-28, 2024). I have been working on the final version of the paper and the code. Join that conference if you want to discuss it and ask me directly :D
https://banksiagui.com
The most features chess GUI, based on opensource Banksia - the chess tournament manager
noobpwnftw
Posts: 683
Joined: Sun Nov 08, 2015 11:10 pm

Re: Felicity EGTB generators and probers

Post by noobpwnftw »

In case you do not know, a lot of people have pionneered this, while I'm not a fan of any academics, here you can find a few references:
http://lpforth.forthfreak.net/
Haw-ren Fang, Tsan-sheng Hsu and Shun-chin Hsu. "Indefinite Sequence of Moves in Chinese Chess Endgames", Proc. 3rd International Conference on Computers and Games (CG), to appear in a Springer-Verlag LNCS volume, 2002. [pdf]

Haw-ren Fang, Tsan-sheng Hsu and Shun-chin Hsu. "Construction of Chinese Chess Endgame databases by Retrograde Analysis" Proc. 2nd International Conference on Computers and Games (CG), Springer-Verlag LNCS# 2063, pages 96--114, 2000. [pdf]

Ren Wu and Donald F. Beal. "A Memory Efficient Retrograde Algorithm and Its Application To Chinese Chess Endgames" More Games of No Chance MSRI Publications Volume 42 , 2002. [pdf]
I don't understand how solving perpetuals is news in 2024, but if you are at limited knowledge level like hgm, then it can be the case.

And I looked at your code, if it involves a runtime search to find the best move, then it is hardly a 'tablebase', even in the Syzygy case, it is about reconstructing the folded ply counter as a part of the compression algorithm rather than actually using the information at runtime to 'correct' results.

It is under my impression that those in academics are serious people(with exceptions), and so far you haven't even convinced a non-serious critic like me about your approach being coherent judging by your previous responses. I wish you will not be grilled about the details, and nobody remembers what they have heard two decades ago.
User avatar
hgm
Posts: 28134
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Felicity EGTB generators and probers

Post by hgm »

It has really become an obsession for you to hide fabricated negative remarks about me in everthing you post, eh?
noobpwnftw
Posts: 683
Joined: Sun Nov 08, 2015 11:10 pm

Re: Felicity EGTB generators and probers

Post by noobpwnftw »

I certainly did not want anything to do with you in the first place.
phhnguyen wrote: Sat Oct 12, 2024 3:57 am Yes, it is good for us all. So far there are so few people working in that field. In this forum, looks like there are only three: you, me and @HGM. Hope some more people join us soon.

My design has been not finalized yet, all may be changed seriously. It is good that you published your EGTB. I am going to publish all my work (EGTB, code, as well as some documents I have been writing). Thus we have chances to verify all methods and make all things work.
As for the facts, despite what you say, you never had a working solution anyways. I only corrected a false impression.
User avatar
phhnguyen
Posts: 1498
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: Mon Oct 28, 2024 7:31 am In case you do not know, a lot of people have pionneered this,
I agree that many people started working on chess/Chinese chess in the very early days. However, some of them claimed only they did this or that, but they didn’t publish their works in writing or code. Who could know, verify their work, or get benefits? Do you always trust any claim from anyone without any or enough evidence?
noobpwnftw wrote: Mon Oct 28, 2024 7:31 am while I'm not a fan of any academics, here you can find a few references:
http://lpforth.forthfreak.net/
Haw-ren Fang, Tsan-sheng Hsu and Shun-chin Hsu. "Indefinite Sequence of Moves in Chinese Chess Endgames", Proc. 3rd International Conference on Computers and Games (CG), to appear in a Springer-Verlag LNCS volume, 2002. [pdf]

Haw-ren Fang, Tsan-sheng Hsu and Shun-chin Hsu. "Construction of Chinese Chess Endgame databases by Retrograde Analysis" Proc. 2nd International Conference on Computers and Games (CG), Springer-Verlag LNCS# 2063, pages 96--114, 2000. [pdf]

Ren Wu and Donald F. Beal. "A Memory Efficient Retrograde Algorithm and Its Application To Chinese Chess Endgames" More Games of No Chance MSRI Publications Volume 42 , 2002. [pdf]
No. Those above authors are pioneers in applying EGTB into Chinese chess but they did not focus nor solve the perpetual check and chase (PCC) issues. Ren Wu generated only one-side-armed endgames (one side has attacker pieces such as Rooks, Cannons, Horses, and Paws and one side has no attackers) to avoid completely the PCC. Haw-ren Fang did the same for some works. In other words, Haw-ren Fang implemented perpetual check only (not perpetual chase) and/or highly abstracted those rules. None of their work was a PCC practical method. None of their work could generate two-side-armed endgames nor publish any data that could be used in real-life chess tournaments.

You should know that any academic paper must review all previous related works. That means it must make sure the new work is novel or novel enough. I’m sure I have reviewed and mentioned all the authors and their works you have mentioned above and even more than that.

FYI, academic papers are always reviewed by teams of scientists in the same field, considering many aspects (including other works and novels), under long processes and they will vote to accept or not.

noobpwnftw wrote: Mon Oct 28, 2024 7:31 am I don't understand how solving perpetuals is news in 2024
I agree PCC itself is academically not new in 2024 because I published a paper about it in 2018 ;) I’m sure it is the first-ever published (novel enough) in that field. I guess you didn’t know that, did you? My current work is not about PCC but to use that work (2018) to apply to a generator of Chinese chess EGTB.
noobpwnftw wrote: Mon Oct 28, 2024 7:31 am but if you are at limited knowledge level like hgm, then it can be the case.
Calm down man, you should not be angry without any reason and attack other people like that! Being polite and respectful of others are the minimum requirements to discuss.

You and someone sometimes claim you are talented and better than us (me and HGM) in some knowledge such as PCC. I agreed too. However, you all didn’t bother to discuss with us about PCC, did not publish anything and ignored totally our efforts and our published works, how could we know how talented you are, your works and/or verify them?

noobpwnftw wrote: Mon Oct 28, 2024 7:31 am And I looked at your code, if it involves a runtime search to find the best move, then it is hardly a 'tablebase', even in the Syzygy case, it is about reconstructing the folded ply counter as a part of the compression algorithm rather than actually using the information at runtime to 'correct' results.

It is under my impression that those in academics are serious people(with exceptions), and so far you haven't even convinced a non-serious critic like me about your approach being coherent judging by your previous responses. I wish you will not be grilled about the details, and nobody remembers what they have heard two decades ago.
Look like you have read my code but have not known/understood the work behind it. Clearly, you haven’t read my paper yet (it will be published by CG2024 this November) but you are in a hurry to make many conclusions. If you want to feedback, suggest, criticise or even attack (academic attacks are accepted but not personal ones) you should at least read it first. I could give you a copy of my paper thus we could discuss it later. I am always happy to improve and defend my work. I agree that there are still some problems/holes in both the paper and code (I have been working hard to improve them) but they are not what you mentioned.
https://banksiagui.com
The most features chess GUI, based on opensource Banksia - the chess tournament manager
noobpwnftw
Posts: 683
Joined: Sun Nov 08, 2015 11:10 pm

Re: Felicity EGTB generators and probers

Post by noobpwnftw »

Well, a few more comments.
phhnguyen wrote: Tue Oct 29, 2024 1:39 amHowever, some of them claimed only they did this or that, but they didn’t publish their works in writing or code. Who could know, verify their work, or get benefits? Do you always trust any claim from anyone without any or enough evidence?
First of all, the site I linked where the references are found also provides tablebase results that dealt with the full ruleset. Which predates mine and is an independent source of information. Maybe you only looked at the papers but ignored everything else found on the same page. The only one here who did not publish anything in writing or code that is verifiable is obvious and I will not mention by name.

phhnguyen wrote: Tue Oct 29, 2024 1:39 amIn other words, Haw-ren Fang implemented perpetual check only (not perpetual chase) and/or highly abstracted those rules. None of their work was a PCC practical method. None of their work could generate two-side-armed endgames nor publish any data that could be used in real-life chess tournaments.
I also do not consider a specific term you invented to describe a secondary metric a distinct one that is unrelated to any previous work. A paper that implemented only a partial ruleset does not invalidate the generic counting method involved, and the same can be said that you probably never generated any tables with two or more attackers on each side to be able to make any claim about a working solution. The above mentioned site did, BTW. There will be complications involved and I can tell you that because I also did it already.

phhnguyen wrote: Tue Oct 29, 2024 1:39 amMy current work is not about PCC but to use that work (2018) to apply to a generator of Chinese chess EGTB.
...
However, you all didn’t bother to discuss with us about PCC, did not publish anything and ignored totally our efforts and our published works, how could we know how talented you are, your works and/or verify them?
Great, then your claim that I did not publish anything is blantly false, not only had my results been available for a very long time, the code has been there for more than a year. Also mind you that you only got your numbers correct fairly recently, so probably I did bother to disscuss with tablebases you. While you can argue that I have no interest in your approach in particular, in my opinion that is purely a detour you took to solve the same underlying problem.

phhnguyen wrote: Tue Oct 29, 2024 1:39 amClearly, you haven’t read my paper yet (it will be published by CG2024 this November) but you are in a hurry to make many conclusions. If you want to feedback, suggest, criticise or even attack (academic attacks are accepted but not personal ones) you should at least read it first.
Lastly, given that you have made bold claims already, I read what you have published and made comments based on what is available to me. Now you are arguing that I can't criticize on anything before some of your future work is done. How does that work? Can I say I'm still working on improving my conclusion and that is what I think it is until further notice?


I never even claimed that I had 'solved' the problem, yet as of today I have built 8669 piece combinations.
How many of those have you built to be the unhumble one?
There is nothing personal, tablebases are mathematical facts and 'working hard' or guilt tripping does not make them more correct.
noobpwnftw
Posts: 683
Joined: Sun Nov 08, 2015 11:10 pm

Re: Felicity EGTB generators and probers

Post by noobpwnftw »

With that said, I wish you good luck with your presentation and I believe I have provided enough information and results for you to digest and verify before a reasonable discussion can proceed. Therefore I will not respond to chitchat until you have done so.
User avatar
hgm
Posts: 28134
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Felicity EGTB generators and probers

Post by hgm »

I have been rethinking my algorithm a bit. One of the tasks it would have to perform is identifying which black-to-move positions (black referring to the losing player) only have non-losing moves that qualify as chases. Originally I planned to mark the positions where a white piece (king or unprotected other) is under attack in the EGT itself, so that this information would be retrieved as a side effect of probing to see whether the position the move leads to is already declared won (for white).

But I now realized that this information can be obtained quite cheaply during the move generation itself. For a given constellation of the white pieces I could mark squares in a board-size array chase[sqr] from where the opponent could attack it, each white piece having a bit assigned to it. When generating moves from a position that is a candidate loss, we could then AND all these codes for the to-squares of moves that (by EGT probing) are found to be non-losing. As soon as the result is zero we could stop, and revert the position to 'undecided', as we would have found a save escape. If this doesn't happen, the resulting chase code will indicate which white piece has to be chased to keep any hope to survive.

When the EGT is scanned by displacing the black pieces in the inner loops, the chase[] board would only have to be re-initialized in an outer loop. E.g. if black has King + Rook once every 9*90 = 810 positions. So this would take only negligible time.

There is one problem with that, though: in some of the 810 black constellations the King might block the move that was marked as attacking a given target. So rather than assigning a single bit to each potential attack, we would need different bits depending on the square it originates from, in particular which Palace squares it crosses. A small table of masks indexed by the king location could then be used to clear the bits from the moves that are blocked.

We cannot plainly AND all resulting chase codes, though, as chases of the same target can now be indicated in different bits. This can be solves by subtracting 1 from the chase code, to see if the carry propagates to some higher bit. If any of the bits indicating the move chases would be set, it would not propagate. By OR-ing all such decremented chase codes we can then determine whether a particular piece must be chased to escape a loss. (Namely when the corresponding bit ends at 0.)
User avatar
phhnguyen
Posts: 1498
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 29, 2024 2:36 am ...had my results been available for a very long time, the code has been there for more than a year.
...
today I have built 8669 piece combinations
First of all, I should say that I always highly appreciate your work and contributions to chess in general and Chinese chess in particular!
noobpwnftw wrote: Tue Oct 29, 2024 2:36 am Lastly, given that you have made bold claims already, I read what you have published and made comments based on what is available to me.
Thanks! So you have read my work, and know I have been working on the field (on which you did not show your work nor activity) but still blamed my knowledge as “you are at limited knowledge level”. ;)

I guess you might not be happy with my work (the one in 2018, and the new one in 2024 are not available yet for public). Do you want to point out clearly what is wrong with that work? ;)

noobpwnftw wrote: Tue Oct 29, 2024 2:36 am Great, then your claim that I did not publish anything is blantly false, not only had my results been available for a very long time, the code has been there for more than a year.
There are two different types of publishing. One is self-simple publishing. A developer may start making his software or his source code public thus other people can access and then he is done. He doesn’t need to show inside algorithms/methods nor prove anything (correctness, novel…). The other one is an academic: the work is mainly in writing and it will be reviewed by a team of scientists before accepting and then be published by a scientific conference or a book/journal.

So far what I have mentioned about publishing is the second one (the academic one since we are talking about my academic paper) and I can't find any academic paper from you or mention your work/code!

I know you and others may publish your/their work as freeware/web software and/or open sources but they are not academic publishes. Recognising your work from millions of open-source projects is impossible, especially when many of them (including yours) don’t have enough documents or even a README. After getting one, the work for just compiling, understanding how to use and then running with the right set of parameters may take a lot of effort and time. Studying thousands of lines of code to understand the methods and/or to verify their correctness is almost impossible either. Thus, except in very special cases, the authors should describe their algorithms/methods clearly and prove the correctness/novels, pass the review of a scientific team to be counted as an academic publish. Never expect a researcher to dig it out from the huge mess of the Internet!
noobpwnftw wrote: Tue Oct 29, 2024 2:36 am Also mind you that you only got your numbers correct fairly recently, so probably I did bother to disscuss with tablebases you. While you can argue that I have no interest in your approach in particular, in my opinion that is purely a detour you took to solve the same underlying problem.
...
yet as of today I have built 8669 piece combinations.
Your EGTB is quite different from mine and I didn’t agree with some data you showed me, thus it is meaningless when you tried comparing them! Software buggy is not a big deal as I will mention later.

noobpwnftw wrote: Tue Oct 29, 2024 2:36 am Now you are arguing that I can't criticize on anything before some of your future work is done. How does that work? Can I say I'm still working on improving my conclusion and that is what I think it is until further notice?
No problem at all!!! You may criticise my work at any time. I always welcome and listen!

I have just suggested reading my paper first since it is the logical first step. Otherwise, you focus on only my code. It is a bit strange from an academic view because software code is a hard target to arm and criticise. I’m sure you cannot understand thoroughly my code within only a few days, especially when you did not consume my paper. It is a very small target and adds only a tiny score to an academic work. Many academic works didn’t have or publish any code. It is also a moving target: I have been changing it daily but I haven’t even merged its branch to the master branch yet and the last pushed one in GitHub may not be the latest one!

The main role of the code is to illustrate that my algorithms can work, producing the data I want, regardless of how buggy and slow it is. It is not about a ready-release state or perfection. So far, it has served me and my work well!

You may know that I have never given up on my software, thus sooner or later it will work well and reach a ready state to release for popular users.
noobpwnftw wrote: Tue Oct 29, 2024 3:14 am With that said, I wish you good luck with your presentation and I believe I have provided enough information and results for you to digest and verify before a reasonable discussion can proceed. Therefore I will not respond to chitchat until you have done so.
Thanks! I don’t mind at all the point you want to continue once we all are talking calmly and politely enough :D
https://banksiagui.com
The most features chess GUI, based on opensource Banksia - the chess tournament manager
noobpwnftw
Posts: 683
Joined: Sun Nov 08, 2015 11:10 pm

Re: Felicity EGTB generators and probers

Post by noobpwnftw »

phhnguyen wrote: Wed Oct 30, 2024 2:27 pm Thanks! So you have read my work, and know I have been working on the field (on which you did not show your work nor activity) but still blamed my knowledge as “you are at limited knowledge level”. ;)

I guess you might not be happy with my work (the one in 2018, and the new one in 2024 are not available yet for public). Do you want to point out clearly what is wrong with that work? ;)
To my knowledge, your previous work was an approach that did not provide full coverage to the corresponding piece set, you were insisting on some partially indexed compression scheme. I do not consider that a valid tablebase solution. Whether this is what you were referring to, I don't know, but I'm glad that now you have ditched it.

And you never actually published any results in terms of WDL results of each table, no? It is to my understanding that, a work in this field, regardless of approach taken, should provide accurate WDL information across a decent amount of piece combinations before making those bold claims. You did it once for one table at year 2024 and it was wrong, so there you have it. I simply expected better.

phhnguyen wrote: Wed Oct 30, 2024 2:27 pm There are two different types of publishing. One is self-simple publishing. A developer may start making his software or his source code public thus other people can access and then he is done. He doesn’t need to show inside algorithms/methods nor prove anything (correctness, novel…). The other one is an academic: the work is mainly in writing and it will be reviewed by a team of scientists before accepting and then be published by a scientific conference or a book/journal.

So far what I have mentioned about publishing is the second one (the academic one since we are talking about my academic paper) and I can't find any academic paper from you or mention your work/code!
Like I said, I'm not interested in academics. However I wonder whether doing the academics does not require you to provide enough correct results in the first place. You probably never attempted to verify your WDL results against any publicly available information, nor does it seem to me that you are interested in doing so. I will be surprised if you say you do not know that they exist.

Let's not brush it off as some 'software bug'. In terms of tablebases as mathmatical facts, you either get it right or you don't. How can this pass peer review is beyond me, yet it appears to me that you just managed to pull this off with an 'idea' that never produced correct WDL results across a variaty of piece combinations and verify for their correctness. I'm not even talking about other 'cosmetics' like efficiency or going into the consideration of the distance counting metrics.

As for the tablebases, algorithms are in the generator code and the method is pretty standard. Every one of those generator code is a huge mess, mine included, but that's irrelevant because by the end of the day nobody cares. I do not need a scientist to review once final data is available for everyone to access and verify for themselves. It is done, once I get to the mathematical facts, there is no need to care about any generation no more. If someone finds an error, then it is undone and they'll either have to fix the generator and rebuild for themselves or have me do it for everyone. In terms of documentation and logic abstraction, since I have read your code, it's not even close but that's just my opinion.

The funny irony is that on one hand you tried really hard to shittalk those previous work published in journals, then at the same time argue that it is important to have yours in because non-academics are nowhere to be found for continuity of their work or correctness.

phhnguyen wrote: Wed Oct 30, 2024 2:27 pm Thanks! I don’t mind at all the point you want to continue once we all are talking calmly and politely enough :D
I can be polite if you stop writing like a GPT. You have a habit of dodging key issues I raised in regard to tablebases.
Let's start with this: how many different piece combinations do you have results on? Can you show WDL numbers of all of them?