(recommended font=courier 8, so the diagrams will be readable)
Hi -
There have been more than a few comments about how GNU Go could use more full-board strategy. I've been investigating how an influence mapping function might be optimized for making full-board strategy decisions. Perhaps there are some of the ideas here that would be useful, and not too costly to implement.
The influence drop-off I'm using is a simple linear function, starting with a value of 8, and decrements by one for every move away from the stone. All other stones (both colors) are considered opaque (blocking influence) and all unplayed points are allowed to be transparent (allowing influence). It is very simple to program and quick to execute.
The only complication I add is that the influence is allowed to reflect back onto the board at the board edge. The purpose of this is to compensate for the fact that a stone near the edge may not reach as many points on the board, but it tends to have a greater impact on the points it does reach. One consequence is that the influence evaluation does not bias play towards the center of the board, as it might otherwise. Rather, it is mostly sensitive to the relative positions of other stones.
The goal, where strategy is concerned, is to have some sort of consistent correspondence between influence values and the realities of the game. For example, if a point is directly surrounded by 3 stones, it has a value of 24 (3x8). A key question is whether OTHER points that have a value of 24 are roughly equivalent: in other words, if the player makes a single play, the point will become secure territory, for all intents and purposes.
Here is another conjecture that would follow (if the model is successful). A point that is surrounded on two sides has a value of 16. Theoretically, an opponent can play there "safely" as there are two free sides that can serve as escape routes. Thus, an influence value of 16 should generally indicate approximately the upper limit of what might be a safe, non-sacrificial play.
It is also kind of interesting that given the uniform drop-off slope of all stones, the slope (simple difference in influence value between two points) itself becomes a source of information: the larger the slope, the greater the opposing thicknesses.
Perhaps a diagram will help illustrate. This example is from Chris Matthew's "Teach Yourself Go".
The fact that the lone White stone at L17 is surrounded by positive numbers is a prime indication that it is weak. But as none of the values are greater than 8, the situation is not dire. (Perhaps one can use a test of these influence values bordering a group as a quick means of determining a safety threshold that triggers an Owl search rather than relying on the cache to be correct.)
As for Black, we know a pincer play (ignoring the bottom half of the board) at N17 (influence value of 3) makes more sense than an approach at J17 (influence value of 16). A general rule could be, given two equal choices, to prefer the lower value (from Black's perspective) as long as it is not lower than -16. (At that point, one is probably approaching opponent thickness rather than framework, and this is generally of little use.)
The high slope (J17-K17=8) also indicates (without examining any other points on the board) that a play there would be backed by greater thickness and would over-concentrated relative to a play at N17 (slope of 2).
When comparing possible plays, one can compute an aggragate influence amount for each play and pick the highest. However, in doing so, one should compensate for the fact that any play that raises an influence value of 24 or greater (for a Black play) to a higher value is worthless, if indeed this value indicates there is already sufficient force such that an opponent play on the point is as good as captured with a single reply. With this "filter function," I've tried a couple example positions and the program has correctly selected the junction point given in the supporting analysis of the position.
Rin Kaiho vs. Akira Ishida, from Ishida's "Attack and Defense"
19: . . . . . . . . . . . . . . . . . . .
18: . . . . . . . . . . . . . . . . . . .
17: . . . O X X . . . . . . . . . . O . .
16: . . O * O X . O . * . . O . O X O . .
15: . . . O X . X . . . . . . . . O . . .
14: . . . O X . . . . . . . . . X X . . .
13: . . . . X . . . . . . . . . . . . . .
12: . . O . . . . . . . . . . . . . . . .
11: . . . . . . . . . . . . . . . . . . .
10: . . . * . . . . . * . . . . . * . . .
9: . . . . . . . . . . . . . . . . . . .
8: . . O O O X . . . . . . . . . . . . .
7: . . X O X X . . . . . . . . . X . . .
6: . O O X O X . . . . X X . . . X . . .
5: . O X X . . . . . O O X . . X O X X .
4: . X X X . . . . . * X O O O O O X O .
3: . . O . . . . . X . X X O . . . O . O
2: . . . . . . . . . . . . . . . . . O .
1: . . . . . . . . . . . . . . . . . . .
a b c d e f g h i j k l m n o p q r s
19: -14 -18 -11 0 11 17 19 12 7 0 -9 -16 -19 -19 -21 -20 -26 -25 -23
18: -18 -18 -13 -4 10 17 18 10 6 -2 -7 -12 -20 -20 -22 -21 -25 -29 -25
17: -30 -30 -24 W B B 18 10 7 0 -5 -11 -16 -18 -20 -18 W -28 -27
16: -36 -37 W -32 W B 18 W 8 2 -6 -11 W -15 W B W -26 -24
15: -39 -38 -38 W B 29 B 15 12 4 -2 -8 -11 -11 -11 W -15 -19 -18
14: -37 -38 -37 W B 24 25 21 17 12 7 1 -6 -7 B B -8 -8 -9
13: -32 -33 -28 -19 B 17 21 17 16 11 9 3 -3 -4 3 1 -1 -3 -3
12: -34 -34 W -15 -3 9 13 11 9 7 6 5 1 1 8 7 6 5 1
11: -33 -31 -23 -17 -4 9 13 9 9 6 8 7 7 7 14 15 13 10 7
10: -31 -33 -27 -18 -3 9 11 9 10 8 9 12 11 14 22 22 19 15 12
9: -32 -32 -28 -21 -5 7 12 10 13 11 14 15 17 20 30 28 24 21 16
8: -32 -30 W W W B 20 20 23 23 24 24 23 27 33 34 30 26 21
7: -28 -25 B W B B 26 29 34 32 32 29 26 26 32 B 32 28 23
6: -27 W W B W B 28 32 37 33 B B 22 23 29 B 30 27 22
5: -22 W B B 21 25 28 33 34 W W B 18 19 B W B B 14
4: -15 B B B 22 27 31 34 35 32 B W W W W W B W 2
3: -14 -8 W 13 17 25 28 29 B 29 B B W -36 -46 -54 W -32 W
2: -9 -1 2 10 18 24 28 28 25 19 11 -1 -19 -34 -47 -56 -61 W -56
1: -9 -3 2 12 16 22 26 25 24 21 13 -1 -20 -38 -52 -62 -67 -69 -65
a b c d e f g h j k l m n o p q r s t
I'm curious what people think of the numbers that are being generated, if they seem to have a useful consistency I was discussing.
I ran a comparison of plays on all points by both White and Black, and the point with the greatest difference was L13, which happens to be the same point Ishida spoke of as the junction point in his analysis of the position. Unfortunately, I still have to write some code to allow me to output the results to a file so I can print them for you. But I won't be able to get to it for a few days.
One thing to keep in mind is that the goal is to find ways to encourage some very basic strategic play (finding junction moves; attacking from framework--not thickness; quick evaluations of relative group safety) and so the needs for precision are considerably less than the influence algorithm currently being used to determine accurate point counts, and local combat.