14. The Most Promising Sequence of Moves using Monte-Carlo Tree Search on a Small Go Board

Title(KR)

• 소형바둑에서의 몬테카를로 트리탐색을 활용한 가장 바람직한 수순

Title(ENG)

• The Most Promising Sequence of Moves using Monte-Carlo Tree Search on a Small Go Board

Keywords(KR)

• small Go board, Monte-Carlo Tree Search, MCTS, most promising sequence of moves, lower-level knowledge

Keywords(ENG)

• small Go board, Monte-Carlo Tree Search, MCTS, most promising sequence of moves, lower-level knowledge

Author

• Byung Doo Lee

Abstract(KR)

바둑게임은 중국에서 적어도 2,500년 전에 창안되었으며, 게임을 이기기 위해 상대방보다 더 많은 영역을 둘러싸는 것을 목표로 한다. 간단한 규칙에도 불구하고 바둑은 인공지능(AI) 분야에서 아주 복잡한 전략적인 보드게임이다. 몬테카를로 트리탐색(MCTS)은 국면 평가의 어려움을 극복하고 게 임트리 내의 엄청난 분기수를 줄여주는 최상우선탐색 알고리즘이다. 컴퓨터바둑 게임에서 MCTS는 수많은 플레이아웃을 수행한 후, 게임트리 내에 있는 현재노드로부터 단말노드까지의 임의의 수순 을 표본 추출하여 다음 후보 착수에 대한 승률을 근사적으로 계산해낸다. AlphaGo를 포함한 모든 강력한 컴퓨터바둑 프로그램은 컴퓨터바둑 게임 진행에 있어 MCTS를 이용하여 가장 유망한 착수 를 구해왔다. 본 연구는 소형바둑 컴퓨터게임에 있어 순수 MCTS를 이용하여 가장 유망한 일련의 수순을 찾고자 했다. 실험결과에 의하면 순수 MCTS는 소형바둑에서 19줄바둑게임에서 벌어지는 포석, 중반전, 끝내기라는 3단계가 아닌 중반전과 끝내기라는 단지 2단계를 진행하였으며, 아울러 순수 MCTS는 맥과 연단수와 같은 하위개념의 지식을 이해 못하는 것을 보였다.

Abstract(ENG)

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.

Page