> _first capture_, no? I think there is some misunderstanding here as in this thread several problems are discussed in parallel.
If by _first capture_ you mean to find an answer to the question "what is the computational difficulty of Capture GO?" then as far as I know no one proved anything yet. Capture GO might be in P but to prove this doesn't look like an easy task. I personally think it is either (1) in P but very hard to prove it, or (2) at least NP hard because, empirically, you may still create few convoluted ladders that don't capture stones and interact to each other in unexpected ways etc. Using loose ladders might be a another way to try building NP hard instances. However, without a proof this assumption is still as valid as (1). I am curious what's John Tromp opinion on the above. (Please note that the problem I've created has nothing to do with Capture GO.) Thanks, Marcel On 19 June 2018 at 13:10, uurtamo <uurt...@gmail.com> wrote: > _first capture_, no? > > s. > > On Mon, Jun 18, 2018, 6:59 PM Marcel Crasmaru <crasma...@gmail.com> wrote: >> >> 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 lower group? >> >> >> > no ko fights and no counting (i.e. first capture) could put this in P. >> >> Not true - please read Tromp et al paper: Ladders are PSPACE hard >> without ko - that is, you can reduce any PSPACE problem in reasonable >> time to a Go problem without kos. >> >> --Marcel >> >> On 18 June 2018 at 22:27, uurtamo <uurt...@gmail.com> wrote: >> > 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 <john.tr...@gmail.com> wrote: >> >> >> >> On Mon, Jun 18, 2018 at 10:24 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 >> >> >> >> Ko fights are needed to take Go problems beyond PSPACE. >> >> For Japanese rules they suffice to go beyond (assuming EXPTIME != >> >> PSPACE), >> >> but for Chinese rules it's an open problem. >> >> >> >> regards, >> >> -John >> >> _______________________________________________ >> >> 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
