Author: Dann Corbit
Date: 17:38:50 01/30/02
Go up one level in this thread
On January 30, 2002 at 20:28:05, Dann Corbit wrote: >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. Note: This sounds like a wash at first blush: Trade 1 table 16 times as large for 16 tables which are 1/16 as large (since they don't carry castling information). I think there is still some savings, because the ones with castling bits on are much smaller. IOW, you won't store any positions that look like this: [D]r7/4k3/7r/8/8/8/7R/R5K1 w - - [snip]
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.