Ref.: Re: computer-go: [Question] Alpha-Beta Pruning & Null Move

[Joan Pons Semelis <joan@xxxxxxxxxxxxxxxx>]

 "Thomas Thomsen" <thomas@xxxxxxxxxxxxxxxxx> escribió el 23/4/01 10:56:

[sniped quote]

>Regarding null-moves, I think 
>it helps to distinguish 
>between two kinds of
>applications: (a) uniform 
>search trees, and (b) 
>non-uniform search trees.

I didn't know this terminology, I called them :
trees where "mini-max + alpha-beta prunning" works
 and
trees where "goal oriented proof-number" works  :-)

[ actual examples of both snipped ]

>Note that (b) doesn't 
>operate with alpha's and 
>beta's. This is because
>obtaining the goal is thought 
>of as an irreversible feat: if a 
>block can be
>captured in 5 plies, there is 
>no risk of it being 
>de-captured when looking a
>few plies deeper. Similarly, if 
>a block is connected, it 
>cannot be
>de-connected deeper in the 
>search tree. However, (a) is 
>different. It may be
>possible to achieve a very 
>good evaluation at depth 5 
>plies, but no matter
>how good the evaluation 
>value is, nothing can 
>guarantee that the result is
>not reverted when looking a 
>few plies deeper.
>
This occurs because the evaluation function is not good enough and the horizon effect.
In the goal oriented search the evaluation is correct and, because of the narrowness of the tree it is searched full depth, so there's no horizon.

>Best regards,
>
>-Thomas Thomsen
>

-- 
Joan Pons i Semelis
 joan@xxxxxxxxxxxxxxxxx