Playing GO with a Artificial Neural Net Simulater

For the subject An introduction to biological computer science

Nicolas Goell nic-goell@magnet.at

Brigitte Kendlbacher brigitte.kendlbacher@gmx.at

Roland Knall roland.knall@gmx.net

Mark Rehbichler mark-rehbichler@magnet.at

DI Mag. Roland Schwaiger^{1} rschwaig@cosy.sbg.ac.at

Version: 19th of march Uhrzeit: 04:00pm

1project coordinator and supervisor

Contents

1

Abstract

GO is a common used application for Artificial Neural Networks. This paper takes a look on the theoretical side, and shows up a realization using netJEN.

Chapter 1

Introduction

In this chapter we will give a short overview about GO, and what kind of work has already be done. It exists in main parts as a summary of [?].

1.1 Playing GO - Basics

For a computer GO is really hard to learn, and the best networks are still weaker as an average human player. There exists a number of reasons for this, just too name a few: the games is pattern oriented, the branching factor is prohibitively large and there are multiple interacting goals. Probably evolving new methods and networks can solve these ( and many other problems connected to this subject ) problems.

1.1.1 GO, the original game

Although the word GO is taken from the Japanese word for the game, it seems to be coming from China about 3000 years ago. It is a simple board based strategy games, but is appears simple in comparison to chess or similair board-strategy games. The main goal is to reach more points than your opponennt. To do so, you can playe stones, black or white, on a square rid with 19 intersections across. Two players, black and white, place alternate on stone of their respective colors on an intersection. The games end when both players pass or no more space for placing stones is left. It is very easy to even the opponent levels. If a player has more experience, he allows his oppenent a number of free moves. You say he ranks x stones higher. ( x is the number of allowed free stones )

How to gain points

Each player tries to catch stones of the opponent. To do so, he has to place them around the opponent stones. If stones got ”captured” in such way, they are removed from the board. At the end of the game the remaining stones are counted. In a normal even game, white can add 5.5 points, offsetting the fact of black’s first move. The player with the highest score wins.

1.1.2 Computers and GO

Although the rule set is relatively simple, computers are still not able to play against good players and win. A game of GO can be divided into three general phases: the opening, the midgame and the endgame. Computer’s success in each of this stages varies and we have to take a deeper look in what can and what can not be achieved with computational methods.

The Opening

The opening game is referred to as the fuseki. Specified combinations of stones in the beginning are referred to as joseki. Good GO programms contain databases with 5000 to 50000 moves, and they have no difficults to play a good beginning with them. But because evolving a good strategy is still a bigger goal, improvements were not made yet in this stage of the game.

The Midgame

This stage of a game contains the bigger problems for computer. Because of the sheer size of a average board (19x19), between 200 to 300 moves are possible on a first sight in a typical midgame position. Therefore brute force searching would result in much too big trees. Techniques which are used contain pattern libraries, tactical analysis and rule-based expert systems. The system first evaluates candidate moves, using one or some of the named techniques and analysis them. There are several problems with the current midgame techniques. They tend to be difficult to apply and error-prone, and because most of them are static, it is difficult to achieve general play and advance must be made by a human.

The Endgame

The endgame of GO is simplier for computers, but normally there are less points to achieve. The board is full, patterns are set and positions taken. Although computers play very well in this stage, they achieve less points compared to what could be taken out of the midgame. So the most important and difficult part of playing GO is in the midgame where the traditional techniques are the weakest.

1.2 Neural Networks and Go

The main factor, that is holding back computer GO programs, is the largely pattern oriented game strategies that need to be incorporated for successfully playing GO. As neural networks are known to be exceptionally good at pattern transformation tasks, employing this relatively new technique seems like a very promising approach.

1.2.1 SANE

SANE (Symbiotic Adaptive Neuro-Evolution) is a specific form of neural network that does not depend on backpropagation as training method which cannot be effectively applied on the intended purpose. It maintains a large pool of neurons, structured as a classic three-layer feedforward network, and additionally a population of blueprints which can be thought of as a selection of neurons specifying an individual neural network. This ensures the evolution of a wide variety of assemblages to compensate for the rather long evaluation intervals. A neuron’s activation is defined by the transfer function σ(x) = \frac{1}{1+e^{−x}}. During the process of evolution SANE evaluates each blueprint’s performance and calculates a fitness value for every neuron in the pool based on the performance of the networks in which it participates. In the so called reproduction phase, the top 25% in the neuron pool and top 15% in the blueprint population are randomly mated making use of a onepoint crossover procedure to obtain new individuals replacing the least fittest ones. On the blueprint level, each link to a breeding neuron is altered to its offspring with a 50% probability. Additionally a conservative mutaion rate of 1% is applied to both populations.

1.2.2 Applying SANE to Go

SANE evolves common three-layer feed-forward networks with input layers of two units (Boolean value) and output layers of only one unit (float value) per board position. Positive output results indicate good and negative results bad moves. The neurones generated are 312 bits long and represent a set of 12 weights. Each generation 200 networks were formed with a mutation rate of 0.1% and 25-30% of the population allowed to breed, which has given good results during experimentation. It showed to be rather difficult to determine the end of a game, to remove dead stones and to check for repetition of entire board positions. Solutions for all these problems were found. An upper bound was placed on the number of moves in order to ban excessively long games. The fitness level for the networks was produced by summing the difference in score between SANE and its opponent over a certain number of games.

1.2.3 Results

SANE was tested with board sizes of 5x5, 7x7 and 9x9, where it was able to beat its opponent program wally after an acceptable number of generations. Larger boards could not be tested due to lack of CPU power. Several experiments showed, that SANE managed to beat deterministic opponents very rapidly, whereas it did not learn to play against more randomly acting players. When trained with a more non-deterministic wally the network developed tricks instead of only being able to win against only one certain player. In order to train the networks at a higher level the GO handicapping mechanism was used to simulate stronger opponents.

1.2.4 Strategies Evolved

An interesting question is, what kind of strategies did the networks evolve because they start with no prior knowledge on how to play the game. Important for the network is the training partner, who is the only source of information for the network. A network with only one specific training partner can work out strategies to take advantage of the opponents weakness. For that reason it is better to use a variety of opponents. The networks outputs are random at the beginning but after a few generations they start to make simple living groups. The evolution system discovered good GO playing strategies without prior knowledge entirely on its own, based on what moves led to wins and losses

1.2.5 Future Work

Future Work will focus on scaling up to larger boards. In the future they plan to play on any board size because now the networks can only play on the board on which they were developed. There are two possibilities to solve this problem:

1. to design a representation that is independent of board size

2. to work out solutions that only consider a portion of the board at a time, but by this method the result is a weaker play.

3. enhancing the network architecture.

There are several ways to make the architecture more effective, including preprogrammed feature detectors and hierarchies of networks. The networks are forced to discover useful features themselves because they are not given any prior knowledge about what features are relevant to playing GO. A pre-defined feature space instead of looking at the raw board might make the assignment easier and might allow the network to learn faster and deal with more complex patterns. and evolving against stronger opponents. A variety of stronger opponents is necessary to achieve truly high levels of play. The stronger player can be simulated by using handicaps but handicap games alone are not enough. A problem is that strong opponents tend to take longer to generate moves than weaker programs. In future it would be necessary to work out networks against human players. This way perhaps GO-playing could finally be evolved that were able to compete with the best humans. New techniques based on pattern recognition and learning like SANE will be required to build GO programs that would be competitive at high levels of play because the traditional methods have been insufficient.

1.3 Former Project: Neural Networks playing GO [?]

We want to take some conlusions over the given work. During preparation for our work, we took a look on given papers and programs. During this collection of facts, we found some points we have to criticize and others we want to take over. A first paper was already summarized in the introduction, so we will give only some short statements for the next one.

1.3.1 Discussing the paper

This group used for their work (see [?]), SNNS and one-hidden layer feed forward nets. One the one side, they only used standard Artificial Neural Networks ( in further shorted with ANN), so they did not implemented an evolution, which improves, in general, the output of the program (see ??).

• The number of input units was far too large for the given situation.

• The number of neurons in the hidden layer seemed to be less than necessary.

• The hidden layer was fully connected to both the input and the output layer.

• The use of only one hidden layer complicates implementations of feedback algorithms.

• A variable system, which can be evolved, is more able to adapt the complex strategies of GO.

• Go is far too complex. So you should use more than the given training patterns.

1.4 Improvements over the given papers

We also found some things, we would improve in further work. This relates not only to [?] but also to the named paper [?] above.

The number of input units In [?] the number of input units was far too large, but this problem occured also in [?]. With a better coding of the given board situation, the number of input nodes could be reduced, and so the complexity of the net.

Hidden Layers Improvements can be made by using more layers in combination with more neurons. Also a feedback between neurons in hidden layers, could result in better performance. Both dicussed papers used only on hidden layer, with many ([?]) or, relied to the complexity of the subject too few ([?]) nodes in the hidden layer.

The hidden layer was fully connected to both the input and the output layer. One paper ([?]) used SANE for keeping the number of connections low. The other ([?]) connected every node in the hidden layer with each of both the input and the output layer. Using a evolution algorithm such as SANE (see ??), the number of connections between I/O Layers and the hidden layer structure can be optimized.

Number of training patterns Strategics used for GO are, on the one side pattern oriented, on the other side tricky. Therefore to train a ANN s with games, you should use a large number of training patterns. But you have to keep in mind, that training costs time. Therefore you will have to evaluate the best combination of training patterns and computation time.

Appendix A

Report of Meetings

1st Meeting

Date: 13th March 1999 Place: Institute for ComputerScience Room 2.30 Persons: Nicolas Goell, Mark Rehbichler, Roland Knall, Roland Schwaiger Discussion: Our assisting project controller came up with some past work on our subject.

He came up with a paper, which will be included in this one, in a shorter version (see ??). Also we defined a modus operandi for the term, discussing the sections, in which this paper will be divided. We also talked about the basic materials for this seminar, which can be found online.

2st Meeting

Date: 20th March 1999 Place: Institute for ComputerScience Room 2.30 Persons: Nicolas Goell, Mark Rehbichler, Roland Knall, Roland Schwaiger, Brigitte Kendl-

bacher Discussion: We discussed the paper, we had to summarize. We talked about the pro’s

and con’s of solving the problem with SANE, and what SANE in general is. We also sorted out some problems which could be improved during this work.

• Only one hidden layer is used.

• Nodes in the hidden layer can only connect to nodes from either the input or output layer. No information flows between nodes in the hidden layer.

• The number of neurons in the input and output layer is big. We also dicussed solutions for this problem, including the following: • Changing the possibilities for nodes to connect to other nodes.

• Evaluation of the “blueprints”

• General changes could be done to the input and output layer. We also talked about the realization of ANN s with NetJen. And the differents between the solution using SANE and a solution using NetJen.