Re: computer-go: How to evaluate unbalanced alphabeta tree?

[david elsdon <david_elsdon@xxxxxxxxxxx>]

At 2002.03.22.l 01:12, you wrote:
> I am wondering how to evaluate the minmax tree with alphabeta pruning when 
> the subtrees are not of the equal size. For instance, when you have such a 
> tree:
>
>                     B(3,3)
>                     /     \
>                 W(3,4)   W(4,3)
>                 /    \
>              B(4,4) B(4,5)
>
> Note the subtrees of B(3,3) are of different depth. This is what I call 
> unbalanced.
Interesting that you should ask that because I have recently been 
analysing  the minimaxing of game trees to discover how it works, when it 
works and what can go wrong!!

I can't actually answer the question, but I do have two observations.

1. Your evaluation function should really take into account whose move it 
is because often, even in positions at the same depth, the fact that it is, 
say, black's move makes a lot of difference to the evaluation of a 
position. E.g. black may have an absolute sente move which is worth 10 
points in a particular position.

2. If you backup from an odd ply your values tend to be high whereas 
backing up from even plies tends to be low. This effect attenuates as you 
look deeper into the game tree.

As a matter of interest, having generated and analysed a few million trees 
of various shapes and sizes, I have discovered that, for my rather uniform 
trees, minimax does indeed improve your chances of selecting a better move. 
However, if you want a more accurate value for a particular position then a 
small modification to minimax gives a better result. As you are handling 
node N, take

0.7*"backed-up value" + 0.3*"evaluation at N"

and pass that up the tree. I don't know why this works, but I'm looking 
into it. It is interesting that this modified minimax is "not" very good 
for selecting a better move.

I would like to stress that I have only tested my modified minimax on my 
experimental trees. I haven't tried it on real go trees yet.

Cheers

David