Re: computer-go: A problem with understanding lookahead

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

>  When people say here that there is no easy evaluation function to go, they
>  seem to mean that there is no evaluation function that can be done is short
>  enough time to be of any use in global searching.

Granted.  What I  envision as ideal in  Go is something like in Chess.
In Chess, a  call to the  evaluator is pretty much meaningless without
combining it with  a  tactical search.   Most evaluation functions  in
Chess don't know a queen is  hanging on the very  next move, instead a
search is  done that may involve  hundreds, or thousands of additional
nodes.    The branching  factor   in Chess is about   40  more or less
depending   on  the situation, but     if the situation  is reasonably
complex, a "simple" one ply search can  involve thousands of nodes.

It's certainly tricky comparing apples to oranges.  Some people design
very fast evaluation function in chess and  others have very slow ones
that try to do much more.  It's not clear which is best, because there
are sucessful examples of both.  It appears  that you can trade on for
the other and get approximately the same results.

So a   well done "static  evaluation"  in Chess   is  totally lousy by
itself,  the search  is  integrated into it.    Apparently it's pretty
similar for Go.  I will mention that it's possible, and has been done,
to  write a think  called a  "static exhange evaluator"  that tries to
actually  return an accurate score without  doing  a tactical or quies
search.  Even programs  that do this  often use a  hybrid of the  two,
looking deeper sometimes and depending on this other times.


>  Your idea of exploring global search mechanisms on really small go board is
>  interesting. I hope someone will do it, and publish results.

I am sure Go is solved on 1x1, 2x2 3x3 up  to some level, mabye 4x4 or
maybe even 5x5   (which I kind  of  doubt, but may   be  possible.)  I
suspect  that someone either already has,  or easily could write a 5x5
Go  program  that is virtually  unbeatable  by   humans  but I'm  just
guessing.  It  wouldn't surprise  me  if very   very good small  board
versions are  possible, such as 7x7,  but most people optimize for the
big board or  are not interested in   these little boards.  I  am sure
there is someone out there who is reading this  who knows the facts on
this.

I think global search is perfectly sound in principle, BUT we are sort
of at the point we were in  Chess when we were  figuring out how to do
quiescience with very shallow searches.   There is  no virtue in  deep
searches when much more  can be gained  by concentrating on evaluation
first, so I guess I believe that we are not ready to think about doing
2  ply searches yet.   We need to think in  terms of doing very good 1
ply searches with quiesence.  I think most people view this as looking
a few ply ahead selectively, but it's really a matter of semantics.  I
see   "evaluation" as everything that happens    after some full width
depth, even if it's  just 1 ply.  By the  way, some people claim  they
are fully selective because they don't consider all  the mvoes at even
the first ply.  Again, most of the is highly semantics, because if you
even consider a move to  reject it, you are "sort   of" doing a 1  ply
search.  You may  of  course have a routine  that  suggests moves  and
doesn't visit some moves even in the most abstract sense and you could
call that selective I suppose.

It's much   clearer to  describe  what we   are  really doing  and the
terminology we  use usually muddles up the  true points.  So even when
we  call chess program  "selective", almost  none  truly are, they are
full width  to some depth, then  they  have several  plys of selective
quiesence, which we call "null  move selectivity" or something roughly
equivalent.  Interestingly, I  have watched terminolgy change over the
years.   People  are starting  to refer to   current chess programs as
BRUTE FORCE again because the man behind the curtain has been exposed.
It's kind of  like what AI has  gone  through, new  AI technology gets
relabeled once the principles are well understood and the smoked glass
and mirrors are exposed.  Computer Chess was once  called AI, now it's
called "engineering."


Don



   From: Heikki Levanto <heikki@xxxxxxxxxxxxxxxxx>

   Don Dailey <drd@xxxxxxxxxxxxxxxxx> wrote:


   > I keep hearing on this group  that Go programs  can't search, they are
   > primarily evaluation based.  That means most of the strength is due to
   > evaluation.  Go programs don't play great, but they play like advanced
   > beginners at least.  Correct?

   Well, yes. 
   The problem with evaluating a go position is that it requires a lot of
   local tactical reading to determine the life status of all groups, etc. 
   At least in GnuGo, the evaluation of the current position is intermixed with
   move generation. When it checks the status of a group, it may find that it
   is unstable, and therefore recommend a move that kills or saves this group,
   and gives the move a numerical value. After having collected all the data it
   can from the game position, it also has a number of move proposals, from
   which it choosed the one with the highest value. It could also evaluate the
   whole position at the end of this sequence, for example to a probability of
   winning the game, but currently it does not need to do so at all.

   It would ntobe too hard to make it try all possible moves, or all reasonable
   moves (by some sort of heuristics), or even just a few of the moves it has
   already proposed, and evaluate the position after those. Adding recursion to
   get a full ply or even teo would not be that difficult. But as it is now,
   this line of programming is completely out of t he question, since the
   single evaluation-cum-move-finding takes several seconds, in cases half or
   whole minute, depending on the processor and settings.

   When people say here that there is no easy evaluation function to go, they
   seem to mean that there is no evaluation function that can be done is short
   enough time to be of any use in global searching.

   I do not know anything about evaluation functions in chess, but from what I
   have heard, they can be reasonably fast. As you say, not just counting
   pieces, but still something "trivial", like counting possible moves, threats
   and defences to the various squares on the board, open lines and diagonals,
   and rows of pawns, and probably weighing all these in some way...

   Your idea of exploring global search mechanisms on really small go board is
   interesting. I hope someone will do it, and publish results.

   - Heikki 


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