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

[Joern Thyssen]

On Thu, Mar 27, 2003 at 01:27:07PM -0700, Thomas Hauk wrote
> 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.

Argh, I was writing a long email to point exactly that out: we do not do
a full search right now:

A 2-ply evaluation is defined as

Loop over 21 possible rolls

    Find and Evaluate all moves on 0-ply
    Move the best move

    Loop over 21 possible rolls

        Find and Evaluate all moves on 0-ply
        "Return" the equity of the best move.


So with the current code we do not examine all possible branches. At
1-ply we only search the branch which has the best 0-ply equity.

If I understand you correctly the *-minimax will search more branches
(with careful selection of interesting branches) so we'll get a better
result (in some sense), but there will be no speed-up compared to the
current code, in fact, it'll be slower?

Jørn