[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

RE: computer-go: perfect play

At 6:35 PM +0100 9/26/00, TMCooper wrote:

<snip>
 > *** 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.

Example: the Conway, Berlekamp sum-of-games theory is about decomposing one game into the sum of independent sub-games. You can only use this theory unconditionally when the games are provably (there's that word again!) independent, and that just about only happens in the go endgame. But underneath the covers, it's not a theory of endgames [*]. It's a theory of a how to add games, WITHOUT forming the (much larger) Cartesian product of their game trees. Voila - reduction in the tree size.

[*] Footnote: PLEASE don't mail me and tell me that the title of Berlekamp's book has the word "endgame' in it. I know. I've got it. If you think I need to be told this, then you have missed the point.

Now suppose we could do CONDITIONAL decomposition into sub-games. E.g. one hyper-branch of our wizzy new representation denotes all games where the choice of move in the lower left corner affects the outcome of the upper right corner, and the other hyper-branch denotes the converse. We can now go to a sum-of-games representation of all games on the latter hyper-branch. With huge savings.

Of course the previous paragraph is highly speculative and naive. Perhaps a serious computational Go theorist, like Martin Müller, can provide a better fantasy. But if what we are discussing revolves around the representational size of a "perfect analysis", then we need to probe a lot harder at the limits to any representation, not just the vanilla one.