Author: James Robertson
Date: 18:33:01 05/21/99
Go up one level in this thread
On May 21, 1999 at 01:26:16, J. Wesley Cleveland wrote: >On May 20, 1999 at 23:41:03, Timothy J. Frohlick wrote: > >>On May 20, 1999 at 15:24:36, Dann Corbit wrote: >> >>>On May 20, 1999 at 14:13:34, Dann Corbit wrote: >>>[snip] >>>>>The thread about representing positions in the minimum number of bits is also >>>>>about setting an upper bound on the maximum number of chess positions. 160 bits >>>>>is 2^160 or ~= 10^48. >>>>Yes, what a fascinating rejoinder! In this case, if 10^52 is correct, then 173 >>>>bits should be the minimum, since 2^173 = 1.197e52 >>>>If we can encode in less, then the number of board positions is less than we >>>>thought (or we have an error in our thinking and the scheme won't work). >>>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! >> >> >>1,000,000,000,000,000,000,000,000,000,000 board positions. There are >>31,536,000,000 seconds in a millenium. That is 31,709,791,983,760,000,000 >>positions per second. I think that we'll find Martians before that happens. > >With alpha-beta, we may need to look at about the square root of that number or >10^15 poaitions. At the 200,000,000 positions/second claimed for Deep Blue, it >would take only about 2 months. I think, though, that 10^40 is closer to the >true number of positions, which would take a couple millenia. You are confusing "search" and "position". Alpha-beta is applicable only in a search, in which there are truly more possibilities than atoms in the galaxy. A position is an arrangement of pieces that must be searched. :) James
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.