RE: computer-go: perfect play

["TMCooper" <tmcooper@xxxxxxxxxxxxxxx>]

> >  > *** First, I think it is obvious that perfect play is not
> possible without
> >  > knowledge of the full game tree. This knowledge can be explicit
> >  > or implicit
> >  > (as in "my dad analyzed the position from here and told me
> this is the
> >  > winning sequence"). Even if some shortcut may exist, for it
> to indubitably
> >  > be "perfect" it has to be based on someone's analyze of the
> full tree.
> >  >
> ><snip>
> >
> >Isn't alpha-beta pruning a refutation of this?
>
> Good point.  Though I would say the answer is "no", the important
> stuff is in the nuances.
> A-B pruning depends on having a sufficiently good static evaluation
> function.  If the static evaluation function comes from a heuristic
> basis, this is insufficient for the rock-solid proof we require of
> "perfect" play.  If the static evaluation function comes from
> "compiled" knowledge of previously seen situations, then it depends
> on what knowledge went into the compilation.  So with a sufficiently
> good Go-compiler we could change the answer to "yes".
>
> I think the important point in the original posting is:
> >   ... the full game tree. This knowledge can be explicit or implicit
> Too many postings on this subject wail at the intractable size of the
> EXPLICIT game tree, but make no estimates of how much reduction we
> might get from better IMPLICIT representations.
<snip>

I am suspicious that IMPLICIT here is a bit of a weasel word.

As the original poster pointed out, Combinatorial Game Theory allows us to
simplify the full game tree (In my opinion significantly), particularly near
the roots.  Other simplifications can be gained through a-b pruning, which
does require rigorous bounds on the value of a position, but these are
sometimes easy to get.  Another significant simplification can be had by
noticing that a particular group simply does not have room to live and
therefore must die eventually, for example the eye-stealing tesuji often
leads to this kind of proof in life and death problems.  The independence
(kos apart) of different regions of the board can be used in more general
circumstances than CGT can currently analyze.

All these insights act synergistically and lead to rigorous reasoning that
allows us to ignore large parts of the full game tree.  Of course these
could all be covered by the phrase 'implicit representation of the game
tree' (or perhaps be labeled as technicalities ;)), but then so could a
lookup table that gave a perfect move for every legal position.  I suspect
that it is hard to define an 'implicit representation of the game tree'
naturally, in such a way that :

'it is obvious that perfect play is not possible without
knowledge of the full game tree'

or even that:

it is true that perfect play is not possible without
knowledge of the full game tree

without making the question a tautology.


On a related matter that has come up.  I am no worse than 192 stones worse
than GoDevil or GoGod, if I am allowed to place my stones myself.  My
strategy is to place my handicap stones in a grid (waffle) pattern to fill
rows 2,5,8,11,14 and 17, and the columns of the same numbers.  Then I will
pass unless my big group is put into atari, at which point I will capture
some enemy stones and continue as before.  At the end of the game I will
have a very comfortable win.

I think that this is a proof.  I am sure that others can find much higher
lower bounds for their strength.  Does anyone know of any better ones? Or
can they come up with any themselves?

Tom.