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

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

DOI QR Code

The most promising first moves on small Go boards, based on pure Monte-Carlo Tree Search

순수 몬테카를로 트리탐색을 기반으로 한 소형 바둑판에서의 가장 유망한 첫 수들

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

Abstract

In spite of its simple rule, Go is one of the most complex strategic board games in the field of Artificial Intelligence (AI). Monte-Carlo Tree Search (MCTS) is an algorithm with best-first tree search, and has used to implement computer Go. We try to find the most promising first move using MCTS for playing a Go game on a board of size smaller than $9{\times}9$ Go board. The experimental result reveals that MCTS prefers to place the first move at the center in case of odd-sized Go boards, and at the central in case of even-sized Go boards.

간단한 규칙에도 불구하고 바둑은 인공지능 분야에서 가장 복잡한 전략적 보드게임 중의 하나이다. 몬테카를로 트리탐색(MCTS)은 최상우선 트리탐색 알고리즘으로 컴퓨터바둑 제작을 위해 사용되어 왔다. 저자는 9줄바둑판보다 작은 바둑판에서의 바둑게임 행위를 위해 MCTS를 활용하여 가장 유망한 첫 수를 찾고자 한다. 실험결과에 의하면 MCTS는 첫 수로 홀수형 바둑판에서는 정중앙, 짝수형 바둑판에서는 중앙 부근에 착수하기를 선호하는 것으로 나타났다.

Keywords

KGOHCL_2018_v18n6_59_f0001.png 이미지

[Fig. 1] The process of MCTS [14]

KGOHCL_2018_v18n6_59_f0002.png 이미지

[Fig. 2] Win rates of the first moves

KGOHCL_2018_v18n6_59_f0003.png 이미지

[Fig. 3] Average win rate of the central Vs Elapsed time for the first move (board size adjusted)

KGOHCL_2018_v18n6_59_f0004.png 이미지

[Fig. 4] Sequence of moves

KGOHCL_2018_v18n6_59_f0005.png 이미지

[Fig. 5] Sequence of moves

KGOHCL_2018_v18n6_59_f0006.png 이미지

[Fig. 6] Sequence of moves

KGOHCL_2018_v18n6_59_f0007.png 이미지

[Fig. 7] Win rates of each position on a 5×5 Go board

KGOHCL_2018_v18n6_59_f0008.png 이미지

[Fig. 8] Win rates of each position on a 6×6 Go board

KGOHCL_2018_v18n6_59_f0009.png 이미지

[Fig. 9] Win rates of each position on a 7×7 Go board

KGOHCL_2018_v18n6_59_f0010.png 이미지

[Fig. 10] Win rates of each position on a 8×8 Go board

KGOHCL_2018_v18n6_59_f0011.png 이미지

[Fig. 11] Win rates of each position on a 9×9 Go board

[Table 1] First move and elapsed time

KGOHCL_2018_v18n6_59_t0001.png 이미지

[Table 2] Average win rates of the central

KGOHCL_2018_v18n6_59_t0002.png 이미지

[Table 3] A comparison of statistic

KGOHCL_2018_v18n6_59_t0003.png 이미지

References

  1. B.D. Lee, "The first move in the game of $9{\time}9$ Go, using non-strategic Monte-Carlo Tree Search" Journal of Korea Game Society, Vol. 17, No. 3, pp.63-70, 2017 https://doi.org/10.7583/JKGS.2017.17.3.63
  2. B.D. Lee and Y.W. Choi, "The best move sequence in playing Tic-Tac-Toe game" Journal of Korean Society for Computer Game, Vol. 27, No. 3, pp.11-16, 2014
  3. B.D. Lee and Y.W. Choi, "Monte-Carlo Game Implementation", Hansan Press, 2017
  4. 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
  5. Wikipedia, "Computer Go", https://en.wikipedia.org/wiki/Computer_Go, October, 2018
  6. B.D. Lee, "AI Go", Books Holic, 2011
  7. R. Coulom, "The Monte-Carlo Revolution in Go", Japanese-French Frontiers of Science Symposium, 2009
  8. B.D. Lee, "Monte-Carlo Tic-Tac-Toe", Hansan Press, 2015
  9. 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
  10. M.H.M. Winands and Bjornsson, "Evaluation Function Based Monte-Carlo LOA", http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.182.2046&rep=rep1&type=pdf, October, 2018
  11. N. Sephton, P.I. Cowling, E. Powley, and N.H. Slaven, "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
  12. 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
  13. T. Pepels, "Novel Selection Methods for Monte-Carlo Tree Search", Master thesis, Maastricht University, 2014
  14. D. Perez, S. Samothrakis, and S. M. Lucas. "Knowledge-based fast evolutionary MCTS for general video game playing". IEEE Conference on Computational Intelligence and Games (CIG), pp.1-8, 2014
  15. E.C.D. Werf, H.J. Herik, and J.W.H.M Uiterwijk, "Solving Go on Small Boards", ICGA Journal, Vol. 26, No. 2, pp.92-107, 2003 https://doi.org/10.3233/ICG-2003-26205
  16. E.C.D. Werf and M.H.M. Winands, "Solving Go for Rectangular Boards", ICGA Journal, Vol. 26, No. 2, pp.92-107, 2009
  17. Sense's Library, "Small board Go", from https://senseis.xmp.net/?SmallBoardGo, 2018.