Shape, Form, Substance

I wanted to return to what I plan to do with the ability to match shapes a bit before starting on the next big topic (which will be influence and territory analysis).

The basic pattern matching maintains a map of instances of every shape on the board at any time, but patterns alone don't convey anything - they must have some properties attached to them which inform either move choice or position scoring.  To achieve this what I actually define in the shape library are different categories of shape (which wind up as subclasses in the implementation), which convey different properties and can be processed accordingly.

The list of different 'types' of shape we could conjure up is probably almost endless, but so far I have considered these (some implemented, some not as yet):

• Basic scored shapes - just attach a numeric value to an instance.  This could be used as part of positional evaluation to take into account the concept of 'good' shape (e.g. - bamboo joints are good, empty triangles are bad - see http://en.wikipedia.org/wiki/Bad_shape)
• Connections - shapes that connect two (or more) clusters of stones together, such as a diagonal connection or a bamboo joint
• Keypoints - patterns that match against existing shapes and indicate potential key points which are moves that are likely to be good candidates for consideration
• Eye shapes - patterns that form eyes, or partial eyes
• Joseki encodings - a joseki is a well-known local sequence of moves, generally related to the early game and often to corners.  As such they are basically sequences of moves, but it would also be possible to represent them as shapes formed at each stage.  This representation handles transpositions automatically.  They are also very cheap patterns to match since they tend to b anchored to corners and thus just have one candiate placement to check.

In particular I want to focus on connections, and use them to give the program a concept of a group. Informally, a group is a set of stones of one colour which is likely ultimately to live or die as a unit.  This is a somewhat looser concept than a cluster, and until very late in the game a group will typical consist of several clusters which are at least loosely connected to one another.  Consider this position:

The highlighted black stones are one example of a group (in this case consisting of 3 clusters).  In this position black basically has 4 groups (one in each corner) or possibly 5 (the body of back stones in the upper middle can readily be cut off from those in the top left corner if white plays at the cutting point).  White has 2 or 3 larger, more nebulous groups (centre right extending to top mid-right, top mid left (arguably the same group in fact), and all the white stones in the bottom left quadrant of the board.  The isolated black stones if the mid lower left would probably be considered dead for the purposes of group determination (at least by a human player).

One major aspect in deciding what constitutes a group, is which clusters are connected to which other, and this is where we can use connection shapes.  By including points of the pattern that the shape connects in the connection-shape definition, we can use a match on its pattern to associate the clusters at those points, and thus define a group.  Having the program understand groups is useful, because they are a convenient (and good) place to attach various scores for position evaluation (their territory, (an estimate of) their life-and-death status, their strategic importance (maybe - that's just an in-principal), and so on.

Of course this is a fairly limitted definition of what a group is - for example shape-connection-detection probably isn't going to connect the upper right white stones to the lower right ones in the above position, so we may also need to add other means of defining connections (influence-based in the example case, which is going to be the subject of a couple of future posts).

We'll also need to evaluate an estimate of life-and-death status for groups.  here again pattern matching can help a lot, in the form of eye shape detection.  As we saw previously a group with 2 eyes is unconditionally alive.  In any search there is going to be a trade-off between accuracy of the position evaluation function for a position, and the depth of search that will be required to refine that to the actual status.  A more accurate evaluation function will converge on the real status faster (in terms of search ply) than a less accurate one, but will typically cost more to evaluate.  The key aspects are that it at least correlates positively with reality (statistically speaking) and converges upon it as we get closer to terminal positions.  To this end (for both connection patterns and eye patterns) I also give them a confidence score (so a bamboo joint has 100% confidence, whereas a 1-point jump has a lower one, a fully-formed eye has 100% confidence, a partial eye shape less).  This means the group safety evaluation can treat two half-eyes like one fully formed eye and asses the total 'eye-potential' of the group (with 2 being the key number at which point we declare the group alive with high confidence).

As of writing this entry the program uses just connection shapes to determine group constituents and just eye shape (plus some non-pattern-related criteria which I'll talk about another time) to determine group safety.