강화된 몬테카를로 알고리즘을 활용한 강력한 삼목게임기 구현
Implementation of robust Tic-Tac-Toe game player, using enhanced Monte-Carlo algorithm
2
조회
0
다운로드
5
인용
0
참고문헌
키워드
초록
Go is an extremely complex strategic board game despite its simple rules. Recently computer Go based on MCTS plays at human-master level and also has defeated top professional players with handicap games in 19×19 Go. Before implementing computer Go, in this paper we show weakness of pure MC algorithm for playing robust Tic-Tac-Toe game and present alternative method to make up the weakness. Furthermore we show how UCB algorithm works for balancing exploration and exploitation in game tree and discuss the need of a hybrid algorithm combined with UCB and strategy based MCTS, for implementing an enhanced computer Go.
Abstract
Go is an extremely complex strategic board game despite its simple rules. Recently computer Go based on MCTS plays at human-master level and also has defeated top professional players with handicap games in 19×19 Go. Before implementing computer Go, in this paper we show weakness of pure MC algorithm for playing robust Tic-Tac-Toe game and present alternative method to make up the weakness. Furthermore we show how UCB algorithm works for balancing exploration and exploitation in game tree and discuss the need of a hybrid algorithm combined with UCB and strategy based MCTS, for implementing an enhanced computer Go.
참고문헌 (22)
- 이병두, "종료된 삼목게임의 전략 적합도 인식을 위한 진화신경망 모델", 한국컴퓨터게임학회논문지, 28(2), pp.95~101 (2015), (사)한국컴퓨터게임학회
- 이병두, "유전 알고리즘을 이용한 삼목 게임 전략 분석", 한국게임학회 논문지, 14(6), pp.39~48 (2014), 한국게임학회[DOI]
- 최영욱, "삼목 게임에서의 최선의 수순", 한국컴퓨터게임학회논문지, 27(3), pp.11~16 (2014), (사)한국컴퓨터게임학회
- 이병두, "한중일 프로바둑기사 포석 분석", 한국컴퓨터게임학회논문지, 26(4), pp.17~26 (2013), (사)한국컴퓨터게임학회
- 이병두, "주성분분석을 활용한 한국 프로바둑기사 포석 인식", 한국컴퓨터게임학회논문지, 26(2), pp.73~80 (2013), (사)한국컴퓨터게임학회
- S. Gelly, "The Grand Challenge of Computer Go : Monte Carlo Tree Search and Extensions", Communications of the ACM, 55(3), pp.106~113 (2012)
- 이병두, "삼목 게임에 적용된 몬테카를로 트리탐색", 한국게임학회 논문지, 14(3), pp.47~54 (2014), 한국게임학회[DOI]
- S. Gelly, "Monte-Carlo Tree Search and Rapid Action Value Estimation in Computer Go", Artificial Intelligence, 175(11), pp.1856~1875 (2011)
- 안일준, "유전 알고리즘과 게임 트리를 병합한 오목 인공지능 설계 및 GPU 기반 병렬 처리 기법", 정보과학회논문지 : 시스템 및 이론, 37(2), pp.66~75 (2010), 한국정보과학회
- A. Bhatt, "In Search of No-Loss Strategies for the game of Tic-Tac-Toe using Customized Genetic Algorithm", GECCO'08, pp.889~896 (2008)
- E. Powley, "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)
- G. Chaslot, "Monte-Carlo Tree Search", Ph.D, pp.2010
- A. A. J van der Kleij, "Monte Carlo Tree Search and Opponent Modeling through Player Clustering in no-limit Texas Hold'en Poker", Master, pp.2010
- J. M. White, "Bandit Algorithms for Website Optimization" (2013), O’Relly
- P. Auer, "Finite-time Analysis of the Multiarmed Bandit Problem" (2002), Kluwer Academic Publishers
- T. Pepels, "Novel Selection Methods for Monte-Carlo Tree Search", Master, pp.2014
- H. Baier, "Monte-Carlo Tree Search and Minimax Hybrids", Computer Games, 504, pp.45~63 (2014)
- "Computer Go" (2015)[URL]
- "On the Genetic Evolution of a Perfect Tic-Tac-Toe Strategy" (2015)[URL]
- "Evaluation Function Based Monte-Carlo LOA" (2015)[URL]
- "Modification of UCT and sequence-like simulations for Monte-Carlo Go" (2015)[URL]
- "Evaluation of Monte Carlo Tree Search and the Application of Go" (2015)[URL]