Understood, and thanks. I didn't mean to throw the conversation sideways too much.
Steve On Tue, Jun 19, 2018 at 7:22 AM Marcel Crasmaru <crasma...@gmail.com> wrote: > > _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
_______________________________________________ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
