Peg Duotaire

Description

Peg Duotaire is a two-player variant of Peg Solitaire introduced in [1], in which two players alternatively make a peg move and the winner is the last player to move.

Related Games

[2] introduced a multi-hop variant of Peg Duotaire, where a series of (single-hop) jumps with the same peg can be made on a given turn.

Peg Duotaire Reachability is a natural 2-player version of Peg Solitaire Reachability introduced in [3], in which pegs are partitioned into white pegs (controlled by the first player) and black pegs (controlled by the second player). A move of the first (resp., the second) player consists of a jump involving only white (resp., black) pegs. However, pegs of a given color can prevent jumps of pegs of the other color since they occupy positions of the board. Moreover, each player has a target position that wants to reach with a peg (and the two target positions might coincide). The winner is the first player that reaches its target position.

Computational Complexity

[3] shows that the problem of deciding whether the first player in a Peg Duotaire instance can force a win is PSPACE-complete, both in the single- and the multi-hop variant of the game.

It further shows that Peg Duotaire Reachability, and variants of it obtained assuming different winning conditions (e.g. that the winner is the player that makes that last move, or that a player wins by either reaching his target position or by leaving his opponent with no available moves), are all PSPACE-complete.

References

[1] B. Ravikumar, “Peg-solitaire, string rewriting systems and finite automata”, Theoretical Computer Science, 2004.

[2] C. Moore and D. Eppstein, “One-Dimensional Peg Solitaire, and Duotaire”, arXiv:math/0008172, 2000.

[3] D. Bilò, L. Gualà, S. Leucci, G. Proietti, and M. Rossi, “On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games”, in FUN 2018.

@misc{cog:peg-duotaire,
    author = "{CoG contributors}",
    title  = "{Peg Duotaire --- Complexity of Games}",
    year   = "2024",
    url    = "https://www.isnphard.com/i/peg-duotaire/",
    note   = "[Online; accessed 2024-04-13]"
}