Re: computer-go: 5x5 Go is solved?

[Don Dailey <drd@xxxxxxx>]

John,  that is very cool idea, I like it!   

There is one technique that might also be applied that doesn't require
any particular  size of  table.  I came  up with  this when I  wrote a
program (along with  a couple of MIT students)  that solved any rubiks
cube in 2 hours  or less (a few years ago.)  Your  email reminds me of
it.  Here is how I did it  for Rubiks cube, then we might consider how
to apply the same (or similar) technique to Go databases:

 The goal  in the rubiks  cube case is  to find the  minimal solution.
 Starting  from a  solved cube,  we work  backwards to  some specified
 depth.  For  the sake  of this discussion,  let's say it's  10 moves.
 Whenever  we encountered a  position with  this backwards  search, we
 store it's depth in a hash  table.  But here is the interesting part.
 We do not worry about hash table collisions.  We only store the depth
 if it's smaller  than the number already in the  table (which for our
 example  is initialized to  the value  10 since  we are  building the
 table to depth  10.)  In this way, the hash  table lookup will always
 give us a bound on the  solution depth.  For instance, if the value 5
 is stored, we know that it is impossible for ANY position that hashes
 to  this location  to  solve in  less  than 5  moves.  This  produces
 incredibly  rich cutoffs  even  though many  entries  may share  this
 single entry.

 When trying to solve a cube, you use a conventional recursive search.
 But the search is done iteratively, you first try to solve in 1 move,
 then 2,  then 3 and  so on.   At every node  in the tree  search, you
 access the  table to see if  there is any point  in recursing deeper.
 It is remarkably  effective, and you can use a table  of any size you
 want, of course bigger is  better.  The initial table can be prepared
 to any  depth you want but at  some point it beomes  saturated to the
 extent  that   it  becomes  increasingly  difficult   to  store  more
 information in it.

 I have left out much detail  of course, the MIT student added a 2x2x2
 cube database which can also produce cutoffs in the 3x3x3 cube and we
 handled color remapping, reflections rotations and other stuff.

 
I'm not  sure how to build  this type of  database for Go, but  I know
what the database would look like  when complete.  It would be a table
of any  arbitrary size (bigger the  better of course)  that would have
bounds information stored for each entry.  You could take any position
and be able say things like,  "this position is guaranteed to be worth
AT LEAST  15 points of  territory."  A relatively shallow  search from
any position would  probably be able to lock in on  the exact score of
the position.  

Right now I'm too tired to think about this, but tomorrow I will think
about how  and if such  a table  could be built  (of course it  can by
building the table the hard way and compressing it to this format, but
if possible we want to build it with limited memory.)

Johns idea  made me  think about this  even though  it's significantly
different because  both ideas conserve  memory in clever ways.   In my
case, I try to make each entry do extra work, in Johns case, the table
is an exception table so less entries are needed.

Don





   Date: Sun, 20 Oct 2002 22:44:26 +0200
   From: John Tromp <John.Tromp@xxxxxxxxxxxxxxxxx>
   Content-Type: text/plain; charset=us-ascii
   Content-Disposition: inline
   User-Agent: Mutt/1.2.5.1i
   Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
   Precedence: bulk
   Reply-To: computer-go@xxxxxxxxxxxxxxxxx

   > More I think about it, more I am convinced, that something like this
   > should already be possible for 5x5 Go with todays hardware-possibilities
   > and that it would be a very funny thing for every Go player to
   > "surf around" in such a database.

   such a database could be made quite small in fact.
   fix a standard go program, like gnugo.
   assume that the program can order all legal moves (plus pass)
   in a position from 0, 1, ... up to k-1, supposedly from best to worst.
   then if move 0 really is an optimal move, we don't store this position in
   the database. if the first optimal move is number i, then we add
   an entry for this position mapping it to i.
   the stronger the program, the smaller the database.

   figuring out the result of a position is now just a matter of playing it
   out with help of the database, until there are 2 consecutive passes.

   actually, gnugo is not the most suitable for this purpose. maybe some
   custom program can be made to do much better...

   regards,

   %!PS                       %  -John Tromp (http://www.cwi.nl/~tromp/)
   42 42 scale 7 9 translate .07 setlinewidth .5 setgray/c{arc clip fill
   setgray}def 1 0 0 42 1 0 c 0 1 1{0 3 3 90 270 arc 0 0 6 0 -3 3 90 270
   arcn 270 90 c -2 2 4{-6 moveto 0 12 rlineto}for -5 2 5{-3 exch moveto
   9 0 rlineto}for stroke 0 0 3 1 1 0 c 180 rotate initclip}for showpage