Breeding Software to Play the Game of Go

Jeffrey Greenberg

 Table of Contents

Overview

Genetic Programming Overview

How Software is Bred

These Efforts

Genetic Programming Applied to Go

First Efforts

The Programming Language

The Fitness Function

Results

Analysis

Board Search Space Size

Expression Tree Search Space Size

Genetic Programming Permutations for Go

Appendix

Genetic Program Class Structure

 

Overview

The overall goal of this effort is to breed software for a complex problem. In this case, the game of Go was selected because it’s state space is so large (much larger than chess for example) that it approaches the complexity of real world problems, and yet it is somewhat simpler than, say, breeding software that would result in a full-blown commercial word-processor. What would be of interest is whether the bred software would play well enough that one could say, "the software bred ‘strategies’ for a complex game". To say this would mean that the technology involved would be capable of solving a larger class of problems with little assistance from programmers and other experts. Calling this a form of self-hatred might not be inaccurate.

Most approaches to complex problems, including Go, require the encoding an experts knowledge or the construction of a model of the experts knowledge. For example, there is an explicit part of the code that might discover what strategy to take based on a set of pre-fixed strategies and pre-fixed weightings of their worth and applicability. Usually these weightings do not cover all circumstances well, and when such a mismatch occurs the program can lose. This then outlines the contrary approach used here: letting the program discover patterns and relationships at a much more atomic level, so that a more fluid and comprehensive solution can be found.

Genetic Programming Overview

Genetic Programming is based on the idea that because evolution is seemingly effective at creating complex individuals, individuals much more complicated and effective than the current computer technology, that by simulating the process on a computer, one might arrive at equally effective solutions to large and complex problems. This simulation of evolutionary genetics is generally referred to as Genetic Algorithms.(cf Holland, 1975(x)). It occurred to many individuals that the metaphorical DNA that was being evolved could just as well be software as anything else, and the technology for working with "large" populations has become more widely available.

How Software is Bred

The process is relatively simple and essentially boils down to this. Take a population of, say, one thousand monkeys banging on a thousand computer terminals. Each of the thousand programs is then compiled, and those that do compile are then run, and out of those that run without crashing, the answer they return is evaluated, and those that actually give an answer closest to the correct answer are given the highest value. And for each program, they are rated by how close they come to the correct score. Then take two of the best programs, and randomly interlace them with each other and randomly scribble in parts of it. And repeat the process. In the end, as incredible as it may seem, you will have a program that does the job.

Now the academic process of investigating Genetic Programming amounts to exploring the various ways this process can be made more efficient. For example, the code might be generated in such a way that no matter how you put it together or cut it up and mix it, it will still be syntactically correct. One such method has been popularized by John Koza(x).

Other optimizations have been worked on such as the automatic creation of subroutines, such that code is more space efficient.() Others have explored languages that have only one data type or that are capable of supporting efficiently many data types() so that certain problems can be more effectively solved. Others have sought to parameterize the amount of code needed to solve a problem of a certain complexity; or how big the population must be, or for how many generations one must breed before a solution can be reasonably expected. Still other efforts have gone to improving the the generality of fitness algorithms.

These Efforts

My efforts have been to illuminate the effectiveness of Genetic Programming in generating complex software. The test bed is the game of Go, which while not as difficult as writing a piece of commercial software, remains an unsolved problem of immense richness and depth, and would help uncover the limitations and help to enumerate some of the requirements for solving large problems.

Genetic Programming Applied to Go

A Genetic Programming platform is developed and put to the task of playing the game of Go. The platform can control a number of parameters: the population size, the problem being solved, the function that will describe the programming language, the fitness function, the rate and type of crossover and mutation, selection parameters for mating individuals.

First Efforts

The Genetic Programming Engine

A genetic programming engine has been developed in C++ and runs under AIX UNIX and under Windows NT. It is general purpose and can be specialized to solve a particular problem. The engine can save & load individual members of the population for reuse. Some months were spent verifying the results.

The Programming Language

The technique requires a set of functions that comprise the code. The functions are only

IfPointAt( x, y, z)

where each of x, y & z are composed of this triple: a board position, the points color (black, white, empty), and the proscribed action (move, pass or resign). The function then checks the current board to see if there is a point at the given position, and if so moves to y else z. Note that x, y & z can be functions that return a point so that IfPointAt can call IfPointAt on an on.

Note also that each point is in absolute, not relative coordinates.

Note that all the program knows about go is that it is played on a board and that all moves are played on the board, as opposed to off the board. Therefore, the nothing prevents the program from moving on top of another point, suiciding, failing to capture dead stones, etc. -- in short it knows nothing about Go. Since it knows nothing, it is up to the fitness function to weed-out the ‘wrong’ individuals.

The Fitness Function

The technique requires a fitness function to evaluate each individual. To choose the fitness function, we investigated the following techniques. 1. Have each individual play a complete game.The fitness function assigns a value to each individual program as follows: each individual is given In this case, the games of masters were choosen.

The Mutation Function

Three types of mutations were utilized: mutation of constants, functions, expression-tree.

Constants

Constants were mutated completely at random at first. However this resulted in points that were off the board or which were of an unsupported color, etc. This would be fine if the language could usefully support such information, but it did not. Moreover, the idea that a point could be off the board clearly affects the entire program and breeding effort -- one would have to breed out such points, so that an optimization based on expert knowledge was introduced: Don’t create points off the board. Breaking the rule of "no expert knowledge" because of necessity presaged changes that were to come. So constant mutation was modified to only result in on board func.

Functions

Since there is only one function, it was only possible for a function to mutate into a constant (ie. a point on the board) and vice-versa.

Expression Tree

An expression sub-tree could be clipped from the larger tree and attached at another point, thus altering the overall expression. This tends to shrink the tree, reducing the overall complexity.

Process

The engine was given a set of boards with a known masters move for which it attempted to breed a tree that would match the board and supply that answer. One member of the population that had done this the most successfully was taken and the human players move fed to it. The answer returned was taken to be the move.

Results

The results were that the program was very poor at breeding individuals that could match. And when it did, the individual would often resign after but a few moves. Why was this occuring? To answer that we must look at the complexity of the problem.

Board Search Space Size

Total number of unique arrangements of k stones of c colors on board of size d

So for a 19x19 board with two color stones:

So with 20 stones on the board:

for a 9x9 board

While this decreases the arrangement count by a massive 12 orders of magnitude the amount is still large.

Note that numbers would be smaller than this for real games since the formula above does not take into account the fact that the number of stones of each color is near equal, and rotations of identical positions is not accounted for here. Still the numbers for likely games is quite large.

Expression Tree Search Space Size

The expression tree generated by the genetic program is one from the total set of possible programs. How many possible programs can be generated by the genetic program?

If we assume that the expression tree is evenly balanced, then we can calculate the number of nodes in the tree this way: Assuming the average number of branches of each node is b and n is the depth of the tree, then the number of nodes in the tree is:

Total nodes in tree = 
Notice a power series relation.

The final nodes, where n is at the limit, are terminal nodes. All the nodes above that, where n is less than the limit, can have a function from a set of f functions

Permutations for all but terminal nodes =

where f is the number of functions that can occur at each node.

Now the number of terminals in the tree in an evenly balanced tree of depth n is:

Number of terminal nodes = 

So that the total number of permutations in the tree would be:

Total Tree Permutations = Permutations for all terminal nodes * Permutations of terminal nodes

or

Total Tree Expression Permutations = 

where V is possible values of each terminal.

For our case, V is 19*19*c*a, where c is one of {empty, black, white} and a is one of {move, pass, resign}, thus V=19*19*3*3=3249. B is 3, f is 1, and for a tree of 3 the value is:

Total Tree Expression Permutations = =(1+3+9)*(27*3249)=1,140,399

Genetic Programming Permutations for Go

Now the total permutations in the Genetic program for go would be:

 Next try

So what do we do next?

1. Given that

each chromosome must be small so that it can evolve in a short enough time, assume:

a. each chrome can only handle a small piece of the problem.

1. There is at least one way to divide the problem into pieces and have a program that will win against strong players.

b. the problem is composed of many chromosomes

2. There is a library of games. The library could be used as follows:

a. to create pattern, move pairs.

These patterns would have to be evolved to find the minimal set.

What a pattern, move pair be useful for:

a. For every square on the board, there would be a pattern. Ideally, only one pattern would match a given board, and the corresponding move could be taken. Note that the pattern would include the move number.

1. This would require a library that had every possible move: 19*19.

2.

b. games that pro's play

 

3. There is an program that could be made to automatically play the program.

 

 

 

Appendix

 

Genetic Program Class Structure