Re: [Bug-gnubg] [Fwd: gnubg search function]

[Thomas Hauk]

On Fri, 28 Mar 2003, Joseph Heled wrote:
> In BG, the node value is the 
> *arithmetical weighted average* of it's children, not a min/max.

True. But recall how alphabeta cutoffs work in minimax trees: if your 
opponent can limit your score to something smaller than what you are 
already guaranteed, then don't bother searching below that node.

Applying this to trees with chance nodes is nearly identical. A simple 
example is this. Let's say you're already guaranteed a score of >1 from a 
search in another part of the tree and you're at a node where the first 20 
rolls all result in a loss. You don't need to bother searching the final 
move because even if it resulted in a win (even a backgammon win), the 
weighted average of the result would be less than a score of 1, so you 
don't need to search that final move.

> This is what makes BG intractable to brute force.

BG has a very high branching factor indeed. However, usage of *-minimax, 
along with techniques such as move ordering and transposition tables, may 
result in programs that can truly search 2- or 3-ply, optimally. This is 
what my research will attempt to find out.

--Tom