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 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.