Coding my 7-men generator

Endgame analysis using tablebases, EGTB generation, exchange, sharing, discussions, etc..

Coding my 7-men generator

Postby h.g.muller » Fri Sep 05, 2008 10:33 pm

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.
h.g.muller
 
Posts: 216
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam

Re: Coding my 7-men generator

Postby guyhaw » Sat Sep 06, 2008 7:51 am

[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
guyhaw
 
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Location: Reading, UK

Re: Coding my 7-men generator

Postby h.g.muller » Sat Sep 06, 2008 2:53 pm

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.
h.g.muller
 
Posts: 216
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam

Apols for my confusion (FEG, 5-1) ...

Postby guyhaw » Sat Sep 06, 2008 10:55 pm

... memory playing tricks again - g
guyhaw
 
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Location: Reading, UK

Re: Coding my 7-men generator

Postby h.g.muller » Sun Sep 07, 2008 11:53 am

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. :wink:
h.g.muller
 
Posts: 216
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam

Re: Coding my 7-men generator

Postby koistinen » Mon Sep 08, 2008 5:53 pm

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?
koistinen
 
Posts: 80
Joined: Fri May 02, 2008 7:59 pm
Location: Stockholm

Re: Coding my 7-men generator

Postby h.g.muller » Mon Sep 08, 2008 8:27 pm

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.
h.g.muller
 
Posts: 216
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam

Re: Coding my 7-men generator

Postby koistinen » Tue Oct 07, 2008 7:03 pm

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.
Attachments
countpos.c
Slow counter of positions after reduction for symmetry, king proximity and pieces on same square.
(1.63 KiB) Downloaded 145 times
koistinen
 
Posts: 80
Joined: Fri May 02, 2008 7:59 pm
Location: Stockholm

Re: Coding my 7-men generator

Postby guyhaw » Fri Oct 10, 2008 9:31 am

h.g.muller wrote: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. :wink:



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
guyhaw
 
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Location: Reading, UK

Re: Coding my 7-men generator

Postby h.g.muller » Fri Oct 10, 2008 12:51 pm

Indeed, from your remarks it is clear that you did understand less than nothing. But your apologies are accepted... :lol:
h.g.muller
 
Posts: 216
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam

Re: Coding my 7-men generator

Postby koistinen » Fri Oct 10, 2008 11:43 pm

guyhaw wrote: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.
koistinen
 
Posts: 80
Joined: Fri May 02, 2008 7:59 pm
Location: Stockholm

Re: Coding my 7-men generator

Postby syzygy » Sat Oct 11, 2008 12:43 am

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 ;)).
syzygy
 
Posts: 162
Joined: Sun Aug 03, 2008 4:02 pm

Re: Coding my 7-men generator

Postby h.g.muller » Wed Oct 15, 2008 8:39 pm

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.
h.g.muller
 
Posts: 216
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam


Return to Endgame Tablebases

Who is online

Users browsing this forum: No registered users and 3 guests

cron