[Computer-go] Quiescence Search for Go?
stefan.kaitschick at hamburg.de
Sun Mar 28 10:29:26 PDT 2010
A major nuisance in chess programming is the "horizon effect".
Unwanted, but unavoidable results are pushed out of the search depth by
interposing unrelated moves.
The fix in chess is to keep the program from deluding itself by extending
the search by possible piece captures.
This is the so called "quiescence search".
Go programming experiences a horizon effect of its own. It's not quite the
same as in chess, because the search is allready extended to final
positions. But the logic is similar. In Go, the losing side constantly
revisits semeais and group attacks in all branches of the search tree. This
pushes the undesired result outside of the maximum node visits.
Maybe a way to do quiescence in go is to trade moves in result-critical
local fights before doing the actual search.
One way to find out wether or not a situation is purely local might be to
compare the RAVE values in different parts of the search tree. The more
uniform the results, the more local the situation. Maybe a specialized
search could be started when the opponent is thinking. Ko fights would have
a new problem though, because threats have been artificially removed. So an
alternative to pre-playout moves might be to just reduce the chance of
trying these moves in the move generator.
More information about the Computer-go