18. Implementation of robust Tic-Tac-Toe game player, using enhanced Monte-Carlo algorithm

Title(KR)

• 강화된 몬테카를로 알고리즘을 활용한 강력한 삼목게임기 구현

Title(ENG)

• Implementation of robust Tic-Tac-Toe game player, using enhanced Monte-Carlo algorithm

Keywords(KR)

• Computer Go, Tic-Tac-Toe, MCTS, Monte-Carlo algorithm, Multi-Armed-Bandit problem, UCB, Upper Confidence Bounds, Exploration-Exploitation dilemma

Keywords(ENG)

• Computer Go, Tic-Tac-Toe, MCTS, Monte-Carlo algorithm, Multi-Armed-Bandit problem, UCB, Upper Confidence Bounds, Exploration-Exploitation dilemma

Author

• Byung-Doo Lee

Abstract(ENG)

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.

Page 135-141