삼목 게임에서 최상의 첫 수를 구하기 위해 적용된 신뢰상한트리 알고리즘

국문 초록 (Abstract)

고대 중국에서 기원된 바둑은 인공지능 분야에서 가장 어려운 도전 중의 하나로 간주된다. 지난 수년에 걸쳐 MCTS를 기반으로 하는 정상급 컴퓨터바둑 프로그램이 놀랍게도 접바둑에서 프로기사를 물리쳤다. MCTS는 게임이 끝날 때까지 일련의 무작위 유효착수를 시뮬레이션 하 는 접근법이며, 기존의 지식기반 접근법을 대체했다. 저자는 MCTS의 변형인 UCT 알고리즘을 삼목 게임에 적용하여 최선의 첫 수를 찾고자 했으며, 순수 MCTS의 결과와 비교를 했다. 아울 러 UCB 이해를 위한 다중슬롯머신 문제를 풀기 위해 엡실론-탐욕 알고리즘과 UCB 알고리즘 을 소개 및 성능을 비교하였다.

다국어 초록 (Multilingual Abstract)

The game of Go originated from ancient China is regarded as one of the most difficult challenges in the filed of AI. Over the past few years, the top computer Go programs based on MCTS have surprisingly beaten professional players with handicap. MCTS is an approach that simulates a random sequence of legal moves until the game is ended, and replaced the traditional knowledge-based approach. We applied the UCT algorithm which is a MCTS variant to the game of Tic-Tac-Toe for finding the best first move, and compared it with the result generated by a pure MCTS. Furthermore, we introduced and compared the performances of epsilon-Greedy algorithm and UCB algorithm for solving the Multi-Armed Bandit problem to understand the UCB.

참고문헌 (Reference)

1 Wikipedia, "Tic-Tac-Toe"

2 B.D. Lee, "The best move sequence in playing Tic-Tac-Toe game" Journal of The Korean Society for Computer Game 27 (3) : 11 ~ 16 , 2014

3 S. Gelly, "The Grand Challenge of Computer Go : Monte Carlo Tree Search and Extensions" Communications of the ACM 55 (3) : 106 ~ 113 , 2012

4 D. Brand, "Sample Evaluation for Action Selection in Monte Carlo Tree Search"

5 G. Hochmuth, "On the Genetic Evolution of a Perfect Tic-Tac-Toe Strategy"

6 T. Pepels, "Novel Selection Methods for Monte-Carlo Tree Search" University of Masstricht , 2014

7 S. Gelly, "Monte-Carlo Tree Search and Rapid Action Value Estimation in Computer Go" Artificial Intelligence 75 (11) : 1856 ~ 1875 , 2011

8 H. Baier, "Monte-Carlo Tree Search and Minimax Hybrids" Computer Games 504 : 45 ~ 63 , 2014

9 B.D. Lee, "Monte-Carlo Tree Search Applied to the game of Tic-Tac-Toe" Journal of Korea Game Society 14 (3) : 47 ~ 54 , 2014

10 G. Chaslot, "Monte-Carlo Tree Search" University of Masstricht, , 2010

11 A.A.J van der Kleij, "Monte Carlo Tree Search and Opponent Modeling through Player Clustering in no-limit Texas Hold'en Poker" University of Groningen , 2010

12 Y. Wang, "Modification of UCT and sequence-like simulations for Monte-Carlo Go"

13 Ł. Lew, "Modeling Go Game as a Large Decomposable Decision Process" Warsaw University , 2011

14 B.D. Lee, "Korean Pro Go Player's Opening Recognition Using PCA" Journal of Korean Society for Computer Game 26 (2) : 228 ~ 233 , 2013

15 A. Bhatt, "In Search of No-loss Strategies for the Game of Tic-Tac-Toe using a Customized Genetic Algorithm" GECCO'08(Genetic and Evolutionary Computation Conference 2008 : 889 ~ 896 , 2008

16 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 : 1 ~ 7 , 2014

17 P. Auer, "Finite-time Analysis of the Multiarmed Bandit Problem" Kluwer Academic Publishers , 2002

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 28 (2) : 95 ~ 101 , 2015

19 S. Takeuchi, "Evaluation of Monte Carlo Tree Search and the Application of Go"

20 I.J. Ahn, "Design of Omok AI using Genetic Algorithm and Game Trees and Their Parallel Processing on the CPU" Journal of the Korea Information Science Society 37 (2) : 66 ~ 75 , 2010

21 Wikipedia, "Computer Go"

22 B.D. Lee, "Comparison of LDA and PCA for Korean Pro Go Player's Opening Recognition" Journal of Korea Game Society 13 (4) : 15 ~ 24 , 2013

23 J.M. White, "Bandit Algorithms for Website Optimization" O'Relly , 2013

24 B.D. Lee, "Applying Principal Component Analysis to Go Openings" Journal of Korea Game Society 13 (2) : 59 ~ 70 , 2013

25 B.D. Lee, "Analysis of Tic-Tac-Toe Game Strategies using Genetic Algorithm" Journal of Korea Game Society 14 (6) : 39 ~ 48 , 2014

26 B.D. Lee, "Analysis of Korean, Chinese and Japanese Pro Go Player's Openings" Journal of Korean Society for Computer Game 26 (4) : 17 ~ 26 , 2013