Re: computer-go: About Viking

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

   From: "Eric Boesch" <ericboesch@xxxxxxxxxxxxxxxxx>

   >I almost forgot my main principle:
   >There should be no compromises in how the program represents
   >things. Either a chain of stones is connected or it is not, and
   >the program should know exactly why.

   That last sentence is my main principle too; and it seems that we agree that 
   methodical positional reading (as opposed to relying exclusively on a static 
   pattern database) is the way to achieve it.  Every time you use an 
   assumption to limit your search space, you are sacrificing both accuracy 
   (your assumption may be wrong) and speed (if you don't keep track of which 
   spaces are relevant to the achievement of a goal, then to achieve any 
   accuracy at all, you must be conservative, so you will usually be 
   considering too many locations, which increases search time).


I feel that  the correct principle  is that as you  get closer to leaf
nodes you can  make more assumptions  and do it  with a  genuine gain.

Having said  that, I am doing  the same thing  you are.  My  search is
100% admissible (you can view it as a proof) and for any given depth I
can't  do any better  even if  I  looked at  every intersection on the
board.

You  stated   that  you   lose   speed and  accuracy.    I   think you
oversimplify.  The ONLY  goal is to improve  accuracy  GIVEN a certain
amount of computing power.  When  TIME and ACCURACY are combined  like
this, you get a situation where speculation can improve both speed and
accuracy.  What do I mean?

If you do not have the  resources (and none  of us do), then having an
admissble search (like we both have) cannot solve every problem, there
is  just not enough  time.  If a  speculative  algorithm is capable of
finding more solutions in less time, then which method do you consider
more "accurate?"

There is a way to guarantee that a search will always find a solution,
even  while  using  speculation.  The  secret is   that the amount  of
speculation you use must vary with distance from the leaf nodes.  Near
the root,  you  must not use  speculation,  or there will be  problems
forever unsolvable.  All of  this assumes enough computing  resources,
but so does  the admissible techniques so you  have no  argument here.
In fact, I  believe that  many  strong  commercial programs  use  this
principle from descriptions I've read about tactical searches.

Even  though I'm not currently using  speculation,  I recognize that I
have no choice if I want a good program.  Evenually  I will add it but
first I  want  to fully understand  how  things work and  gain as much
experimence with  admissible  techniques.  Find the  right speculative
rules may be just as difficult as improving our addmisibility pruning,
because as you say, it can hurt you if you don't do it right.

I would rather avoid doing any speculation, it's ugly and what we are
doing is fun and beautiful.  Another compromise!

Don