All-Moves-As-First Heuristic applied to the game of Tic-Tac-Toe
2
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
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%).
Abstract
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%).
참고문헌 (17)
- 이병두, "삼목게임에서의 몬테카를로 트리탐색과 신뢰상한 트리탐색간의 경쟁", 한국컴퓨터게임학회논문지, 29(1), pp.1~6 (2016), (사)한국컴퓨터게임학회
- 이병두, "강화된 몬테카를로 알고리즘을 활용한 강력한 삼목게임기 구현", 한국컴퓨터게임학회논문지, 28(3), pp.135~141 (2015), (사)한국컴퓨터게임학회
- 이병두, "종료된 삼목게임의 전략 적합도 인식을 위한 진화신경망 모델", 한국컴퓨터게임학회논문지, 28(2), pp.95~101 (2015), (사)한국컴퓨터게임학회
- 이병두, "삼목 게임을 위해 개선된 몬테카를로 트리탐색 알고리즘", 한국게임학회 논문지, 16(4), pp.79~86 (2016), 한국게임학회
- D. Silver, "Mastering the game of Go with deep neural networks and tree search", Journal of Nature, 529(7587), pp.484~489 (2016)
- H. Baier, "Monte-Carlo Tree Search and Minimax Hybrids", Computer Games, 504, pp.45~63 (2014)
- 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)
- S. Gelly, "The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions", Communications of the ACM Computational Intelligence and Games (CIG) of IEEE, 55(3), pp.106~113 (2012)
- D. P. Helmbold, "All-Moves-As-First Heuristics Monte-Carlo Go", Proceedings of the 2009 International Conference on Artificial Intelligence (2009)
- Byung-Doo Lee, "Monte-Carlo Game Impleme –ntation" (2017), Hansan Press
- A.A.J van der Kleij, "Monte Carlo Tree Search and Opponent Modeling through Player Clustering in no-limit Texas Hold'en Poker", Master, pp.2010
- "Monte Carlo Tree Search in Go" (2017)[URL]
- "Computer Go" (2017)[URL]
- "Tic-Tac-Toe" (2017)[URL]
- "Evaluation Function Based Monte-Carlo LOA" (2016)[URL]
- "Sample Evaluation for Action Selection in Monte Carlo Tree Search" (2016)[URL]
- "Challenge for Implementing Monte Carlo Tree Search into Commercial Games" (2017)[URL]