Chrisd/Computer Go Improvements

Sub-page of Chrisd

The basics of my computer go program are described elsewhere. The main point of this "elsewhere"-page is that my program is such that it detects inconsistencies in its evaluation function automatically. As the strength of the program is totally determined by the quality of the evaluation function, theoretically all I need to do to obtain a very strong program is to fix all the inconsistencies reported. At the moment I only intend to fix inconsistencies worse than 0.6 (what that number means is defined elsewhere). The purpose of this page is to report the inconsistencies that I fixed.

Tedomari

(4 Nov 2006) My code was a bit of a mess. I had all kinds of different data structures for storing how important a particular move was. There were thermographs. The code for "bigger surrounded regions" would in the case of an unsettled position also produce a data structure telling how big killing/saving the unsettled position was. Finally, the code cheking for atari would also produce something similar, but not quite the same. I now made all this code produce thermographs so that it is now quite easy to compare them. Just ask a thermograph what its temperature is! So, if there are a bunch of thermographs, we should assume that the graph with highest temperature is picked out? Wrong! It is also important to get the last move before a significant drop in temperature. This is called tedomari. For instance, if there are a sente and a gote of about the same temperature the sente should be played first. I now implemented this. The character of a move is determined by looking at the shape of the top of the thermograph. Also the case of ko is interesting. If a gote is hottest (of temperature t_G) and the next-to hottest move is a ko (temperature t_K) and the rest of the moves has a maximum of t_E (for environment) then the ko should be played first if 3*t_K > 2*t_G + t_E.

I talked about the importance of moves, but my program really works by evaluation. The reader may be wondering how this fits together. The answer is that if one move is clearly biggest this is played and the evaluation of the original position is made equal to the result after playing this biggest move. That is why I also need to know how to order moves.

Bigger surrounded regions

(10 Sept 2006) Below we had "small surrounded regions". I now implemented handling bigger surrounded regions. Using search it is determined whether some bunch of stones can live inside a region of the opponent. The search terminates if the stones form a Benson region or if the opponent succeeds in creating something that is dead according to the criterea given under "small surrounded regions". It now solves the corner (that comes from the test games)

[Diagram]
corner  

and it solves it very fast (a few secs), reaching the conclusion that White is unconditionally dead. The solver is not exact. If the number of nodes at a certain search depth becomes too large, it assumes that whoever is to move can reach his goal. However, this can only happen if no promissing looking moves were found one level higher up the search tree.

The reason that it has been three months since the last improvement is not just that I do this in my spare time but also that massive improvements in the rest of the program were needed to make this search finish within an acceptable amount of time. The code for "small surrounded regions" needed to be improved, because it did not spot all kinds of false eyes. The board representation was improved substantially, making doing/undoing moves at least ten times as fast.

Spotting atari

(7 Jun 2006) My program now looks whether stones can be captured. For evaluation purposes it is assumed that the capture that is the most urgent will be carried out. This is measured by how many stones are captured. The non-urgent captures are assumed to have a probability of 50% to be carried out. After all, the opponent might defend. Also the size of a typical move is estimated by looking at the largest open area on the board. If this estimate is larger than the largest capture all captures get a probability of 50% to be carried out.

Bigger regions for thermography

(14 May 2006) Below I stated that thermography was only attempted for local situation consisting of at most four intersections and surrounded by Benson-alive stones. I now changed this to 14 intersections. Obviously, the problem is that doing thermography on 14 intersections can take forever because my algorithm tries all posibile moves for both colors in every position in the move tree. To fix this, I now keep track of the branching of the move-tree. At every level the number of possibilties is counted and these numbers are multiplied. If this product gets too large, which I at the moment define as larger than 1000, evaluation is done heuristically. The same evaluation function as used normally is called but with a flag set that indicates that computationally expensive operations (that could well include thermography!) should not be performed.

Also, calculated thermographs are stored in a cache in order to only have to compute them once.

Another silly bug

(22 Mar 2006) The feature of recognizing small surrounded regions (see above under the heading of the same name) was quite broken. It recognized the border intersections of such a region by testing whether an intersection was adjacent to a black stone. This goes wrong if it is not Black who surrounds a small region but White. Also it should not look wheter an intersection is adjacent to a stone of some color but whether it is adajacent to a Benson region. This is because a smal enclosed region can quite well contain stones of the same player that surrounds the region.

Silly bug

(21 Mar 2006) I had a silly bug in the code calling the thermographic functions. The result was that regions with more than four intersection (i.e., regions for which the thermographic functions are not used at the moment) would be automatically considered to be fully surrounded by Black, if they were in fact next to Benson-regions of both players.

Thermography

(19 Mar 2006) I implemented thermography. As I am for the moment considering the case without ko-threats neither of the players should be komaster. The two players should be treated equivalently. The solution is to allow moves that would be forbidden by the ko-rule but if a player does such a move his opponent becomes ko-master for all follow-up moves. A player being komaster can be implemented by demanding that if a komaster plays a move that would be forbidden by the ko-rule he has to immediately make another move. Note that there is no restriction for the moves of the player that is not komaster. After this was implemented a simple two-stage ko as displayed on this page was evaluated correctly. If the temperature is lower than 2 (area scoring) the four points where the ko occurs should be owned by the player who is to move. Implementing this also allowed me to remove the code for evaluating final ko's as the thermography will take care of that (albeit it is probably a bit less accurate). I take the temperature to be given by the local temperature of the one-to-largest local position. Also, at the moment I only invoke thermography for local situations that do not consist of more then four intersections. This should probably change in the future.

Small surrounded regions

(12 Feb 2006) My evaluation function now also recognizes areas that are completely surrounded by be a Benson-alive group but too small to support two eyes. These areas are automatically owned by the player that has surrounded them.

Final ko's

(12 Feb 2006) Because the evaluation function is still quite bad, it thinks that every stone on the board is alive. In particular it does not see the need to fill ko's at the end of the game. However, it does notice that capturing in a ko is profitable. This makes games the end with very long ko-fights where it is only by coincidence that a ko ever gets filled. Therefore I made the evaluation function evaluate a position consisting entirely of unconditional territory (as defined by the Bensons algorithm) and ko's correctly. Note that this is not very difficult because if the rest of the board is Benson, there are by definition no ko-threats.


Chrisd/Computer Go Improvements last edited by 213.140.6.103 on November 4, 2006 - 11:24
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
RecentChanges
StartingPoints
About
RandomPage
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Goproblems.com
Login / Prefs
Tools
Sensei's Library