Re: computer-go: How many bits are needed to encode an N x N Go position?

[Don Dailey <drd@xxxxxxx>]

   From: stefanmertin@xxxxxxxxxxxxxxxxx (Stefan Mertin)
   Content-Type: text/plain; charset=ISO-8859-1
   Date: Sat, 19 Oct 2002 02:15:52 +0200
   X-Sender: 520031531393-0001@xxxxxxxxxxxxxxxxx
   Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
   Precedence: bulk
   Reply-To: computer-go@xxxxxxxxxxxxxxxxx

   Don Dailey wrote:
   > Hi Jean-Pierre,
   > Interesting discussion!    

   indeed!

   > Also, hash tables are very expensive  in one sense.  The kind of table
   > you are refering  to requires you to store the whole  Go board in each
   > entry (or  at least  many bits of  checksum.)  That's  very expensive.
   > The scheme  I proposed makes the  position itself be the  key of "hash
   > table", so no  type of collision detection is  necessary and the entry
   > size can be just one or  2 bits, depending on how much information you
   > want to capture.   (You can put number  of moves to a win  or loss, 
   > the final results, or you can  store 1 bit representing
   > whether some goal was achieved.)

   Yes, that would correspond a lot more to my idea of a "solved" 5x5 GO:
   a huge database with all the possible positions (3^25 for 5x5),
   in which only for the relevant (legal) positions
   an information is stored 
   e.g. 1 byte = 2 (W or B to play next) * 4 bits (final result:
	0 = net yet computed
	1 = -7 or worse for Black
	...
	8 = jigo
	...
	15= +7 or better for Black)

Yes, that's probably the way to encode the scores. 

   I even would think, that we may easily get rid of the whole 
   awfully difficult KO-complex! We just only store positions WITHOUT
   any KO-forbidden points! I think we just donīt need them in our database:
   We only handle with the KO-problems in the games that occur.
   After every KO comes a move that makes a position without a KO-forbidden
   point! If this position is stored in our database with a correct result,
   what do we need else...

I need to think about this more,  but it sounds great if it will work.
In a program  that used this database to play, we  would have to treat
actual KO positions as simply  not existing in the database.  I wonder
if there are any strange consequences that we are not thinking of?  As
I said, I want to think about this.


   BUT... How long would a program take to fill in all the values for
   every position = for every move
   that may occur in rational games?

Each pass of the algorithm would have to perform a 1 ply search.  The
early passes will take a long time, but as the table fills, each pass
will take less and less time.  

Don



   > This  is not  a  direct  search problem  (yet.)   It needs  retrograde
   > analysis.  The beauty of this, is  that once you build this table, the
   > solution (or  score) or  every position is  readily available  for all
   > time.

   sic!  :-)

   > I'm tempted to write the  program now and apply
   > it to 3 x 3 as a warmup exercise.>
   > Don

   Perhaps 
      3 x 5 (3^15 =    14.348.907),
      4 x 4 (3^16 =    43.346.721) or even
      4 x 5 (3^20 = 3.486.784.401)
   should allready be possible with todays hardware!?


   Stefan