Author: Marc Bourzutschky
Date: 04:21:40 03/26/03
Go up one level in this thread
On March 25, 2003 at 17:30:52, martin fierz wrote: >i computed some checkers endgame databases with retrograde analysis based on the >paper by the chinook team. for larger databases, i have a memory size problem; >specially as win32 only allows a process to use 2GB. >i once heard that it was possible to compute a win/loss/draw endgame database >using only 1 bit per position as opposed to 2 bits as i was using up to now (and >like in the chinook paper). > >does someone here know more about this? i'm looking either for an explanation >for dummies, or for a reference to a paper. > >thanks in advance > martin 1-bit per position algorithms are described in: "Fast, Memory-Efficient Retrograde Algorithms" R. Wu and D. Beal (2001), ICCA Vol. 24, No. 3, pp. 147-159 "6-Piece Endgames" K. Thompson (1996), ICCA Vol. 19, No. 4, pp. 215-226 If you want truly spectacular memory savings at the cost of doing substantially more programming you can try to implement something like Johan de Koning's FEG algorithm. The basic idea is that you only need random access on the pieces that are moving (except for captures which I assume are handled separately anyway). Storing the side-to-move in the least significant bits thus allows you to take the other other side piece positions out of the random access loop. With even material configurations you'll only need the square-root of the RAM that you would need otherwise. For lop-sided material distribution the savings is less, but I imagine those are of less interest anyway. You'll probably also need a reasonably efficient on-the-fly compressor. AFAIK there is no useful published literature on this algorithm, so you are on your own. The fact that it can be done is proven by Johan de Koning's impementation for chess, which requires only about 15Meg do to arbitrary 6-man endings (except for the pathological 5 vs 1 configuration) at a speed as fast or faster than the traditional memory hungry algorithms. I think this algorithm might be even simpler to implement for checkers than for chess.
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.