Saturday, March 5, 2011

Aspirations to Territory

Haven't had so much time to work on things lately, but in the tiem I've had I've been working on establishing a decent estimate of territory as an overall part of position evaluation.

It's easy (ish) to evaluate territory for terminal positions because group life and death status is (mostly) fairly easily determined.  Finding a good estimate for a non-terminal position however, is proving a little tougher.  To start with we can't easily tell which groups are alive when they are loose and not very played out (locally).  Although one could simply be conservative and only score 'obvious' territory (just whatever is fully formed) that (leaving aside the question of how easy it would be anyway) wouldn't really give good evaluation results (consider a large moyo with a few enemy stones inside it that a human would consider 'obviously' dead).  The net result would be likely to be a program that played to make small secure territories and always lost to a moyo-building opponent.

One could also treat influence directly as territory (say any vacant intersection with an influence level above some threshold).  This would be better in the moyo situation postulated above, but would still lead to a tendency to 'erode' an opponent's territory by playing stones into it almost arbitrarily (since even dead stones will negate influence, at least naively).  Also, influence is not the same as territory, and it's an adage of Go that one shouldn't use influence to directly build territory (usually anyway), so it's not an ideal basis.

In the end I decided to try an influence-based approach anyway (imagination failure!), but not just use a simple, influence threshold (I played around with that first, but didn't like the results it was giving me).  Instead I am (currently - still not entirely happy with this but it seems to give 'ok' results for now) defining two levels of territory, for the purposes of the game position evaluation.

Firstly proto-territory, as being any point within the influence of a player and also entriely surrounded by points also within that player's influence (or stones belonging to that player).  This is easy (aka fast) to calculate iteratively as moves are played, based on the existing influence system.

Secondly, a modifying layer that evaluates a safety function for groups, and for those below a certain level considers them dead.  Dead stones are considered to be points of territory for the opponent, as are any surrounding points.  If two groups of opposing 'considered dead' stones are in close proximity the overlap is not considered territory for either player.  Essentially territorial status is 'read through' the second layer, falling through to the first layer if layer two doesn't assert local dead stones.

Obviously the results depend on what the group safety evaluator considers to be dead, and that's an area I'm still actively working on.  For the usual test position the results (highlights for white territory) look like this:


This obviously isn't perfect, and has a couple of obvious artifacts:
  • The lower right point showing as white territory that is closer to being a captured stone - this is a weakness in the influence evaluator as much as anything, but should only ever result in small artifacts, so unlikely to result in negative correlation with the ideal.
  • The 'hole' in the white territory in the middle.  This is partially a weakness in the influence function, stemming mostly from the limited range of the paths used to derive it, and partially a weakness in the proto-territory definition.  The point in the middle of the hole has a net 0 influence (it's too far away from all but 3 white stones to receive influence from them, and it also has similar paths to 3 black stones - an extension of influence range by 1 would correct this in this case, as it happens).  The definition of proto-territory requires a point to be entirely surrounded so the neighbours of this point are not proto-territory.  This might be worth a special case for points of 0 influence that are themselves entirely surrounded (TBD).
Anyway, the major features here look ok (the 3 black stones on the mid-lower left are considered dead and so this is evaluated as white territory).  It's a little on the optimistic side, but that applies also to its evaluation of the black territory, so the net result is balanced.

Although I'm not entirely happy with this I have decided to cut my losses (for now) since this at least appears to have reasonable correlation with reality, and should suffice when used in search pruning.

Sunday, February 27, 2011

Under the Influence

A common concept in Go is influence.  This is hard to formally define, but essentially a collection of stones tend to make the area of the board near them more likely to end up under the control of the owner of those stones.  This may mean it eventually turns into territory for that player, or just that that player will have tactical advantage in any fights that take place in that part of the board.

Take this position for example:

In the lower left corner black has secured a small amount of territory in return for which white's wall of 3 stones gives him considerable influence on the bottom part of the board.  This influence is not the same as territory, but it means that white will have considerable advantage in fights in this area.  Collections of stones with strong influence are often referred to as being 'thick'.  The white shape below is an example of thickness, which generates influence to the right:


Evaluating influence is useful in both evaluating a position (who has the greater control) and suggesting moves to play (often playing near influence boundaries will provide good ways to grow one's own area and reduce the opponent's).

Zobrist's original Go playing program included an influence generation algorithm.  Zobrist's algorithm worked by considering each stone as an independent source of influence and iteratively 'radiating' from it by (at each generation) adding 1 to the influence value at each vacant neighbouring intersection of an intersection that had influence assigned by the previous generation (seeding the stone itself as being the 0th generation's result point).  Zobrist's program employed 4 such generations (so the maximum 'range' of any stone's influence was a Manhattan distance of 4 from it).  It summed the contributions from every stone on the board to arrive at a final influence map.

We can visualise an influence map by shading parts of the board (darker for black, lighter for white), as in the following picture (not using the Zobrist algorithm, but just to illustrate the idea):


A major problem with Zobrist's algorithm is that it's expensive to compute (especially if you try to extend its range by adding more generations), so computing it for every node you want to evaluate in the game tree is really going to slow things down.  What I figured I needed was an iteratively computable influence map - i.e. - one in which computing the influence map for a position which results from adding one stone to a position, for which we have already calculated the influence map, is cheap. What I discovered was that this was harder than it sounds!

I spent a couple of days working on what ultimately turned into dead ends, trying to adjust Zobrist's algorithm to make it iteratively calculable, by maintaining 'flow' values of influence contributions arriving at each intersection from each neighbour.  The idea was that when a stone is played the 'flows' into that intersection can be used to generate their downstream results and those results subtracted from the existing state before adding in the contribution from the new stone.  Although I was able to get this working functionally (captures are a pain to handle though) it was still too slow to really be palatable (hundreds of micro seconds on average).

Eventually I started working on another approach, somewhat analogous to ray-tracing in graphical rendering.  The idea was that if an intersection had a 'line of sight' to a stone then it should receive an influence contribution from that stone.  In this context 'line of sight' really means a contiguous path through vacant intersections to that stone.  For example the path below from the white stone to the terminal point:

Provided we restrict the paths to those which always move closer to their end point (so no doubling back on itself) what emerges is 'shadows' cast by stones, so for example, the lower white stone above has no path to the intersection to the immediate left of the black stone (the upper white stone does however).  Notionally the algorithm considers the set of paths from any source point (a played stone) to a given vacant intersection, and assigns to that path a contribution of:

    C = f(p1,p2)/N(p1,p2)

where p1 and p2 are the coordinates of the two points (the source point and the terminus of the path), f is a function determining overall contribution based on the distance from p1 to p2, and N is a function returning the number of paths between p1 and p2.  Essentially this amortises the distance-based influence contribution between all the possible paths.  This normalises things for differing path counts between points which arise from the fact that we are only considering paths which always move toward their destination (this means there are more paths between points 1 and 3 below than between 1 and 2 (3 paths, vs 1 path), so without this normalisation we'd see oddly distorted influence at 3 relative to 2)

The influence at a point is then the sum of all contributions from paths which are not blocked by non-vacant intersections.  Using an exponential decay based on Manhattan distance for f seems to give reasonable results.

So far this all sounds very well, but how do we calculate it iteratively and with high performance?

The key observation is that the paths themselves are features of the basic board geometry, not of the position occupying the board.  That is if we consider the complete set of all paths between all pairs of points on the board, all that changes as stones are played (or removed) is whether the path is actually extant in terms of making a contribution (i.e. - if it's origin point has a stone on it, and no other point on it does).  Consequently we can (in principal) pre-calculate all paths and simply toggle them on and off as the position changes.

In practise there are a (very) large number of paths between all possible pairs of points on the board (there are 361 X 360 / 2 (over 360,000) pairs of points before we even start considering the multiple paths between them!)  To reduce this to a manageable number we can do two things:
  1. Only consider paths between points within a certain distance of one another (which will give our influence a maximum range, but remember we already had that issue with the Zobrist algorithm anyway so this is no worse in that regard)
  2. Only consider 'reasonable' paths between pairs of points. 
To illustrate what I mean by (2) look at the two paths below:

The yellow path looks like a not very reasonable way for influence to flow, whereas the red path seems more natural.  Basically if we restrict max path length to 5, and path construction between two points operates in a 'greedy' fashion (always take the choice for the next point as the one that reduces the euclidean distance to the destination the most, which in a discrete grid will give at most two choices), then generating paths in both directions (to ensure a symmetric result) gives us a grand total of 143296 paths (that is the number debugging stats report  so don't ask me to derive it mathematically!).  This may sound like a lot, but it moves the bulk of the computation up front - playing any move requires (very inexpensive) processing of at most 188 paths.  The memory cost is more substantial (a little over 8M), but on a modern PC is not really a big deal.

For each path I maintain:
  • Source coordinate
  • Terminus coordinate
  • Contribution
  • Current state of the source point (black, white, empty)
  • Count of other points occupied
For each point of the board I maintain a list of paths (references not instances) that:
  • Originate at that point
  • Terminate at that point
  • Pass through that point
I also maintain the current influence score for each point of the board.

When a new stone is played all we have to do is:
  1. For each path originating at the played point set its origin state to the played stone, and if it has a 0 occupancy count, add the path's contribution (sign reversed for white) to the path's terminal point's current influence
  2. For each path passing through the played point, increment its occupancy count, and if it previously had a 0 occupancy count and a stone at its origin, subtract its contribution from its terminus
  3. For each path terminating in the point increment its occupancy count
Removing a stone is similar.  The code is very simple.  Here is what the routine to place a stone looks like (C#):


        public void PlaceStone(BoardCoordinate point, bool isBlack)
        {
            sourced[point] = true;
            values[point] = 0;

            //  All extant paths from this source provide influence
            bool signCalculated = false;
            bool reverseSign = false;

            foreach (Path path in sourcedFrom[point].paths)
            {
                if (!signCalculated)
                {
                    signCalculated = true;
                    reverseSign = ((path.contribution > 0) != isBlack);
                }

                if (reverseSign)
                {
                    path.contribution = -path.contribution;
                }

                path.sourced = true;

                if (path.occupationCount == 0)
                {
                    values[path.terminus] += path.contribution;
                }
            }

            //  Paths thru this point are no longer extant
            foreach (Path path in passThrus[point].paths)
            {
                if (path.occupationCount++ == 0 && path.sourced)
                {
                    values[path.terminus] -= path.contribution;
                }
            }

            //  Paths terminating here can now be marked occupied
            foreach (Path path in terminateIn[point].paths)
            {
                path.occupationCount++;
            }
        }

The end result is that maintaining the influence map for a 19 X 19 board costs me about 15 micro-seconds per move (amortised over 100 games of 250 random moves each).  This is  price I am prepared to pay.  It also seems to give results that look reasonable, at least to my eye (the shaded map earlier on this page was in fact produced by this code).  Furthermore it has the advantage that the path set can be tweaked arbitrarily without affecting the runtime code (just the path generation code), so (for example) I might choose to add a small number of longer paths to extend the influence range, and can do so without algorithmic changes, or dramatic runtime cost changes (provided I can choose a reasonably small subset of the set of possible paths

Saturday, February 26, 2011

Random Thoughts

I had a few minutes spare so I thought I'd make a very brief post on a couple ideas that occurred to me, which are probably distant-horizon possibilities for actual implementation but struck me as interesting.

GPGPU for pattern analysis

The basic pattern match algorithm is very simple, and very memory-localised for an individual pattern (the data to be considered only scales with the size of the pattern library really).  For a realistic shape library my guess is (including generated symmetric partners) we'll probably be looking at order of a thousand or so patterns.  It strikes me that parallel matching all the patterns against the board data in a highly threaded architecture could be extremely efficient.  This seems like a great candidate for GPGPU (which sadly is a pig to program with current tools) .  In reality we'd likely want to feed the GPU a bunch of position nodes at once because of the latency overhead of data exchange between CPU and GPU (this may reduce as APUs become more common over the next few years though).  Anyway, passing all the sibling nodes of one parent in the game tree would be fairly natural and mean we could have match results basically waiting for us if we have  tree search that can usefully consume breadth-first analysis.  This could easily buy a couple of orders of magnitude in pattern match performance...

Board sub-domains for transposition analysis

In many cases (certainly not always, but often) key variations are played out locally without reference to distant parts of the board.  In a naive tree analysis we're likely to re-evaluate the same move sequences in a local area many times when considering the whole-board game tree.  To avoid re-analysing whole-board sequences that occur by transposition (e.g. - swapping the order of two moves) it is  fairly common technique to use the Zobrist checkums of analysed positions to find matching subtrees and avoid the need to evaluate them multiple times.  Given the (frequent) local nature of fights in Go it strikes me we could divide the board into sub-domains, and construct Zobrist hashes of each sub-domain.  This would allow transposition-like detection of subtrees that take place entirely within one sub-domain.  By favouring early analysis of sub-domain-localised trees it should be possible to find alpha-beta (or other) cutoffs that cause large score swings by only operating within a subdomain, and applying them to other tree branches by use of sub-domain-equivalence tables (akin to full board transposition tables).  Sub-domains would probably be arbitrary (overlapping to avoid non-coverage of positions played out on boundaries) regions pre-determined (e.g. - 6X6 rectangles, spaced every 3 intersections or something), though maybe having them dynamically determined would be possible/desirable.  I haven't really thought this one through in detail, but it just struck me as interesting...

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.

Thursday, February 24, 2011

Oh yeh, the Rules!

Well ok, so now we can detect some nice geometrical shapes, but we haven't really related it to the game of Go as such.  To do that we need to teach the computer a bit about the rules, so that it can at least process the effects of a move, and determine whether a proposed move is legal or not.

Fortunately Go has very few rules - all the complexity flows from their application.

So, here are the basics:

1) The game has two players, one taking the black stones, the other the white. 
2) Players take alternating turns, beginning with black.  On each turn a player places one stone of his or her own colour on a vacant intersection of the board.  A player may choose to pass rather than play if they wish to.
3) Stones are captured if they have no liberties.  To define what this means we need to talk a bit about some basic concepts.  I'll do that in a moment.  First lets quickly finish up on the remaining rules
4) It is illegal to play a stone in such a way that it would immediately have no liberties unless by doing so it captures one or more opposing stones and thus gains one or more liberties in the resulting position (no suicide)
5) It is illegal to play in such a way as to repeat a previous position (strictly this is a generalised variant of a slightly harder-to-state rule called the 'ko' rule, but we'll just go with the easier-to-understand generalisation (which means we'll be playing what are called 'Chineese rules'))
6) The game terminates after 3 consecutive passes, after which the winner is determined by adding up the territory owned by each player + any captured stones they have gained during play (more on territory below)

So this all boils down to two concepts, which need better definition:

Liberties

A 'liberty' is a vacant intersection adjacent (directly - no diagonals) to a connected set of stones.  You'll find rule books tend to talk about liberties of a 'group' but I'm going to reserve that term for a more general concept that better equates to the way Go players use it when talking about positions.  Instead I will henceforth use the term cluster for a connected set of stones.  The highlighted stones in the diagram below are all examples.


The vacant intersection directly adjacent to the stones of each cluster are its liberties.  These are illustrated below:


So the cluster of a single stone (left) has 4 liberties, the 2-stone cluster 6 and so on.  Now we can examine what rule (3) (Stones are captured if they have no liberties) means.  In the position below the black stones would be captured if white played at the highlighted point, as this is their only remaining liberty:


Captured stones are removed from the board, and each counts as one point when the scores are determined at the end of the game.

Territory

The final concept we need then is territory.  At the end of the game players agree which stones that have not actually been captured are anyway  'dead' (what this boils down to is stones which both players agree would be captured regardless of anything the owning player could do if they chose to play things out locally).  A simple example of  a dead stone is shown below - because it is obviously futile for white to play further stones (each of which will ultimately be one more point for his opponent when eventually captured) he will not do so.  In the event of a disagreement between the players over what is dead, the onus is on the player claiming they are not to demonstrate he can forms two eyes (see below) and thus avoid capture).

Because of rule (4) (It is illegal to play a stone in such a way that it would immediately have no liberties unless by doing so it captures one or more opposing stones and thus gains one or more liberties in the resulting position) it is possible to create uncapturable clusters by creating what are known as eyes (which are essentially enclosed vacant intersections).  Consider this position:

White can never capture the black stones because to do so he would have to play at both marked points, but each of them is illegal to play at because of the no-suicide rule.  These marked points are examples of what are known as eyes. Any cluster that can makes 2 eyes is therefore immune to capture.

Once all dead stones are removed each vacant point entirely surrounded by one colour is a point of territory for the player enclosing it.  A player's territory + captures is their final score.  The white player often (though this is more an adjunct than a rule really) is also awarded what is known as a komi, or extra points to compensate for black's advantage in having the first move.  A typical komi (which may vary from tournament to tournament) is 5.5 points (thus avoiding draws).

Finally to illustrate rule (5) (no repeated positions) take a look at this position:

If it is black's move he may play the marked vacant point, capturing the white stone (this is not illegal by the suicide rule because by playing there he captures  a stone and so winds up with a liberty).  However, the result is this:
Which is symmetrical and at first sight could be responded to just by white playing the marked point and recapturing again.  This shape is what is called a ko.  White cannot immediately recapture, because to do so would produce a repeated position.  Instead he must play elsewhere, possibly intending to recapture on his next turn (when the intervening moves will mean the position is not repeated).  If the result of this ko is important (and sometimes games hinge on them) white will play what is called a ko threat elsewhere - this is a move that threatens something dire and must be responded to.  At some point one or other player will run out of threats that their opponent deems severe enough to outweigh winning the ko, and it will be resolved (usually by black filling in the marked point in the last position above, or white in the symmetrical position).

Ok, so I've gone on long enough about the rules.  What about implementing them?

The main thing needed is to track liberties, either dynamically (so evaluate when a stone is played to see if it is a capture) or iteratively (keep track of all the clusters and their liberties so you only have to update those adjacent to the played move each time).  Which will ultimately be more efficient depends on how often you need to ask about the liberties of a cluster, but since it not only underpins legality validation, but also informs position evaluation and move choice I went for an iterative approach to minimise recalculation.  There's no rocket science here so I'm not going to dwell on the details.  The main thing is that the result is a Go-policing game surface (it isn't a player yet) that will perform captures, count captured stones and prevent illegal moves.

As a detail, we can use Zobrist checksums to check for repeated positions, which is well-known technique for games like this to hash a position.  We retain a list of previous position hashes and check that after each move we have a new one.  This technique was invented by Albert Zobrist, who also devised the concept of influence functions for Go programs, which I'll be coming back to in a future post.

Tuesday, February 22, 2011

Shape shifting

So after a small diversion to give a bit of UI, it was back to the original proposition - that it should be possible to perform useful shape matching rapidly enough to not drag the time to perform a game tree node analysis into the mire.

The key insight...well, maybe 'idea' is a better word - 'insight' is perhaps a bit presumptive...was that we can easily represent a board position as a bitmap, and patterns similarly, and sweep one across the other with logical rotations which boil down to a very small number of machine ops.

To illustrate, consider the slightly simpler problem whereby we just want to match patterns of occupation of the board, without regard to the colour of stone on each point.  In that case each point on the board just needs a single bit to encode it (occupied or not) and we represent a row of the board as the first 19 bits (or whatever board size we're using) of a convenient word (32 bits say).  Similarly each row of the pattern is represented by the first N-bits of a word (where N is the pattern width), together with a mask word which masks out parts of the pattern's bounding rectangle we don't care about.  To perform a search for any given pattern sweep the first row of the pattern across the first row of the board by XORing them together (and ANDing out the mask) at each bit position (bit rotation of the pattern-row-encoding word sweeps the pattern across the board columns).  On finding a match in pattern row 1 verify the next pattern row in the same positon against the next board row and so on.  After finding or failing to find a match alligning the first row of the pattern to the first row of the board move down the board repeating the above procedure until the entire board is scanned.

The kernal of this loop is VERY efficient in terms of machine instructions required, and obviously the range of positions that need be checked is constrained by the size of the pattern and of the board (no point trying to match a 4-wide pattern within 3 intersections of the right hand edge and so on).  It also exhibits highly localised data access patterns which are very cache-friendly.

In practise the matching problem for Go isn't just occupancy of course - board intersections may be occupied by either white or black stones, and similarly pattern points.  However, that doesn't really change anything - we just need 2 bits per posiiton (I use the high and low order 32-bits of a 64-bit word, which these days is the CPU native size on most machines).  In fact the 4th value available also turns out to be very handy - we will often be interested in matching patterns that relate to edges or corners of the board, and we can easily accomodate this by making our board-encoding array 2 virtual intersections larger than the actual board and storing the otherwise unused 4th value in the off-the-board 'edges', allowing patterns to match against them also (effectively pinning the pattern to the edge/corner).

So enough of the theory.  How does it work out in practise?

I started off with a small shape library containing 4 common shapes that we'll need as part of any complete library - one-point jumps, bamboo-joints, diagonal connections, and what I chose to call L-joints.  These are illustrated below:


Left to right: Bambo joint, L-joint, 1-point jump, Diagonal connection.

In each case the highlighted area is the set of intersections to be included in the pattern (so note that the L-joint, for example, is non-rectangular because we don't care about any stones that may or may not be present in two of the intersections).

The code that loads the pattern library automatically generates all symmetric partners (rotations, reflections, and colour-swaps) which gives a total of 28 raw pattern bitmaps for the above 4 canonical shapes.  My initial implementation matched the full pattern library (28 shapes) against a full board position (19X19 so order of 300 or so possible pattern placements for each pattern) in a shade over 20 micro-seconds.

Considering this is single-threaded, implemented inside a virtual runtime (.NET) on a 2-year old desktop that seemed fast enough to be encouraging.

In a real game-tree analysis however, there is scope for significant optimisation of position anlysis (of which the pattern matching is ultimately a sub-component).  Specifically as we traverse the tree, the analysis for a child node only differs from that of its parent by the effects of playing one move.  For Go that means adding one stone most of the time (captures complicate things but are relatively rare).  Hence if we can make our positional analysis routines operate on some result-state iteratively, then they only have to consider elements that have changed.  For shape-matching this means that playing a stone at some point can only possibly influence pattern placements that overap that point.

This is very easy to take advantage of - instead of doing full-board pattern matches every move, build up a map of pattern-match instances (2-tuples of pattern and matched position) which persists between moves.  When a move is played, invalidate all instances overlapping the played point, and then scan the pattern library over the subset of the board that overlaps (this is all very analogous to clipping rectangles in graphics).

Doing that got me down to a bit under 15 micro seconds to update the shape map for each move played (based on amortised mesurement over 100 random games of 250 moves each).

Now what are we going to do with our new-found ability to match shapes?

...a tale for another day...

Sunday, February 20, 2011

Neccessary(?) Diversions

Sadly I couldn't just implement a shape recognizer in isolation - I was going to need infrastructure:  UIs to display positions, highlight shapes for debugging purposes, edit the shape library, etc.

When I mentioned I was going to spend some time working on UI first to my wife she was sceptical.  As she pointed out, on my previous attempt back when 512K was a lot of memory (no, really), I'd gotten bogged down in UI work and lost sight of the the bigger picture, forever polishing the surface.  Well, she was right of course, and a compromise was needed.

A little bit of rationalisation and reflection supported the case for some UI beyond the very most basic I could get away with.  Since I professionally program mostly at a systems level, with very little UI surface, this was an ideal opportunity to broaden my skills and learn how to do UIs (yeh, right - I did mention some rationalisation was involved didn't I?).  Also it was clear that some visualisation capabilities would aid in later debugging, and that eventually I'd want something that looked pretty!

Based on this I decided the best approach was to design some fairly robust abstract interfaces for display and interaction with Go-board-like objects, but for now to instantiate them relatively crudely.  That way the game engine could develop assuming a fairly capable front end, but the actually implemenation wouldn't cost too much effort up front.

In the end it took me a few hours to knock up a functional-enough UI that just represented the board 2-dimensionally in a reasonably tidy grid, with circular stones, and which fed clicks back to the engine to interpret.  For debugging and editing purposes I embelished it slightly to also support highlighting of points and area selection.  Here's an example display (ignore the toolbar - that was actually a later addition which I'll no doubt be posting about later):


The same UI could readily be re-used to both display games (and process user interaction with them), and to form the basis of a shape editor.  Of course, I secretly planned a more prettified implementation later based on a photo of my physical Go-ban (I have  pretty decent 2" thick, 4 pedestral-suppoprted, wooden Go-ban that is reasonably authentic to the Japaneese roots), presented in 3-d, with sampled stone click sounds etc., but I guess that'll be the subject of a future blog.  For now here's a picture for reference: