🚀 go-pugleaf

In rec.games.chess.computer Greg Kennedy <gmgk@earthlink.net> wrote:
>> > Chess, is a theoretically finite activity. If my experience with end
> game
>> > tablebases is any indication, this fact is not impossible for a
> computer.

> snip

>> Here is a terrifying thought:  If you make the raw assumption...


>   What if you don't make such assumptions?

That "assumption" is based on a lot of fact.  Namely that a chess
position can be encoded in 168 bits...  that turns into roughly
10^50 (2^168 roughly approximated).  Therefore, that is a pretty
likely number that has been used many times.


>> that there
>> are 10^50 chess positions possible (this is based on many attempts to
>> find the smallest number of bits



>   Assumming that in the future, all computers must use
> "bits" for data storage.

Doesn't matter.  There are _still_ 10^50 positions.  Encode them any
way you like, you still have to deal with that tree of positions.


>> ... necessary to store any legal chess position
>> plus enpassant status and castling status), then the tablebase generator
>> has an interesting task:
>>
>> Assuming you could search one position per nanosecond, and assuming you
>> could search for 1 trillion years, you only have searched 10^23 positions.
>> You have a _long_ way to go.  At one position per picosecond, you are
>> up to 10^26 positions.
>>
>> One problem:  The universe won't last one trillion years...



>   Another assumption.  I believe that with all
> these assumptions in the way, you wouldn't be
> able to solve this problem, even given infinite
> time.   :-)

I don't think it is solvable regardless of the kind of hardware someone
might assume will exist in 1,000 years.  That will barely scratch the
surface.

BTW that last "assumption" isn't an assumption.  It is a solid theory
borne out by scientific observation (ie big bang theory).


>   Here is another example of this kind of "reasoning:"

>   Suppose that there are over one trillion grains of
> sand on a beach.  Now, suppose that we are able to
> recruit every human being on the planet to gather them,
> and that each person can scoop up and carry hundreds
> of grains each.  Can we move the beach?  Heck no-
> while they are all there at the same place, at the same
> time, they will either starve or else nobody will be able
> to move, for it would be far too crowded!   So the
> beach cannot be moved!  It is immoveable.  Just leave it
> the heck alone!   :-)


>    (note: man invents a device called a bulldozer, allowing
> one man to move the beach by himself.)



>    There are so many possible positions in chess that it
> would be impossible to even count them!  How are we
> going to solve chess if we don't even know how big it is?

We pretty well know how big the game is...  we already have an algorithm
that will solve the game.  It is the 32-man case of the already computed
3-4-5-6 man endgame databases.  That therefore isn't a guess at all, it
is a pretty well-known number.

>   Let's assume there are only 50 bazillion different, unique
> positions in chess.  Now, if it takes as little as ten Alpabits
> to store each one, how many Alphabits do we need to
> store them all?  Too many!  There aren't enough Alphabits
> in the whole world to store them all!  Not to mention the
> problems of insects and rats.  And how about cereal bowls?
> We could never make enough to hold 'em all!

>   Nosir.  It just can't be done.  Don't listen to those
> silly radicals who say otherwise.  We can no more solve
> chess than we can put a man on the moon.  Or blow up
> the Earth, for that matter.


>    (note: the Chinese invent gunpowder, then Nobel
> invents dynamite, then comes the atomic bomb, then
> Sputnik is launched, then "one small step for man,"
> then...)

If you think we are going to search 10^50 positions, think again.
If you had one trillion years, searching one position per nanosecond,
you could search 10^23 positions total.  You are a +long+ way from
that final solution.  In fact, you have not really started.  If you
assume computers 1 billion times faster than that, then you are all
the way to 10^32.  You have _still_ barely started.

I think that math stands the test of time.


-- 
Robert Hyatt                    Computer and Information Sciences
hyatt@cis.uab.edu               University of Alabama at Birmingham
(205) 934-2213                  115A Campbell Hall, UAB Station 
(205) 934-5473 FAX              Birmingham, AL 35294-1170