> > 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. _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
