Author: KarinsDad
Date: 15:41:28 10/22/99
Go up one level in this thread
On October 22, 1999 at 15:44:26, Dann Corbit wrote: >For instance: >http://www.treasure-troves.com/math/Chess.html >gives three different estimates of: >10^120 (I'd say this is pretty well blown out of the water!) >10^43 (with derivation!) >10^40 (probably from Hakmem below) > >HAKMEM says: >PROBLEM 95: >Solve chess. There are about 10^40 possible positions; in most of them, one side >is hopelessly lost. Well, my algorithm puts the ballpark at approximately 10^48. When I look at it, I come to the conclusion that the range of possible legal positions is probably between 10^46 and 10^48 and not anywhere near 10^43. Also, I know for a fact that a 164 bit compression can be done without breaking a sweat (with no possibility of error), so the number of legal positions MUST be under 2.34e49. My reasoning for the 10^46 to 10^48 range is distorted, but it is as follows: 1 bit side to move 64 bit bitboard That leaves 96 bits for the 32 pieces or exactly 3 bits per piece (from 161 bits and not including location). Now, this is very interesting since 3 bits represents color and 4 types of pieces, not color and 6 types of pieces (which is what we find on the chessboard). This means that the compression algorithms are capable of effectively representing 6 piece types (plus states) into 4 piece types. To me, that is fairly significant. I cannot comprehend a significant increase in the compression rate. However, a lot of these positions have to be illegal ones. But, even if the illegal positions outnumbered the legal positions 4 to 1 (which I doubt since that is a high ratio), it would only drop the 2.92e48 number to 5.85e47. Now granted, I am not taking into account the large number of positions that can be stored in less than 161 bits via the algorithm, but I truly wonder how much that drops the value (a factor of 3?, a factor of 10?, a factor of 100?). It's hard to say, but maybe some mathematician can figure it out someday. KarinsDad :) PS. I have been thinking about an interesting mechanism to drop out the illegal positions. However, that would require a totally different type of algorithm and would throw most of my previous work out the door. Guess I won't work on that until after I publish my first algorithm.
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.