Computer Go Algorithms

Table of contents Page purpose Connecting to a Server Score/Influence/Territory/Moyo Estimation Known Algorithms Discussion See Also Connections Known Algorithms Discussion Life and Death, Eye Counting, and Eye Classification Known Algorithms Discussion Pattern Matching Known Algorithms Discussion Strings/Groups Known Algorithms Discussion Center vs Edge Heuristic Known Algorithms Discussion Reducing the Scope of Move Searches Known Algorithms Discussion Other Algorithms Known Algorithms Discussion

Page purpose

jhouse: At the time that I created this page, I was trying to code a go AI and hadn't found a reference that I consider satisfactory for collecting the various algorithms (good and bad) that can be used for a go AI. This page was intended to fill this need.

jhouse: In light of others having issues, I think it's best to shift this page's focus slightly. Besides algorithms, there are other computer go design issues that also pop up. I want to expand this page to cover that.

For each category of algorithms, I hope to provide a comprehensive listing of implementation options along with a discussion of the trade-offs of each approach. I don't know the best way to insert the discussions without excessive clutter of the page. Any tips on how to do this would be most welcome. I also have seen references to a "subpage" feature but I don't yet know how to do this...

A related wiki book is located at http://en.wikibooks.org/wiki/Computer_Go

Connecting to a Server

GTP (Go Text Protocol)

I think the official page (along with sample code) is here

GMP

This is out of date and has been replaced by GTP

KGS

Connect using kgsGtp

This page discusses configuration of kgsGtp and how to do tournaments

IGS

Can someone provide a link for this?

Score/Influence/Territory/Moyo Estimation

See Influence and Moyo for basic theory

Known Algorithms

Bouzy's 5/21 Algorithm/BouzyMap

Applies standard computer vision methodologies to estimating influence/territory on the board

WaveFrontAnalysis

GNU Go's influence function

Influence decays exponentially from stones. Influence by color is done independently and used to compute a probability that a particular space becomes territory

MonteCarlo evaluation.

If black tends to dominate an area of the board when both players play randomly, then black probably has influence in that area. -- AlistairTurnbull

Discussion

The following are criteria for evaluating an influence function:

• Modifiable influence for strong/weak/dead stones
• Tunability
• Speed (whole board evaluation as well as incremental)

jhouse: HouseBot 0.1 has had rather poor performance from using a raw Bouzy-based algorithm. I don't think it meets any of the above criteria.

See Also

InfluenceFunction

Seems to be a page with similar purpose to this section. Maybe one day this section and that page should merge?

InfluenceMap

Pictures of influence

http://lyon-shinogi.jeudego.org/go_blob/

Particle-based influence propagation

Connections

See Connection for basic theory

Known Algorithms

CGTValuesOfConnections

Assigns numerical values to the quality of connections and then combines the individual values for a single result. (Someone please correct me if I've misread this)

Pattern Matching

See the pattern matching section of this page for additional details

Discussion

Life and Death, Eye Counting, and Eye Classification

See LifeAndDeath for basic theory

Known Algorithms

BensonsAlgorithm

Detects live stones in the strongest sense. Even if ignored, the opponent can not capture the stones.

A. Kishimoto. Correct and Efficient Search Algorithms in the Presence of Repetitions

PhD thesis describing the currently strongest tsumeGo solver.

A. Kishimoto and M. Müller. Search versus Knowledge for Solving Life and Death Problems in Go

Short paper in AAAI 2005 with tsumeGo results.

M. Müller. Playing it safe: Recognizing secure territories in computer Go by using static rules and search

Detects stones and territories that are safe under alternating play, with conservative assumptions otherwise (e.g. attacker is komonster)

X. Niu and M. Müller. An improved safety solver for computer Go

improves upon the search algorithms of the Müller 1997 paper.

X. Niu, A. Kishimoto, and M. Müller. Recognizing seki in computer Go

X. Niu and M. Müller. An open boundary safety-of-territory solver for the game of Go

X. Niu and M. Müller. An improved safety solver in Go using partial regions

K. Chen and Z. Chen, Static Analysis of Life and Death in the Game of Go, Information Sciences, 121, 113-134, 1999.

Analyzes eye spaces with the possibility of open skirts. Introduces the concept of a diagonal index for determining what they call a full eye point and a half eye point. A full eye point would be any empty space in a fully enclosed eye region.

R.Vilá and T. Cazenave, When One Eye is Sufficient: A Static Classification

Analyzes all eye spaces up to and including 7 spaces. Thorough case by case evaluation of shapes, the possibility of life, and how many opponent moves can be ignored before a response. It also identifies shapes that are alive regardless of the enemy stones inside of them.

Discussion

jhouse: There must certainly be other fundamental algorithms out there, I just have not seen any links to them. After listing known algorithms, I'd like to follow this up with a discussion of the strengths and weaknesses fo the various algorithms as well as fundamental ideas people have for what should be inside L&D Algorithms.

Jared: The strength of Chen & Chen's analysis is its speed. Slower algorithms use brute force search. Static analysis does not.

Pattern Matching

Known Algorithms

PatternMatching

Basics on building a pattern matcher

Deterministic Finite State Automaton

Patterns are compiled into an efficient finite state automaton. This is the pattern matching method used within Gnu Go.

Discussion

Strings/Groups

Known Algorithms

Gnu Go's Methodology

Gnu go uses the lowest position ID of all stones in a string/group to identify the entire group (The position ID's are a single number based on a 1D board...). When two strings/groups merge, every stone in one of the two strings/groups is updated to list the new group ID. If I remember right, I've inferred this from the origin field that gnu go uses. See Gnu Go Documentation: Worms and Dragons

Disjoint Set Algorithm also known as Union-Find

Rather than update every stone on mergers (an O(n) operation), instead use a more complex but more efficient method (nearly O(1) operations)

Follow Left Wall

Used for detecting splits of groups (usually of empty areas)

Discussion

Center vs Edge Heuristic

Known Algorithms

Discussion

Pashley Various heuristics might be used to seek the best area to play in. Once there are moyos, you could look for the borders. Earlier on, you might seek to keep a balance between high and low stones, influence and territory.

I wonder about some sort of moment function, or group of them, about tengen to suggest where to play. First moment is center of gravity in physics, mean in statistics. It would tell you to keep stones balanced across the board. Second Moment is polar moment in physics (how far is the weight from the axis?) and Standard deviation in statistics. A heuristic based on it might lead to 3rd and 4th line plays.

Reducing the Scope of Move Searches

Known Algorithms

Zobrist Hashing

Used to avoid duplicated board states in tactical reading (commonly used in chess programs)

Alpha/Beta

If this new branch to consider can result in nothing better/worse than what was already considered, don't consider this new branch.

Null Window Search

This is a modified form of Alpha-Beta that sets the min/max value to be identical or very close together. This allows a fast initial search before going more in depth

Lambda Search

I found this link but I don't know if there's better out there

Kosh: Thomas Thomsen is the inventor of Lambda Search. Kosh did some research on this topic too and wrote some extensions.

Markov Chain

Kjeld Petersen I have been reading up on this subject, and I found it quite interesting. I was wandering if any had made some testing using Markov Chain to make a algorithme that could suggest good moves?

Move Ordering

Most search methods require some sequence to consider moves. The most common method for this is to cache past search results for a particular move.

Proof Number Search

Tracks how many nodes would be required to prove or disprove some kind of true/false hypothesis (such as "can I kill this group"). The algorithm searches the node that is most likely to lead fast conclusion. For example, if branch A requires 3 sub-branches to work while branch B requires 12 sub-branches to work, it'll search branch A first.

UCT

Used with Monte Carlo searches for move ordering. It's based on a minimization of regret for a k-armed bandit. Each arm represents a possible move. It's said to favor quiet moves, but has also lead to significant strength gains in Monte Carlo bots.

Discussion

Other Algorithms

Known Algorithms

Discussion