Author: Dann Corbit
Date: 17:28:05 01/30/02
Go up one level in this thread
On January 30, 2002 at 20:12:28, Dan Andersson wrote: >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. 1. Generate all chess positions. 2. Run gperf and have it hash to 256 bits. You didn't say it had to be feasible. Do I get my golden star? > 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. That would be 4 bits. Does that mean that the shrinkage is 2^4th = 16 fold? A simple way to accomplish that is to have 16 separate tables. Then you don't need any bits for castling rights. What about sliding move equivalence sets? Don't we form an equivalence set (with some fuzz about the eval) by reduction into these equivalence sets in the same way that we do by reflecting, reversing colors, etc? Another notion for reduction has to do with piece types. Suppose that we have only 4 piece types left on the board. We can encode these types with only 2 bits. So, if we have (for instance) KQRkqb, we could encode all the pieces as follows: K=00 Q=01 R=10 B=11 and one bit for color. If we predefine some ranking of the pieces, the calculation of the bit values for these pieces can be implicit. Simpler things like KQk could be encoded with a single bit: K=1 Q=0 and one bit for color.
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.