Journal of Korea Game Society (한국게임학회 논문지)

Korea Game Society (한국게임학회)
권호 표지
DOI QR코드

DOI QR Code

The first move in the game of 9⨯9 Go, using non-strategic Monte-Carlo Tree Search

무전략 몬테카를로 트리탐색을 활용한 9줄바둑에서의 첫 수

  • Lee, Byung-Doo (Dept. of Baduk Studies, Division of Sports Science, Sehan University)
  • 이병두 (세한대학교 체육학부 바둑학과)
  • Received : 2017.05.30
  • Accepted : 2017.06.20
  • Published : 2017.06.30
Download PDF
⟨ Previous Next ⟩

Abstract

In AI research Go is regarded as the most challenging board game due to the positional evaluation difficulty and the huge branching factor. MCTS is an exciting breakthrough to overcome these problems. The idea behind AlphaGo was to estimate the winning rate of a given position and then to lead deeper search for finding the best promising move. In this paper, using non-strategic MCTS we verified the fact that most pro players regard the best first move as Tengen (Origin of heaven) in $9{\times}9$ Go is correct. We also compared the average winning rates of the most popular first moves.

인공지능 연구에서 바둑은 위치평가의 어려움과 엄청난 분기수로 인해 가장 도전적인 보드게임으로 여겨지고 있다. 몬테카를로 트리탐색은 이러한 문제점을 극복할 수 있는 고무적인 돌파구이다. 알파고의 숨겨진 아이디어는 주어진 위치에서의 승률을 예상하여 깊은 탐색을 유도한 후 가장 고무적인 착수를 찾아내는 것이었다. 본 논문에서는 무전략 MCTS를 활용하여 9줄바둑에서 프로기사들이 최상의 첫수로 여기는 천원점이 옳다는 것을 확인했으며, 또한 가장 유행하는 첫 수들의 평균승률을 비교했다.

Keywords

References

  1. B.D. Lee, "Enhanced strategic Monte-Carlo Tree Search algorithm to play the game of Tic-Tac-Toe", Journal of Korea Game Society, Vol. 16, No. 4, pp. 79-86, 2016. https://doi.org/10.7583/JKGS.2016.16.4.79
  2. B.D. Lee, D.S. Park and Y.W. Choi, "The UCT algorithm applied to find the best first move in the game of Tic-Tac-Toe", Journal of Korea Game Society, Vol. 15, No. 5, pp. 109-118, 2015. https://doi.org/10.7583/JKGS.2015.15.5.109
  3. B.D. Lee, "Competition between MCTS and UCT in the game of Tic-Tac-Toe", Journal of Korean Society for Computer Game, Vol. 29, No. 1, pp. 1-6, 2016. https://doi.org/10.21493/kscg.2016.29.2.1
  4. B.D. Lee, "Analysis of Tic-Tac-Toe Game Strategies using Genetic Algorithm", Journal of Korea Game Society, Vol. 14, No. 6, pp. 39-48, 2014. https://doi.org/10.7583/JKGS.2014.14.6.39
  5. B.D. Lee, "Monte-Carlo Tree Search Applied to the Game of Tic-Tac-Toe", Journal of Korea Game Society, Vol. 14, No. 3, pp. 47-54, 2014. https://doi.org/10.7583/JKGS.2014.14.3.47
  6. B.D. Lee and Y.W. Choi, "Monte-Carlo Game Implementation", Hansan Press, 2017.
  7. A. Couetoux, M. Müller and O. Teytaud, "Monte Carlo Tree Search in Go", from https://webdocs.cs.ualberta.ca/-mmueller/ps/2013/2013-gochapter-preprint.pdf, 2017.
  8. D. Silver, et al., "Mastering the game of Go with deep neural networks and tree search", Journal of Nature, Vol. 529, Issue 7587, pp. 484-489, 2016. https://doi.org/10.1038/nature16961
  9. T. Song, "Monte Carlo Tree Search and Its Application in AlphaGo", from https://stlong0521.github.io/20160409%20-%20MCTS.html, 2017.
  10. S.H. Jung, et al., "Modern Baduk theory", Dacom Press, 2016.
  11. Wikipedia, "Komidashi", from https://en.wikipedia.org/wiki/Komidashi, 2017.
  12. Wikipedia, "List of Go terms", from https://en.wikipedia.org/wiki/List_of_Go_terms
  13. Sensei's Library, "$9{\times}9$ Openings", from http://senseis.xmp.net/?9x9Openings, 2017.
  14. H. Baier and M.H.M. Winands, "Monte-carlo Tree Search and Minimax Hybrids", Computer Games, Vol. 504, pp. 45-63, 2014.
  15. M.H.M. Winands and Y. Brornsson, "Evaluation Function Based Monte-Carlo LOA", from http://www.ru.is/-yngvi/pdf/WinandsB09.pdf, 2017.
  16. A.A.J van der Kleij, "Monte Carlo Tree Search and Opponent Modeling through Player Clustering in no-limit Texas Hold'en Poker", Master thesis, University of Groningen, 2010.
  17. E. Powley, et al, "Heuristic move pruning in monte carlo tree search for the strategic card game lords of war", In Computational Intelligence and Games (CIG) of IEEE, pp.1-7, 2014.
  18. B.D. Lee, "Evolutionary neural network model for recognizing strategic fitness of a finished Tic-Tac-Toe game", Journal of Korean Society for Computer Game, Vol. 28, No. 2, pp. 95-101, 2015.
  19. B.D. Lee, "Implementation of robust Tic-Tac-Toe game player, using enhanced Monte-Carlo algorithm", Journal of Korean Society for Computer Game, Vol. 26, No. 3, pp. 135-141, 2015.
  20. B.D. Lee and Y.W. Choi, "The best move sequence in playing Tic-Tac-Toe game", Journal of The Korean Society for Computer Game, Vol. 27, No. 3, pp. 11-16, 2014.
  21. B.D. Lee, "Comparison of LDA and PCA for Korean Pro Go Player's Opening Recognition", Journal of Korea Game Society, Vol. 13, No. 4, pp. 15-24, 2013. https://doi.org/10.7583/JKGS.2013.13.4.15
  22. B.D. Lee, "Analysis of Korean, Chinese and Japanese Pro Go Player's Openings", Journal of Korean Society for Computer Game, Vol. 26, No. 4, pp. 17-26, 2013.
  23. B.D. Lee, "Korean Pro Go Player's Opening Recognition Using PCA", Journal of Korean Society for Computer Game, Vol. 26, No. 2, pp. 228-233, 2013.
  24. S. Gelly, et al., "The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions", Communications of the ACM, Vol. 55, No. 3, pp. 106-113, 2012. https://doi.org/10.1145/2093548.2093574