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.