Strings-and-coins and Nimstring are PSPACE-complete

MaRDI QIDQ3390719zbMATH OpenFDO

Authors Erik D. Demaine, Yevhenii Diomidov

Publication date 25 March 2022

Full work available at URL https://arxiv.org/abs/2101.06361, http://math.colgate.edu/~integers/vb7/vb7.pdf

Mathematics Subject Classification ID

2-person games (91A05) Combinatorial games (91A46) Algorithmic game theory and complexity (91A68)

Abstract: We prove that Strings-and-Coins -- the combinatorial two-player game generalizing the dual of Dots-and-Boxes -- is strongly PSPACE-complete on multigraphs. This result improves the best previous result, NP-hardness, argued in Winning Ways. Our result also applies to the Nimstring variant, where the winner is determined by normal play; indeed, one step in our reduction is the standard reduction (also from Winning Ways) from Nimstring to Strings-and-Coins.

Recommendations

• Strings-and-coins and nimstring are PSPACE-complete
• A PSPACE-complete graph nim
• PSPACE-Hardness of some combinatorial games
• Nimstring values for \(2\times n\) rectangular arrays. I
• On the complexity of the misère version of three games played on graphs

Cites work

• scientific article; zbMATH DE number 1944415 (Why is no real title available?)
• scientific article; zbMATH DE number 2004829 (Why is no real title available?)
• scientific article; zbMATH DE number 1503566 (Why is no real title available?)
• Narrow misère dots-and-boxes
• On the complexity of some two-person perfect-information games
• Playing games with algorithms: algorithmic combinatorial game theory

Cited in

(3)

• Strings-and-coins and nimstring are PSPACE-complete
• A PSPACE-complete graph nim
• Nimstring values for \(2\times n\) rectangular arrays. I

This page was built for publication: Strings-and-coins and Nimstring are PSPACE-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3390719)