Entropy of capturing value

    Keywords: Theory

KarlKnechtel's idea for unifying liberty and eye counts; possibly a useful heuristic for computer programs.

Motivating forces:

  1. A group with two eyes is alive because there are zero ways to capture it.
  2. A live group effectively has an infinite number of liberties when it comes to a semeai, because of its uncapturability.
  3. A group with n liberties can have its liberties filled in at most n! different ways (orders).
  4. For calculations of entropy - converting a number of states to an amount in 'bits' of entropy - taking logarithms is often useful. It happens that ln(n!) is approximated closely by (n * ln n) - n.
Tom: Being picky, ln((n-1)!) is more closely approximated by that.

Are you sure? I have

   n! =~ (n/e)^n sqrt(2*pi*n)
ln n! =~ ln((n/e)^n) + ln sqrt(2*pi*n)
      =~ n ln (n/e) + (ln n)/2 + ln(sqrt(2*pi))
      =~ n (ln n - 1) + (ln n)/2 + ln(sqrt(2*pi))
      =~ n ln n - n + (ln n)/2 + ln(sqrt(2*pi))

--KK


Funkybside: Tom, maybe for small n, (which is all you could ever dream of verifying on a calculator lol). For large N, which is the whole purpose of using this approximation:

               n! ~= n ln(n) - n + ln(n)/2 + ln (sqrt(2*pi*N)).

This is known as Stirling's approximation.

For more information see : [ext] http://hyperphysics.phy-astr.gsu.edu/hbase/math/stirling.html


Tom: Formulas can be confusing (for me at least), there are generally a number of different forms you can re-arrange them into. If you want to talk about these things properly, I'm afraid it is necessary to state what you want to say more precisely, which involves tedious "mathematical analysis", which I hate. As an alternative, if you have a calculator, you can check which approximation is closer on some numbers.

I already have. I designed the formula so that the final result would be close to linear for eyeless groups, which it is.

Therefore I define the entropy of capturing for a string with n liberties as

(n * ln n) - ln c(n)

where c(n) is the number of ways in which the stones can be captured, without intervention. Thus this measure will be the same for all eyeless groups with the same number of liberties, and (of course) infinite for all groups with two eyes.

This is the rawest sort of value along these lines that might used, e.g. in trees for CGT-style game analysis. One might also consider "entropy of capturing without self-atari", "entropy of capturing with best alternating play" (the result coming out of CGT analysis of raw EoC - I think), and so on. "Entropy of capturing without self-atari" I think may be most useful for heuristics when the situation cannot be fully read out.

[Diagram]
Example  

One of the inside liberties must be last when White fills without opposition; once that is specified, the other seven liberties may be filled in any order. Thus the EoC is 8 ln 8 - ln(4*7!) =~ 6.72408. For reference, 9 liberties with no eye yield EoC =~ 6.97319; 8 liberties with no eye yield EoC =~ 6.03093. So this is a very flimsy sort of illustration of four is five.


Sebastian: Interesting idea. Remarks:

  • The usual letter for entropy is S. How about calling it Sc?
  • The rawest definition would simply be S = ln(n!). Why are you adding n - ln c(n) ?
Yes, it seems I messed up the terminology. Good call. The correction is intended to keep things linear for a "simple" set of liberties, where c(n) =~ n!.
  • I currently can't see how this entropy could effectively be combined with the one in footnote 4 of TemperatureAndTerminologyDiscussion.
  • Counting liberties and four is five are already helpful concepts. Does this new concept help to go beyond that?
See below.

Bill: Indeed, an interesting idea. :-)

Not to be a wet blanket, but don't you get the same result for this position?

[Diagram]
Example?  

The problem, OC, being that Black is alive.

RafaelCaetano: If I understood the definition correctly, in this case Black has an "infinite" number of liberties. Either entropy isn't defined for this group or (equivalently?) it's infinite. So, no, you don't get the same result. :-)

Bill: I was relying on the phrase, without intervention. :-)

Karl Knechtel: The idea is that you build a game tree with the EoC at each node. Since the plays at a are miai, the algorithm finds that there is always a way to bring the EoC up to infinity.

But I misrepresented myself I think; I imagine that this is more useful as a heuristic for use in analyzing running fights and semeai in the centre. E.g. if the computer algorithm tries to search 10 ply of the game tree and gets to a point where it's still complicated, then the algorithm could use the EoC as the value at that "leaf", and propagate up/do alpha-beta pruning/whatever. :)

Bill: Thanks for the clarification, Karl. :-)

But now I do not understand without intervention, when you build game trees. In particular, four is five is derived from the game tree.

I really should have picked a better example, except then it might not have been so clear what I was talking about. Maybe a group where several approach moves are required to capture, would make a better illustration?

"Without intervention" in the context of a game tree means (to my thinking anyway) without further intervention beyond that node. Again, the "without self-atari" version might be more useful, especially with those approach-move-required situations.



Entropy of capturing value last edited by hotcoffee on June 9, 2005 - 11:29
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
RecentChanges
StartingPoints
About
RandomPage
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Goproblems.com
Login / Prefs
Tools
Sensei's Library