Adjusted Length Analysis

    Keywords: Shape

This is a completely cracked idea I came up with, somewhat inspired by WaveFrontAnalysis, when I tried to think about how I judged tenukis and decided how far away I should play. Good shape is one thing, but how do you decide which shapes to try for, especially in the fuseki? One could say IkkenTobiIsNeverWrong, but proverbs can only take you so far. After all, two space extensions are more common along the third line, just as an example I've observed. If every move on a 19x19 board is IkkenTobi, then it's not much different from playing normally on 9x9 ;) Again, it's very rough and has little if any basis in theory. Oh, and I wrote it up at 2-3 AM local time and haven't had a chance to edit it yet, either. :/ (I'm making minor changes now, but still - very rough.)

The idea here is to evaluate the size of tenuki play by determining the expected value of the territory that will be surrounded eventually. If you play further away, you might think you are claiming more EyeSpace, but it becomes harder to connect.

The first idea we need is the adjusted length of an extension. I came up with completely arbitrary heuristics for this that appealed to some perverse aesthetic mathematical sense ;) My idea is to multiply the Pythagorean distance between the stones by the probability that they will connect. Similarly, the area 'staked out' by a set of stones is the area within, connecting the centres of stones with straight lines, multiplied by the product of all those connection strengths. Logical enough, no? But now we have to get those probabilities... :)

Through absolutely no statistical research but a whole bunch of messing around with Gaussians and other stuff that seemed to appease my brain, I decided on the formula: connection strength = e^-((distance^2 - 1)/16). One can imagine a circular region of tension (?) between two stones; the area represents the difficulty in connecting them. (Any single stone of the same colour within that circle provides a more solid connection). Then I had to make slight adjustments to account for things like the fact that a nobi is never going to be cut.

So we get the following strengths:

|nobi |<1.00 |kosumi |<0.94 (1) |IkkenTobi |<0.83 |keima |<0.78 |HazamaTobi|<0.65 |NikenTobi |<0.61 |ogeima |<0.57

{1} miai is not a guarantee if there are bigger plays elsewhere, no?

And we can extend the table as need be, although I don't know of names for bigger extensions than that.

If there are other stones nearby, they represent alternate connection paths, strengthening the connection. To simplify the task of evaluating a large moyo, we might pick three stones on the outside as sides of a triangle, and find that area - the other stones serve to strengthen the side connections. Which three? Er... ^^;

First off, I would suggest only considering stones within the aforementioned 'circle of tension' between the stones to be connected:

Critical area for various extensions (circled).  

A same-colour stone in that region increases the connectivity. An opposed-colour stone decreases it. My idea is: for each subset of same-coloured stones in the region, find the best-connected path using those stones and the end points, where the connectivity is the product of connectivities between each pair. (The idea is that any of the 2^N combination of stones works, but only one path should be counted for each). Similarly do the same for paths using the two end points plus only opposite-coloured stones. The (direct) path using no stones is counted as a same-colour path.

Then, the net connectivity is the 1-(product of (1-(same-colour connectivities))) * (product of (opposite-colour connectivities). The assumption is that connecting the endpoints with opposite-colour stones has the same difficulty as preventing a same-colour connection. (Probably not a very good assumption at all!)

Finally, we define the expected area of triangles. (Maybe I should have called this "Adjusted Area Analysis"...) Heron's formula for the area of a triangle is sqrt((s)(s-a)(s-b)(s-c)), where a,b,c the side lengths and s=(a+b+c)/2. The area inside a triangle marked out with stones is going to be somewhat less than that; assuming we connect, the edges are 1 stone thick and half of that is inside the triangle, so we subtract (s) - but need to add about 1 back, to cover overlap at the corners. (This is somewhat inspired by Pick's theorem for area of shapes with lattice-point coordinates.) Finally, we multiply that by the net probability of connecting all three sides (and the assumption of independence here is probably very dangerous too. But it's a start... :/ )

So our net "size" for a move (and finally note that this doesn't count things like influence resulting from the move, etc.) is: C(a)*C(b)*C(c)*(sqrt((s)(s-a)(s-b)(s-c)) - s + 1), where for simple situations C(x) = e^-((x^2 - 1)/16) and s = (a+b+c)/2. Whew. Of course, for simple situations Heron's formula isn't needed for that part of the calculation.

Let's try it out:

What does our analysis say about extending from a line of three stones?  

Let's consider the 'area' resulting from each of the marked points. We'll take the circled stones plus the marked point as sides of a triangle, with the circled stones of course being solidly connected. (The paths are IkkenTobi for .83 , and nobi+nobi for 1.00 which makes the IkkenTobi irrelevant. So at least we get *something* right. ;) ) Without the squared stone the results would be proportional, since that just changes the connectivity of the one side. (or would it? For point a, the squared stone makes the connection from a to the far endpoint solid when it wouldn't otherwise be. Similarly for b and c, but not for d onwards. A slight change, then.) In each case, note that the Heron's formula part of the area just becomes the number of rows we extend down (i.e. one point for a and b, two for c and d etc.)

Point a gives connections nobi, (nobi+nobi+nobi) to the circled stones for a connectivity product of 1; the area is 1-(1+2+sqrt(5))/2 + 1 = -.62. (A negative result; reinforcing the idea that TheEmptyTriangleIsBad, perhaps?)

Point b is also solidly connected and the area is 1-(2+sqrt(2)+sqrt(2))/2 + 1 = -.41.

Point c connects as an IkkenTobi to the near stone and through four non-solid paths to the far stone. Those paths work out to give near-certain connection, though, so the connectivity product is .83 for the IkkenTobi. The unadjusted area is 2-(2+2+sqrt(8))/2 + 1 = -.41. The adjusted area, finally, is -.34. Still improving, you see, but still not the right move.

Point d connects as keima to both endpoints; the squared stone is outside the region of influence (for a keima, just the two 'waist' points count). So the connectivity is (.78)^2 = .61. The unadjusted area is 2-(2+sqrt(5)+sqrt(5))/2 + 1 = -.24; the adjusted area is -.14. A pattern emerges; the centre plays are better, because the same triangular area is enclosed with a shorter perimeter, conserving territory. Again, play at the point of symmetry. So we won't consider the side plays any further.

Point e connects as ogeima to both endpoints and again the squared stone doesn't matter (and won't from now on). The connectivity is .57^2 = .32. The unadjusted area is 3-(2+sqrt(10)+sqrt(10))/2 + 1 = -.16 and the adjusted area is -.05.

Point f gives connectivity .37^2 = .14. The unadjusted area is 4-(2+sqrt(17)+sqrt(17))/2 + 1 = -.12 and the adjusted area is -.02.

Another pattern emerges; some simplification shows that this series approaches zero asymptotically. The conclusion is that we should play as far away as we can get away with, which doesn't seem quite right. Oh well, I started writing this without having done any previous testing, so I figured it would be miraculous if the system predicted NikenTobi (point e) right off the bat (as I'm told is the usual extension from that line). Any suggestions are more than welcome :)

Some Lurker? This is a cool idea . . . and I think possesing of much merit. My only beef is that unless I am mistaken you are using Euclidean distance for this . . . which seems inappropiate. At large distances it is probably a good approximation but something like the city block metric is probably better. In thinking about it it seems to me that the city block metric isn't quite right either since Kosumi seems to be a stronger connection than a one point jump. Apologies in advance if I turn out to be full of it.

HolIgor: In computer go the city block metric is called the Manhattan distance. I think that an additional characteristic that is the multiplicity of paths can make the mathematical description better. Both kosumi and ikken tobi have the same Manhattan distance but kosumi has two paths while ikken tobi has only one. Kosumi is stronger.

Daniel: I have actually have been working on some odd variants of the distance metric based off of a formula for something known as the super ellipse; essentially D=(X^N+Y^N)^(1/N) (yes the nth root) as n increases beyond zero the value returned comes closer and closer to returning equipotential lines in the form of squares radiating outward (more information on super ellipses can be found at wolfram mathworld (they have their own site) essentially the important point is that using something along the lines of this as a distance metric rather than Manhattan distance or Euclidean distance would rate a kosumi as being superior to a ikken tobi while depending on the n you chose rating it as worth slightly less than a stand myself I like how n=32 works out for me with the computer go AI I am working on.

Adjusted Length Analysis last edited by on January 6, 2012 - 07:00
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Login / Prefs
Sensei's Library