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

[Don Dailey]

Magnus,

It Viking5 primarily an alpha/beta searcher using monte/carlo as the
evaluation function?    I know you have other good stuff in there, but
does this characterize your program in general terms?

- Don



On Sun, 2006-07-23 at 17:19 +0200, Magnus Persson wrote:
> Quoting Rémi Coulom <Remi.Coulom at univ-lille3.fr>:
> 
> > I believe your approach is dangerous, because your confidence 
> > intervals shrink as 1/N. They should shrink as 1/sqrt(N). Your idea 
> > might work in practice, but it does not look very consistant with 
> > theory. My idea of a fudge can be justified in the Bayesian framework 
> > in terms of a "safe prior". It applies to the estimation of the 
> > value, not the confidence bounds.
> 
> I was just thinking about this difference, since DD's method appears to prune
> more aggressively when N gets large. But if the fudge constant is large 
> then it
> might be more conservative when N is small and still prune aggressively for
> increasing N´s. I had to use a minimum N to avoid instability in the search.
> When N is sufficently large the effect of mistaken lazy evaluations might not
> be important because the error cannot be very large compared to a small N.
> 
> 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.
> 
>