Abstract: We study the computational complexity of the popular board game backgammon. We show that deciding whether a player can win from a given board configuration is NP-Hard, PSPACE-Hard, and EXPTIME-Hard under different settings of known and unknown opponents' strategies and dice rolls. Our work answers an open question posed by Erik Demaine in 2001. In particular, for the real life setting where the opponent's strategy and dice rolls are unknown, we prove that determining whether a player can win is EXPTIME-Hard. Interestingly, it is not clear what complexity class strictly contains each problem we consider because backgammon games can theoretically continue indefinitely as a result of the capture rule.
Introduction
For over 20 years, the computational complexity of backgammon remained a mystery, standing in stark contrast to games like Chess and Go. While we’ve known for decades that games played on 2D grids are computationally "hard," backgammon remained an outlier. This paper finally settles the score, proving that backgammon is EXPTIME-hard in its most realistic setting, effectively solving an open challenge posed by Erik Demaine in 2001.
The delay in establishing this complexity was due to two main technical hurdles. First, the "Forcing" Problem: in complexity proofs, one must "force" a player into specific moves to simulate logic gates. Backgammon’s numerous dice combinations and uniform movement rules make it difficult to ensure a player has only one viable move. Second, Dimensionality: most hard games are played on 2D grids, facilitating the construction of logic "gadgets." Backgammon is essentially one-dimensional, making it harder to "wire" these structures together.
Methods
The author employs polynomial-time reductions, showing that if backgammon could be solved efficiently, so could other famously difficult logic problems. The study defines a Generalized Backgammon—where board length $n$ and piece count $p$ can scale—and analyzes it under three information settings:
- KSKR (Known Strategy, Known Rolls): Full knowledge of future dice and opponent moves.
- USKR (Unknown Strategy, Known Rolls): Known dice, but the opponent plays optimally against you.
- USUR (Unknown Strategy, Unknown Rolls): The realistic setting with unknown dice and opponent moves.
To overcome the 1D board limitation, the author designed clever "gadgets"—specific arrangements of pieces acting as variables and clauses in a Boolean formula. This requires mapping the traditional board into a linear format suitable for reduction.
Key Insights and Ideas
The primary engine of complexity identified is the capture rule (hitting a lone piece and sending it to the bar). This rule allows pieces to be reset, creating the potential for games to continue indefinitely—a hallmark of higher complexity classes.
Furthermore, the author uses Dice as a Forcing Function. Instead of limiting choices through board geometry, specific sequences of dice rolls are used to "block" all but one possible move, turning a game of chance into a deterministic logic circuit. Finally, the paper demonstrates that a 1D board is sufficient to simulate complex logic by arraying variable and clause gadgets along the board's linear path.
Key Results
The paper establishes a hierarchy of hardness based on player information:
- NP-Hard: Even with perfect knowledge of future dice and opponent moves (KSKR), deciding if a win is possible is NP-hard.
- PSPACE-Hard: With known dice but an unknown opponent strategy (USKR), the problem is PSPACE-hard.
- EXPTIME-Hard: In the standard version (USUR), backgammon is EXPTIME-hard, placing it in the same league as Chess and Go.
Conclusion and Future Work
While the paper proves Hardness (a lower bound), it does not prove Completeness (an upper bound). Because the capture rule allows for theoretically infinite games, it is not immediately clear if backgammon is in EXPTIME. It might belong to an even higher complexity class. Future work remains to determine the exact complexity class that strictly contains these problems.
Summary updated