삼목게임에서의 몬테카를로 트리탐색과 신뢰상한 트리탐색간의 경쟁

• 영문명: Competition between MCTS and UCT in the game of Tic-Tac-Toe
• 발행기관: 한국컴퓨터게임학회
• 저자명: 이병두(Byung-Doo Lee)
• 간행물 정보: 『한국컴퓨터게임학회논문지』제29권 1호, 1~6쪽, 전체 6쪽
• 주제분류: 공학 > 컴퓨터학
• 파일형태: PDF
• 발행일자: 2016.03.30

영문 초록

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.

목차

1. 서론

2. 본론

3. 실험 결과

4. 결론

키워드

Computer Go Tic-Tac-Toe MCTS Monte-Carlo algorithm UCT Upper Confidence Bounds for Trees Exploration-Exploitation dilemma UCB Upper Confidence Bound