Common fate graph patterns in Monte Carlo Tree Search for computer go

摘要

In Monte Carlo Tree Search often extra knowledge in form of patterns is used to guide the search and improve the playouts. Shape patterns, which are frequently used in Computer Go, do not describe tactical situations well, so that this knowledge has to be added manually. This is a tedious process which cannot be avoided as it leads to big improvements in playing strength. The common fate graph, which is a special graphical representation of the board, provides an alternative which handles tactical situations much better. In this paper we use the results of linear time graph kernels to extract features from the common fate graph and use them in a Bradley-Terry model to predict expert moves. We include this prediction model into the tree search and the playout part of a Go program using Monte Carlo Tree Search. This leads to better prediction rates and an improvement in playing strength of about 190 ELO.