Development of Master Level Computer 9x9 Go Program

Since the beginning of AI, mind games have been studied as relevant application fields. Nowadays, computer programs are better than human master players in most popular board games: Deep Blue in Chess, Chinook in Checkers, ELP in Chinese Chess.

However, Go programs lag far behind their counterparts in any other popular board games. While Go programs have advanced considerably in the last 10-15 years, they can still be beaten easily even by human players of only moderate skill. The branching factor of 9×9 Go is comparable to Chinese Chess. But the strongest 9×9 Go program is only in the amateur level, too. One reason is that the rules of Go are very different to other board games and there is complexity inherent in the Evaluation Function. The other is that only a few researcher study in 9×9 Go program. After circumspect study, based on our research result of Go/Chinese Chess and the speedup of computer hardware, a master level 9×9 Go program may be developed.

We will develop a master level computer 9×9 Go program in three years. Research result on open game knowledge base, retrograde algorithm and game tree search algorithms of our computer Chinese Chess program will be useful in this plan. Combinatorial game theory and Ko procedure theorem will also be applied in this 9×9 Go program. Our research team contains a Go grand master and 4 Go master players. Each of them is also a good programmer. Based on their Go expert knowledge and programming technique, we will develop some methods of machine learning, such as self-learning and learning from data. Those methods will help this system automatically acquire expert knowledge on the Internet Go servers.

Three contributions will be made in this plan. Firstly, playing Go is an acknowledged intelligent behavior. Solving this problem by information techniques is an important significance in AI research area. Second, some search algorithms and machine learning methods will be developed. More than four relevant papers will be published. Finally, this computer 9×9 Go program can help human player to study Go. We expect this program will get the champion of Go program competition in Computer Olympiad easily after two years. When this plan is completed, we will try to challenge human Go master players. The result is also one of our contributions.

 

A Chinese Chess Knowledge Discovery System with Auto-acquiring Expert Knowledge Function

On the design of computer chess program, the major factors that affect performance are the size of opening game database, search depth, and measure function. Traditional Chinese chess database, including opening database and endgame database, have little achievement of the difficulty in knowledge acquisition, increment of the size of knowledge base, lack of judgment for knowledge and integration with chess program.

On this plan, we try to construct the CCKD(Chinese Chess Knowledge Discovery) system to solve problems of the traditional Chinese chess database. We will represent new approaches in the design of data structure and indexing to increase efficiency of knowledge base, and use the knowledge base to improve the factors that affect program performance mentioned before.

Firstly, we search for some Chinese chess websites, and then we design an intelligent agent to download chess manuals that made by master player from the websites. Finally we use the chess manuals as the source of expert knowledge and apply KDD(Knowledge Discovery in Database) techniques to construct an efficient knowledge base.

We estimate that it can get 400 chess manuals, about 20000 positions, per day. It means we will get about 600000 positions per year. In other words, we can obtain about 6000000 problems and their solutions. From the increasing problems and solutions, it can discover large number of Chinese chess knowledge for us, and the knowledge is various. The characteristic of the approach is that chess programmer no longer needs to get chess knowledge from top chess player.

 

Development of System of tsume-Go Problem

 

 

Development of the Evaluation Function of Computer Go