Re: computer-go: perfect play

[Robert Jasiek <jasiek@xxxxxxxx>]

Mark Boon wrote:
> > GoDevil of an opponent p is a non-deterministic automaton
> > that plays go according to given rules optimally in the
> > subtree of the complete game tree that is given by
> > using only those choices of p he might choose.
> Sorry, I don't understand the definition of the GoDevil here at all. Can you
> elaborate?

An opponent p is given.
For each situation p considers only a subset of all legal moves.
This is his choice for every situation. So we take the complete
game tree, search the current situation (together with its superko
move history, e.g., the situation is a well-defined node in the
complete game tree), consider all edges to the situation node's
childs, keep only those edges that correspond to p's subset 
consideration (the choice of moves p considers), and cancel all
edges (together with their subtrees below) of those remaining edges
that do not correspond to p's subset consideration (i.e. moves that
p does not consider).
GoDevil knows p, so he knows what p considers in each theoretically
possible situation. Thus GoDevil can prune the complete game tree
as above. He then plays perfectly within the pruned tree.
Pruning takes place only for nodes of p's colour, not for any
nodes of GoDevil's colour. Thereby p's options are restricted but
GoDevil still analyses all his options.

> Also, why non-deterministic for the GoGod?

We speak of automatons. Non-deterministic means that GoGod's algorithm
has a constant running time. He analyses the complete game tree as if
it were a table (mapping a situation to possible moves) of constant
size.
A deterministic automaton (or algorithm) would be in EXPTIME, etc.

If GoGod has more than one perfect move option for a situation, then it
does not matter much, which he selects. If you want to make that
deterministic, then enumerate the coordinates from 1 to 361 and let
GoGod choose the minimally indexed coordinate among all perfect move
coordinates.

--rj