[computer-go] Lazy Evaluation in Monte Carlo/Alpha Beta Search for Viking4

[Rémi Coulom]

Magnus Persson wrote:
> Take this hypothetical scenario for Viking4 playing 19x19 searching 1 
> ply with
> 20 candidate moves all of almost equal value followed by one critical 
> move that
> is superior. 1/N might here reject several moves that might be evaluated
> slightly better then the current best but may search more moves and then 
> find
> the critical move in time that the more picky 1/sqrt(N) would not find 
> in time.
> 
> 

If I wanted to be more selective, I would still use the 1/sqrt(N) 
formula, but with a lower level of confidence in the confidence 
intervals (ie 90% instead of 95%, for instance). That would be more 
coherent with theory.

Also, when you have a bunch of moves to evaluate at 1 ply, it might not 
be efficient to evaluate them sequentially. Maybe you should evaluate 
them all at the same time, by allocating a random simulation to the move 
with the highest upper bound (which should also be the move with the 
highest lower bound if intervals are symmetrical). When the alpha-beta 
window is wide open, this approach is certainly better than considering 
the moves in sequence.

Rémi