Convergence and correctness analysis of Monte-Carlo tree search algorithms: A case study of 2 by 4 Chinese dark chess
Journal
2015 IEEE Conference on Computational Intelligence and Games, CIG 2015 - Proceedings
Pages
260-266
Date Issued
2015
Author(s)
Abstract
The convergence and correctness of the UCT algorithm is a hot research problem. Previous research has shown the convergence of UCT-based algorithm on simultaneous turns or random turns games, but little is known for traditional alternating turns games. In this paper, we analyze the performance of the UCT algorithm in a 2-player imperfect information alternating turns game, 2 × 4 Chinese dark chess (CDC). The performance of the UCT algorithm is measured by the correctness rate and convergence speed. The correctness is defined by the percentage that the UCT algorithm outputs the same move with the one having the best game theoretic value. The convergence speed is defined by the entropy of a set of moves, which are output by the UCT algorithm using the same number of iterations. Experimental result shows the convergence of the UCT algorithm in the CDC, which can also be applied to explain the existence of diminishing returns in the UCT algorithm. Experimental result also shows an UCT algorithm does not always output moves with the best game theoretic value, but these with the highest chance of winning.
SDGs
Type
conference paper