Balancing MCTS by Dynamically Adjusting the Komi Value

Article type: Research Article

Authors: Baudiš, Petr¹

Affiliations: Prague, Czech Republic

Note: [1] Faculty of Math and Physics, Charles University, Prague, Czech Republic, SUSE Labs, Novell, Prague, Czech Republic, email: pasky@ucw.cz. Supported by the GAUK Project 66010 of Charles University Prague.

Abstract: Monte-Carlo Tree Search tends to produce unstable and unreasonable results in the game of Go when used in positions with an extreme advantage or disadvantage. This is due to a poor move selection because of the low signal-to-noise ratio. Notably, it frequently occurs, when playing in a high handicap game. The handicap advantage is in some sense a disadvantage for the computer when playing against a strong human opponent. We explore and compare multiple approaches to mitigate this problem by artificially evening out the game by modifying the final game score by a variable amount of points (“dynamic komi”) before noting the result in the game tree. Moreover, we compare the performance of MCTS and the traditional tree search in the context of extreme positions and measure the effect of the dynamic komi on the actual playing strength of a state-of-art MCTS Go program. Based on our results, we formulate a conjecture on the resilience of the game search tree to changes in the evaluation function throughout the search.

DOI: 10.3233/ICG-2011-34302

Journal: ICGA Journal, vol. 34, no. 3, pp. 131-139, 2011