RE: [computer-go] Designing faster, better influence functions

["Mark Boon" <tesuji@xxxxxxxxx>]

It all depends on what you want to use it for. Generally influence is used
for a variety of things. Usually it's used to determine territory,
eye-space, groups, moyo etc... I don't think there exists such a thing as a
'perfect' influence function. What is important is to have an indication to
what extent points are influenced by either side. The rest is a matter of
interpretation. And that's where the hard part starts.

To me, your definition of ownership is pretty useless. But that's because it
doesn't fit how I'd want to use it. But for you it may be OK.

The influence function in the TSGL is very similar to an 8-step Zobrist
function. The reason it's not clear from the code is that the code is not a
straightforward implementation. I published how it works in the Computer Go
Journal a long time ago. It's a bit complicated, that's why it's not
documented in the code itself. The essence is anyway that it just computes
influence, and not any interpretation you may give to it later, like
eye-space or ownership. What the function does is calculate the influence of
a new position based on the influence of an already computed position (which
doesn't need to be similar). Since only affected points are processed, this
provides tremendous speed-up, especially when the board gets fuller and the
number of affected points stays small. Of course the more the position is
like the one for which the influence was computed previously, the faster.
Even in the worst case scenario, where the two positions are completely
different, does it perform as good or better than the straighforward
implementation. It means I the option of not having to store state when
doing lookahead because it takes about the same time to compute the
influence for a position with a (say black) stone at point B, based on
influence where the move was first played at point A as it would computing
the influence from a position without the black stone. Provided move A and B
are close to each other, which in practice is very often the case.

I have no idea how many microseconds it takes. I always tested it by playing
through a set of 10 games and adding up total computation time. So it
reflects a real-world case and you get both the performance early in the
game and later in the game. If you want to know how your method compares to
mine, write a little test, all you need is in the library :) But anyway it's
not clear what speed comparisons would mean. I can think of influence
functions that are much faster to compute than the one I have, but that are
simply not useful to what I want to do with it. If however someone would
find a faster way to compute 8-step Zobrist influence, I'd be very
interested to see it.

> -----Original Message-----
> From: computer-go-bounces@xxxxxxxxxxxxxxxxx
> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx]On Behalf Of Frank de Groot
> Sent: Saturday, October 30, 2004 14:35
> To: computer-go
> Subject: [computer-go] Designing faster, better influence functions
>
>
> This is the output of my "ownership" function:
>
> http://www.moyogo.com/Influence.gif
>
> On the right, output from a "Bouzy" function with "influence" and
> "territory", on the left the same position but my function's
> "likely owned"
> estimation.
>
> The idea is not to have (like Bouzy's 5/21) "inner influence ("territory")
> and "outer influence" ("Moyo") but to have a single estimation of
> what will
> pretty certainly become "owned" by a color (occupied by its
> stones or as its
> territory).
>
> My "ownership" function has a cutoff treshold for "inner" and "outer"
> influence but I simply discard the "outer" influence (it is not
> displayed in
> the GIF) as I prefer to classify points in:
>
> - Pretty sure W
> - Pretty sure B
> - Undecided
>
> Bouzy has 2 more:
>
> - W influenced
> - B influenced
>
> My function classifies half of Bouzy's "influenced" as "pretty
> sure B/W" and
> half as "undecided".
>
> I will disclose how my function works, as I did not find it in literature
> (Mark Boon's influence function is AFAIK not ducumented). It took
> only a few
> hours to design & code but it contains a few parameters that I spent hours
> tuning to get results similar to Bouzy's. I could have put all
> parameters in
> a loop and find the best parameters to exactly copy Bouzy's
> results but that
> was no the objective.
>
> My "ownership" function treats stones as magnetic monopoles and
> the edges of
> the board as field-conducting metal. For every empty point, I
> calculate the
> resulting magnetic field. So I do not have interfering wavefronts, I work
> with field strengths.
>
> I found some references to "magnetic field strengths" between stones but I
> read this just now, after I coded up my influence function :)
>
> http://senseis.xmp.net/?MagneticStonesIdea
> http://senseis.xmp.net/?MagneticStonesExampleGame1
>
>
> This function takes 578 uSec (microseconds) to do for a whole
> 19x19 board on
> a 2 GHz Athlon XP, and it takes 85 uSec to delta-update a move,
> non-optimized (it can be sped up by at least a factor of 20).
>
> My questions are:
>
> - How does this speed compare to your implementations of Bouzy's 5/21 or
> your own implementations,
>
> - Does my function look reasonable (I am not a Go player..)
> The sole black stone on the right edge is not guaranteed
> territory, but what
> is most important is that the overall balance is correct. That black stone
> does not signify "territory", it means that on that part of the
> board, there
> will be at least 1 black stone or at least 1 black territory point. For
> white, there is no such "guarantee" (with optimum play of both).
>
> - What do you think about doing away with the difference between
> "moyo" and
> "almost certain territory" and instead trying to classify more of
> the "moyo"
> into "territory"?
> I am less interested in "sphere of influence" than I am in "will
> become B/W
> when vigorously defended". The least ambiguity, the better?
>
> - Does any of you use an influence function in a tree search or
> do you limit
> it to the first ply?
>
> _______________________________________________
> computer-go mailing list
> computer-go@xxxxxxxxxxxxxxxxx
> http://www.computer-go.org/mailman/listinfo/computer-go/
>

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/