Author: Carsten Kossendey
Date: 18:35:10 09/01/98
Go up one level in this thread
Here's a pretty old post of mine on how I do it in my own program. I believe the quoted text is Hyatt's, but don't nail me on that. X-Sender: ckossend@mail.nrw-online.de Mime-Version: 1.0 Date: Tue, 24 Feb 1998 23:50:54 +0100 To: crafty@alpha.jpunix.com From: Carsten Kossendey <carsten.kossendey@nrw-online.de> Subject: Re: [Crafty] Thompson Tablebases Sender: owner-crafty@alpha.jpunix.com Precedence: bulk Reply-To: crafty@alpha.jpunix.com >pawnless endings require 10*64^(N-1) bytes, but this is doubled because >each position can be either white-to-move or black-to-move. If you have >pawns, you can not do this reflection stuff because you end up with pawns >moving sideways and so forth... but you could get by with something less >than 64^N bytes because you could at least constrain pawns to be on only >1/2 of the board and reflect if it is on the other end... > >There are other minor tricks as well... > >We use 'em all. :) The files are *so* big, of course.. I cannot quite agree to the first statement, which makes me agree to the second ;) (a) pawnless endings These currently use 10*64^(n-1) bytes, or 640*64^(n-2) bytes. Thompson is absolutely right to use only 462*64^(n-2) bytes since not all symmetries are exploited (if both kings are on the a1-d4 diagonal you can restrict another piece to either half of the board). That's a 27.8% compression for a starter. In my own program I go even further. Since no two pieces are allowed to be on the same square you only need 462*62*61*60 bytes (for 5 men). That's another 13.4% compression (again, for 5 men). Now if you have classes where you have runs of equal pieces (KQQQK, KQQKR, but *not* KQKQR) you can save another factor N! for N equal pieces since it doesn't matter which of them is where. KQQQK is then only 33.33m as opposed to 320m currently. Furthermore I use minimum bits coding. For KQQQK (wtm) I only need 3 bits, for (btm) 4 (since there are stalemates). (b) endings with pawns These currently use 32*64^(n-1) bytes, which is comparable as far as wasted space goes. One pawn is restricted to one half of the board, everything else is floating freely. Now that's silly. First of all you can do the "run of N pieces" and "minimum bits" compression as above. Furthermore, pawns are usually on ranks 2-7 ;) Edwards uses the 8th rank for promoted pawns which is required for his generation process but not in the final file so you save 12.5% on each file with at least one pawn. The 1st rank is used (actually it is not since tbgen is work in progress) for pawns which can be captured en passant. If only one side has pawns you save another 14.29% per class. And even if both sides have pawns there further compression is possible - I didn't look into the details yet, tho. My databases are without EP support currently since I didn't touch 5 men EP classes yet. Lastly, there's only 3612 ways (Forgive if I'm wrong, I didn't look up the actual number) to place two kings on an empty board such that they don't check each other (disregarding all symmetries) which saves you another 11.8% per class. Now KPPPK has only 2*((3612/2)*48*47*46)/6 = 62473152 bytes (less with minimum bits coding) as opposed to 1 gig currently which means I save 94.2%, roughly. Further compression is possible for cases where one or two kings are on the 2nd-7th rank but I wanted to keep that challenge for the next century ;) In essence, I can keep all 4 men databases in RAM and all the pawnless 5 men databases fit on a single 4 gigabyte partition. Using Edwards' scheme you need 18.75 gigs ...
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.