[computer-go] Technical Report on MoGo

[House, Jason J.]

> > I'd be a bit more careful about the comparison with alpha-beta in
> > section 2.3.  I believe that iterative deepening of alpha-beta is
very
> > common.  It can be argued that when iterative deepening is used, an
> > early termination isn't very detrimental.  [...]
> > Alpha-Beta is for practical reasons of course also an anytime
algorithm. 
> >[...] .My reaction when I read this
> > statement was: "iterative deepening is not yet invented in the Go
> > community".
> 
> Of course iterative deepening exists. But to me it does not make
Alpha-Beta 
> algorithm an "anytime" algorithm. First because the unit (one
iteration) 
> costs much more in alpha-beta. By "iteration" I mean that if you stop
your 
> program during an iteration, then it behaves as in the last iteration
(the 
> current iteration is lost). In MC/UCT, the iteration takes less than
1 ms. 
> Second, and more importantly, the time increase of the iteration is
huge in 
> alpha-beta. The time to perform the search at depth k+1 is much
higher than 
> for depth k.
> 
> So for me the reasons we gave comparing to alpha-beta hold, even if
you are 
> right by saying that we should have mentionned iterative deepening.

Maybe my implementation of alpha-beta with iterative deepening is poor,
but here's what I do:
* When searching at depth k, create a reordered move list for the
future search at depth k+1
* If a timeout occurs while searching at a particular depth, return the
best move found so far

For the reordering, here's what I do:
* If a move evaluation doesn't result in an improved minimax value,
leave its position alone
* If a move evaluation does result in an improved minimax value, move
it to the head of the list

By using that method, I guarantee that the best move at depth k is
searched first at depth k+1.  If a timeout occurs, an early stop caused
no harm in the evaluation.  If more time is available, the 2nd move
considered is the 2nd best move at depth k+1.  Let's say the 2nd best
proved to indeed be not as good but that the 3rd best shows an enhanced
result.  Even if there's 10 more moves to look at, a timeout will cause
the alpha-beta to return what would have otherwise been considered the
3rd best at depth k, but is really the best of what has been considered
at depth k+1.

Regardless of if a true best for depth k+1 is returned, it's guaranteed
that the move returned from a partial search is as good as or better
than the results from a search at depth k.  The extra effort isn't a
waste.  I also cache the partial search and allow alpha-beta to pick up
where it left off.