Author: F. Huber
Date: 10:32:20 11/27/03
Go up one level in this thread
On November 27, 2003 at 13:08:45, F. Huber wrote:
>On November 27, 2003 at 11:11:42, Bruce Cleaver wrote:
>
>>On November 26, 2003 at 15:44:11, Dustin Moore wrote:
>>
>>>Are there any theoretical numbers on the number of
>>>*reasonable* chess positions availible in a game?
>>>
>>>For my purposes a reasonable chess position is one
>>>that could be reached by two good engines looking
>>>out to about to ply 13 or so from a normal opening.
>>>
>>>I'm sure someone has written a paper on this at some
>>>point.
>>>
>>>I wonder how impossible it would be to make a massive
>>>hash table with all the positions likely to be reached
>>>in a game. I'm wondering just how many hundreds of
>>>TB it would take to store the hash table.
>>
>>
>>
>>Estimates of the number of distinct chess positions vary between 10^43 and
>>10^48.
>>I know Karins Dad in this forum worked on the minimum number of bits
>>necessary to describe a position and came up with about 160 bits. 2^160 = 10^48
>>positions.
>>
>>Now comes a leap of logic: many (most?) of the positions are nonsense full of
>>lopsided material.
>>I am going to conjecture that the ratio of non-ridiculous postions to all
>>positions is the same as alpha-beta to minimax search;
>> that is, there would be about 10^24 positions of true interest that need to be
>>hashed.
>>
>>So, 160 bits (for the hash code) * 10^24 positions = 1.6*10^26 bits, or about
>>1.8*10^13 Terabytes!
>>
>>Smaller than I might have thought. The true number might be smaller yet, as
>>some of the positions cannot be reached by legal play, or are symmetric, etc.
>>If the number of bits necessary to describe a chess position is smaller than 160
>>bits, the total storage would be smaller too.
>
>Hi Bruce,
>
>this ´estimate´ (?) of 10^43..10^48 possible chess positions is totally wrong!!
>
>Everbody could prove this in a very easy way:
>
>There are 13 kinds of ´pieces´ - PNBRQK x 2 colors + ´empty field´.
>Now consider that each of the 64 chess fields could contain each of this
>13 pieces, totally independent from every other field.
>Of course that´s not true - this would allow a lot of impossible positions like
>´no piece at all´ or ´64 kings´ - but so the calculation is very simple.
>
>The (theoretical) number of positions is now 64^13 = 3*10^23.
>
>This is really an ABSOLUTE UPPER LIMIT for all possible (better ´unpossible´)
>chess positions - the ´true´ number is of course MUCH lower (because of all
>those ´unallowed´ positions I´ve mentioned above).
>
>So whenever you see such strange numbers as 10^43 (or more), simply forget them
>-
>they are complete nonsense!
>
>And so also your value ´1.8*10^13 TB´ would be much smaller indeed.
>
>Best regards,
>Franz.
Sorry, but I´ve just discovered, that I made a BIG ERROR! :-((
Of course MY calculation would lead to a number of 13^64 = 2*10^71 !!
So not some others but _I_ was talking NONSENSE. ("errare humanum est" ;-))
Very disappointed (about myself) :-(
Franz.
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.