Ko fights are the thing. Ladders are hard, but without ko fights I'm pretty sure it's not even PSPACE-complete.
Steve On Mon, Jun 18, 2018 at 1:52 PM Álvaro Begué <alvaro.be...@gmail.com> wrote: > I don't think ko fights have anything to do with this. John Tromp told > me that ladders are PSPACE complete: https://tromp.github.io/lad.ps > > Álvaro. > > > > On Mon, Jun 18, 2018 at 2:58 PM, uurtamo <uurt...@gmail.com> wrote: > > FWIW, first-capture go (i.e. winner is first one to make a capture) > should > > not be PSPACE-complete. > > > > the thing in go that makes it hard is ko fights, which don't exist in > > capture go. > > > > s. > > > > > > On Mon, Jun 18, 2018 at 11:55 AM Marcel Crasmaru <crasma...@gmail.com> > > wrote: > >> > >> Errata: > reduction from GO to an EXP hard problem > >> > >> should be the other way around :) > >> > >> --Marcel > >> > >> On 18 June 2018 at 19:36, Marcel Crasmaru <crasma...@gmail.com> wrote: > >> >> 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 the gist of it from a very early > >> > draft of my master thesis > >> > - I used Robson's idea of reduction from GO to an EXP hard problem > >> > using ladders instead of pipes (he used groups > >> > connected through long string of pieces, aka, "pipes") > >> > > >> > If you have related questions I am happy to answer them although John > >> > Tromp might have even better insights - ask him too. > >> > > >> > Best, > >> > Marcel > >> > > >> > On 18 June 2018 at 17:54, Mario Xerxes Castelán Castro > >> > <marioxcc...@yandex.com> wrote: > >> >> Hello. I am asking for help finding the following paper: > >> >> > >> >> J. M. Robson (1983) “The Complexity of Go”. Proceedings of the IFIP > >> >> Congress 1983 p. 413-417. > >> >> > >> >> I could not find it online. There is no DOI anywhere to be found (I > >> >> searched Crossref and here: > >> >> https://dblp.uni-trier.de/db/conf/ifip/ifip83.html#Robson83 ) and > the > >> >> conference proceedings are not in Library Genesis either. > >> >> > >> >> Thanks in advance. > >> >> > >> >> > >> >> _______________________________________________ > >> >> 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 > > > > > > _______________________________________________ > > 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
_______________________________________________ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
