Hosted by Inventivity
Commented Papers on Go Programming
Edited by Jeffrey Greenberg
copyright 2001-2009 Jeffrey Greenberg Papers last updated Dec. 7 1998. (Send me papers! Let me know if links change! )
Page last published July 24, 2001Available at this site:
Paper Comments
AdversarialPlanningComplexDomain-Willmott.ps.zip
AdversarialPlanninginGoThesis-Willmott.ps.zip
thesis too large for my site
Excellent paper based on the assumption that Go can be broken down into a heirachical tree of goals and sub-goals. This is an MS thesis work which just begins to examine this.  He was able to get good results against a set of beginning Go problems.  No one has proven this won't work.  It requires expert knowledge to create the goal oriented knowledge.  There is the thesis and a summary paper with his advisor.  This sort of general approach could provide the framework for adding further knowledge to a program in the form of goals and methods; these could be hand-entered as they are here or synthesized.
AutoAcqTacticalGoRules-Cazenave.ps.zip
AutoOrderingPredicatesMetarules-Cazenave.ps.zip
ConstraintBasedExplanation-Nigro.ps.zip
SelfFuzzyLearning-Cazenave.ps.zip
Cazenave has been examining methods to automatically acquire knowledge.  In these papers he describes variants of genetic or evolutionary computing techniques that evolve sets of patterns.  This is quite close to the spirit of my work.  The particular mechanisms here are quite specific to Go. 
RE: Automatic Acquisition of Tacticcal Go Rules: Interesting. Uses a matrix representation of  rules for GA manipulation… Further goes through effort and rule representation is good enough to conveniently support condensing of rules (i.e. removing of redundant or equivalent rules) and generalizing rules (i.e. the combining of sub-rules into more general ones). Calculates the specificity of a rule i.e how many exact and variable matches are needed for a pattern to match. Uses a constant cutoff to throw away rules that are too specific to be of use. Iterates  each point in the matrix (not really a GA ??) to find a "rule" to test. Lots of expert knowledge needed to evaluate a rule… Each pattern describes 4 goals: 1. Whether a group can become an eye, 2 have an eye removed, connect some stone, disconnect some stones; and whether this can be accomplished 1 no matter what the opponent does, 2 if player goes first or if it fails if the opponent goes first, 3 is impossible, 4. Cannot be achieved if player goes first but is achieved if the opponent goes first. These latter for correspond to the outcomes specified by Berlekamp, et.al.
EvolutionaryAlgorithmExtended-Kojima.ps.zip
FlexAcqGoKnoledge-Kojima.ps.zip
An idiosyncratic (non-language based) means to evolve Go software.
EvolvingNNforGo-RIchards.ps.zip Using genetic methods to evolve a neural network to play Go.  Beat wally.
ExploratoryLearningInGo-Pell.ps.zip
EyespaceValuesInGo-Landman.ps.zip
GoTools-Wolf.ps.zip
GoToolsOpenPos-Wolf.ps.zipA
Landman extends some of the Elwyn Berlekamp and Thomas Wolfe work on Mathematical Go.  Wolf describes GoTools which is based on same.
Golem.ps.zip,  H Enderton Neural network plus expert knowledge intermixed. NN to train a move generator in alpha-beta search.
GomokuThreatSpaceSearch-Allis.ps.zip Allis has created a number of interesting seach extensions including proof number search.  In this one, he uses the possible threats as a way to reduce the search space.  He does this for Gomoku however, not Go...  So it may not apply. 
The link (cf. http://www.cs.vu.nl/~victor/thesis.html) will describe proof number search, which is an alpha-beta variant.
LearningPredictMethodsTemporalDiff-Sutton.ps.zip
PlayingItSafe-Muller.ps.zip An excellent paper that extends and details Benson's algorithm.
KnowledgeRep-Fotland.txt.zip
fotland.txt.zip
MFGO92Doc-Fotland.txt.zip
A detailed and excellent description of data structures in a sophisticated Go program -- especially with regard to pattern search.  Unfortunately not a detailed picture of the design of such a program. 
Second paper on design considerations. 
Third is on MFGO and predecessor programs.  Details data structures and types of processing, including some of the algorithms, the programs do.
go++.txt.zip
goahead.txt.zip
Very limited information on Michael Reiss's Go++ which also goes under different commercial names. 

Go Ahead is written in Basic! I understand.

RiscIgo-Wilcox.txt.zip  A detailed and excellent description of another expert go program.  Details on pattern search with comparison to Fotland's approach.  More information on software design.
CoevolvingStrategiesForGo-Rosin.ps.zip This thesis is very much like my own work on GP and Go; it interests me in that we are following quite similar ideas: he's tried some variations I've had in mind for building up a Go program from base knowledge. Good stuff.  Instead of starting with a individual composed of IfThenElse statements and occupancy rules and using a tree-form with standard mutation & crossover operators as mine does, Rosin  defines an individual as an array of such rules. An individual is run by matching the rules in order operating on a board.  The board is then checked to see if a point has been marked; if so, the first such one is played, else the side passes.  Rules operate with locality (3x3grid)  (like Cazenave).  Mutation modifies: bits in the matching grid; Crossover 'cuts' on rules.  This turns out to be enough to beat Wally.  He then goes on to add more expert knowledge: absolute position to points (not just relative to the matching grid), search for ladders, string information (liberty counts, etc); and more general knowledge: rules can be added, deleted, swapped.  This turns out to be enough to beat Explorer.  Q: has he done enough with the 'rule' operators that such that one could say this is the method for handling rule-based schemes in general?  (None of this is formalized into theory in this work.)

OpenGo - Go Programming Environment. 
Architecture of a Go Programming Environment-Greenberg

Programming Go by Breeding Software - Greenberg
 
 
 
 

An software environment to facilitate developing Go programs (by editor of this list! 8-) )
 

Describes using Genetic Programming to evolve a Go Program.  It becomes clear that the technology on it's own is not sufficient i.e. evolving something "smart" from the most minimal of knowledge is highly unlikely to succeed.  Additional help must be involved in order to succeed.
Calculates the complexity of using raw GP with Go.

Available Elsewhere:
Monte Carlo Go, Brügmann B., 1993 Very interesting technique.  Related to randomness used in GP.  Applies only to 9x9 boards but does not converge rapidly enough for larger boards.  Worth looking at.
The Integration of A Priori Knowledge into a Go Playing Neural Network, Markus Enzenberger Scheme for using Neural Nets to play Go. Describes NeuroGo
Go and Genetic Programming, Playing Go with Filter Functions, Stephan F. da Silva's 
ftp://ftp.wi.LeidenUniv.nl/pub/CS/MScTheses/dasilva96.ps.gz 
gopaper.tex.zip  -- supplementary note
M.Sc. thesis.  GP to find eval function for an alpha-beta search. Unable to beat Wally. Uses public domain lilgp 1.0. Too slow to actually do alpha beta.. Failure?
An Architecture for Computer Go, David Mechner and Tim Klinger http://cns.nyu.edu/~mechner/compgo/ In process Go program organized around expert rules and search. It generates a complex state about the game in a database of sorts ("knowledge-base").  The program then will presumably query against this data-base in some way...? Also available is source code for a "revertable object" encapsulating saving and recovering state of objects.
Score completed games , shape library, game tree searching techniques, Dave Dyer Reports and descriptions on various search techniques. Overview of search strategies.