Author: Ratko V Tomic
Date: 00:22:00 11/26/99
Couple weeks ago I left a description of the encoding algorithm which can encode any legal chess position in 155 bits. Since then I had found that the core idea of that algorithm (section 2, on indexing the piece placements) has been thought up earlier as a general data compression algorithm, known as "Enumerative Coding." A nice online reference about that algorithm can be found at the (Univ. of Minnesota) site: http://www.ece.umn.edu/users/kieffer/ece5585.html The Enumerative coding is in the "Supplementary Notes, III" (the page above contains a general course on data compression in 14 chapters and 6 supplements; the files are in PDF format). This particular compression method was originally published in: T. M. Cover "Enumerative Source Encoding" IEEE Trans. Inf. Theory, IT-19(6) 783-795 (1973). After reading that online text and the Cover's paper, it occured to me that since my method in seciton 2 was a regular entropy coder in disguise, one could replace it with a less optimal but a more practical entropy coder (such as arithmetic coder) to encode the piece placement part of the full position code. Basically, once the material content is given, one would construct probability tables for the arithmetic coder (which would include codes for empty squares as well as for the piece types) and procede as in the regular adaptive arithmetic coding, except that, since the exact counts are known upfront for the empty squares and for each piece type, instead of incrementing counts (as is normally done in adaptive arithmetic coding) one would decrement counts of whatever symbol was output. The encoding would stop as soon as the counts for all pieces drop to 0 (the rest then must be empty squares). This technique would produce 1.5-2 percent longer output (2-3 bits more; still below 160 bits) , but it would be much quicker (replacing the section 2 algorithm) since it wouldn't require the high precision integer math of the section 2.
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.