Re: computer-go: perfect play

[Heikki Levanto <heikki@xxxxxx>]

John Aspinall <jga@xxxxxxxxxxxxxxxxx> wrote:
> 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. 
>>
>>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 almost agree with you. But not quite. 
It must be possible to prune a search tree, even if we require searches to
go all the way to the end, or at least until provable endgame. If I open at
1-1, and you prove (exhaustively) that capping at 2-2 wins over it, you do
not have to prove any other move. You may want to do so to to get a shorter
and more obvious win, but for the prove it is enough that you win. So, you
can prune your tree by a factor of 359 for the second move.

I haven't read the original paper on math. endgames, but what you say sounds
very much in keeping what others have said, that it is a theory of adding
subgames without a combinatorial explosion. The obvious continuation to it
would be to consider positions where some subgames can be made independent
or need to be considered as one, like in cutting and connecting stones. 

Maybe this can be extended to situations where a move will affect two (or
more) subgames, without affecting the rest. (Say, jumping out with a weak
group affects the group itself, and its two neighbours if they are weak
enough). Of course I realize that there is an awful long way to go before we
can have solid proofs on these lines... And they may well require local
reading in much more depth than is currently feasible.


- Heikki


-- 
Heikki Levanto     LSD Levanto Software Development   heikki@xxxxxxxxxxxxxxxxx
               "In Murphy we Turst"