Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Nalimov's TBs: one question

Author: Eugene Nalimov

Date: 11:00:26 11/18/98

Go up one level in this thread


On November 18, 1998 at 06:04:49, Jouni Uski wrote:

>They should be about 50 % of older format, but which way is this improvement
>achieved? Was it some kind of symmetry reductions or what?

Several tricks, mostly already known (Ernst A. Heinz wrote an
excellent article, maybe it'll be published in ICCA journal;
Carsten Kossendey sent a good letter to Crafty discussion group
some time ago, too). Each one trick saves not much, or works
only for some endgame subclasses, but net result is 50%
reduction in used disk space.

Brief summary:

1. For pawnless ending, you can restrict one piece to a1-d1-d4
   triangle (that was done in SJE's generator). But if that piece
   happens to be on a1-d4 diagonal, you can restrict other piece
   to 'large' a1-h1-h8 triangle (exploit one more symmetry).
2. When you place second piece on the board, one square is
   occupied already, so there are only 63 possible squares;
   for third - only 62, etc.
3. If there are 2 identical pieces (e.g. as in knnkp), you can
   order their locations - e.g. force second piece to occupy
   square with smaller number. Then you have not N*(N-1) total
   combinations, but N*(N+1)/2.
4. Pawns usually occupies ranks 2-7. Even if you want to handle
   en passant captures, there are better ways to do that than to
   reserve entire rank (or two) for possible en passant target.
5. Kings never can be near each other, so there are only 3612 ways
   to place 2 kings on the empty board (do not using symmetries),
   versus 4096 when using SJE's format.
6. You cannot capture enemy's king, so, if you know where it's
   located, there are some forbidden squares for the pieces of the
   side-to-move.

Also you can use minimal bits encoding - for 5-man ending, 7 bits
usually enough. That will save additional 12.5%. I decided against
it because I hope to use much better on-the-fly decompression
schema.

Eugene



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.