Backgammon Is Hard

R. Teal Witter

TL;DR

For over 20 years, the computational complexity of backgammon remained a mystery, standing in stark contrast to games like Chess and Go. 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.

What Problem Does This Paper Address?

While we’ve known for decades that games like Chess, Checkers, and Go are computationally "hard" (meaning they require exponential time to solve as the board grows), backgammon remained an outlier. Despite being one of the oldest and most popular board games, its complexity was never formally established.

The delay was due to two main technical hurdles:

  1. The "Forcing" Problem: In complexity proofs, you need to "force" a player into specific moves to simulate logic gates. Because backgammon has many dice combinations and all pieces follow the same movement rules, it's incredibly difficult to ensure a player has only one viable move.
  2. Dimensionality: Most hard games are played on 2D grids, which makes it easier to build complex "gadgets" (logic structures). Backgammon is essentially one-dimensional, making it harder to "wire" these logic structures together.

Methods

The author uses polynomial-time reductions, a standard tool in theoretical computer science. To prove backgammon is hard, the author shows that if you could solve backgammon efficiently, you could also solve other famously difficult logic problems.

The paper defines a Generalized Backgammon (where the board length $n$ and number of pieces $p$ can grow) and analyzes it under three different information settings:

  • KSKR (Known Strategy, Known Rolls): You know every future dice roll and exactly how your opponent will play.
  • USKR (Unknown Strategy, Known Rolls): You know the dice rolls, but the opponent plays optimally/adversarially against you.
  • USUR (Unknown Strategy, Unknown Rolls): The "real life" setting where both dice and opponent moves are unknown.

To overcome the 1D board limitation, the author designed clever "gadgets"—specific arrangements of pieces that act like variables and clauses in a Boolean formula.

Datasets

As a theoretical paper in computational complexity, this work does not use empirical datasets or training benchmarks. Instead, it relies on mathematical reductions from established hard problems: 3SAT (for NP-hardness), $G_{pos}$ (for PSPACE-hardness), and $G_6$ (for EXPTIME-hardness).

Key Insights and Ideas

  • The Power of the Capture Rule: The author identifies the "capture rule" (hitting a lone piece and sending it to the bar) as the primary engine of complexity. This rule allows pieces to be reset, creating the potential for games to continue indefinitely, which is a hallmark of higher complexity classes.
  • Dice as a Forcing Function: Instead of trying to limit the player's choices through board geometry alone, the author uses specific sequences of dice rolls to "block" all but one possible move, effectively turning a game of chance into a deterministic logic circuit.
  • 1D Logic: The paper demonstrates that you don't need a 2D grid to simulate complex logic. By arraying "variable gadgets" followed by "clause gadgets" along the 1D line of the board, the author successfully simulates Boolean satisfiability.

Key Results

The paper establishes a hierarchy of hardness for backgammon based on how much information the player has:

  1. NP-Hard: Even if you are a "cheater" who knows every future dice roll and exactly what your opponent will do (KSKR), deciding if you can win is still NP-hard.
  2. PSPACE-Hard: If you know the dice rolls but the opponent's strategy is unknown (USKR), the problem becomes PSPACE-hard.
  3. EXPTIME-Hard: In the standard version of the game where both the opponent's strategy and future dice rolls are unknown (USUR), backgammon is EXPTIME-hard. This puts it in the same league as Chess and Go.

Limitations and Future Work

The most significant limitation is that the paper proves Hardness but not Completeness.

In complexity theory, "Hardness" provides a lower bound (the problem is at least this difficult). "Completeness" would provide an upper bound. Because the capture rule in backgammon allows for games that could theoretically last forever (a piece gets hit, enters, gets hit again, etc.), it is not immediately clear if backgammon is in EXPTIME. If a game can go on forever, it might actually belong to an even higher complexity class (like those associated with undecidable problems).

The author suggests that a natural follow-up would be to determine the exact complexity class that strictly contains these backgammon problems.

Summary updated

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.
BibTeX
@inproceedings{witter2021backgammon,
  author = {R. Teal Witter},
  title = {{Backgammon Is Hard}},
  booktitle = {COCOA},
  year = {2021},
  doi = {10.1007/978-3-030-92681-6\_38},
}

Loading related content...

Figure