The Most Promising Sequence of Moves using Monte-Carlo Tree Search on a Small Go Board
1
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
The game of Go was invented at least 2,500 years ago in China and aims to surround more territory than the opponent to win a game. Despite its simple rule, Go is a very complex strategy board game in the field of Artificial Intelligence (AI). The Monte-Carlo Tree Search (MCTS) is an algorithm with best-first search to overcome the difficulty of state evaluation and to reduce the enormous branching factor in a game tree. In the game of computer Go it performs numerous playouts to approximately estimate the win rates of the next candidate moves by sampling a sequence of moves starting the current node to the terminal node in a game tree. All powerful computer Go programs including AlphaGo have used MCTS to find the most promising move in playing computer Go game. We tried to find the most promising sequence of moves using pure MCTS in playing a computer game of small board Go. The experimental result shows that pure MCTS on a small Go board proceeds only two phases, the middle and the end games, rather than three phases, the opening, the middle and the end games happening in a 19×19 Go game; It also lacks of understanding of lower-level knowledge such as tesuji and oki.
Abstract
The game of Go was invented at least 2,500 years ago in China and aims to surround more territory than the opponent to win a game. Despite its simple rule, Go is a very complex strategy board game in the field of Artificial Intelligence (AI). The Monte-Carlo Tree Search (MCTS) is an algorithm with best-first search to overcome the difficulty of state evaluation and to reduce the enormous branching factor in a game tree. In the game of computer Go it performs numerous playouts to approximately estimate the win rates of the next candidate moves by sampling a sequence of moves starting the current node to the terminal node in a game tree. All powerful computer Go programs including AlphaGo have used MCTS to find the most promising move in playing computer Go game. We tried to find the most promising sequence of moves using pure MCTS in playing a computer game of small board Go. The experimental result shows that pure MCTS on a small Go board proceeds only two phases, the middle and the end games, rather than three phases, the opening, the middle and the end games happening in a 19×19 Go game; It also lacks of understanding of lower-level knowledge such as tesuji and oki.
참고문헌 (17)
- 이병두, "All-Moves-As-First Heuristic applied to the game of Tic-Tac-Toe", 한국컴퓨터게임학회논문지, 30(2), pp.1~7 (2017), (사)한국컴퓨터게임학회[DOI]
- 이병두, "삼목게임에서의 몬테카를로 트리탐색과 신뢰상한 트리탐색간의 경쟁", 한국컴퓨터게임학회논문지, 29(1), pp.1~6 (2016), (사)한국컴퓨터게임학회[DOI]
- 이병두, "강화된 몬테카를로 알고리즘을 활용한 강력한 삼목게임기 구현", 한국컴퓨터게임학회논문지, 28(3), pp.135~141 (2015), (사)한국컴퓨터게임학회[DOI]
- 이병두, "무전략 몬테카를로 트리탐색을 활용한 9줄바둑에서의 첫 수", 한국게임학회 논문지, 17(3), pp.63~70 (2017), 한국게임학회
- 최영욱, "삼목 게임에서의 최선의 수순", 한국컴퓨터게임학회논문지, 27(3), pp.11~16 (2014), (사)한국컴퓨터게임학회[DOI]
- 이병두, "삼목 게임을 위해 개선된 몬테카를로 트리탐색 알고리즘", 한국게임학회 논문지, 16(4), pp.79~86 (2016), 한국게임학회
- R. Coulom, "The Monte-Carlo Revolution in Go", Japanese-French Frontiers of Science Symposium (2009)
- 이병두, "삼목 게임에서 최상의 첫 수를 구하기 위해 적용된 신뢰상한트리 알고리즘", 한국게임학회 논문지, 15(10), pp.109~118 (2015), 한국게임학회
- N. Sephton, "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)
- H. Baier, "MCTS-Minimax Hybrids with State Evaluation", Journal of Artificial Intelligence Research, pp.193~231 (2018)
- Byung-Doo Lee, "Monte-Carlo Game Implementation" (2017), Hansan Press
- Byung-Doo Lee, "AI Go" (2011), Books Holic
- T. Pepels, "Novel Selection Methods for Monte-Carlo Tree Search", pp.2014
- "Computer Go"[URL]
- "Komidashi"[URL]
- "Scoring"[URL]
- "Baduk rules"[URL]