[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

computer-go: PSPACE complete



At the coming ComputerGames2000 conference in Japan, I'll present a paper
by Marcel Crasmaru and myself showing that Ladders in Go are
PSPACE complete.
Doesn't this mean that even the trivial-looking problem of finding out the result of a ladder (remember the go proverb: "if you don't understand ladder give up playing Go") is computationally untractable, the same as finding the whole game tree?

Sorin

_________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com.

Share information about yourself, create your own public profile at http://profiles.msn.com.