Felicity EGTB generators and probers

[phhnguyen]

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.

I realise that you have been talking about an apple and me about an orange

Clearly, you didn’t read my work in 2018. The paper was about the implementation of perpetual check-chase (PCC) rules only, not about EGTB at all!

Thus I believe your mentioning about the limited knowledge of HGM and me is just a non-supported or a false claim!!!

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.

WDL is just a statistic and I have created many of them and changed them many times since my code is in development, changed almost daily.

Looks like you so insist on the correctness of those statistics, I could say: that my first post about WDL statistics here was incorrect since it differed from later ones.

Frankly speaking, I’m not sure if my latest ones will be unchanged forever since I have been still changing my 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.

I am sure that any data and my stats are always verified for correctness. They all are always perfect for the design and implementation at the time they are created.

For novel work, we may not have anything else to compare to.

I used to verify my results with yours. Unfortunately, I wasn’t satisfied with the results from your EGTB since they didn't pass my tests or my view. Please note that I didn’t mean or say yours was incorrect because your view and design are quite different from mine. We all may need more time, study, and effort as well as create some better test sets and better ways to evaluate.

An academic work must review all related academic ones but not compulsory for practical works, especially when we don’t trust or are not sure about their correctness.

[noobpwnftw]

Well, that's pretty unfortunate. Whatever you claim you did in 2018 never reached my ears, and I know a good number of people who actually do relevant work in this field and/or built their tablebases and made them publicly available.

I do not care about how you think about metrics or methods whatsoever that is unrelated to tablebases, building tablebases is more of an engineering problem, and I simply need to see results before I judge whether the engineering took to get to them is valid. If you end up building rectangle wheels, I will not want to read about how you were forging them.

You and hgm never published any significant amount of data in terms of game outcome WDL stats, those are provable facts btw, regardless of the method you use or metrics you count distances, and those are the fundamentals of any tablebases that exist, let's not reinvent what a tablebase is, thank you very much.

It's funny that you claim that those WDL results should change, no they don't. If you haven't gotten them right, you didn't 'solve' the problem. Some may do it faster, some slower, doesn't really matter, you can write a paper on how to efficiently solve the problem, or use less memory, whatever, but if you didn't get the correct outcome, your work is invalid and you should get it right before making wild claims(even if it is horribly slow and works only for a small number of piece combinations, the bar is really low, just FYI).

You don't need to trust anyone, you show your own results and let's see which one is right. If you don't, there is nothing to prove and cannot be trusted.

[hgm]

I think I have finalized a resonably detailed description of the EGT generation I have in mind.

Terminology
successor: a position that can be reached from the current one through a normal ('prograde') pseudo-legal move.
predecessor: a position from which the current one can be reached by a normal move.

General strategy
Because the processes of determining white wins and black wins are completely independent, and the complexity of the end-games they can handle is limited by the amount of storage, it is a bad idea to run those simultaneously, sharing the storage. We therefore solve for white wins vs white non-wins, and leave the determination of which of these non-wins are black wins to the generation of the end-game with reversed colors. We will first outline the algorithm focusing on correctness and storage requirements. How the efficiency can be improved (leading to a speedup) will be discussed after that. In the entire discussion we will use the KRCKR end-game as an example.

The algorithm
Each board position will be mapped to an array element by an index calculation. That array element will then contain information for that position with both white to move (wtm) and black to move (btm). The winning distance (Distance To Mate or other) will only be stored for the btm positions. It appears that in this case a single byte will be sufficient to hold all information. The code stored in the byte will determine the state of both the wtm and btm position. These can be:

white to move:
UNSET position is not yet proven to be a win
WON position is a proven win
PERPETUATE-K position that might be a win due to perpetual checking
PERPETUATE-C position that might be a win due to perpetual chasing of the Cannon
PERPETUATE-KC position that might be a win due to checking or chasing

Black to move:
UNSET position is not yet proven to be a loss
LOST(2N) position is a proven loss in N full moves
MUSTCHASE-K position where the only non-losing moves check
MUSTCHASE-C position where the only non-losing moves chase the Cannon

Note that the PERPETUATE and MUSTCHASE are special cases of UNSET; a win/loss is not proven for those. The MUSTCHASE and PERPETUATE states occur in two flavors: 'candidate' or 'cleared'. This means there are 2x3+2 = 8 states for the wtm position, requiring 3 bits. That leaves 5 bits (i.e. 32 states) for the btm positions. The MUSTCHASE and UNSET states take 5 of these, leaving room for 27 LOST states.

We calculate up to capture of the black King, so wtm positions are won in an odd number of ply, and btm positions lost in an even number of ply.

Initialization
Initially all wtm and btm positions will be in the UNSET state. The wtm positions from which the black King can be captured will then be set to the WON state. At this stage all WON positions are won in 1 ply.

Iteration
At the start of iteration number N, in which we determine the LOST(2N) positions, in general all states will occur, with the understanding that all PERPETUATE and MUSTCHASE positions have the 'candidate' flavor, the LOST(2M) positions only occur with M < N, and all WON positions will be won in in at most 2N-1 ply. We then start running through all UNSET btm positions, ('pass 1') and calculate their successors by prograde black moving, to probe the state of these successors. The black move generator is aware of which moves qualify as checks or chases; other moves we call 'safe'.
* If a safe move to an UNSET (wtm) successor is found, the examined position remains UNSET.
* If all successors are WON, the examined position will be set to LOST(2N). This because there must at least be one position amongst those which is won in 2N-1 ply, or the examined position would already have been set to LOST in some previous iteration.
* If all safe moves lead to WON successors, but there are still checking or chasing moves to successors in an UNSET or PERPETUATE state, and these all chase the same piece (K or C), the examined position is set to MUSTCHASE (K or C) if it was not in that state already.
In the latter case we immediately generate the (wtm) predecessors through retrograde checking or chasing evasions that chase the same piece, and set their state to PERPETUATE if it was not already WON. Note that the state could already have been a PERPETUATE of a different type, in which case the newly chased piece is added to this. (E.g. PERPETUATE-C will become PERPETUATE-KC if it has a MUSTCHASE-K successor.) All new MUSTCHASE and PERPETUATE states will have the 'candidate' flavor (like the already existing ones).

After we have treated all UNSET btm positions this way, we perform perpetual detection. This will take multiple 'sub-iterations'. In Each of those we start running though all MUSTCHASE-X positions (X = K or C), for generating the prograde black checking or chasing moves (as the case requires ('pass 2a'); by definition all other moves would go to WON wtm positions, i.e. lose). If these all lead to WON or PERPETUATE-X positions of the 'candidate' flavor we don't do anything (yet). If not, we change the flavor of the examined MUSTCHASE-X position to 'cleared', to indicate that black has a move to escape the perpetual cycle.

We then go through all PERPETUATE-X candidates, generating their prograde moves, to test whether there still is at least one that goes to a MUSTCHASE-X candidate ('pass 2b'). (So not one that has been cleared!) If not, it the examined position is cleared.

Step 2a & 2b will be alternately repeated until one fails to clear any positions. We then finally run through all MUSTCHASE and PERPETUATE positions again ('pass 2c'): those that are still candidates will now be set to LOST(2N) or WON, respectively. Those that were
cleared will be reset to candidates.

To finish the iteration we must run through all UNSET wtm positions ('pass 3'), and generate prograde moves from those to probe the successors. If one of these successors is LOST, the examined position can be set to WON. (The lost position would be a LOST(2N), and the
WON position won in 2N+1 ply, or this would have happened already in a previous iteration, and the wtm position would not have been UNSET anymore.)


EFFICIENCY

Generating prograde moves from all UNSET positions to probe their successors, and see if their state requires update of the state of the examinend position is a rather inefficient way of doing things. This because typically in many leading iterations only relatively few positions will get their state changed. So you would repeat the same test on a position over and over again, with identical outcome, because none of the successors changed state during the previous iteration. It is then much more afficient to start from the positions that did change their state in the latest iteration, and first generate retrograde moves from those, to arrive at predecessors that
did have at least one successor that changed state. You can then do the test on the other successors of those.

Determination of the WON positions in the initialization step can be conveniently done by calculating for every constellation of the pieces other than the black King which squares in the black Palace these attack, and then set the positions with the black King on those squares to WON. That way you don't have to test all UNSET wtm positions to see whether these are won or not, but selectively generate those that are WON, without further testing.

During iteration efficiency is improved by identifying positions that have changed successors selectively by retrograde moving from these successors, and then only test the identified ones. Retrograde non-captures are the same as prograde non-captures; it is just the captures that do not exist in retrograde moving. Instead you would have 'uncaptures': even non-capturing move from a position that does not have all pieces on the board would also have to be tried as an uncapture of the missing pieces, i.e. with one of the missing pieces appearing on the from-square of the non-capture. In Xiangqi there can be limitations as to what pieces can appear on a given square, as some piece types are bound to a subset of the squares.

At the expense of some extra storage we could use an auxiliary data structure for remembering where the retrograde moves go to. This could be either a 'to-do bitmap' or, when this map would be very sparsely populated, a hash table for storing the indices. These techniques might be especially helpful for the MUSTCHASE positions, of which there might only be a few through which we have to cycle multiple times for indicating perpetuals.

The described algorithm also makes use of retrograde check or chase evasions, for finding PERPETUATE predecessors of MUSTCHASE positions. Since the MUSTCHASE is piece-specific, you know which white piece should be under attack in the predecessor. In KRCKR there is only one black piece that can chase or check, namely the Rook. (A King cannot check, and chasing with a King is allowed, and thus doesn't have to be treated special.) This can be done efficiently through relatively small tables indexed by the locations of the chasing piece and the piece you want chased, or (with even smaller tables) by the relative position of the two. For distant slider moves you would still have to test whether the path of attacker and chased piece to the tabulated locations are not obstructed.

Faster move generation
For generating prograde moves from btm positions we have to qualify the moves as check, chase or safe. This is relatively easy to do, by using an auxiliary board where each square is marked with the pieces that would be attacked from it by the various types of potential chasers. E.g. if the black Rook is the only possible chaser, the files and ranks of chasable pieces would be marked by an indication for what would be chased from there, and all Rook moves would test the destination square on that board to see if and what they chase. (In KRCKR the white Rook would not be a chasable piece, as according to the chasing rules attacks on R by R are not chases, but 'offer to exchange'.) By scanning through the positions in a suitable order we can make it such that the auxiliary board has to be recalculated infrequently, and then can be used for classifying the moves from many positions.

When examining an UNSET btm position we would try the safe moves immediately, and stash the checks and chases for later examination if no safe move to an UNSET wtm position is found. If we examine a MUSTCHASE-X positions, however, we already know there are no such safe moves, and it would help if we could generate the checks and chases selectively. This should be possible with the aid of small tables that contain possible attack squares and are indexed by the relative position of attacker and target. Only a small fraction of the moves would be checking or chasing: in KRCKR at most two for checking, and two for chasing, while there could be 17 Rook moves and 4 King moves in total.

The verification of UNSET btm states would usually be done over and over again, once in every iteration. Even if we limit this to positions where we know that one of the successors changed, this can become a source of inefficiency. Initially this is not so best, and most wtm positions will be UNSET too, and the first safe move we try will then already be enough to certify the examined position as remaining UNSET. But in generally won end-games the final iterations would have nearly all wtm posiitons declared WON, and we might have to try many moves before we find one to an UNSET position. This would then be repeated in the next iteration.

It would help if this next iteration somehow had a clue as to which moves have already be tried in vain previously, and thus can be safely skipped. This could be done by setting apart some of the codes in the btm field of the EGT entry for the position for indicating this (all meaning UNSET as far as the state is concerned), instead of the DTM. With a DTM limit of 26 there is not much room for this, though. But if the potential black moves are divided in groups, like {King moves, Took North, Rook South, Rook East, Rook West}, we could use 5 codes to indicate which of the earlier groups can be skipped.

Extending DTM
Small DTM range is not completely fatal, though. If the EGT is not yet fully resolved when the maximum DTM is reached, we can safe the result, collapse all LOST posiitons to LOST(2), redefined to mean LOST(2*MAX_DTM), and continue generating using this new mapping of codes to DTM.

An alternative is to sue smarter encoding: Instead of reserving 3 bits for encoding the wtm state, we can make use of the fact that all PERPETUATE states involving K (i.e. in-check positions) will always remain UNSET for btm, as black can apparently capture the King there. So PERPETUATE-K and PERPETUATE-KC of both flavors can be collapsed into a single wtm code, using the btm code to distinguish them. That leaves only 5 wtm states to encode, and thus 256/5 = 51 possible btm state codes. With 5 such codes used for UNSET and the four versions of MUSTCHASE, that still leaves 46 possible DTM, rather than 27, so that it is not so critical to spare some of those for use as UNSET with a move hint.

[hgm]

I guess that in general we would also need MUSTCHASE states for btm positions that attack more than a single piece. I thought such a state would not be necessary, because if the only non-losing moves check or chase one piece OR another, you could alsways switch what you are attacking, and at worst get into a one-chases-many situation. (Which is allowed.) But it is possible that all moves do attack one piece AND another, so that in fact the position could be part of two forbidden perpetuals. And this isn't even very unlikely, if only a single non-losing move is left. Even in KRCKR the black Rook can easily do a move that checks as well as chases the Cannon.

I suppose that in KRCKR (which I am now programming as a 'proof of principle') I can get away by treating such a double attack as a check, as a single Rook cannot perpetually chase a Cannon in a loop that also contains a check: white would have to resolve the check, and cannot do that by moving the Cannon. So the Cannon would remain under attack (but parhaps cannot be taken because of a mate threat), which means that the Rook cannot create a new attack on it in the next move. Keeping attacking it from a different location would not count as chase.