Re: computer-go: perfect play

["Vlad Dumitrescu" <vladdu@xxxxxxxxxxx>]

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

Just a thought. You are right here, but there's no true contradiction
either.

"Knowledge of the full game tree" does not necessarily involve having all of
it available at any time. Should the search be depth first, one could stop
when finding a winning move, yes. But the point is that one has to be
prepared to search the whole tree anyway, because there might not be any
winning move at all.

/Vlad