On Tue, Jun 19, 2018 at 3:55 PM, Marcel Crasmaru <crasma...@gmail.com> wrote: > "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.
I spent some time thinking about the loss-less-ladder problem, that asks if Black can capture a given white group in a ladder without losing any stones herself. I've come to suspect that this is an instance of (1), and that it might be easier to prove than the general capture go problem of which it is a special case. regards, -John _______________________________________________ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
