Author: F. Huber
Date: 10:08:45 11/27/03
Go up one level in this thread
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.
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.