Yet Another Novice Tries To Write A Go Program
A couple of years ago I gave Computer Go a try. It never got much past the static evaluation phase, played horribly (even by computer standards). It has remained unchanged for a year+ now (although some pieces made their way into GoSuite). I thought I'd document some of the ideas so they don't die and with the hope of stirring up discussion:
AshleyF: Note: I commented out the screen shot images for now because feniello.com is down. I'll put them back later...
The first cut was some basic infrastructure to display a board, handle the rules. It actually played a complete game but just by randomly filling in the 'influence boundaries' and passing when no more boundaries exist.
- Board Class
- Stores position, Maintains groups (aka 'strings' of stones)
- Can enumerate groups, liberties, etc.
- Handles capture, tracks Ko point, etc.
- Fires events when changes/captures occur
- BoardUI UserControl
- Resizable visual representation of position with limited markup
- SGF Reader/Writer/Utilities
- Very simple forward only SGF reader/writer
- Compose/Decompose compound SGF fields, Convert SGF coordinates, etc.
- Simple proximity-based influence
- Simple influence-based connection analysis
- No life/death analysis yet
- Crazy-simple engine:
- Takes empty corners
- Takes/Saves immediate capture
- No search at all yet
- Simply takes random point along 'influence borders'
- Passes when no borders remain
- Displays connection status and influence
- Plays against itself on 13x13 board. That's it.
The influence function was just a standard implementation with values falling off with distance (I chose inverse to the square of the distance - like light). The only interesting part was that I imagined a rim of stones just off the edge of the board and allowed them to radiate influence in from the edges. This edge influence would only register proportional to existing influence from actual stones. Edge influence would combine with either Black or White influence equally. This way the edge would sort of help out whoever was nearby.
The connection status was simply determined by the proximity of the two stones in question (or a stone and the nearest edge) and the influence along the line between them.
Next, I tried to define the concept of 'enclosure'. At one point, I made a visualization for this that looked like:
Insane! In trying to define enclosure I imagine the red lines as barriers. Visualized a different way, the dots (below) are what I'm calling 'bridge points' which represent points that form a virtual wall. You can have Unsettled or Weak bridge points of course. Also, although the visualization doesn't show it, you can have a single point that serves as an Unsettled bridge point for both Black and White simultaneously.
So, there's now a static evaluator for bridge points; can now ask Bridge.Status(point, color) getting back a ConnectionStatus.
Then based on this there is now also a static evaluator for 'enclosure'; can ask Enclosure.Status(point) and get an EnclosureStatus of None, Black, or White.
Occupied points are not considered enclosed. Bridge points are considered the edge of the enclosure and not part of the enclosure itself. The exception to this is 'inner bridge points' which are within a larger enclosure.
You can see that life/death and invasion are not taken into account (as it will be for territory evaluation) but one step closer.
As it plays you can see the enclosure status toggle constantly which is due to the fact that the engine knows nothing about defending connections.
Next I worked on the concept of 'blocks'. Block.Points - given the point of a stone, enumerates connected (not necessarily touching) stones. Added a visualization for this (red squares). Obviously, without tactical search it doesn't notice things like the cut at F11.
Horizon.View and Horizon.Edge - This is a concept I've never seen in a Go engine but I think may be useful. Given a point it looks out as far as it can see in a straight line. Cannot see through stones or enemy settled connections (settled bridge points). 'View' gives all of the points seen. 'Edge' gives only the points at the very edge of view. Edge points may be stones blocking the view, settled enemy bridge points, or the edge of the board itself. Added a visualization for this (red dots for View, squares for Edge) - below example is Black's view from the center of the board. You can see that the black and white stones block the view but that only white connections block.
I think this would be useful for determining runability and just openness of a position. Essentially, View is a measure of partial enclosure. If a block will have trouble making eye space on the side and must run, where will it run? Search the horizon Edge for friendly stones or, in the early opening perhaps, just feel some safety because of the sheer vastness of View. 'Outside' view (running space) vs. 'Inside' view (eyespace) can be distinguished by the Enclosure evaluator. Planning to use this for a basic 'first glance' life/death evaluation.
First I added super primitive life and death detection. Works reasonably well for open positions. Not very accurate but at least does determine death of completely stranded eyeless stones. This helps with the other evaluators so that, for example, a single cut off and dead stone doesn't spoil an enclosure evaluation. Notice the transparent (dead) stones in the lower right:
The Life algorithm is very stupid. The main goal at the moment was just to keep obviously dead stones from messing up the other evaluators. Gives the benefit of the doubt in most cases.
- If large enough enclosure (currently 10), then Alive
- If large enough expanse (currently 100), then Alive
- If enough liberties (currently 5), then Unsettled - needs further evaluation in the future
- If ratio of friendly to enemy control exceeds 1:2, then Unsettled - needs further future running evaluation
- If the weak group has any unsettled connections, then return Unsettled - needs further evaluation obviously (can't assume that connecting makes life!)
- Otherwise, Dead
I added Bensons Algorithm to detect absolute life (purple):
Next I added GTP support and hooked up GnuGo. Great scott! Even with a 13-stone handicap (on 19x19) GnuGo usually takes the entire board! I think we at least need a few decent move generators before even beginning to measure strength.
Next I added a few move generators and alpha/beta search. It plays somewhat better now but still needs 11 stones from GnuGo! It can beat its ‘old self’ pretty handily now though.
Things learned: Evaluation is too slow and inaccurate, search is too narrow and shallow, and its really, really difficult to arbitrate between move generators. I think the main thing is to come up with some standard attributes to give to move ideas (not just weight) so that some ‘smart arbitrator’ can choose moves from a pool of suggestions. I think also that blind search with position valuation is ridiculous for Go. Some day I want to do the Adversarial Planning thing from this paper: http://www.informatics.ed.ac.uk/publications/online/0103.pdf.
While it’s the wrong approach really, it’s a starting point. It can actually beat GnuGo with a high enough handicap. Before it was just too random to give any kind of skill measurement. I’d say it’s about 20 kyu by computer standards now. Better than immeasurably horrible, but still awful! Oh well... it's fun.
- Added simple fixed depth/width search
- Currently set to 3 plys deep with decreasing width: 10 candidates on first ply, 5 on second, 2 on third.
- Uses move generator weights to narrow the search but then does territory/influence evaluation to assign positional value
- Evaluates position as:
- Stones and territory, 1.0 each
- Outward influence control (non-territory point where friendly influence outweighs enemy influence), 0.5 each
- Basic move generators with simple weights
- Take Empty Corners, weight of 30.0
- Settle Connections (play on unsettled bridge points), 15.0
- Extend On Third Line, 10.0
- Control Borders (same as Classic Go Sharp), 9.0
- Capture Or Extend From Atari, 25.0
- Play Away From Thickness
- Penalty of 0.8 for playing where influence is > 4.0
- Penalty of 0.6 for playing where influence is > 3.0
- Penalty of 0.4 for playing where influence is > 2.0
- Penalty of 0.2 for playing where influence is > 1.0
- Penalty of 0.2 for playing below the third line
- Be Super Timid (for playing high handicap)
- Penalty of ½ of current weight for touching enemy stone while not touching friendly ( tsuke)
- Bonus of ¼ for directly adjacent extension (sagari)
- Combine Multiple Purposes
- Literally sum of weights for multiple move generators suggesting the same point
I've since read Bruce Wilcox's EzGo and think that a lot of this could be done differently. A lot of his theory is based on very specific principles (e.g. less than 5 liberties is unsettled in a contact fight). Approaching static evaluation as more of an 'analog' thing with thresholds makes it too vague, makes it difficult to understand why that machine is choosing to play the way it is (for tuning), and makes dependencies difficult to track (for caching).
For example, having static connection status depend on influence is wacky. I could just handle a few basic connection shapes and evaluate based on known cutting points. Specific shapes with specific known cutting circumstances. This way the cached evaluation would have dependencies on only a few points rather than the whole board (a distant stone changes influence slightly). For example: