[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: computer-go: minimax and go





   From: Heikki Levanto <heikki@xxxxxxxxxxxxxxxxx>

   Yes, of course we need some sort of searching. Probably more than "just"
   local string battles, but I believe that a global search alone will not be
   practically possible in the next few decades or centuries.

I offered a theoretical model  that I don't personally take seriously.
My  goal   was  to construct  (on   paper)  a model  that    has these
characteristics:

  It plays Go.
  It plays better Go with better hardware.
  It plays perfect Go given "enough" hardware.

This was enough to demonstrate that it is possible to write a scalable
Go program.  I didn't try to prove it was possible to write a scalable
Go program that is  very good on CURRENT hardware,  but I believe this
is possible.  Perhaps some programs already exist that are like this.

Yes, I think it will involve global search.   I didn't say fixed depth
full width search.  I envision something like you describe in the next
paragrah.   

These   discussion  always degrade  to   considering   Go as having  a
branching factor of  361 and a calculation of  how much power it takes
to do a full width search to 1000 ply.  But that is not the model that
makes any sense.  There are many opportunities in Go, to be selective.
The Chess model of  looking n ply deep  and looking at everything  was
even abandonded in Chess (although  it actually still works reasonable
well,  selectivity is still much  better.)  Go might respond extremely
well to a   very sophisticated  pruning  mechansism.  String  searches
might  be considered a part of  the evaluation of  a position although
they would have  to be generalized tremendously (you  need to hash the
result of  little local searches  and even  more than  that, you might
need to  generalize the  result so   that minor configuration  changes
don't get researched whenever possible.)


   Or rather I believe that if there will be a global search, it will not be
   directly related to the board image, but happen on a much higher level. For
   example considering an invasion here, the search might jump directly (via
   some patterns, one local search, or other means" to the seven most likely
   results of that invasion, and only if it decides to make that invasion, it
   will read it out in more details, and check that those fit in the global
   "search". I guess this sort of search would better be called planning.

   I believe this sort of approach is much more reasonable in go than in chess,
   because the local subproblems are so much less interconnected.

   No, I have no guaranteed path to prove that this approach (or any other)
   will eventually provide a perfect player. I only have a strong gut feeling
   that such a thing will not be seen in the next few centuries...

   Have you calculated on your model: How much more computing power would you
   need to get a perfect chess player? Assuming Moore's "law" holds, how long
   would *that* take? And how long until we can have your perfect go player,
   that searches the whole game? If we assume that there are some theoretical
   limits on the size and speed of a processor (a switching unit the size of
   electron, not working faster than light goes through it, perhaps), how fast
   can this thing of yours ever play? How many parallel processors will it
   need? Will there be enough material and time in the universe to play the
   perfect game?

The  universe is far too small,  light is too slow  to ever search the
entire game  tree within  a few   billion years.   But my  argument is
theoretical.  The practical goal is not even to play  good Go, it's to
play "better" Go than we did yesterday with a computer.

There are two ways in which we could  push forward:

   1. Make the programs better (even on the same hardware)
   2. Stop wasting computing power.

But  I believe 2  is  exactly  the  same as  1.    If there exists,  a
theoretical  best  possible Go  program that   will run  on  a 200 MHZ
pentium, it should play better on 1200 MHZ computer.


   -H



   -- 
   Heikki Levanto     LSD Levanto Software Development   heikki@xxxxxxxxxxxxxxxxx
		  "In Murphy we Turst"