삼목게임에서의 몬테카를로 트리탐색과 신뢰상한 트리탐색간의 경쟁
Competition between MCTS and UCT in the game of Tic-Tac-Toe
2
조회
0
다운로드
5
인용
0
참고문헌
키워드
초록
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 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.
Abstract
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.
참고문헌 (17)
- 이병두, "강화된 몬테카를로 알고리즘을 활용한 강력한 삼목게임기 구현", 한국컴퓨터게임학회논문지, 28(3), pp.135~141 (2015), (사)한국컴퓨터게임학회
- 이병두, "종료된 삼목게임의 전략 적합도 인식을 위한 진화신경망 모델", 한국컴퓨터게임학회논문지, 28(2), pp.95~101 (2015), (사)한국컴퓨터게임학회
- 이병두, "유전 알고리즘을 이용한 삼목 게임 전략 분석", 한국게임학회 논문지, 14(6), pp.39~48 (2014), 한국게임학회[DOI]
- D. Silver, "Mastering the game of Go with deep neural networks and tree search", Journal of Nature, 529(7587), pp.484~489 (2016)
- 이병두, "삼목 게임에서 최상의 첫 수를 구하기 위해 적용된 신뢰상한트리 알고리즘", 한국게임학회 논문지, 15(10), pp.109~118 (2015), 한국게임학회
- 최영욱, "삼목 게임에서의 최선의 수순", 한국컴퓨터게임학회논문지, 27(3), pp.11~16 (2014), (사)한국컴퓨터게임학회
- S. Gelly, "The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions", Communications of the ACM, 55(3), pp.106~113 (2012)
- A.A.J van der Kleij, "Monte Carlo Tree Search and Opponent Modeling through Player Clustering in no-limit Texas Hold'en Poker", 석사, pp.2010
- E. Powley, "Heuristic move pruning in monte carlo tree search for the strategic card game lords of war", Computational Intelligence and Games (CIG) of IEEE, pp.1~7 (2014)
- T. Pepels, "Novel Selection Methods for Monte-Carlo Tree Search", 석사, pp.2014
- G. Chaslot, "Monte-Carlo Tree Search", 박사, pp.2010
- "Computer Go" (2016)[URL]
- "Tic-Tac-Toe" (2016)[URL]
- "Sample Evaluation for Action Selection in Monte Carlo Tree Search" (2016)[URL]
- "Modification of UCT and sequence-like simulations for Monte-Carlo Go" (2015)[URL]
- "Evaluation Function Based Monte-Carlo LOA" (2016)[URL]
- "Monte Carlo Tree Search" (2016)[URL]