Is normal-play dots-and-boxes PSPACE-complete (YES) or in NP (NO)?
54%
chance

https://en.wikipedia.org/wiki/Dots_and_Boxes

The game starts with an empty grid of dots. Usually two players take turns adding a single horizontal or vertical line between two unjoined adjacent dots. A player who completes the fourth side of a 1×1 box earns one point and takes another turn. A point is typically recorded by placing a mark that identifies the player in the box, such as an initial. The game ends when no more lines can be placed. The winner is the player with the most points.

As usual when studyinh hardness of games, we want to consider the problem of deciding who wins from a given position.

Buchin, Hagedoorn, Kostitsyna, van Mulken (2021) showed that this is PSPACE-complete.

But what if we change the win condition to normal play (that is, the player unable to move loses)? Is it still PSPACE-complete? This question is one of the open problems from Demaine et al (2021).

Resolves YES if it is proved to be PSPACE-complete
Resolves NO if it is proved to be in NP.
(In case NP=PSPACE, the market resolves YES or NO based on which result was proved first. If they were proved at the same time, the market resolves N/A)

Sort by:
cos avatar
cos
bought Ṁ10 of NO

Doesn't normal-play dots-and-boxes fall fully within the domain of the Sprague–Grundy theorem? And since Nim is PSPACE-complete, it would follow that normal-play dots-and-boxes is also PSPACE-complete?

ManifoldDream avatar

Is normal-play dots-and-boxes PSPACE-complete (YES) or in NP (NO)?, 8k, beautiful, illustration, trending on art station, picture of the day, epic composition