Considerations around captures and playing on previously occupied spots, including Ko fights, are quite complex and they are indeed behind the EXPTIME-hardness of Go (Robson's result).
On the other hand, there are meaningful strategic choices to be made even in the ladders or first-capture go cases. Unlike ko-fights, these aspects are not difficult enough to lead to EXPTIME-hardness, but they are enough for PSPACE-hardness. The paper by Crâşmaru and Tromp shows that Ladders are PSPACE-hard and Section 3.4 in https://hal.inria.fr/hal-01256660/file/gocomplexities_draft.pdf tackles first-capture go. (NB: the proof in this paper of ours is flawed, but I'm confident it could be fixed if one spent the time, and hopefully the approach as currently described can give you intuition in why ko-fights may not be necessary for PSPACE-hardness) Abdallah 2018-06-18 23:19 GMT+02:00 uurtamo <uurt...@gmail.com>: > 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 >
_______________________________________________ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
