[Computer-go] Quiescence Search for Go?

Stefan Kaitschick 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.

Stefan





More information about the Computer-go mailing list