Monte-Carlo tree search with heuristic knowledge: A novel way in solving capturing and life and death problems in Go.

摘要

Monte-Carlo (MC) tree search is a new research field. Its effectiveness in searching large state spaces, such as the Go game tree, is well recognized in the computer Go community. Go domain-specific heuristics and techniques as well as domain-independent heuristics and techniques are systematically investigated in the context of the MC tree search in this dissertation. The search extensions based on these heuristics and techniques can significantly improve the effectiveness and efficiency of the MC tree search.;Two major areas of investigation are addressed in this dissertation research: (I) The identification and use of the effective heuristic knowledge in guiding the MC simulations, (II) The extension of the MC tree search algorithm with heuristics. Go, the most challenging board game to the machine, serves as the test bed. The effectiveness of the MC tree search extensions is demonstrated through the performances of Go tactic problem solvers using these techniques.;The main contributions of this dissertation include: (1) A heuristics based Monte-Carlo tactic tree search framework is proposed to extend the standard Monte-Carlo tree search. (2) (Go) Knowledge based heuristics are systematically investigated to improve the Monte-Carlo tactic tree search. (3) Pattern learning is demonstrated as effective in improving the Monte-Carlo tactic tree search. (4) Domain knowledge independent tree search enhancements are shown as effective in improving the Monte-Carlo tactic tree search performances. (5) A strong Go Tactic solver based on proposed algorithms outperforms traditional game tree search algorithms.;The techniques developed in this dissertation research can benefit other game domains and application fields.