Re: [Computer-go] Paper “Complexity of Go” by Robson

Hi Mario, > 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/ I am very interested in such a project; please let me know about your progress! I don't know

Re: [Computer-go] Paper “Complexity of Go” by Robson

I've eventually managed to create a problem that should show a full reduction from a Robson problem to Go - I hope is correct. The Problem: https://drive.google.com/file/d/1tmClDIs-baXUqRC7fQ2iKzMRXoQuGmz2/view?usp=sharing Black just captured in the marked ko. How should White play to save the

Re: [Computer-go] Paper “Complexity of Go” by Robson

My understanding: ko fights will take this to (at least, I haven't seen the EXP argument) PSPACE. no ko fights and no counting (i.e. first capture) could put this in P. s. On Mon, Jun 18, 2018 at 3:21 PM John Tromp wrote: > On Mon, Jun 18, 2018 at 10:24 PM, Álvaro Begué > wrote: > > I don't

Re: [Computer-go] Paper “Complexity of Go” by Robson

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

Re: [Computer-go] Paper “Complexity of Go” by Robson

On Mon, Jun 18, 2018 at 10:24 PM, Álvaro Begué 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 Ko fights are needed to take Go problems beyond PSPACE. For Japanese rules they suffice to go

Re: [Computer-go] Paper “Complexity of Go” by Robson

On Mon, Jun 18, 2018 at 10:30 PM, Marcel Crasmaru wrote: >> 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:

Re: [Computer-go] Paper “Complexity of Go” by Robson

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é wrote: > I don't think ko fights have anything to do with this. John Tromp told > me that ladders are PSPACE complete:

Re: [Computer-go] Paper “Complexity of Go” by Robson

> 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

Re: [Computer-go] Paper “Complexity of Go” by Robson

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 wrote: > FWIW, first-capture go (i.e. winner is first one to make a capture) should > not be

Re: [Computer-go] Paper “Complexity of Go” by Robson

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

Re: [Computer-go] Paper “Complexity of Go” by Robson

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 wrote: > Errata: > reduction from GO to an EXP hard problem

Re: [Computer-go] Paper “Complexity of Go” by Robson

Also - a downloadable link: https://drive.google.com/file/d/1tLCYr74UwVQsXAE2QrcwrGALIduH34b8/view?usp=sharing --Marcel On 18 June 2018 at 19:35, Andries E. Brouwer wrote: > On Mon, Jun 18, 2018 at 11:54:51AM -0500, Mario Xerxes Castelán Castro wrote: >> Hello. I am asking for help finding

Re: [Computer-go] Paper “Complexity of Go” by Robson

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

Re: [Computer-go] Paper “Complexity of Go” by Robson

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 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

Re: [Computer-go] Paper “Complexity of Go” by Robson

On Mon, Jun 18, 2018 at 11:54:51AM -0500, Mario Xerxes Castelán Castro 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

[Computer-go] Paper “Complexity of Go” by Robson

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: