Author: Fabien Letouzey
Date: 07:10:55 06/18/04
Go up one level in this thread
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? Uncompressed is OK only for 4-man bases. 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. 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. >>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. >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. I have plans but too long-term for your taste, I am afraid. Dieter will be much faster. Eugene is also considering WLD bases I think. Fabien.
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.