Influence function

Most Go programs use an influence function to segment the board into black and white territory.

It was introduced by Albert L. Zobrist as part of his PhD thesis on "Feature Extractions and Representation for Pattern Recognition? and the Game of Go." Graduate School of the University of Wisconsin, August 1970.

Subpages

• I have created a script that tries to represent influence visually. By no way a scientific approach :) (louismeckes)
  • see InfluenceMap
  • see also Goblob http://lyon-shinogi.jeudego.org/go_blob/, particle-based influence propagation
• WaveFrontAnalysis
• Bouzy Map
• AlbertLZobrist

• Influence influence in general

See Also

ComputerGoAlgorithms

See "Score/Influence/Territory/Moyo Estimation" section

Discussion

I understand computer programs sometimes use an influence function to determine how much influence a given wall or other shape projects over the board. I was hoping to get some insight into what these look like.

Gorobei: I was mucking about with territory/influence maps today. Here's a BouzyMap

Are they a matter of assigning a value to the shape itself or computing numerical values for the influence of a shape at various parts of the board? For example, "the White wall creates 50 units of influence at the tengen, but only 15 at the side star region, and 5 near blacks thickness in the opposite corner" vs. "White's seven stone wall on the fourth line is worth the equivalent of 25 point of territory at this stage of the game". I think there might be room for both lines of thought. there is some merit in think of a stone as projecting influence like an electromagnetic field. The analogy is apt in that it helps one understand various concepts like:

1. In trying to reduce territorial frameworks it is often good to play on the sector line . One can overplay the sector line a bit if one's formation is stronger. See Attack and Defense by Ishida and Davies for an explanation. This makes excellent sense if one thinks of one's own stones and the opponent's as having opposite electric charges proportional to their strength.

2. Walls are very different from territorial frameworks. It is often a good concept to drive enemy groups right into one's wall whereas one would never wish to encourage the opponent to drive a spike through a framework. A wall can have a more significant effect on fights elsewhere than just a framework of friendly stones in that part of the board. This reminds me how, in the three dimensional world of physics, an electric field from a charged point or line will die off with distance, but a charged plane will cause a field which is constant in strength everywhere. Of course, with something like a capacitor plate there are edge effects, so the field will look constant in close-up and like an inverse square far away. This is somewhat similar to the effect of a wall in Go.

KarlKnechtel: Indeed, I often like to think in terms of CapacitanceAndResistance when trying to find the right move. :) The usefulness seems limited, though.

The field concept is not very useful when dealing with ladders, because these are a discrete tactical concept specific to Go, and the precise positioning of the stones matters. Generally, one should never try to substitute analogies or vague concepts, where reading out possibilities precisely is possible, but rather to guide one's intution. In accordance, another place where the field concept fails is when a wall has defects, or its life is in question. I don't believe I have ever had the experience of driving a group against a wall and then killing my own wall in the process (see WallDeath), but I tend to play very thickly and sometimes use walls for moyos instead. Nevertheless, I hear walls do die! Most importantly, the analogy fails in suggesting that an enemy wall should attract your stones! Neither side should play close to a wall, except to extend it or to forestall further extension of it. Otherwise, playing near a wall is inefficient for its owner and dangerous for the enemy.

Can that be considered a "tactic" per se, slamming an enemy group into a wall and killing your wall in the process? That seems like an awfully large loss - 15 stones +? -- lavalyn

To answer your question, I have heard of people killing their own wall and still winning, but I would not think of it as a tactic. I was submitting it as an example of a mistake which one should avoid, and one which isn't really covered by the idea of stones generating a "field" on influence.

Kjeld Petersen: The BouzyMapping does have one big disadvantace. There is no area with mutual influence. As long as the game is going on all boundaries are not drawn yet. And if you think of only 2 stone placed on a board say on the fourth line and with distance of say 3 spaces. It is not possible to say at the early stage of the game who will actual get the space in between, or even if the one or other will get the area close aroud there stones. So by my opinion is that there should be mutual influece (more or less) in the space between the 2 stones. And the stones should even have influence past the others. On the page Manhattan distance there is a picture of a stone with distance 9, witch wraps around a opponent wall. So we could say that the single black stone has a influence that wraps around the white wall, but at the same time will the white wall have influence that wraps around the black stone. What need to be defined is what makes the influence to stop. Maybe in what degree. There should be mutual influence instead of influence with boundaries.

w=white influence, b=black influence, m=mutual influence  

Kjeld Petersen: Here is my idea for an influence function: vicinity function

aceofspades: I once was interested in an influence function that, by summing up results from stones over the whole board, would take an early (opening stage) position, with no fights and lots of open space, and give (hopefully) an idea of the relative overall influence each player exerted at a point. Or even if the only vaguely-accurate result was the "difference" between the players' influences that'd be fine too. Anyway, I started from something vaguely like Capacitance and Resistance, thinking of each stone as a point charge in the 2D Goban plane, and the color as corresponding to the sign of the charge. Then the influence on a point is like the field strengh there: I(x,y):C/d^2, where C=+/-1 based on color of the stone, and changing multiplicative constants to 1 so everything is simple. d of course is the distance between (x,y) and the stone exerting the influence. The problem is that I wanted my algorithm to evaluate the influences on a point by "all" stones, including that one, which means that the influence of a stone at its own point is infinite. There are several ways one could bypass this; my weird idea, which people may not think makes any sense, was to take the field strength formula, add 1 to the denominator, and get a (multiple of a) Cauchy distribution instead ( http://en.wikipedia.org/wiki/Cauchy_distribution). Note that AdjustedLengthAnalysis used a variation of Gaussians, which are a p.d.f. like the Cauchy distribution.) Thus we use I(x,y)=C/(d^2+1), again retaining the form of the equations while leaving everything as simple as possible. The rest of the way is mostly straightforward. To determine the influence of a player at some point, we first sum up the influence exerted on that point by each of that player's (live) stones, including a possible stone at that point itself. Now, say this sum equals S. The main problem so far is linearity: stones reinforce each other. The influence of two stones is more than twice the influence of a lone stone; there is some influence that comes from the connection and reinforcement these stones provide for each other. My second significant idea was a very brute way of making the function nonlinear: add a quadratic term with some unknown constant. In other words, if before the influence was S=Sum(i=1 to 361, C/(d(i)^2+1)), we now take S+C*cS^2, where c is some unknown positive number that controls how strong the grouping effect is (the factor C=+/-1 is added to make the squared term have same sign as the linear one). Finally, in case one is considering varying board sizes, I believe that in general - at least for normal size range - it is reasonable to take influence as inversely proportional to number of board points. Consider for example that a tengen play in a 9x9 board has a strong effect and can often be a good move, but tengen in a 19x19 is quite weak in terms of influence on other points. So, with the assumption that we don't want an extra factor for the 19x19 standard board, we have ((N/19)^2)*(S+cS^2). Calculate this number for each player and compare (you can add the two together, since they have opposite signs representing opposite charge). The End. I have no idea whether this is very stupid or somewhat interesting. I am curious though to see whether choosing moves based on this influence function could give reasonable opening moves, after finding a good value for the nonlinearity parameter c. Or whether the function was okay at predicting which player would, say, win a corner. One may possibly want to add another parameter, which is actually present in the general Cauchy distribution function - a factor in front of the distance so that the influence tapers off more slowly or quickly. On a further note about possible revision, there is the problem that as the influence grows, the quadratic term grows dominates the linear one, and could theoretically grow unboundedly many times greater than it. I think this is unrealistic; the nonlinear effect has to be bounded or slowed down some way. One possibility is to replace the quadratic term with an O(n log n) term. This doesn't make the nonlinear term bounded, but it does make it grow slower. If one wants a bounded nonlinearity, one could replace the quadratic term with some rational function like C*aS^2/(b|S|+1). This would account for the fact that as stones become overconcentrated, their proximity is no longer as useful.