Author: Wylie Garvin
Date: 02:49:24 11/16/01
Hi all, I'm a newcomer here who got interested in chess programming a while back and have been pretty gusto about it over the last two months. There seem to be several past threads about shrinking endgame databases. In my research I came across Heinz's excellent publications about DarkThought. There don't seem to be any posts about this style of endgame-database use, so I thought I'd post one! +Brief+ summary: DarkThought uses knowledgable encoding to shrink >150MBs of databases to 15.1MB. It loads them into RAM and consults them everywhere in the search. It uses interior node recognition to efficiently classify positions and apply specialized scoring to them (in this case, database lookups tempered with weighted scoring functions). The loss of optimal play is a small disadvantage, but consulting the databases at every potentially recognizable position (even 20+ ply deep in quiescence!) is a big advantage. DT searches smoothly from late-middlegame positions into the endgame databases and then plays those endgames solidly. And those 15.1MB of "bit-bases" are not even compressed! My own idea is to store them in RAM in a compressed format that still allows efficient random access (i.e. 2-3 loads and a few simple insns). I have not tested this out yet; I am working on two chess engines of my own but I have a bunch of other stuff I better do before I go back to fooling around with endgame databases...but I have a wild and totally untested theory that I can adapt the sparse-table compression algorithms used e.g. in parser generators (compiler toolkits) to this purpose. I have good reasons to believe this will not affect performance at all--it will just (hopefully) shrink the RAM consumption a bunch so I can afford to do the same thing with some 5-piece subgames (e.g. all 5-piece endgames with rammed pawns??) and load them into RAM too! Muahahahaha. Anyway, here are the links: Knowledgeable Encoding of Endgame Databases http://supertech.lcs.mit.edu/~heinz/ps/know_edb.ps.gz Efficient Interior-Node Recognition http://supertech.lcs.mit.edu/~heinz/ps/node_rcg.ps.gz http://supertech.lcs.mit.edu/~heinz/dt/node33.html How DarkThought Plays Chess: http://supertech.lcs.mit.edu/~heinz/dt/ Cheers, Wylie
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.