Author: Dieter Buerssner
Date: 08:49:50 06/18/04
Go up one level in this thread
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 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). >>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. Regards, Dieter
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.