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)
1,000
3.00Doesn'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?
@cos The Sprague-Grundy theorem is concerned with sums of impartial games. Dots-and-boxes is not impartial as each player does not have the same set of moves (the color of the lines matters). Nim [can be solved in polynomial time](https://en.wikipedia.org/wiki/Nim#Mathematical_theory) and so is not PSPACE-complete (if P != PSPACE).
