Monte-Carlo Tree Search (MCTS) is a best-first search algorithm to evaluate states of the game tree in game playing, and has been successfully applied to various games, especially to the game of Go. Upper Confidence Bounds for Trees (UCT), which is a variant of MCTS, uses the UCB1 formula as selection policy, and balances exploitation and exploration of the states. Rapid Action-Value Estimation (RAVE), which is a All-Moves-As-First (AMAF) heuristic, treats all moves in a simulation as the first move, and therefore updates the statistics of all children of the root node. In this paper, we evaluate the performance of RAVE and UCT playing against each other in the game of Tic-Tac-Toe. The experimental results show that the first player RAVE is much inferior to the second player UCT (13.0±0.7%); on the other hand, the first player UCT is far superior to RAVE (99.9±0.1%).

Go is an extremely complex strategic board game despite its simple rules and is the great challenging classic game for AI due to its enormous search space. The computer program AlphaGo finally defeated Fan Hui, the European Go champion, without handicaps on a full-sized 19 ×19 board in October 2015. Monte-Carlo Tree Search (MCTS) is a widely-used algorithm for game-tree search in game playing. MCTS based on statistical sampling is a best-first tree search technique to evaluate states; UCT which is a variant of MCTS uses the UCB1 formula as selection policy. In this paper, we evaluate the performance of MCTS and UCT playing against each other in the game of Tic-Tac-Toe. The experimental results show that the first player UCT is slightly superior to the second player MCTS (54.3±1.0%), the first player is always advantageous to the second player regardless of the MCTS and UCT players, and the result of each game should be a tie if both players do their best in Tic-Tac-Toe.

Go is an extremely complex strategic board game despite its simple rules. Recently computer Go based on MCTS plays at human-master level and also has defeated top professional players with handicap games in 19×19 Go. Before implementing computer Go, in this paper we show weakness of pure MC algorithm for playing robust Tic-Tac-Toe game and present alternative method to make up the weakness. Furthermore we show how UCB algorithm works for balancing exploration and exploitation in game tree and discuss the need of a hybrid algorithm combined with UCB and strategy based MCTS, for implementing an enhanced computer Go.

본 논문은 컴퓨터 바둑에서 돌의 영향력(Stone Influence)과 영향력점(Influence Point) 그리고 영향력 영역(Influence Area)을 제안한다. 돌의 영향력은 놓인 돌과 빈 정점사이의 거리에 따라 정의하며, 영향력점은 돌의 영향력에 대해 임계치를 이용하여 정의한다. 형세평가를 위한 요소로 영향력 영역을 영향력점 덩어리와 코어를 이용하여 정의한다. 저자는 정석 자료를 이용한 실험을 통해서 영향력점의 임계치를 구하였으며, 영향력 영역이 바둑 게임에서 세력으로 성공적으로 적용 가능하였습니다.