okvonnegut/ Catanus

Scroll down for pictures!

I (okvonnegut) have written a small program in C to evaluate go positions / approximate score. It's very poor at recognizing large dead groups (involving life & death problems), but (I think) it handles fuseki and thickness etc. reasonably well.

As an example, I feed it this position:

 

Since the SL diagram codes are a wee bit limited when it comes to labels I'll have to screenshot how an outputted SGF looks in CGoban3, but this is what it comes up with:

Note, it uses area scoring, so effectively it tries to calculate the probability that a white or black stone will end up on a given intersection.

Legend:

WW = "definitely" White's
W = most likely White's
w = probably White's

Likewise for Black.

This is just a preliminary version. It is slower than it needs to be because it looks at the goban's intersections as a graph instead of an array and very few things are hard-coded. Not even the number of players is hard-coded. I did it this way because I thought it would be fun to be able to generalize it to unusual gobans, but now I'm thinking I want to make it more intelligent instead, and to do that I also want to make it faster so it might even be a useful node evaluator in tree searching (only for fuseki/middle game: it will still be terrible at "estimating" endgame sequences and life and death status).

My only ambition is to make it better than CGoban's SE (shouldn't be too hard, right?!).

Note: not publishing code yet, because a) one would have to study the code to figure out how to use it. E.g. it has really primitive input/output and I have to use Python scripts as wrappers to talk to it b) rewriting it as I speak c) some of the code is embarrassing :)

This is also why I made a sub-page instead of a new SL entry. Besides I haven't named it yet. Catanus is the temp name. (If you have any questions regarding that name the answer is likely to be "yes.")

Update: I haven't made it faster (actually I've just made it slower) or smarter yet, but I did make a little PyQt front-end for it (the C code is compiled to an .so lib which Python uses). It updates "live" while clicking:

Nevermind that the coordinates are off & that there is a round-off error (fixed now) that causing the colored backgrounds to become displaced when approaching the lower-right corner. :)

It's still piss-poor at handling big dragons:

It's confused because it can't handle the "semeai" in the top center. Also, the huge black group in the lower right is evaluated as "very very very alive", though I personally wouldn't be so optimistic...

Oops. I've forgotten to detail how it actually works. Well, I hope nobody is disappointed, but it's simple and simply Monte Carlo evaluation. At first it was completely random play, but I tried increasing its intelligence by hard-coding some of the most basic patterns (similar to the list at Spightonians) and though its overall moves/sec speed decreased (because it had to evaluate more and selecting a move became more complex), there were some benefits:

• the territory inside thick positions became more marked; e.g. regular 3-4 shimaris were shown to hold corner territory by much higher probability (Note: the above diagrams based on the old code)
• games becamse shorter (smarter play => less mucking about)

First (second?) step in making it even smarter: greater pattern recognition.

 

The pattern consists of the points surrounding . Each moku has one of four possible values: Empty, , , and Edge. It's always Black's move (the marked stone in the center).

There are slightly under^[1] 193995 of these patterns:

Out of the 2**24 (16777216) possible combinations, about 91% can be ruled out immidiately as illegal because of invalid edge placement (~96.8% of the combinations will feature one of more edge points). Further ~7-8% can be discarded as transpositions.

So the remaining ~200 thousand patterns now has to be evaluated using all the games I can find. From this I'll assign a probability of it being a good move (without regards to the surroundings), and use these probabilities to execute Monte Carlo simulations on board.

Move selection might also be improved by lowering the probability of moving on points that have already been estimated to be located inside extremely strong influence of either player (avoid suicide invasions and onverconcentration). Ideally, this will also lead to shorter games so more simulations can be performed.

[1] I say "slightly under" because there are some rare illegal cases in the corners where liberty shortage can be inferred that I did not bother weeding out (yet):

 

Code of the day:

ca_pattern_t ca_pattern_invert_colors(ca_pattern_t pat)
{
    static const ca_pattern_t   u = 0xcccccccc,
                                l = 0x33333333;
    ca_pattern_t    ux = pat & u,
                    lx = pat & l,
            iux = 3*ux - ux/2 & u,
            ilx = 5*lx/2 & l;

    return iux | ilx;
}

C can be so ugly sometimes :(