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

[Joern Thyssen]

On Tue, Apr 01, 2003 at 09:51:02AM -0700, Thomas Hauk wrote
> On Thu, 27 Mar 2003, Øystein Johansen wrote:
> > >2) Where does the current search function hide? I'm told gnubg just
> > >performs a 1-ply full-tree search. Is this a part of eval.c? It's a huge
> > >file. Can you help point me toward the function?
> > 
> > The search functions are all hidden in eval.c. It's implemented as a 
> > recusive 
> > function. See EvaluatePositionCubeful3, EvaluatePositionCubeful4, 
> > EvaluatePosition, EvaluatePositionFull and EvaluatePositionCache.
> 
> I've stared at the code for a while, but I'd like to just confirm my 
> understanding:
> 
> EvaluatePosition calls EvaluatePositionCache to determine if the state has 
> already been evaluated and cached in order to speed things up. If it 
> hasn't, then EvaluatePositionCache calls EvaluatePositionFull. 
> EvaluatePositionFull contains a recursive call to EvaluatePositionCache if 
> nPlies is greater than 0; else it performs a leaf evaluation.

Yes, that's correct. 

> 
> Am I correct to interpret a return value of 0 as "nothing went wrong" and 
> any other value to mean "something went wrong"?

Yes, two things can go wrong: the evaluation is interrupted (Ctrl+C in
the terminal or the Stop-button in the GUI) or the adding of the new
evaluation to the cache fails.

> Does gnubg simply perform a 1-ply search out of the box?

I'm not sure I understand the question... 

> How do EvaluatePositionCubeful3 and 4 factor into the search?

Cubeful4 calculates cubeful equities. The logic is more or less the same
as EvaluatePositionFull except that cubeful equities are calculated.

The major difference is that all possible cube positions are collected
and evaluated at the leaf node. The "no double" and "double take" equity
are combined with the "double pass" equity to form the optimum cubeful
equity.

Assume we have a centered cube in money game and peform a 2-ply
evaluation. At the leaf node we'll be evaluating the following pairs of
cube position/values:

Centered 1-cube        \
                        >  "no double" cubeful equity (a)
Opponent owns 2-cube   /


Opponent owns 2-cube   ->  "double take" cubeful equity (b)
-


Opponent owns 2-cube   ->  "no double" cubeful equity (c)
-

Owned 4-cube            \
                         > "double take" cubeful equity (d)
Opponent owns 8-cube    /


So there is 4 different cube values/positions (although the current
logic evaluates all 6 above) at the leaf nodes.

At the 1-ply internal nodes there is

Centered 1-cube ("no double" cubeful equity(a))       \
                                                       > "no double" (i)
Opponent Owns 2-cube ("double take" cubeful equity(b))/


Opponent Owns 2-cube ("no double" cubeful equity(c))  \
                                                       > "double take" (ii)
Owned 4-cube ("double take" cubeful equity(d))        /

At the 2-ply internal node there is

Centered 1-cube        ("no double(i)")
Opponent owns 2-cube   ("double take (ii)")

These are combined for the final cubeful equity.


Joern