RE: computer-go: Live or Die

[Martin Mueller <mueller@xxxxxxxxx>]

>I believe the best (and only ?) way to do this is to use the classic
(B>Benson's criteria. They recognise static life (stones that can't be captured
(B>even if the attacker plays an unlimited number of moves while the defender
(B>tenuki). They can be elegantly worded in a recursive way, and their main
(B>advantage is to use only a static algorithm (no game tree search is needed).
(B>The proverbial two eyes are expressed in mathematically accurate terms as
(B>two adjacent safe regions.
(B>
(B
(BBenson's algorithm is mathematically elegant, but it does not help you that
(Bmuch in practice. If you run it on the test data from my paper you will see
(Bmany obviously alive areas that are not Benson-alive.
(B
(B>"Common" extensions of Benson's theories cover static recognition of L&D
(B>under alternate play. No one has found a way to check this _in general_
(B>without searching the game tree. Also, I don't know any way to statically
(B>recognise seki positions.
(B>
(B>Martin M$B{K(Jler has published some of these techniques under his "Playing it
(B>safe" paper, available from
(B>http://www.aist.go.jp/ETL/etl/suiron/~mueller/publications.html. The
(B>concepts of regions, surrounding stones, potential eye space, etc. are not
(B>too well defined IMO, but the ideas are nice. Anyway this gave me some good
(B>ideas for experiments on static algorithms.
(B>
(B
(BI think it is well-defined :) What exactly do you think is not
(Bwell-defined? For reference, here are the definitions from the paper, as
(Bprinted:
(B
(BThe following terminology for blocks and regions is standard.
(BA {\it block} is a maximal connected set of stones on the Go board.
(BEach block has a number of adjacent empty points called
(B{\it liberties}. A block that loses its last liberty is
(B{\it captured}, i.e. removed from the board.
(B
(BA {\it region} is a connected set of points on the Go board
(Bwhich is surrounded by blocks of the same color.
(BA block is called {\it enclosing block} of a region if it
(Bhas at least one adjacent point that belongs to the region, and
(Bat least one adjacent point that does not belong to the region.
(BThe color of enclosing blocks is called the {\it defender},
(Bthe other color is called the {\it attacker}.
(B
(BThe {\it interior} of a region is the subset of points not adjacent
(Bto an enclosing block.
(BThere may be both attacker and defender stones in the interior.
(B
(B
(B>I would like to read other papers on Benson's theory extensions to alternate
(B>play, or any other way to ensure a region is settled or unsettled. I know
(B>some exist, but have they ever been published ?
(B>
(B
(BThe best currently existing static rules are probably those in Thomas
(BWolf's program. He has written several papers about his program. However,
(Bthere is little detail information about the rules he uses. His focus seems
(Bto be on small areas occurring in Life-and-Death problems, while I worked
(Bmainly on proving the safety of large, well-surrounded areas.
(BI have worked a bit on my program since the GPW'97 paper. I can prove about
(B40% of the areas safe now on that test set. However, there is still lots of
(Broom for improvement. Seki is one area to work on.
(B
(B	Martin