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.ht
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 t
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 GO
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 a
Thanks Andries!
On 18/06/18 13:35, Andries E. Brouwer wrote:
> This is
>
> The Complexity of GO, report TR-CS-82-14, D.C.S., A.N.U.,
> also in: IFIP World Computer Congress 1983, pp. 413-417.
>
> A.N.U. = Australian National University
>
> A scan of this report can be found in
> https://www.lri
Thanks Ingo.
On 18/06/18 13:45, "Ingo Althöfer" wrote:
> Hello Mario,
> the authors of the following paper should be able to help you:
> https://hal.inria.fr/hal-01256660/file/gocomplexities_draft.pdf
>
> Regards, Ingo.
signature.asc
Description: OpenPGP digital signature
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 the
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
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 equ
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 PSPACE-comple
> 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
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: https://trom
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: https://tromp
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 beyond
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 case
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
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 lo
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 a
18 matches
Mail list logo