Author: Dann Corbit
Date: 14:37:58 05/21/99
Go up one level in this thread
On May 21, 1999 at 17:22:50, José de Jesús García Ruvalcaba wrote: >On May 21, 1999 at 16:03:17, Dann Corbit wrote: > >>On May 21, 1999 at 15:58:32, Tim Mirabile wrote: >>>On May 20, 1999 at 15:24:36, Dann Corbit wrote: >>> >>>>Which brings up another fascinating idea. If we can come up with a minimal >>>>encoding, we can bound the maximum possible number of chess positions. If the >>>>claim that all positions can be encoded in 100 bits is true, then there are >>>>"only" about 1e30 board positions!! Several orders of magnitude below any limit >>>>claimed that I know of. After all, if the mapping really is invertible, we will >>>>have a one to one and onto map from a 100 bit binary number to all possible >>>>board positions! >>> >>>A while ago I posted to RGCC about a dozen things to consider when trying to >>>decide if a certain random position of pieces/pawns/promoted pawns is legal. >>>I'll try to dig it up when I get home. But many of these deal with such >>>specific cases its hard to imagine an encoding scheme which can catch them all. >>>And some positions could only be tested by doing a retrograde analysis back to >>>the opening position; I don't see any way to catch those. >>These sort of checks *reduce* the number of legal positions. Any check like >>this will lower the estimate when applied. If we can find an encoding scheme >>that will cover any contingency (including 'legal positions only' as a subset) >>then that number of bits will record them all. Perhaps less bits are needed, >>but as long as we have a ceiling, we can say that the number of possible moves >>is no more than "x" and possibly much less. > > Is the discussion about posible moves or about posible positions? The focus (at least my focus) is to find a ceiling for the count of board positions. If we can prove that a particular minimal encoding can reversibly describe every board position, then two raised to the exponent of the count in bits of that coding will give is a hard limit for the most possible board positions. The estimates I have seen vary wildly from 10^120 on down. I have never seen any sensible proof of any hard limit before.
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.