> FWIW, first-capture go (i.e. winner is first one to make a capture) should > not be PSPACE-complete.
Actually this is not obvious. If you are able to replace the White Choice gadget shown at page V in this paper: https://tromp.github.io/lad.ps with an equivalent Go gadget that doesn't capture any stone then I believe you actually prove that first-capture go is PSPACE complete. --Marcel On 18 June 2018 at 20:17, Marcel Crasmaru <crasma...@gmail.com> wrote: > You can also find here one of my attempts to create a difficult Robson > like problem on a Go board but I guess I've run into difficulties and > didn't finish it: > > https://senseis.xmp.net/?Crasmarum%2FStrangeTsumego > > However, it might help you understand how to convert Robson's problem > instances to equivalent Go positions. > > --Marcel > > On 18 June 2018 at 18:42, Mario Xerxes Castelán Castro > <marioxcc...@yandex.com> wrote: >> Thanks you very much, Marcel. I will be reading your thesis. I am >> interested in formalizing results about the game of Go as my next >> project. I have have a repository of computer-verified proofs here: >> https://puszcza.gnu.org.ua/projects/hol-proofs/ Right now I am still >> finishing a formalization of algorithms for handling dates in the >> Gregorian calendar (the ordinary calendar). >> >> Regards. >> >> On 18/06/18 13:23, Marcel Crasmaru wrote: >>> Hi Mario, >>> >>>> J. M. Robson (1983) “The Complexity of Go”. Proceedings of the IFIP >>>> Congress 1983 p. 413-417. >>> >>> If you are interested in how to prove that GO with kos and Japanese >>> rules is EXP complete you can get an idea from my master thesis draft >>> - I used Robson's idea with ladders instead of pipes (he had groups >>> connected through long string of pieces, aka, "pipes") >>> >>> If you have related questions I am happy to answer them. >>> >>> Best, >>> Marcel >>> >> >> >> _______________________________________________ >> Computer-go mailing list >> Computer-go@computer-go.org >> http://computer-go.org/mailman/listinfo/computer-go _______________________________________________ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
