Author: KarinsDad
Date: 15:11:35 08/16/99
Go up one level in this thread
On August 16, 1999 at 17:31:40, Dan Andersson wrote: >Keep it up. A couple of years ago two of my friends who are working >mathematicians (Im not presently) made a strong case for suggestiong 147 bits as >a maximum number of chess positions. Not until now I realized that this was a >big thing. Im trying to see if ther is possible to make it a rigorous proof, >maybe using some more bits. No, it doesnt suggest a working compression method, >sorry! > >Regrds Dan Andersson From what I can tell, there are 3 possibilities which would allow a compression method: 1) 2^y possible positions where y <= 160 (basically what your friends came up with). In this case, it appears that a one to one representation is required. But the work on this would be a nightmare. 2) Storing the location of each piece. This is the typical 64 square for king #1, 63 squares for king #2, 63 squares for piece #3 (including off the board), 62 for piece #4, etc. As far as I can tell, there is no easy way to compress this type of data nor is there an easy way to derive it. The problem I see with this type of schema is that is allows the storage of a lot of illegal positions. Hence, if it does achieve a maximum number of positions greater than 2^160, it would be difficult (not impossible) to re-use those illegal positions by changing the algorithm. For example, if the opposing queen is checking our king and it is the opposing side to move, those positions would be dropped from the number of positions possible for the opposing queen. The same with if two knights are checking a king simultaneously or if the kings are right next to each other, etc. But pulling out the illegal positions would be tough since you have to know which are legal and which illegal and that information may not be available due to interposing pieces that have not yet been "placed" on the board. Also, one would have to come up with a way to represent the pawns in one of 5 states. This algorithm probably works. But, proving it may be extremely difficult (especially if the illegal positions bump the count above 2^160). 3) Using a bitboard for the location of pieces and a set of bits to describe the piece. This is what I am attempting to do. I am using basic algorithms discussed here on this forum, but adding in a bunch of rules which compress it. For example, if there are less than 2 pawns on the board, then you do not need an en-passant bit. Or, if you have encountered 16 pieces of one color, then the color bit for all future pieces is the other color (I do not use this particular rule since it does not work for all cases, but I wanted to give an example of the kind of compressions due to knowledge at hand that could be done). KarinsDad :)
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.