Monte-Carlo Tree Search (MCTS) is a best-first search algorithm to evaluate states of the game tree in game playing, and has been successfully applied to various games, especially to the game of Go. Upper Confidence Bounds for Trees (UCT), which is a variant of MCTS, uses the UCB1 formula as selection policy, and balances exploitation and exploration of the states. Rapid Action-Value Estimation (RAVE), which is a All-Moves-As-First (AMAF) heuristic, treats all moves in a simulation as the first move, and therefore updates the statistics of all children of the root node. In this paper, we evaluate the performance of RAVE and UCT playing against each other in the game of Tic-Tac-Toe. The experimental results show that the first player RAVE is much inferior to the second player UCT (13.0±0.7%); on the other hand, the first player UCT is far superior to RAVE (99.9±0.1%).

Go is an extremely complex strategic board game despite its simple rules and is the great challenging classic game for AI due to its enormous search space. The computer program AlphaGo finally defeated Fan Hui, the European Go champion, without handicaps on a full-sized 19 ×19 board in October 2015. Monte-Carlo Tree Search (MCTS) is a widely-used algorithm for game-tree search in game playing. MCTS based on statistical sampling is a best-first tree search technique to evaluate states; UCT which is a variant of MCTS uses the UCB1 formula as selection policy. In this paper, we evaluate the performance of MCTS and UCT playing against each other in the game of Tic-Tac-Toe. The experimental results show that the first player UCT is slightly superior to the second player MCTS (54.3±1.0%), the first player is always advantageous to the second player regardless of the MCTS and UCT players, and the result of each game should be a tie if both players do their best in Tic-Tac-Toe.

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.

Evolutionary computation is a powerful tool for developing computer games. Back-propagation neural network(BPNN) was proved to be a universal approximator and genetic algorithm(GA) a global searcher. The game of Tic-Tac-Toe, also known as Naughts and Crosses, is often used as a test bed for testing new AI algorithms. We tried to recognize the strategic fitness of a finished Tic-Tac-Toe game when the parameters, such as a sequence of moves, its game depth and result, are provided. To implement this, we've constructed an evolutionary model using GA with back-propagation NNs(GANN). The experimental results revealed that GANN, in the very long training time, converges very slowly; however, performance of recognizing the strategic fitness does not meet we expected and, further, increase of the population size does not significantly contribute to the performance of GANN.

The game of Go is an oriental strategic board game originated from China at least more than 2,500 years ago. The Monte-Carlo Tree Search (MCTS) algorithm in Go is a method that uses a large number of simulations to approximately estimate the winning rate of candidate moves by sampling the game. The two computer Go programs called Crazy Stone and Mogo defeated human Go professionals on the 9⨯9 board in 2006. Prior to our implementing MCTS into computer Go, we tried to find out the best move sequence in playing Tic-Tac-Toe game as a test bed. The experimental results revealed that the first player should play the center to ensure the highest winning rate, and the game result becomes a draw if two players do their best.

몬테카를로 트리탐색은 최대우선탐색 알고리즘이며, 많은 게임 특히 바둑 게임에 성공적으로 적용되어 왔다. 삼목 게임에서 MCTS 간의 대국을 통해 성능을 평가하고자 했다. 첫 번째 대국 자는 항상 두 번째 대국자에 비해 압도적인 우위를 보였으며, 최선의 게임 결과가 무승부가 됨 에도 불구하고 첫 번째 대국자가 두 번째 대국자에 비해 우월한 이유를 찾고자 했다. MCTS는 반복적인 무작위 샘플링을 기반으로 하는 통계적 알고리즘이기 때문에, 특히 두 번째 대국자를 위해 전략을 요하는 시급한 문제를 적절히 대처하지 못한다. 이를 위해 전략적 MCTS(S-MCTS)를 제안하며, S-MCTS는 결코 삼목 게임에서 지지 않는다는 것을 보였다.

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

바둑은 단순한 규칙에도 불구하고 매우 복잡한 전략보드 게임이다. 몬테카를로 트리탐색을 이용하여 컴퓨터 바둑 프로그램들이 접바둑으로 프로기사를 제압해 왔다. 몬테카를로 트리탐색은 전략의 개념보다는 몬테카를로 시뮬레이션에 의해 계산된 승률에 근간을 한다. 반면에 적절한 적합도 함수로 된 유전 알고리즘은 게임 내 최적 해를 찾아낼 수 있다. 삼목 게임(또는 ◯x게임)은 가장 대중적인 게임 중의 하나이다. 저자는 삼목 게임에서의 최선의 전략을 찾고자 했다. 실험 결과로 유전 알고리즘은 효율적인 전략들을 찾을 수가 있으며, 바둑과 서양장기와 같은 여타 보드게임들에 적용할 수 있음을 보였다.

바둑 게임은 가장 오래된 게임 중의 하나이며 적어도 2,500년 전에 기원되었다. 게임프로그래밍에서 대부분의 성공적인 접근법은 평가함수를 활용한 게임트리 탐색을 사용하는 것이다. 그러나 컴퓨터바둑에서 그럴싸한 평가함수를 구축한다는 것은 매우 어렵다. 몬테카를로 트리탐색(MCTS)은 9줄 바둑에서 프로기사를 제압한 MoGo와 CrazyStone과 같은 강력한 컴퓨터바둑 프로그램을 만들어 내었다. 몬테카를로 트리탐색은 몬테카를로 시뮬레이션에 의해 계산된 승률을 근간으로 한다. 몬테카를로 트리탐색을 컴퓨터바둑에 구현하기에 앞서 삼목에서 최상의 첫 수로 중앙, 귀, 변의 세 수에 대한 각각의 승률을 측정하려고 했다. 실험 결과로 최상의 첫 수는 중앙이 우선하고, 다음은 귀, 마지막으로는 변이라는 사실이 밝혀졌다.