Author: Dan Andersson
Date: 17:12:28 01/30/02
Compression, was Question about Bit storage. This is a try to explain the apparent contradictions in a previous thread. Hope I don't screw it up to badly. Anyone interested in further reading should search for compression tutorials on the net. Let's do some definitions first. Assume that when have an ordered array containing all chess positions and their result. Call it C The representation of the chess position need dot be minimal. Call the number of bits needed X. And that the result of every position is a win or loss. Just to get a nice even bit. We now use the array to get the Value Number (also known as index) of each chess position. That means that we can make a result array that needs one bit per position. Call it R That is equivalent to a perfect hash function of all possible chess positions. I don't know how to construct that function. Anyone who finds it gets a golden star marker. It's obvious that the size ratio of the data of C and R is X+1 to 1. Does this mean that the number of chess positions are two? A silly question. Of course not! What we are experiencing is compression of the data representation of the results array. The indexes of the two arrays are still the same. This makes it clear that the mirroring possible if castling is absent allow you to compress the file size fourfold. But any decent compression scheme will do that anyway. But the index will only shrink by the number of bits required to hold castling rights. MvH Dan Andersson
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.