From: barrett@scooby.cs.umass.edu (Daniel Barrett)
Newsgroups: comp.sys.amiga.advocacy
Subject: Re: UChess.lha Avail via ftp
Date: 17 Dec 92 16:47:07 GMT
Reply-To: barrett@scooby.cs.umass.edu (Daniel Barrett)
Organization: BLAZEMONGER INCORPORATED

>Roger Uzun (uzun@crash.cts.com) wrote:
>>The L version of the [Chess program] plays somewhat stronger, but requires
>>10M of FAST RAM.

In article <1992Dec17.041024.28695@sol.ctr.columbia.edu> clueless@bradley.edu (Mark Kristie) writes:
>WHAT THE HELL IS IT DOING THAT REQUIRES 10 MEG?  to be blunt.

	Chess is an extremely hard problem to solve.  The further the
search depth (number of moves in the future that the program tries to
predict), the better the play.  The more prediction, the more memory
needed.

	Searching "all possible moves" is impossible in our limited
lifetimes.  If there are (say) 25 possible moves at any moment, and the
average chess game lasts (say) 20 moves each for black and white, you've got
to look at approximately 25^40 chessboards, which is somewhere around
82718061255302767487140869206996285356581211090087890625.  This number is
over 100000000000000000000000000 times larger than the number of seconds
that have passed since the (theoretical) beginning of the universe 20
billion years ago.  So checking every possible move is not feasible.

	Let's do some "ballpark" calculations.  A chessboard has 64 squares
and 12 kinds of pieces (6 types each of white and black).  So you need a
minimum of 4 bits to represent a chesspiece.  Multiple by 64, and we get 256
bits needed to store an entire chessboard configuration... just 32 bytes.
Pretty small, right?

	While searching for the "best" chess move, a program must store
many possible chessboard configurations, since it cannot know which is
best until it concludes the search.  Here is where the problem starts.

	At any given point in a chess game, there are (say) 25 different
moves one can make.  So searching 1 move ahead (both white and black move)
requires examining 25 * 25 = 625 chessboards.  To store all this requires 8K
of RAM.  Not very much, right?  But looking only 1 move ahead is not a very
smart strategy.  So let's look 5 moves ahead.  To store all the possible
chessboard configurations would require 25*25*25*25*25*25*25*25*25*25*25*
25*32 bits or 200 billion megabytes.  So we can't possibly store all of
them.  How many should be stored?  There are standard techniques in
Artificial Intelligence for eliminating unlikely or obviously bad moves.
But it doesn't surprise me at all that 10 MB is used by a good chess
program.

	All of this is ignoring the actual code involved in implementing
the chess program; it has some size too!

	I hope this helps a little bit.  (And any computer chess experts
out there should feel free to correct my calculations or explain things
further.  I am not an expert in this at all.)

                                                        Dan

 //////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
| Dan Barrett -- Dept of Computer Science, Lederle Graduate Research Center |
| University of Massachusetts, Amherst, MA  01003  --  barrett@cs.umass.edu |
 \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\/////////////////////////////////////
Newsgroups: comp.sys.amiga.advocacy