Author: Eugene Nalimov
Date: 18:42:47 08/31/98
Go up one level in this thread
On August 31, 1998 at 14:14:40, Ernst A. Heinz wrote: >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= I wrote generator that use those and several other ideas. I hope that soon I'll make it public - I want to verify results before doing so; for now everything looks good (Rémi, if you want, I can send to you current code - but I'm sure indexing schema will be changed before final release). Eugene PS. I want to thank Ernst for discussions and his kind help in improving indexing schema.
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.