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

["Dan Andersson" <rhq093s@xxxxxxxxx>]

On 22 Mar 2002 at 20:26, david elsdon wrote:

> 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!!
Non uniform Mini-Max, Alpha-Beta and Nega-Max trees are de rigeur in Chess and 
Checkers search. And they can be heavily pruned as well. You should go for Alpha-
Beta search directly. It's way more effective. In the order of Sqrt(MiniMax). Nothing 
new there. You would be well adviced to peruse texts from those fields. And also 
texts about the game Amazons (It has a really mean branching factor). As for 
advice. To reduce the swings in evaluation you usually have a quiesence-search at 
the end nodes and sometimes a bonus for the side to move.The term non-uniform 
depth tree is more apropriate. And they are usually the result of some kind of best-
first search.

MvH Dan Andersson