Kyle BurkeAt #Integers2025 this spring, I collaborated with a new group and proved that Misere Partizan Arc Kayles is PSPACE-complete. That paper just went up on the arXiv: https://arxiv.org/abs/2511.21888
For that paper we implemented two new playable games: Misere Partizan Arc Kayles itself (https://kyleburke.info/DB/combGames/miserePartizanArcKayles.html) and a Normal-Play version of Bounded Constraint Logic (https://kyleburke.info/DB/combGames/normalBoundedConstraintLogic.html).
I'm especially excited about how clearly we talked about using Constraint Logic to provide computational hardness.
Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs
We show that Misère Partizan Arc Kayles is PSPACE-complete on planar graphs via a reduction from Bounded Two-Player Constraint Logic. Furthermore, we show how to embed our gadgets onto the square and triangular grids. In order to clearly explain these results, we get into the details of Bounded Two-Player Constraint Logic and find three PSPACE-complete variants of that as well.