Computer Chess Club Archives


Search

Terms

Messages

Subject: Ideas to reduce size of tablebases

Author: Rémi Coulom

Date: 10:25:24 08/31/98


I am now implementing tablebase support in TCB. My code is based on
Steven J. Edwards' OCD toolkit and can read tablebases like Crafty does.
I am not sure if these savings are worth the effort, but I have a few
ideas that could significantly reduce the size of tablebase files with
almost no cost in terms of speed by improving the indexing method. I am
new to the use of tablebase, and maybe some much better file formats
have already been invented. I think I heard about Ken Thomson (I am not
sure about the spelling) and Bruce Moreland making their own. Does
anybody know if they are more efficient ?

Anyway, here I go with my ideas :

1. For every ending with two identical pieces for one player (KNNK,
KRRKR, etc.) the size of the file could be divided by two since there
are only 64*63/2 ways to place two identical pieces on a chess board
and not 64*64. In the case of three identical pieces, it could be
divided by 6.

2. By noticing that a pawn can be on only 48 out of 64 squares, the
size of tablebases containing pawns could be reduced by 25% for each
pawn it contains.

3. Since two pieces can not be on the same square, some more space
could be saved by multiplying by 63, 62, 61, etc. depending on the
pieces already positionned on the board. Even bigger gain can be
obtained by using the fact that once a King is on the board, this
removes at least 4 possibilities for the opponent's King.

4. For symmetrical endings, like KPKP, only one of the .tbw and .tbb
is necessary.

5. If you have all necessary .tbw files then none of the .tbb files are
required since a one ply search can give you the answer .tbb would have
given. This saving is costly in terms of performance, however. I still
think that an intelligent programming of the search algorithm can make
it work well.

Here are some illustrations of these points.

The size of KPKP is 32 * 64 * 64 * 64 = 8 388 608
It could be reduced to
  32 : Pivot = White King
* 60 : squares for the Black King
* 48 : squares for the White Pawn
* 47 : squares for the Black Pawn
= 4 331 520

The size of KRRKR is 10 * 64 * 64 * 64 * 64 = 167 772 160
It could be reduced to
  10 : Pivot = White King
* 60 : squares for the Black King
* 62 : squares for the first White Rook
* 32 : possible distances for the second White Rook
* 60 : squares for the Black Rook
= 71 424 000

The size of KRNKR is 10 * 64 * 64 * 64 * 64 = 167 772 160
It could be reduced to 10 * 60 * 62 * 61 * 60 = 136 152 600
(this is the worst case, but 20% is still significant)

The size of KRPKR is 32 * 64 * 64 * 64 * 64 = 536 870 912
It could be reduced to 32 * 60 * 48 * 61 * 60 = 337 305 600




This page took 0.02 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.