Published articles about computer go
This list of articles bellow is meant for personal use only.


General articles :
Cognitive psychology :
Combinatorial Game Theorie :
Machine learning
 Neural nets :
Evolutionary algorithms : Temporal Difference Learning : Knowledge based approaches : Other :




Computer Go as a Sum of local games
Martin Müller, Zurich 1995
We develop a sum game model for heuristic Go programming and a program for perfect play in late stage endgames. As a case study in Knowledge Engineering, the "Explorer" program presents new approaches to modeling Go knowledge. We adapt a string matching algorithm for Go pattern matching, develop algorithms for board partition, and create a framework for identifying, searching and evaluating local games. For measuring the performance of Go programs, we introduce the Computer Go Test Collection containing thousands of annotated positions.

Honte a go-playing program using Neural Nets
A. Dahl, Norwegian defence research establishment, 1999
The go playing program Honte is described it uses neuralnets with more conventional AI-techniques like alpha beta search. A neural net is trained to initiate local shapes made in a database of expert games. A second net is trained to estimate the safety of groups using TD(lambda)-learning. A third net is trained to estimate the territorial potential of unoccupied points, also based on selfplay and TD(lambda)-learning. Conclussion : although results have not reached the level of the best commercial go-programs, the results are encouraging.

Evolving Go Playing Strategy in Neural Networks
Paul Donnelly, Patrick Corr, Danny Crookes, Department of Computer Science, The Queen's University of Belfast, 1994
This paper examines the possibility of using evolutionary techniques in the specification of neural networks, to play Go. This is a much more difficult problem than the 'toy­problems' with which evolved neural networks have been successful to date. Results of a simple experiment using a Genetic Algorithm to evolve a Go position evaluation network are reported, the factors affecting performance are discussed, and proposals are made for more sophisticated networks and evolutionary schemes that may potentially be better suited to complex problems that involve an interaction of pattern recognition and serial reasoning. Conclussion : It can be seen that there is a general trend of improvement, but that this is superimposed with a lot of local variability. In terms of objective performance, the resulting networks were very poor, and were unable to beat even the weakest available Go programs.

Learning to evaluate go positions using temporal difference learning
Nicol N. Schraudolph, Peter Dayan Terrence, J. Sejnowski, Computational Neurobiology Laboratory, The Salk Institute for Biological Studies San Diego, 1994 and revised May 2000
A demonstration of a viable alternative by training neural networks to evaluate Go positions via temporal difference (TD) learning. Our approach is based on neural network architectures that reflect the spatial or­ganization of both input and reinforcement signals on the Go board, and training protocols that provide exposure to competent (though unlabelled) play. These techniques yield far better performance than undifferentiated networks trained by self­play alone. A network with less than 500 weights learned within 3 000 games of 9x9 Go a position evaluation function superior to that of a commercial Go program. Comments!

GO SVM GO
Thore Graepel, Mike Goutrié, Marco Krüger, and Ralf Herbrich, Computer Science Department, Technical University of Berlin, Germany, 2000.
We consider the game of Go from the point of view of machine learning. We discuss the representation of both board positions and candidate moves and introduce the common fate graph (CFG) as an adequate representation of board positions for learning. Single candidate moves are represented as feature vectors with features given by subgraphs relative to the given move in the CFG. Using this representation we train a support vector machine and a kernel perceptron to discriminate good moves from bad moves on a collection of life­and­death problems and on 9 by 9 game records. We thus obtain kernel machines that solve Go problems and play 9 by 9. Conclussion : with regard to a a competent Go playing machine our approach represents only a first step.

An evolutionary Algorithm extended by ecological analogy and application to the game of Go
Takuya Kojima, Kazuhiro Ueda, Saburo Nagano, College of Arts and Sciences The University of Tokyo, 1997
The following two important features of human experts' knowledge are not realized by most evolutionary algorithms: one is that it is various and the other is that the amount of knowledge, including infrequently used knowledge, is large. To imitate these features, we introduce an activation value for individuals and a new variation­making operator, splitting, both of which are inspired by ecological systems. This algorithm is applied to the game of Go and a large amount of knowledge evaluated as appropriate by a human expert is acquired. Various kinds of Go knowledge may be acquired such as patterns, sequences of moves, and Go maxims, part of which has already been realized.

Flexible acquisition of various types of knowledge from game records: Apllication to the game of go
Takuya Kojima, Kazuhiro Ueda, Saburo Nagano, College of Arts and Sciences The University of Tokyo, 1997
A large amount of knowledge is considered very useful for systems playing games such as Go and Shogi (Japanese chess), for which the search space larger than that for chess. Knowledge acquisition is therefore necessary for systems playing these games. This paper introduces a new flexible algorithm which acquires various types of knowledge from game records. This algorithm is especially applicable to Go because Go has the largest search space among major games. The algorithm enables computer systems to acquire patterns with a variety of shapes and sizes. Sequences of moves, which are useful for human players but lacking in the present game­playing systems, are also acquired by this algorithm. The possibility of acquiring other types of knowledge --- such as maxims, patterns with situations, and patterns for tsume­go --- is discussed. The possibility of applying the algorithm to games other than Go is also discussed.

A model of acquisition and refinement of deductive rules in the game of go
Takuya Kojima, General Systems study, graduate division of international and interdisciplinary Studies The University of Tokyo, 1995
In order to build Go playing systems, knowledge intensive approach should replace brute force search, which has succeeded in chess. It is too difficult, however, to implement enormous patterns which human experts know and which should be implemented in terms of knowledge intensive approach, thus rule acquisition algorithms should be proposed in order to build stronger Go systems. However, there are four problems in the previous studies on building Go learning systems: existing pattern acquisition algorithms are less powerful, there are no rule refinement algorithms in adversary games, no learning systems have been compared with humans and the hierarchical structure of knowledge in most expert seems abnormal. In this study, these above problems are partly settled. First, a new knowledge acquisition system is built to settle the first problem. This is the first system to acquire rules in Go. Minton [23] proposes a pattern acquisition algorithm in go­moku, which is not powerful enough to learn rules in Go, because State­ Update rules need to be given, which are difficult to be defined in the domain of Go. The proposed algorithm does not need to be given State­Update rules, because it makes direct use of the positions and the moves appearing in process of a game. This algorithm uses the concept of Explanation­Based Generalization (EBG). Secondly, a new refinement algorithm is proposed, which is the first attempt in adversary games. Thirdly, these algorithms are compared with human beginners. This is the first attempt to compare algorithms with humans in adversary games. This system partly uses EBG. This system, however, has three differences from EBG. First of all, while EBG does symbol level learning, this system realizes knowledge­level learning. Secondly, while EBG does not use negative examples, this system does. Finally, while EBG does not change the acquired rules, this system refines acquired rules. The reasons for the differences are that the target problem of this system is one of adversary games and that EBG is used globally and locally in this system.

The challenge of Go as a domain for AI Research: a comparison bettween Go an chess
Jay Burmeister and Janet Wiles, Proceedings of the Third Australian and New Zealand Conference on Intelligent Information Systems, 1995
 Chess Go
1 board size 8 x 8 squares 19 x 19 grid
2 # moves per game ~80 ~300
3 branching factor small (~35) large (~200)
4 end of game and scoring checkmate (simple definition quick to identify) counting territory (consensus by players ­ (hard to identify)
5 long range effects pieces can move long distances (e.g., queens, rooks, bishops) stones do not move, patterns of stones have long range effects (e.g., ladders; life & death)
6 state of board changes rapidly as pieces move mostly changes incrementally (except for captures)
7 evaluation of board positions good correlation with number and quality of pieces on board poor correlation with number of stones on board or territory surrounded
8 programming approaches used amenable to tree searches with good evaluation criteria too many branches for brute force search, pruning is difficult due to lack of good evaluation measures
9 human lookahead typically up to 10 moves even beginners read up to 60 moves (deep but narrow searches e.g., ladders)
10 horizon effect grandmaster level beginner level (e.g., ladders)
11 human grouping processes hierarchical grouping [5] stones belong to many groups simultaneously [6]
12 handicap system none good handicap system

The integration of cognitive knowledge into perceptual representations in computer Go
Jay Burmeister, Janet Wiles, Helen Purchase, Proceedings of the Second Game Programming Workshop in Japan, September 1995
This project targets one facet of Go programming ­ how to relate simple patterns of stones (e.g., kogeima links) to high level properties (e.g., the outcome of a ladder) for a given context (e.g., the presence or absence of a ladder­breaker stone). The numeric representation generated by a simple influence function provides the "perceptual representation". The conditions under which a ladder is won constitutes "cognitive knowledge". As Cognitive Scientists, our goal is to design algorithms for integrating cognitive knowledge about Go into perceptual representations which may be used by others to build Go programs. Typical artificial intelligence (AI) approaches to Go programming are based on the translation of perceptual information (modelled by pattern recognition processes) to symbolic form (modelled by rule­based systems) for access by symbolic reasoning processes. In this project we explore the converse process ­ seeking to integrate cognitive knowledge into a core perceptual representation which can then be accessed by symbolic reasoning processes. The underlying theory is an extension of Hofstadter's theory of highlevel perception, originally applied to letter­string analogies in the Copycat project (Chalmers, French and Hofstadter, 1990).
We demonstrate the concrete instantiation of our theory in four simulations. The core algorithm we used in the simulations integrated cognitive knowledge by directly modifying the numeric information contained in the perceptual representation of the board. The four simulations each implemented different variations of our core algorithm (i.e., static, additive, multiplicative and context­sensitive modifications of influence values).

Accessing Go and computer Go resources on the internet
Jay Burmeister, Janet Wiles, Department of Computer Science, Department of Psychology The University of Queensland 1995
The game of Go provides a rich domain for academic research in computer science, artificial intelligence and psychology. Researchers in the computer Go field as well as individuals involved in implementing Go programs for recreation or profit can benefit from resources available on the Internet. This paper provides a guide to accessing the resources that may ben­efit those in the computer Go field. We describe these resources and how they can be accessed.

On relating local and global factors: a case study from the game of Go
Jay Burmeister, Janet Wiles , Helen Purchase Department of Computer Science and Department of Psychology of the University of Queensland, Australia, 1995
Traditional artificial intelligence (AI) approaches to programming the game of Go are based on the translation of local information (modelled by pattern recognition processes) to global symbolic form (modelled by rule­based systems) for access by symbolic reasoning processes. In this paper we explore the converse process ­ seeking to relate local and global factors by integrating global factors into a local representation which can then be accessed by symbolic reasoning processes. We demonstrate one method for such an integration ­the interaction of bottom­up and top­down processing. The algorithm we use in our simulation integrates global factors by directly modifying the numeric information contained in the local representation of the board. We use Go as an example of a domain with the characteristic that local and global factors cannot be identified independently of each other. Thus, to form a representation of a Go board requires an interaction between bottom­up processing (to identify local factors) and top­down processing (to identify global factors). In the final section we briefly relate these constraints to other domains.

Automatic acquisition of Go knowledge from game records: deductive and evolutionary approaches.
Takuya KOJIMA, General Systems Studies, Graduate Division of International and Interdisciplinary Studies The University of Tokyo, 1998
The final goal of this study is to construct a model of Go experts, which works as experts and performs well as experts. Toward this goal, this study focused on knowledge, and two algorithms for acquiring Go knowledge were proposed. One is an algorithm acquiring strict knowledge in a deductive way. This algorithm is a model of human novices and intermediates, who acquires Go knowledge in a deductive way. This algorithm is an application of Explanation­Based Learning (EBL), which is one of the major deductive algorithms. This algorithm constructs ``explanations'' why a good move succeeds, and as a result a good move is identified and the relevant objects are chosen among the whole board. In adversary games as Go, the perfect rules are di#cult to acquire from one example. When a negative example of acquired rules is given, this algorithm refines the acquired rules by constructing ``explanations'' why the negative examples succeed for the opponent. While normal EBL does not use negative examples, this algorithm uses them as the sources of refinement. One of the advantages of this deductive approach is that rather proper knowledge can be acquired from a small number of rules. One of the disadvantages is, however, that the reasons why a good move succeeds should be clearly explained. Since Go has little constraints and the goal is vague in most moves, most moves of Go are hard to explain even for human experts. The other knowledge acquisition algorithm is introduced for the kind of knowledge, heuristic knowledge. Although most previous systems acquiring heuristic knowledge acquire knowledge from fixed regions, the shape of knowledge of human experts is not at all fixed, or uniform. Therefore the proposed algorithm acquires a large number of flexible knowledge. The proposed algorithm takes an evolutionary approach, because the normal approach such as exhaustive search is not tractable because of the huge search space of Go. It intro­ duced activation value to all individuals in order to take frequency as a fitness indicator. It also introduced a new operator, split, which allows flexible representation than ordinary evolutionary algorithms. While this algorithm could acquire appropriate patterns from 9x9 board games, the percentage of appropriate patterns becomes less in 19x19 board games. A new domain specific search bias, vision, is introduced to narrow the search space. As a result, the percentage of getting appropriate rules becomes much higher. Se­quences of moves, which are important for human experts but lack in nowadays computer systems, are also acquired. Although individual rules are evaluated as good by human experts, whether acquired rules as a whole are appropriate is not easy to evaluate. To do this, Tsume­Go problems are solved by acquired rules. Rules are automatically given priorities by new priority assign mechanisms to solve Tsume­Go. As a result, the performance of the system is as good as human 1 dan , suggesting that the system can acquire appropriate knowledge. The knowledge representation of human 2 kyu is as simple as this system: it consists of board configuration, stones or edges of the board. It is reported that the knowledge representation of 1 dan player, on the other hand, contains verbal information. By defining terms human experts use to describe rules, rules with the terms can be acquired by this algorithm, and more human­like knowledge is expected to be acquired. It is also expected that knowledge the system acquires can be probes to extract knowledge from human experts. It will be a big contribution not only to artificial intelligence but also to cognitive science.

AI techniques used in computer Go
Jay Burmeister and Janet Wiles, Schools of Information Technology and Psychology The University of Queensland, Australia, Fourth Conference of the Australasian Cognitive Science Society, Newcastle. 1997
This paper surveys the most competitive Computer Go programs. It is targeted generally at the Cognitive Science community as an introduction to Computer­Go, given the growing importance of Go as a domain for Cognitive Science research, and specifically at Computer Go programmers (or prospective Go programmers). We survey the best current Computer Go programs, Handtalk, Go4 ++, Many Faces of Go, Go Intellect, and Explorer. We summarise the AI techniques used, key challenges that must be faced, and issues involved in game tree search, showing why Computer Chess techniques do not translate well to the Go domain.

Applying adversarial planning techniques to Go
Steven Willmott, Julian Richardson, Alan Bundy, John Levine (1999), Theoretical Computer Science, Vol. 252, No. 1-2, February 2001, Elsevier, 45--82.
Approaches to computer game playing based on alfa-beta search of the tree of possible move sequences combined with a position evaluation function have been succefully for many games, notably Chess. Such approaches are less successful for games with large search spaces such as Go, and we are led to seek alternatives. One such alternative is to model the goals of the players, and their strategies for achieving these goals. This approach means searching the space of possible goal expansions, typically much smaller than the space of move sequences. Previous attempts to apply these techniques to Go have been unable to provide results for anything other than a high strategic level or very open game positions. In this paper we describe how adversarial hierarchical task network planning can provide a framework for goal­directed game playing in Go which is also applicable both strategic and tactical problems.

Review computer Go 1984 - 2000
Martin Müller, Department of computer siences at the University of Alberta
The main breakthroughs within computer go are made for specialized problems, like endgame and restricted live and dead problems, not for complete game programs.
The main different stages in computer Go programs for the last 10-15 years :
The main challanges that Martin Müller point out are :

Golem and why computer Go is hard
Herbert Enderton, School of Computer Science, Carnegie-Mellon University, CMU-CS-92-101, 1991
With my go program Golem I have tried to create simple algorithms to play the game based on fundamental principles of the game. Golem has no hand­coded knowledge of openings, connection patterns, or anything of that sort. Unlike most go programs it does not have rules that say "if you see this stone pattern play here." Instead it has an evaluation function which estimates territory, and uses a small top­level search to decide which move gains the most territory. Golem does use neural networks which have absorbed some knowledge of stone patterns by being shown professional go games, but I have tried to minimize its dependence on such knowledge in order to be sure that it understands (in some sense) the basic tactical concepts of go.
Intresting 1, For each of eight points surrounding the proposed move, what color is on that point. Possible values are side­to­move's stone, opponent's stone, empty, or off­the­board. There is a canonical order to the eight points so that, for example, the fourth input unit is associated with the point just "below" the move, i.e., in the direction of the nearest edge. How many liberties would the move have? If the opponent played there, how many liberties would she have? For each of the four neighbors, if it's a stone, how many liberties does it have? This network has 29 input units, 10 hidden units, and 1 output unit, completely connected. It provides a value between.
Intresting 2, Golem's neural networks are extremely fond of contact plays, and tend to avoid starting new groups in empty regions. Part of the reason is that they have more information moves that are near other stones. But the main reason is that in a typical position there are many points in large open regions that are all roughly equivalent. When the feature set is restricted to facts about the immediate 3*3 neighborhood these points look identical, but even when more features are included, there is not very much to distinguish one point from another in empty regions. The odds of any one such point being chosen by the professional go player are low, so these points show up much more often as negative examples. It is not clear what a satisfactory solution to this would be.

The integration of a priori knowledge into a Go playing Neural Network
Markus Enzenberger, September 1996
The best current computer Go programs are hand crafted expert sys­tems. They are using conventional AI technics such as pattern matching, rule based systems and goal oriented selective search. Due to the increas­ing complexity of managing this kind of knowledge representation by hand, the playing strength of these programs is still far from human master level. This article describes methods for integrating expert Go knowledge into a learning artificial neural network. These methods are implemented in the program NeuroGo. The network learns by playing against itself using tem­poral difference learning and backpropagation. The expert knowledge that is implemented at present in NeuroGo is simple compared with a conven­tional computer Go program. Despite of this, NeuroGo is able to achieve a playing strength which is equal to a conventional program playing at a medium level.
Intresting 1, The NN evaluation is interpreted as the prob­ability that this intersection will belong to Black at the end of the game. It is trained by looking at a set of features and a relation expert.
Intresting 2, After a period of 500 training games, a set of 100 games against the opponent was played without training (50 with black and 50 with white). The medium playing level 8 (of 20) was chosen at the oppenent program. As can be seen in figure 3 the largest network is able to achieve equal level of play after about 4500 games. It shows a more steady performance against the opponent than the smaller networks.

Exploratory Learning in the game of Go
Barney Pell, In D.N.L. Levy and D.F. Beal, editors, Heuristic Programming in Artificial Intelligence 2 - The Second Computer Olympiad. Ellis Horwood, 1991.
This paper considers the importance of exploration to game­playing programs which learn by playing against opponents. The central ques­tion is whether a learning program should play the move which offers the best chance of winning the present game, or if it should play the move which has the best chance of providing useful information for fu­ture games. An approach to addressing this question is developed using probability theory, and then implemented in two different learning meth­ods. Initial experiments in the game of Go suggest that a program which takes exploration into account can learn better against a knowledgeable opponent than a program which does not.

Monte Carlo Go
Bernd Brugmann, Technical report, Physics Department, Syracuse Universit, 1993.
We present an algorithm for the board game go which attempts to find the best move by simulated annealing. Remarkably, without including any go knowledge beyond the rules, our implementation leads to a playing strength of about 25 kyu on a 9x9 board.

Where is the dousand dollar Go ?
Elwyn Berlekamp and Yonghoan Kim, Games of no Chance, Cambridge University Press, 1996
This paper features a problem that was composed to illustrate the power of combinatorial game theory applied to Go endgame positions. The problem is the sum of many subproblems, over a dozen of which have temperatures significantly greater than one. One of the subproblems is a conspicuous four­point ko, and there are several overlaps among other subproblems. Even though the theory of such positions is far from com­plete, the paper demonstrates that enough mathematics is now known to obtain provably correct, counterintuitive, solutions to some very difficult

Experiments in computer Go endgames
Martin Muller and Ralph Gasser, In Games of No Chance, pages 273-284. Cambridge University Press, 1996
Recently, the mathematical theory of games has been applied to late­stage Go endgames [Berlekamp and Wolfe 1994; Wolfe 1991]. Based upon this theory, we developed a tool to solve local Go endgames. We veri­fied all exact game values in [Wolfe 1991] and analyzed some more complex positions. We extended our method to calculate bounds for positions where optimal play depends on Ko. Our program Explorer uses this tool to play full board endgames. It plays a nontrivial class of endgame positions perfectly. In a last section we discuss heuristic play for a wider range of endgames.

Metaprogramming forced moves
Tristan Cazenave (Université Pierre et Marie Curie), Proceedings of the 13th European Conference on Artificial Intelligence (ECAI-98)
Knowledge about forced moves enables to select a small number of moves from the set of possible moves. It is very important in complex domains where search trees have a large branching factor. Knowing forced moves drastically cuts the search trees. We propose a language and a metaprogram to create automatically the knowledge about interesting and forced moves, only given the rules about the direct effects of the moves. We describe the successful application of this metaprogram to the game of Go. It creates rules that give complete sets of forced moves

Knowledge acquisition from game records
Takuya Kojima, Atsushi Yoshikawa NTT Communication Science Labs. Japan, 1998
A large amount of knowledge is considered very useful for systems playing such games as Go and Shogi (Japanese chess) which has a much larger search space than chess. Knowl­edge acquisition is therefore necessary for sys­tems playing these games. This paper ex­plains two approaches to acquire Go knowl­edge from game records: a deductive ap­proach and an evolutionary one. The for­mer is taken to acquire strict knowledge; sev­eral rules are acquired from a single training example. The latter is taken to acquire a large amount of heuristic knowledge from a large amount of training examples. Tsume­ Go problems are solved in order to compare the performance of the algorithm with others.

Generation of patterns with external conditions for the game of Go
Tristan Cazenave (Labo IA, Dept Informatique, Université Paris) Advances in Computer Games 9
Patterns databases are used to improve search in games. We have generated pattern databases for the game of Go. The generated patterns are associated to conditions external to the pattern. This enables the pattern to cover much more positions, but it leads to new problems for pattern generation. We explain how we have managed to solve these problems. We believe that patterns associated to external conditions can be useful in other games

Integration of different reasoning modes in a Go playing and learning system
Tristan Cazenave (Université Pierre et Marie Curie), Papers from the 1998 AAAI Spring Symposium, 1998
Integrating multiple reasoning mode is useful in complex domains like the game of Go. Go players use various forms of reasoning during a game. Reasoning at the tactical level is completely different from reasoning at the strategic level. Choosing a plan requires a different form of reasoning than knowing how to execute a plan. This paper gives examples of the integration of these reasoning modes into a single system. Rule­based reasoning, Constraint­based reasoning and Case­based reasoning are used in this hierarchical order. Constraint­based reasoning uses the results of Rule­based reasoning, and Case­based reasoning uses the results of Constraint­based reasoning and Rule­based reasoning.

Automatic acquisition of tactical Go rultes
Tristan Cazenave (Université Pierre et Marie Curie), Proceedings of the 3rd Game Programming Workshop, 1996
Gogol is a rule­based computer Go program. It uses a lot of reliable tactical rules. Tactical rules are rules about simple goals such as connecting and making an eye. Gogol uses a simplified game theory to represent the degree of achievement of the goals. The automatic acquisition of tactical rules follows a three step process : Pattern generation, Game evaluation, Generalisation. Gogol has metainformation about the correct use of the rules in global Go positions.
Intresting 1, The classification of learning algorithms, similarity based versus deductive.

Gogol (an analytic learning program)
Tristan Cazenave (Université Pierre et Marie Curie), Fost Cup 1997
A model of how Gogol works. (four pages of diagrams)

Spatial reasoning in the game of Go
Bruno Bouzy, LAFORIA­IBP, Université Paris, 1996
This paper addresses Spatial Reasoning in the game of Go. Combinatorial complexity of the game of Go obliges the Computer Go community to study spatial representations of human players that are complex. These representations contain the concepts of grouping and fractioning. Spatial Reasoning in Go is qualitative. It creates objects and relationships between them in order to qualify them. This description of Spatial Reasoning in Go is a positive contribution to the SR community.

Shared concepts between complex systems and the game of Go
Bruno Bouzy and Tristan Cazenave, LAFORIA­IBP, Université Pierre et Marie Curie, Paris, ????
We developed complex systems playing the game of Go using specific concepts and methods. Due to the inherent complexity and to the riches of the game of Go, some concepts can be shared with other complex domains. We present links with domains such as Economy, Social Sciences, War simulation, Linguistic, Biology and Earth Sciences. Links with Economy are based on investment and decision making. Links with Social Sciences deal with the relative importance of social agents. War simulation uses strategic concepts of Go. Go provides Linguistic with two ­dimensional representations. Biology and Computer Go deal with ontological problems. Earth Sciences and Computer Go give place to chaotic and complex behaviours.

On meta-game approaches to computer Go
Bruno Bouzy and Tristan Cazenave, LAFORIA­IBP, Université Pierre et Marie Curie, Paris, 1995
Meta­game approaches are studied through the design of the Go playing program INDIGO. Computer Go is a challenge for AI and the machine still remains weak compared to humans in the game of Go. This difference is used to try new technics as such as the Meta­ game technique discussed in this paper. A conceptual structure and a notion of Conway's game theory are described in order to show four approaches. Each approach is presented to show its method using games, its computational cost, its precision and its Meta­game's utilisation. This paper is an illustration of Meta through the game of Go.

Towards abstraction in Go knowledge representation
Bjorn Goldis, Research Paper for Dr. K. Cooper' s Advanced Artificial Intelligence CAP 6680, April 1999
Humans use synthesizing methods to understand positions globally and guide tactical maneuvering. Computer programs have traditionally employed search and pattern matching techniques to drive decision making, or rule application. The complexity of Go prevents this low-level, perceptually based approach; more human like reasoning is required. In this paper, we have seen some conventional techniques used, and illustrated the potential for a different kind of knowledge representation that attempts to encode high level cognitive functioning in a hybrid pattern/ algorithmic form of the influence map, adjusted for context. This adjustment substitutes for search and matching and provides a cognitive level knowledge representation from which prospective pattern generation could begin, according to evaluations of overall board balance and strategic concepts. We see the effect and importance of the cognitive arts' involvement in algorithmic design; Psychology can provide insight into new ways of looking at function design. In the next decades more research in cognition and perception, and other mental features such as memory usage by Go players may provide further tools for AI programming. In the meantime, some programmers have intuitively explored the area of cognitive interpretation and made programs that incorporate the spatial representation analogue of visual perception using set theory based notation. Both the experiment with the integration of cognitive knowledge into perceptual representation on influence maps and the spatial representation material have yet to incorporate analytical components into their models, yet the important point is that the realm of cognition as humans use it in the game of Go has begun in a way that never was required with Chess, relying as it can

The use of inferential information in remembering Go positions
Jay Burmeister and Janet Wiles, Departments of Computer Science and Psychology, The University of Queensland, Third Game Programming Workshop, Kanagawa, Japan, September 1996
Depending on the design of a memory experiment, it may be possible for subjects to make inferences from partly reconstructed responses which enable better performance than would be possible solely by memory. In explaining skilled chess memory perfor­mance, de Groot (1965; 1966) and Chase and Simon (1973a; 1973b) diminished the role played by inference, instead concentrating on perceptual and pattern recognition pro­cesses. In order to highlight the impact that inference may have on memory performance without the confound of the reliance on perceptual or pattern recognition processes, we tested our subjects episodic memory for sequences of Go moves and their ability to inferentially reconstruct the order of moves leading to a final Go position. Thus, we ex­amined the use of information made available by inference (inferential information) and by episodic memory (episodic information) in remembering Go positions. We report on two experiments in which the subjects had to indicate the order of play for the stones from the opening of Go games. In the first experiment, cued reconstruction was used whilst in the second experiment, unassisted reconstruction was used. There were two tasks in both experiments; in the episodic task the stones were presented sequentially every two seconds whilst in the inferential task no sequential information was provided. Thus, in the episodic tasks, both episodic and inferential information was available to the subjects whilst in the inferential tasks, inferential information was the main source of information available to the subjects. We discuss our results which confirm earlier findings regarding expertise by de Groot (1966) and Chase and Simon (1973a; 1973b) and compute an upper limit for the propor­tion of performance which may be due to the use of inferential information. We conclude that the use of inferential information may have a significant impact on memory perfor­mance.

Memory performaces of master Go players
Jay Burmeister, Yasuki Saito, Atsushi Yoshikawa and Janet Wiles, Schools of Information Technology and Psychology The University of Queensland, Australia Published, IJCAI workshop Using Games as an Experimental Testbed for AI Research, Nagoya, August 1997
Our overall goal is to study the use of informa­tion by Go players and the structure of their Go knowledge. In particular, in this paper we focus on human memory, and conclude with a discussion of the benefits of modelling human memory to AI and Go programs. We report on two memory experiments. The first experiment used Japanese Go players to replicate earlier studies on Australian Go play­ers. The second experiment consists of three case studies of master Go players (6 to 8 dan amateurs). The general task in the experiments was to re­construct Go positions stone by stone in cor­rect game order. Two separate tasks were per­ formed: in the episodic task, the moves from a Go game were shown to the subjects in a se­quential presentation; in the inferential task, the subjects had to reconstruct Go positions with no information about how the game was played. In both tasks, feedback was provided after placement of each stone. The first experiment replicated previous results for the experienced and beginner subjects. The case studies showed that extremely high levels of memory performance by the master subjects extended even to very fast presentation rates.

Complex games lab workshop
Article 1, Move Evaluation Tree System
Hiroto Yoshii
This paper discloses a system that evaluates moves in Go. The system—Move Evaluation Tree System (METS)—introduces a tree architecture algorithm, which is a popular algorithm in the field of pattern recognition. Using the METS algorithm, we can get emergency values of every empty position at any situation of the game. The experiment using a large database shows that the METS algorithm has a great ability to recognize a configuration of stones and evaluate the significance of empty positions.

Article 2, Memory-Based Approach in Go-program "KATSUNARI"
Shinichi Sei, Toshiaki Kawashima
To make a strong Go-program, programmers analyze the thinking process of expert players and devise some algorithms to make good moves based on the result. However, such work is very difficult and there isn't a strong Go-program. We had proposed a new method which makes good move by using a large quantity of pattern knowledge extracted from professional players' games. And we had developed a Go-program "KATSUNARI" which included the method. Because our method can make good moves by using pattern knowledge directly, we don't need di.cult work of usual way. To make KATSUNARI stronger, we are improving mainly its database which has pattern knowledge. We classied pattern knowledge into two categories: the knowledge which show basic skill and the knowledge difficult to understand validity. Examples of former knowledge are pattern of JOSEKI and pattern of local competition and examples of latter knowledge are professional players' moves. We made two types of databases which included each knowledge. By using these databases properly, KATSUNARI can make good moves under any board situation than before. In this paper, we describe about new databases of KATSUNARI and how KATSUNARI uses them.

Article 3, Zero Sum Games As Distributed Cognitive Systems
Robert L. West, Department of Psychology, University of Hong Kong
In the case of two individuals in a competitive situation, or “game,” the game itself (i.e. the players, the rules, the equipment) can be considered to constitute a distributed cognitive system. However, the dominant model of competitive behavior is game theory (VonNeumann & Morgenstern, 1944), which has traditionally treated individuals as isolated units of cognition. By simulating game playing with neural networks, and also by using human subjects, it is demonstrated that the interaction between two players can give rise to emergent properties which are not inherent in the individual players.

Review computer Go 1984 - 2000
Martin Müller, Department of computer siences at the University of Alberta, 2000
The main breakthroughs within computer go are made for specialized problems, like endgame and restricted live and dead problems, not for complete game programs. The main different stages in computer Go programs for the last 10-15 years : The main challanges that Martin Müller point out are :
Computer Go
Martin Muller, NTT Communication Science Laboratories, Atsugi, Japan 2000
The introduction briefly describes the rules of the game, and the history of computer Go. Section 2 gives an overview of the current state of the art, and discusses the many challenges posed by this research domain. Section 3 surveys the different kinds of knowledge built into a heuristic Go program. Applications of minimax game tree search in Go are described in Section 4, and Section 5 discusses subproblems of the game for which specific solution techniques have been developed. The final Section 6 poses challenge problems for further research in the field. A glossary contains brief definitions for technical terms that are marked by a star in the text, as in: komi*. There is an extensive but by no means exhaustive bibliography.

Learning a Go heuristic with Tilde
Jan Ramon, Tom Francis, Hendrik Blockeel, Department of Computer Science, Katholieke Universiteit Leuven, Belgium, 2000
In Go, an important factor that hinders search is the large branching factor, even in local problems. Human players are strong at recognizing frequently occurring shapes and vital points. This allows them to select the most promising moves and to prune the search tree. In this paper we argue that many of these shapes can be represented as relational con­cepts. We present an application of the relational learner Tilde in which we learn a heuristic that gives values to candidate­moves in tsume­go (life and death) problems. Such a heuristic can be used to limit the number of evaluated moves. Even if all moves are evaluated, alpha­beta search can be sped up considerably when the candidate­moves are approximately ordered from good to bad. We validate our approach with experiments.

Evolving Neural Networks to Play Go
Norman Richards, David E. Moriarty, and Risto Miikkulainen, The University of Texas at Austin
Go is a difficult game for computers to master, and the best go programs are still weaker than the average human player. Since the traditional game playing techniques have proven inadequate, new approaches to computer go need to be studied. This paper presents a new approach to learning to play go. The SANE (Symbiotic, Adaptive Neuro­Evolution) method was used to evolve networks capable of playing go on small boards with no pre­programmed go knowledge. On a 9 x 9 go board, networks that were able to defeat a simple computer opponent were evolved within a few hundred generations. Most significantly, the networks exhibited several aspects of general go playing, which suggests the approach could scale up

In Coevolution: Turning Adaptive Algorithms upon Themselves,
Alex Lubberts, Department of Computer Science, Twente University, Enschede, The Netherlands, 2001
When evolving a game­playing neural network, fitness is usually measured by playing against existing opponents. In this article that need is overcome by applying the competitive co­ evolutionary techniques of competitive fitness sharing, shared sampling and hall of fame to the SANE neuro­evolution method. This approach is tested by evolving networks to play go on small boards. Networks evolved through co­evolution were compared against those evolved against the gnugo program. The co­evolutionary techniques were found to speed up the evolution and to res­ult in better networks not limited by the quality of the opponent.

The indigo program
Bruno Bouzy, LAFORIA­IBP, Université Pierre et Marie Curie, Paris, 1995
Between 1991 and 1994, we built a cognitive model of the human Go player. This work is related in [Bouzy 1995]. We tested the validity of the cognitive model on a computer. In this meaning, our model is computational. We developed a Go playing software named INDIGO. This program aims to play full Go games as well as possible. We already gave a one hundred pages description of INDIGO in our french thesis dissertation. The aim of this paper is now to give a ten pages description of this program. In the first part we describe INDIGO. In particular, we show how an interaction model between groups is useful to static evaluation of life and death of not fully cercled groups. Also, we show how fuzzy mathematical morphology is useful to static evaluation of territories. In the second part, before conclusion, we show the results and we discuss about strong and weak points of our approach.

There are no winning moves except the last
Bruno Bouzy, LAFORIA­IBP, Université Pierre et Marie Curie, Paris, 1996
Our work dealt with the Go 1 game that has many chaotic features. During our thesis [Bouzy 1995] on Cognitive Modelling of the human Go player, we developped, in 1992 and 1993, a Go playing program : INDIGO 2 . It is ranked on the international Computer Go Ladder [Petersen 1994]. We have already shown that fuzzy sets are useful to model "territories" and "influences" in Go [Bouzy 1995c]. In this paper, we want to shed light on links between Computer Go and Uncertainty Management with fuzzy methods.
The nature of this paper is prospective. It suggests an Uncertainty Management in INDIGO with numeric methods and fuzzy functions. It will screen the chaotic behaviour of Go positions and could then increase the INDIGO's level in the next release.
To do so, part 2 shows related work in Computer Go and introduces the INDIGO program. Part 3 explains main weaknesses of INDIGO and states the problems to be solved. Part 4 shows that some fuzzy methods can be applied to quiet Go positions and that chaotic positions are very difficult to handle without lookahead. Before conclusion, part 5 explains that fuzzy functions screen chaos of unstable positions and therefore are useful to the global move decision process.

Incremental updating of objects in Indigo
Bruno Bouzy, LAFORIA­IBP, Université Pierre et Marie Curie, Paris, 1996
This paper shows the incremental updating that is used in the Go playing program Indigo. Due to the size of the board and time constraints, incremental mechanisms are relevant to update data. The evaluation of a position includes the construction of a taxonomy of objects which are linked by a lot dependencies. Therefore, classical incremental approaches use browsing of the taxonomy to udate objects. In Indigo, we use a different approach that use the spatial features of the game of Go. Each object is a "relying object" with a "location" and a "track". The later is the set of intersections on which the object depends. When a move is played somewhere on the board, browsing of dependencies is not necessary and "tracks" are used instead. The objects whose track meets the location of the move are deleted and the other ones are not. This mechanism symplifies the task of the programmer in pushing the incrementality problem into the specification of the track of each class of objects. This mechanism slightly reduces the response time of Indigo by a ratio of 50 on 19x19 boards without modifying the play of the program.

Computer Go: an AI Oriented Survey
Bruno Bouzy, LAFORIA­IBP, Université Pierre et Marie Curie, Paris, 1996
Since the beginning of AI, mind games have been studied as relevant application fields. Nowadays, some programs are better than human players in most classical games. Their results highlight the efficiency of AI methods that are now quite standard. Such methods are very useful to Go programs, but they do not enable a strong Go program to be built. The problems related to Computer Go require new AI problem solving methods. Given the great number of problems and the diversity of possible solutions, Computer Go is an attractive research domain for AI. Prospective methods of programming the game of Go will probably be of interest in other domains as well. The goal of this paper is to present Computer Go by showing the links between existing studies on Computer Go and different AI related domains: evaluation function, heuristic search, machine learning, automatic knowledge generation, mathematical morphology and cognitive science. In addition, this paper describes both the practical aspects of Go programming, such as program optimization, and various theoretical aspects such as combinatorial game theory, mathematical morphology, and Monte­ Carlo methods.

Management of uncertainty in combinatorial game theory
Tristan Cazenave (Université Pierre et Marie Curie), ????
We describe a method to handle uncertainty in combinatorial game theory. This method has been implemented in Gogol, a general game playing system mainly applied to the game of Go. In complex games such as Go, a search intensive approach is intractable. Gogol uses a lot of knowledge and little search. This knowledge is represented using combinatorial game theory. We have adapted this theory to take into account the uncertainty due to the intractability of search in complex games. The system uses its evaluation of the game to choose a strategy. This strategy is applied by handling the uncertainty resulting from incomplete tree searches.