Author: Dann Corbit
Date: 15:04:02 06/18/04
Go up one level in this thread
On June 18, 2004 at 11:49:50, Dieter Buerssner wrote: >On June 18, 2004 at 10:10:55, Fabien Letouzey wrote: > >>On June 17, 2004 at 21:05:21, Dann Corbit wrote: >> >>>On June 17, 2004 at 19:32:17, Dieter Buerssner wrote: >> >>>>If anybody wants to implement "bitbases", and really doesn't want to do it more >>>>or less with own ideas, the articles of Ernst Heinz show really everything >>>>needed. After that, it should only be a programming exercize. The articles are >>>>avialable at http://supertech.lcs.mit.edu/~heinz/node17.html >> >>>>Especially interesting in this context: >> >>>>Space-efficient indexing of chess endgame tables. >>>>Knowledgeable encoding and querying of endgame databases. >>>>Endgame databases and efficient index schemes. >>>>Efficient interior-node recognition. >> >>>Yes, I have those papers. >> >>Do I correctly remember they don't address compression at all? > >Correct (from my memory). > >>Uncompressed is >>OK only for 4-man bases. > >All 4-men use about 14 MB here. For a typical modern Computer loading one or a >few 5-men bitbases into RAM is no big problem. Yace does this for KPPKP now >(around 40 MB). One could dynamically load an interesting bitbase depending on >the position. In long time control games, it would even be possible to create >them when needed from (say) Nalimov TBs. > >For example KRPKR would need > > 3612*62*61*24/5 = ~65 MB > >for one side to move (one side could be enough, giving cutoffs at least one ply >later, than both side to move would give) with a typical not too sophisticated >indexing scheme. Actually for KRPKR W/D only would probably work well, giving a >divisor of 8 instead of 5 above. I think the best way to store the records is in a database with a unique index for tables of more than 5 chessmen. For smaller tables, just hold it in memory. >>I suggest you read articles about other (converging) games. Checkers/Draughts >>of course, but also Awari and even Nine Men Morris (I can give you pointer if >>you don't find them). They usually use RLE/LZ/LZH to compress fixed-size >>blocks. > >Using compression may slow down things significantly, makeing it not attractive >anymore to probe at each node. Also, some memory overcomittment might not really >hurt. Unused parts of the bitbases will be swapped away. For material >constellations with pawns, one could make the pawn (especially the column of the >pawns) the most significant part of the index. Because pawns don't change >colums, without changing the material constellation, large parts of the RAM used >by the bitbase will be unused (in many situations). > >>More ambitious approaches to compression are knowledge-based; store only the >>exceptions to some rules. Apparently the author of KnightDreamer >>(http://www3.tripnet.se/~owemelin/johan/KnightDreamer.html) has had some success >>with machine learning (unfortunately also only private stuff). Bear in mind he >>had to provide the rules in the first place, of course. > >I think, Delphi also uses some knwledge based approach (perhaps even combined >with compression). > >>>>But with knowledge of the basic ideas, who to use symmetry to index >>>>TB-positions, many people will be able to come up with similar ideas, that >>>>should also work well (and perhaps identically). It might be more fun. >> >>>I sometimes wonder if there is a fundamentally better way to compress. I have >>>thought about a minimal perfect hash for every legal move on a sparse board. We >>>could encode it in a minimum number of bits, amounting to the number of possible >>>total moves for a set (as reduced by reflections, rotations, etc). >> >>>Of course, you would have to compute a new hash for each new set. >> >>How does this relate to TBs, which are position-based? >> >>Do you mean storing the best move for each position? It can't be smaller than a >>W/L/D result. > >Like Fabien, I really don't understand this, either. One can consider the index >calculation of TBs as a perfect hash function, a very efficient and dense one, >too. > >Compared to typical distance to mate/conversion/... formats (using at least one >byte per position), storing moves (in a very compact way) might be an >alternative, using a similar amount of space (uncompressed). You have some position, and you want to find the answer. The chess engine does this: compute the unique key for this position. For instance, this: 6nk/6pp/8/2R5/2R5/R1p1RR2/2R3PP/2R3NK w - - is equivalent to all of these: 6nk/6pp/8/2R5/2R5/R1p1RR2/2R3PP/2R3NK w - - kn6/pp6/8/5R2/5R2/2RR1p1R/PP3R2/KN3R2 w - - 2r3nk/2r3pp/r1P1rr2/2r5/2r5/8/6PP/6NK b - - kn3r2/pp3r2/2rr1P1r/5r2/5r2/8/PP6/KN6 b - - So we form the permutations, sort them, and use the least lexically as a key. Now, we do not use the key as is. Instead, we feed it to our perfect hash function. Suppose, in a tablebase of 4 men there are 500,000 legal possibilities after all redundancies are removed. Then the perfect hash function we generated will return a number between 0 and 499,999. It will take 19 bits to encode this number, but we will use an int to hold it. This int will be multiplied by 2 to give us the offset into a bit string. We collect the two bits addressed by our number and they will mean: 00 lost for side to move 11 won for side to move 10 drawn for side to move 01 this is what the bit string is initialized to, and so we have a coding error. So for the two million positions, boiled down to 500,000 distinct entries, we need a total of 1,000,000 bits = 125,000 bytes of storage. >>>The reason I brought it up was that I think it would be nice if there were a >>>standard way to do it. Imagine if every chess program author made his own >>>tablebase files. Sounds like a clever thing that would encourage innovation. >>>That's on the one hand. On the other hand, there would be 250+ redundant 7 gig >>>file sets on my computer. That would be a bit annoying. > >Sure, I agree. But with bitbases used from RAM the space needed will be not that >much. It will be comparable to typical RAM sizes, not to typical disk sizes. What about my ten man bitbbase files?
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.