I've read that La Pipopipette is known to be NP-hard. I have not yet found analysis specifying an exact complexity class for Dots and Boxes, or for some variations in the analysis of Go.

Here's a rough comparative construction starting from the rules of Go:

Start with a checkerboard that contains a grey stone on every red tile.

Each grey stone does not limit the freedoms of player stones, but is initialed by whichever player fills its last open neighbor.

Captured neutral stones may correspond to moves in a normalized game of Go translating red tiles as neighbors.

Little is needed to demonstrate that both games share a focus on encircling quanta of space. The extra move requirement in D&B is a larger distinction, somewhat alleviated by the shared notion of territory. The player who manages to capture more territory has the ability to make more moves, the difference being whether extra moves are afforded midgame or postgame.

My question is whether rule extensions in the above outline, or by others, formally embed D&B with co-Go. The main conflict I see is that D&B is strictly an additive game, where Go can be rewritable. Those versions of Go look to be more compatible with DSPACE.

I suspect that I am stumbling across a few pieces of well-established game theory in the study of regular planar graphs and related subjects. Would anyone kindly point out whether this perspective that D&B and Go are similar is in error?

  • $\begingroup$ Also if this question is better suited to cstheory please say so! As mentioned I am unsure it is a research-level question. $\endgroup$
    – Lem n
    Dec 19 '19 at 6:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.