RE: computer-go: NP-complete problems solved?

["Sai To Wang" <stwang@xxxxxxxxxxxxxxxxxxx>]

> > 
> > As far as I know, GO si PSPACE-complete without Ko and 
> > is EXPTIME with Ko.
> 
> What does it mean "Go without ko"?
> As I understand, if the ko rule is simply discarded, the game tree of
> course grows.
> 
> bye 
>     Rafael Caetano <rcaetano@xxxxxxxxxxxxxxxxx>

What I meant of "without Ko" is: no Ko sequence is legal, in the 
other word,.. one stone group (string) on the same board position
cannot be captured more then once. So the game tree will be a
strict sub-set of the "with Ko" game tree when all other rules are
equal.

Wang Sai To
[wangsaito@xxxxxxxxxxxxxxxxx]