Author: Ernst A. Heinz
Date: 11:14:40 08/31/98
Go up one level in this thread
On August 31, 1998 at 13:25:24, Rémi Coulom wrote: >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 Dear Remi, You are absolutely correct and I have already used these ideas for the endgame databases in "DarkThought". Furthermore, I have recently submitted an article tentatively entitled "Endgame Databases and Efficient Index Schemes for Chess" to the ICCA Journal which reports about these and some other ideas as well. =Ernst=
This page took 0.01 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.