Author: Angrim
Date: 14:05:55 10/23/01
Go up one level in this thread
On October 23, 2001 at 11:01:40, Ratko V Tomic wrote: <snip> >>>Considering also that using the best-move you may be able to >>>fit couple times more table information on any given disk >>>or RAM size you have available, >> >> All the TBs so far use 8 bit values. So there is no savings >> on the "best move" approach until we get to the 6 piece files >> with mates > 127... > >Well, no saving if you encode the best move in a byte. With the >right pattern preprocessor/dictionary extractor and move generator >the best move ought to fit on average in 1 bit or less. The best I still think this is quite optimistic, but even given your 1 bit per position value, your savings are not that good. The current tablebase method takes around 1.3 bits per position after compression. This is a long ways from your guess that you could store a "couple times more" data. >move table can easily take advantage of any endgame rules or >knowledge, human or computer extracted patterns, to make the >move generator produce the best-move in many fewer tries than >a random move generator would do (which is the most of a >pattern that Huffman or similar memoryless stream compression >could squeeze out). > >With distance-to-mate tables the only compression available is >of that 'memoryless stream' type, since the values in these tables >are result of multi-step iterations of highly nonlinear functions, >so for all practical purposes any simple connection to the >patterns in the initial positions is lost by the time you reach >the terminal node and get the distance value. The only regularity >left which is readily extractable are the bulk frequencies of >different distance values. The rest of pattern is oblitareted. Totally wrong. DTM tables actually have a quite high level of predictable patterns, the most common ones being that positions whose indexes differ by 1, 8, or 64 tend to have the same value. This is because these positions differ only by one piece being located one square away. These predictable patters provide a significant boost to the compression rate as compared to huffman by itself. Note: for tables with a knight, 2, 16 and 128 entries apart are often identical, because for example a knight on either D1 or F1 can move to E3 so if that was the best move the values will be the same. >The best-move tables are more similar to gradient methods of >optimization which are sensitive to the local patterns. The move >generator used in the best-move table decoder can easily and >beneficially (for compression ratio) absorb any amount of >knowledge/regularity in data one can come up with. Angrim
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.