Re: computer-go: Re: alternatives to Alpha-Beta Search

["P.J.Leonard" <P.J.Leonard@xxxxxxxxxx>]

Hi Dave,

 Thanks for your interesting comments,

Dave Dyer wrote:

> There are two problems with proof number search from the
> viewpoint of a go program.  The lesser problem is that it
> derives only a single bit, ie; true or false for a proposition,
> rather than a value. 


 You can always change your proof statement during the search.

e.g.  If you have a value based evaluation you can start of
by proving. " value greater than lower limit can be achieved "
This should give you an easy problem to solve if you set your
limit low enough. Once this is proven you can increase the limit
reset the values of the terminal evaluated nodes and restart the search.

 Another interesting application is to formulate your proof statement 
in terms of a logical expression of subgoals. 

e.g. STATEMENT1 = A and B and C

 You could start doing interesting things here because

    STATEMENT2 = A or B or C  must be true if STATEMENT1 is true.

 One stratergy is to start by proving A B and C inpendently if
any of these are false then STATEMENT1 is FALSE. If any are TRUE
then STATEMENT2 is true.

 So you can see that there is a sensible stratergy for refuting AND
statements
and proving OR statements that require narrower searches than
considering the
final combined goal. 

 I just don't see this sort of thing in ALPHA-BETA ?


> The major problem is that it requires you
> to switch "current node" more or less at random, which makes it
> very hard to use in conjunction with any kind of caching or
> incrementally derived state. 

 Well you could turn your statement round and say that any
cache scheme that requires you to use alpha-beta is a limit.

 However , I agree that it is a problem.
You could have some sort of heap of hashed data (indexed by board
state).
You could resuse memory of the last used data when your virtual memory
is full.

 Incidently my experience of watching my PN engine attempt to solve
problems
is that it tends to stay in a local situation for several moves (until
it realizes
that there is another area that is less effort to prove). It is my
strong
belief that the PN scheme is closer to the way us humans think than
alpha-beta.

  cheers Paul.



> A go program which approaches the
> board from scratch on every single evaluation would be very
> slow indeed.