Dynamic Decomposition Search: A Divide and Conquer Approach and its Application to the One-Eye Problem in Go.
Akihiro Kishimoto, Martin Müller · 2005
Abstract- Decomposition search is a divide and conquer approach that splits a game position into sub-positions and computes the global outcome by combining results of local searches. This approach has been shown to be successful to play endgames in the game of Go. This paper introduces dynamic decomposition search as a way of splitting a problem dynamically during search. Our results in solving one-eye problems in the game of Go show the promise of this approach. Additionally, we propose relaxed decomposition, a more ambitious way of splitting positions. 1