Earticle

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 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.

바둑에 있어 사활 문제는 컴퓨터 바둑을 구현하기 위하여 반드시 극복되어져야 하는 기본적인 문제이다. 사활 문제와 같은 국부적인 문제를 풀기 위하여, 중요하게 고려되어야 할 사항은 어떻게 하면 게임 트리의 분기수와 그 깊이를 줄일 수 있느냐는 것이다. 본 논문에서는 게임 트리를 위한 첫 수들을 생성하기 위하여 휴리스틱 세력 함수로 눈 모양 분석이라는 초유의 방법을 적용하였다. 휴리스틱 세력 함수로 둘러싸인 돌들의 눈 모양을 분석하는 주요 목적은 아주 짧은 시간내에 둘러싸인 돌들이 살았는지, 미생(未生)인지 아니면 죽었는지를 판단하는 것이다. 만약 둘러싸인 돌들이 죽거나 미생일 경우가 높으면, 완전 게임 트리 내에서 최선의 수순을 찾아내기 위해 소요되는 엄청난 계산 시간을 절약할 수 있는 가능한 급소 점(첫 수)들로 사용될 수가 있다. 비록 눈 모양 분석기는 40% 미만의 정확도를 보였지만, 단순한 휴리스틱 세력함수로 된 눈 모양 분석기는 짧은 시간 내에 둘러싸인 돌들의 생사 여부를 판단하는 데 상당한 도움이 됨을 발견했다.

In the game of Go, the life-and-death problem is a fundamental problem to be definitely overcome for implementing a computer Go program. To solve local Go problems such as life-and-death problems, an important consideration is how to tackle the game tree's huge branching factor and its depth. We applied a novel method, eye shape analysis with a heuristic influence function, to generate a set of first moves for the game tree. The main objective of analyzing the eye shape of a surrounded group with a heuristic influence function is to determine in a short time whether the surrounded group is alive, dead or unsettled. If there is a high possibility that the surrounded group is dead or unsettled, then we can use the possible vital points (the first moves) to save enormous amounts of computing time in searching for the best sequence of moves in a complete game tree. Although the resulting accuracy of the eye shape analyzer is less than 40%, we found that the eye shape analyzer with a simple heuristic influence function can significantly contributes to quickly finding the life-and-death status of the surrounded group.

In 1970 Albert Zobrist published his Ph.D. thesis describing the first computer program for Go. Judging by the progress made in the past 35years, it will likely be many decades before there is a program capable of playing at an expert level. This paper gives a highly personal overview of some results in computer and mathematical Go with references to the details. In some sections, I give an overview of my own work, including plans for the future.

컴퓨터 바둑에 대한 기존연구에서는 형세를 판단하거나 행마를 하기 위해 게임이론에 입각한 인공지능적 알고리즘을 주로 사용하였다. 본 논문에서는 이러한 틀에서 벗어나 각 착점의 의미를 언어학적으로 파악하고자 하였다. 이를 위해 먼저 바둑 용어를 의미에 따라 구분하여 정리하였고 분류된 용어에 대하여 세분화된 의미특성을 부여하였다. 정리한 용어를 활용하여 각 착점이 반상에서 가지는 역학관계를 표현하고 그 의미를 해석할 수 있게 하였다. 이를 토대로 각 착점의 가치를 수치화할 수도 있게 되었다. 이러한 분석과 분류는 바둑 한판의 내용을 이야기로 보는데 있어서 그 기초를 제공한다.

컴퓨터 바둑에 있어서 형세 평가는 일반화되어 있지 않다. 정확한 평가를 위해서 국면의 변화에 따른 361 자리의 소유 여부를 분명히 할 필요가 있다. 본 논문에서는 바둑의 규칙과 특성을 분석하는 방법으로 그래프 표현을 적용하였으며, 돌의 세기, 영향력, 안정도, 자리값, PM 등의 요소를 정의하여 임의의 국면에 대한 형세를 평가하는 시스템(SES)을 제안하였다. 이는 혹, 백간의 영역 차이를 명백하게 표현하므로 바둑의 전반적인 형세를 평가하는데 매우 효과적이다. 결론적으로 SES는 초반의 형세 평가에 매우 우수하며, 프로기사에 대한 254개의 실전 기보에 대해서 70.9%의 적중률을 보였다. 정석 사례를 구축하여 사용하는 상용 프로그램, Nemesis와 비교 실험한 결과에 의하면, 프로기사에 대한 형세 평가 적중률에 있어서 SES는 Nemesis보다 전체적으로 10% 앞서는 것으로 나타났다.

In computer Go, the method evaluating the situation of a face is not generalized. To evaluate the situations all the faces accurately, computer Go must judge owners of 361 positions according the changes of the faces. In this paper, we apply the structure of graph as a method analyzing the rules and characters of Go. The Situation Evaluation System(SES) which can evaluate the situation of a face without DB information oかy using strength of stone(SS), influence power(IP), safety(S), position value(PV), and position-value matrix(PM) is proposed. This system is very effective to evaluate the whole situations of Go because it can show the owner of 361 positions between Black and White. As a result, SES can well compute the situations in the opening game of Go. It makes 70.9% hit-ratio as compared with the practical Go games of professional players. According to the results compared with Nemesis, the commercial program which has the joseki(established stones: hewn sequences of moves near the corner which result in near-equal positions for White and Black), SES is superior to Nemesis by 10% higher in the hit-ratio of situation evaluations of professional players.