Re: computer-go:life and death

[Daniel Bump <bump@xxxxxxxxxxxxxxxxxx>]

Tim Klinger wrote:

> A life and death problem is *correctly solved* by a program iff the
> program finds a tree of moves representing the program's moves and the
> player's counter-moves, recursively, which leads to positions that are
> statically solvable.  Such a tree is in effect a "proof" of the
> correctness of the result under the assumption that the moves considered
> at each ply include one that does indeed work when such a move exists.

Such a goal is not realistic in every situation. Some life and
death problems, particularly in fluid open board positions,
the move tree might be of such complexity that finding a subtree
giving a rigorous proof of the correctness of an evaluation may
not be possible. There may not be a such a subtree which is not
prohibitively large.

Nevertheless current programs attempt with some success to find
subtrees of the move tree to support the evaluations they
arrive at.

David is right that the example Tim gives seems to show that
he underestimates what current programs can already do.  In my
opinion the claim (on p.4 of the paper) that ``such an analysis
is beyond current go-playing programs ...'' is demonstrably false.

In the position Tim gives recent (2.7.238) GNU Go correctly
evaluates the status of every group on the board and gives F1
attacking the sole unsettled group as the best move. (Assuming W
to move.) This is quite an easy position.

> For example, even in the problems that our program ultimately failed to
> solve because of missing or incorrect domain knowledge, the "analysis" or
> structure that represented the problem at hand -- the fact that
> successfully capturing one block, would allow save another for example --
> was still correct. My conclusion that current programs do not do this kind
> of analysis comes from the lack of any published literature to the
> contrary, my discussions with you and other authors of strong programs, as
> well as the general conversation on this list.

Certainly every program must deal with inferences of the sort
``capturing one block will save another'' in their evaluations.

Of course this does not affect the obvious merit of Tim's thesis.

Dan