Author: Ratko V Tomic
Date: 02:05:40 11/16/99
Go up one level in this thread
> I'd like to see such a model :-) > If the model basically consists of a gigantic lookup table then it > kind of defeats the purpose of compression don't you think? It was "model" in quotes. You guessed it right. > Of course none of what you say refutes what I said, because I said > 'any given position' (which means any possible position) couldn't > be compressed into 64 bits. Yes I know you meant "any given position" == "any possible position" otherwise what you said wouldn't have made sense. But the wording was ambiguous (which was the point of my comment), since when we say we have a compression algorithm for some domain, we can only mean we have an algorithm which, for some _proper_ subset of all possible data records (messages, items) in that domain, will produce smaller encoding than what mere indexing (i.e. array lookup) of the domain's data records would require (which is a L=log2(N) bits, where N is the number of all possible data records in that domain). The samples from the full set of records cannot be compressed beyond the plain lookup/indexing performance. If you have an algorithm which can compresses some _proper_ subset to fewer than L bits per record, such algorithm would produce explicitly more than L bits per record on average, if the samples to compress were taken from the set of "all possible" records for that domain. So, it is not meaningful to use word "compression" of data records in some domain when one is applying it to "all possible" data records from that domain, since any such algorithm is actually an "expansion" algorithm when tested on samples from "all possible" data records. One might argue that, some algorithm is still properly called "compression" (even when one means "all possible" records), since indeed it does produce fewer bits per position than someone elses encoding of chess positions. But if one uses that semantics for "compression," then any encoding algorithm (for "all possible" chess positions) can be called "compression" since there certainly always exist ways to do worse. Regarding ecoding of "any possible" chess positions, there is another ongoing thread on that exact topic, where I describe an algorithm which can encode "any possible" chess position in exactly 155 bits. While there are still some reductions possible (down from the 155 bits), specifically if one were to eliminate positions with illegal checks (i.e. the checks to the side not having the turn to move, or by too many pieces for either side), I think it is within a bit or two from the absolute lower limit on encoding of all "legal" chess positions.
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.