[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: computer-go: perfect play
Robert Jasiek wrote:
> Mark Boon wrote:
> > Also, why non-deterministic for the GoGod?
> 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,
I have mixed too many things here. EXPTIME becomes only relevant on
boards of variable size N, IIUC. For fixed N = 361 even the complete
game
tree is of constant size, of course. Then we have to distinguish the
complexities of finding a solution and of applying it. GoGod applies
a table of constant size (or one table for each node). However, how
do we measure the time complexity for GoGod creating that table?
Traversing the complete game tree of constant size takes constant
time, if expressed in terms of game tree size. Does this make sense
or should we express it depending on N, which is another but smaller
constant? Traversing the tree should be done deterministically.
Presumably more than one best line of play will be found and GoGod
gets more than one possible move for some situations. As said before,
a choice among such moves can be prescribed or done randomly. In
case of the latter do we leave GoGod with an element of choice and
should call his algorithm non-deterministic or must this be called
a deterministic mapping to some set of legal moves? I am still a
little confused with the terminology...
--rj