Re: computer-go: A problem with understanding lookahead

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

Your first sentence is not true, unless  your definition of "credibly"
is  extremely  forgiving.  Even  though most  programs  do   not do  a
significant  amount  of  tactical  analysis  as  part  of  the  STATIC
evaluation, it can and has been done.  Of course this gives you a much
slower evaluation, not the simple fast one  you envision.  

By the  way, it takes  a 2 ply search  WITH captures to see  a trivial
fork.  It takes 3 ply  to see that your opponent  can fork you if  you
don't respond  right now.  If you write  an  evaluation good enough to
know this, you  have  probably written  a  very slow evalautor.   Most
programmers  don't bother, because it is   more productive to design a
fast  evaluator and  let the program    do the extra searching.   Some
programs do more  of this than others,  it's individualistic.  I don't
know of many that try to find forks without a search.  (I think Zarkov
does however.)

I don't see much point in going on too much  more.  I think you have a
misconception  about how good Chess  evaluators are  and this is given
away by  your  statement  that you can  tell  who  is winning a  large
percentage of  the  time.  The  way it  works is that  you are usually
right  a large percentage of  the  time if  you crushing your opponent
(even then your evaluation may be wrong.)  If it's close, all bets are
off.

It's this way in Go too, if  you are already  dominating the board and
the  issue   is a few   dead   stones here and  there,  probably  your
evaluation at least knows you have an advantage.

In  Chess you can  be a queen up  which you would define as completely
wining, and yet be dead lost.    A simple unseen tactical shot makes
the evaluation complete and utter nonsense.  I can construct positions
all day long (with absolutely no difficulty) that will defeat any
evaluator you can write.   

In fact, I can write a program to generate these at  will.  I could do
a search from almost ANY position and find them scattered all over the
tree, I don't need to do anything fancy.    From the opening position:
  
   1. d4  e5?   material evaluation = 0.   
  
   refutation dxe5!   woops, the evaluation must have been wrong,
                      I've already lost the game.

----------------------------------------------------------------------




   From: Dave Dyer <ddyer@xxxxxxxxxxxxxxxxx>

   I still disagree strongly.

   I can write a chess evaluator that will take milliseconds to evaluate
   a position, and will play well enough to play credibly against human novices
   without any additional search.  Roughly, I'll count material, number of threat
   inputs to each space, threat outputs from each piece, and immediate king
   safety. This will be good enough to favor capturing material, detect threats, 
   avoid overloading pieces, and discover simple forks and uncovered attacks. 

   I'm pretty sure than any expert in the field would agree that these
   are the fundamentals, and then go on to name more aesoteric concepts
   to be added.   Just the simple fact that I can name these off the top
   of my head, and readily see how to implement them, should demonstrate
   that the framework is well understood.

   The easily computed quantities that a Go evaluator can use (liberties, 
   group size, geographical influence) are laughably bad as evaluators; 
   and moving beyond these obvious elements is uncharted territory. The
   best Go programs have made some progress, especially using patterns,
   but the progress has been painfully slow; and based on ad-hoc algorithms
   rather than a sound theoretical framework.

   The fundamental difference is that in chess, if you use simple concepts 
   such as I outlined, you can understand a position and tell who is winning
   a large percentage of the time.  In Go, you undersand NOTHING until you 
   have decided which stones are dead, and that is a fundamentally hard
   problem.