Coding my 7-men generator

[h.g.muller]

I finally started coding on my 7-men generator. At least for 3+4 and 4+3 end-games; 2+5 will likely need another algorithm. Some details of how to orgnize the tablebase on disk during the building are still in the open, but it will be something like this:

The tablebase will be organized as 4-(black)-men chunks, and a regular pawnless 7-men like KQRKQRN would have 528*64 of those. Each chunk would occupy 15 (hopefully contiguous) MB on disk; 2MB for a bitmap of the won (wtm) positions, one bit per position, and after that packed lists of lost(0), lost(1), ... lost(N) btm positions. The lists would be packed with a form of run-length coding, where a single byte would specify two lost positions (if the sum of their run length measured as the number of non-lost positions before them is smaller than 19), one lost position (if its run-lengt is between 0 and 63), or zero lost positions (if it is just a spacer of 64 or 4096 non-lost positions, needed to bridge large gaps in the tablebase).
Lost(N) could mean lost in N moves or lost in N plies, and 'lost' could mean checkmated, converted or zeroed, that does not really matter to the format.

This format is how the tablebase will be left on disk by the generator after the building process. People interested in the actual data (I am usually only interested in the statistics obtained during the build) can convert this fomat to a more compact form, like a Hufman encoded DTx tablebase, or a bitbase.

More news later.

[guyhaw]

[quote="h.g.muller"]The tablebase will be organized as 4-(black)-men chunks, and a regular pawnless 7-men like KQRKQRN would have 528*64 of those.

May I ask what you mean by '4-men chunks'?

Btw, did you finish your work on 5-1 FEG DTM EGTs? Any news of the zugzwang positions in 5-1 endgames?

g

[h.g.muller]

You must confuse me with someone else. I never worked on 5+1 tablebases, nor with FEG.

With 4-(black)-men chunk I mean a slice of a 7-men tablebase that keeps all 3 white pieces fixed. This is for the case of a 3+4 men. If it is 4+3, the chunks are still slices that keep 3 white pieces fixed, so in that case they are 1+3 slices.

The indexing scheme within a chunk will be simple concatenation of the 6-bit square numbers. The white piece or the black King will provide the most significant bits. The part of the chunk that is a bitmap (indicating won wtm positions) is stored identically on-HD and in-RAM. The part that consist of packed lists, which can only be read sequentially, will generate the lost(N) btm positions in the order of inceasing index.

For the (first three) white pieces, indexing really has no meaning, as the chunks can be loaded in memory in any order. During the building we load slices that keep the white King and one other white piece fixed. The 64 chunks differing in loction of the 'running' white piece will be loaded in such a way that it seems that piece is providing bits 24-29 of the index. This might mean gathering the chunks in a funny order, when the piece is involved in defining the symmetry. Chunks differing in position of the white King can be positioned in memory in any order, depending on which buffer (capable of holding a 5-men slice) was available at the time it was read.

[guyhaw]

... memory playing tricks again - g

[h.g.muller]

My first goal as a test-case and benchmark for what perfomance to expect will be to use the 7-men disk-storage scheme and in-RAM processing code to generate a 6-men tablebase for KQ*Q*KN!N!, not making use of the exchange symmetry of like pieces. Here N! means an invulnerable Knight, and Q* means a semi-royal Queen. Semi-royal means you lose if you no longer not have it at the beginning of the opponent's turn, unlike a true royal piece, where you already lose if you don't have it at the beginning of your own turn. In practice this means you cannot risk capture of the Queens by legal moves, but you don't have to worry about captures that would put your opponent's King in check. And you are not allowed to capture the Knights. This to avoid the drudgery of having to probe successor tablebases in case of a conversion: conversions are not possible uner these rules.

My intuitions says that even under those rules, two Queens provide enough superiority over the invulnarable Knights to make this a generally won end-game, thus making it a good benchmark, which can be run (and used for debugging) at an early stage. If not, I will replace on of the Queens by an Amazon, or one of the Knight by a Wazir.

[koistinen]

With 16GB of ram it would be fairly easy to make your leapfrog algorithm work well for all 7-man endgames, right?

I would guess that within a year, getting a PC with 16GB of ram will be fairly common and not all that expensive.
Today 8GB of ram is not too expensive and there are plenty of motherboards that support it.
Maybe the year waiting for PC:s with 16GB ram could be spent generating all 6-1, 5-2, 4-3 endgames?

[h.g.muller]

Leapfrog already works for 3+4, 4+3 and 5+2 with 2GB provided that white has a King. This is what I will be using:

To have all white moves of one of the two groups that you alternate fall within memory, you need to store 5 different King locations, (using K-slice factorization) and 64 locations of the dynamic piece. So 320 chunks. With 2MB per chunk for the won bitmaps, and ~2MB for the lost(N) and lost(N+1) run-length-coded lists, this fits in 1.25 GB. Each pass takes the (completed) lost(N) info, and the (partial) lost(N+1) info, to complete the lost(N+1) with its own white moves, and generate the partial lost(N+2) through those moves from it, which then both serve as imput to the alternate pass.

Within the memory-loaded data set, we first treat white moves to generate a newly-won run-length-coded list, (first cache load), and then runt through the data-set again with the black pieces in the inner loop, to generate black retro-moves and do the verification. (Second cache load.)

The limitation comes from the requirement that a slice with all black pieces dynamic has to fit in L2. With upto 4 black pieces this is the case, as it requires two 2MB bitmaps for won and lost positions, and a little for the newly-won list.

[koistinen]

I noticed that by not storing illegal positions and exploiting symmetry you can save quite a bit of i/o as well as some disk space.

Code: Select all

$ gcc -O2 -Wall countpos.c
$ ./a.out
uint64_t poscount[8]=
{
           462,
         28056,
       1707888,
     102455640,
    6044812200,
  350598895920,
  19984136644080
};

I think it is best to implement the saving in the code that loads and stores bitbase chunks and that it is best to do it after the code is working.
Maybe excluding positions where black is in check would also be good.

[guyhaw]

My first goal as a test-case and benchmark for what perfomance to expect will be to use the 7-men disk-storage scheme and in-RAM processing code to generate a 6-men tablebase for KQ*Q*KN!N!, not making use of the exchange symmetry of like pieces. Here N! means an invulnerable Knight, and Q* means a semi-royal Queen. Semi-royal means you lose if you no longer not have it at the beginning of the opponent's turn, unlike a true royal piece, where you already lose if you don't have it at the beginning of your own turn. In practice this means you cannot risk capture of the Queens by legal moves, but you don't have to worry about captures that would put your opponent's King in check. And you are not allowed to capture the Knights. This to avoid the drudgery of having to probe successor tablebases in case of a conversion: conversions are not possible uner these rules.

My intuitions says that even under those rules, two Queens provide enough superiority over the invulnarable Knights to make this a generally won end-game, thus making it a good benchmark, which can be run (and used for debugging) at an early stage. If not, I will replace on of the Queens by an Amazon, or one of the Knight by a Wazir.

New pieces, new rules, (possibly flawed) chessic logic, intuition ... I'm afraid this appears to me to be so baroque that I will not understand what the output means or what it's integrity is. If I'm not trying hard enough to understand, I apologise in advance.
g

[h.g.muller]

Indeed, from your remarks it is clear that you did understand less than nothing. But your apologies are accepted...

[koistinen]

New pieces, new rules, (possibly flawed) chessic logic, intuition ... I'm afraid this appears to me to be so baroque that I will not understand what the output means or what it's integrity is.

My understanding is that it is the cpu time and disk use that is the important output of the benchmark. At least for people no into fairy chess and given that the guess that it is generally won is confirmed. If not, h.g.muller is planning to make it easier to win in order to get a reasonable benchmark in a slightly different and slightly harder way. Not that I know or feel I need to know what a Wazir is.

[syzygy]

My guess is that first and foremost, h.g.muller is defining a chess-like game without captures and promotions, so that he can first develop and test a (somewhat simplified) version of his algorithm, and so that he does not have to generate subtables first. Certainly a nice idea.

The intuition about the final outcome is of no importance to chess (nor is the final outcome itself), but there's no harm in it either. After reading koistinen's reply and rereading h.g.muller's, I suppose the intuition is of some importance for the benchmark's practical usefulness (but to be honest, I'm not sure why ).

[h.g.muller]

Yes, exactly. I don't want to bother with successors, yet.

The intuition might be wrong, btw, but the generator will figure that out soon enough. An end-game that is not generally won is not a good benchmark, as the win-front dies out very quickly. The main purpose of he benchmark is to get an idea of what performance to expect, and how to optimize it. The actual results are not very intersting at this point, except that I could play out a few of the winning ines to see if they make sense.