Computer Go Algorithms
Table of contents |
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
- I think this is out of date and has been replaced by GTP
KGS
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
- 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
- Seems to be a page with similar purpose to this section. Maybe one day this section and that page should merge?
- Pictures of influence
http://lyon-shinogi.jeudego.org/go_blob/
- Particle-based influence propagation
Connections
See Connection for basic theory
Known Algorithms
- 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
- 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
- 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)
- 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
- 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.
- 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.