Benson Rules!

[mueller@xxxxxxxxx (Martin Mueller)]

>Recently there has been a number of messages questioning Benson's rule.
>I thought Benson's Rule was proven and is Benson's Proof.  Is it
>actually proven fact or not?  If so, no point in questioning it...

It is proven and true. There seems to be some simple misunderstanding about
the way regions are defined.

Benson's algorithm depends on suicide being forbidden by the rules. A
counterexample if suicide is allowed is easy to construct. One example is
shown in my Ph.D. thesis p.62. In regions where the interior is non-empty
but filled by opponent stones, allowing suicide would destroy the
healthy-ness by allowing these interior points to become empty.

Benson's algorithm finds blocks that are safe even if the opponents gets an
unlimited number of moves in a row. In my Ph.D. thesis and in the GPW'97
article, I have studied some extensions which are less elegant
mathematically, but more useful under the usual alternating play. I needed
them for my endgame solver, which first computes safe stones and
territories and then analyzes the connected components of the rest of the
board. I believe my extensions are also proven and true. (There is one bug
in the dame-finding algorithm as printed in the thesis but this has nothing
to do with the earlier safety calculation.)

>
>Where is Benson's work or complete definition of the rule published?
>

@ARTICLE{benson76,
 AUTHOR       = "Benson, D.B.",
 TITLE        = "Life in the Game of {Go}",
 JOURNAL      = "Information Sciences",
 VOLUME       = "10",
 NUMBER       = "",
 PAGES        = "17--29",
 YEAR         = "1976",
 NOTE         = "Reprinted in Computer Games, Levy, D.N.L. (Editor), Vol.
II, pp. 203-213,
Springer Verlag, New York 1988"}


There is also an older version of the Benson article, reprinted in Heine's
booklet, but this one is better. The other version has a bug which is
mentioned in my thesis, and its algorithm for finding safe blocks is much
less efficient than the later one given in {benson76}.

        Martin