RE: computer-go: Live or Die

[Jean-Pierre Vesinet <jvt@xxxxxxxxxx>]

I believe the best (and only ?) way to do this is to use the classic
Benson's criteria. They recognise static life (stones that can't be captured
even if the attacker plays an unlimited number of moves while the defender
tenuki). They can be elegantly worded in a recursive way, and their main
advantage is to use only a static algorithm (no game tree search is needed).
The proverbial two eyes are expressed in mathematically accurate terms as
two adjacent safe regions.

Of course the recognition of static life is only used when a "deep" search
is done, or in goal driven search. But they are absolutely necessary for
_exhaustive_ game tree search, to recognise regions that are (terminally)
settled. Statically alive stones are also useful for splitting the game in
several independent games.

"Common" extensions of Benson's theories cover static recognition of L&D
under alternate play. No one has found a way to check this _in general_
without searching the game tree. Also, I don't know any way to statically
recognise seki positions.

Martin Müller has published some of these techniques under his "Playing it
safe" paper, available from
http://www.aist.go.jp/ETL/etl/suiron/~mueller/publications.html. The
concepts of regions, surrounding stones, potential eye space, etc. are not
too well defined IMO, but the ideas are nice. Anyway this gave me some good
ideas for experiments on static algorithms.

I would like to read other papers on Benson's theory extensions to alternate
play, or any other way to ensure a region is settled or unsettled. I know
some exist, but have they ever been published ?

Regards,
Jean-Pierre Vesinet

--
> -----Message d'origine-----
> De:	Yu Jiang [SMTP:YuJiang@xxxxxxxxxxxxxxxxx]
> Date:	mercredi 24 novembre 1999 09:41
> À:	go
> Objet:	computer-go: Live or Die
> 
> Judging if a string surrounded by opposing part's stones is alive or dead
> is
> such a difficult job.
> the basic problem is: how to distinguish a string's "eye"?
> someone can give a good way?
>