Poset game

In combinatorial game theory, poset games are mathematical games of strategy, generalizing many well-known games such as Nim and Chomp.[1] In such games, two players start with a poset (a partially ordered set), and take turns choosing one point in the poset, removing it and all points that are greater. The player who is left with no point to choose, loses.

Game play

Given a partially ordered set (P, <), let

denote the poset formed by removing x from P.

A poset game on P, played between two players conventionally named Alice and Bob, is as follows:

  • Alice chooses a point x ∈ P; thus replacing P with Px, and then passes the turn to Bob who plays on Px, and passes the turn to Alice.
  • A player loses if it is his/her turn and there are no points to choose.

Examples

If P is a finite totally ordered set, then game play in P is exactly the same as the game play in a game of Nim with a heap of size |P|. For, in both games, it is possible to choose a move that leads to a game of the same type whose size is any number smaller than |P|. In the same way, a poset game with a disjoint union of total orders is equivalent to a game of Nim with multiple heaps with sizes equal to the chains in the poset.

A special case of Hackenbush, in which all edges are green (able to be cut by either player) and every configuration takes the form of a forest, may be expressed similarly, as a poset game on a poset in which, for every element x, there is at most one element y for which x covers y. If x covers y, then y is the parent of x in the forest on which the game is played.

Chomp may be expressed similarly, as a poset game on the product of total orders from which the infimum has been removed.

Grundy value

Poset games are impartial games, meaning that every move available to Alice would also be available to Bob if Alice were allowed to pass, and vice versa. Therefore, by the Sprague–Grundy theorem, every position in a poset game has a Grundy value, a number describing an equivalent position in the game of Nim. The Grundy value of a poset may be calculated as the least natural number which is not the Grundy value of any Px, x ∈ P. That is,[2]

This number may be used to describe the optimal game play in a poset game. In particular, the Grundy value is nonzero when the player whose turn it is has a winning strategy, and zero when the current player cannot win against optimal play from his or her opponent. A winning strategy in the game consists of moving to a position whose Grundy value is zero, whenever this is possible.

Strategy stealing

A strategy-stealing argument shows that the Grundy value is nonzero for every poset that has a supremum. For, let x be the supremum of a partially ordered set P. If Px has Grundy value zero, then P itself has a nonzero value, by the formula above; in this case, x is a winning move in P. If, on the other hand, Px has a nonzero Grundy value, then there must be a winning move y in Px, such that the Grundy value of (Px)y is zero. But by the assumption that x is a supremum, x > y and (Px)y = Py, so the winning move y is also available in P and again P must have a nonzero Grundy value.[1]

For more trivial reasons a poset with an infimum also has a nonzero Grundy value: moving to the infimum is always a winning move.

Complexity

Deciding the winner of an arbitrary finite poset game is PSPACE-complete.[3] This means that unless P=PSPACE, computing the Grundy value of an arbitrary poset game is computationally difficult.

References
  1. Soltys, Michael; Wilson, Craig (2011), "On the complexity of computing winning strategies for finite poset games", Theory of Computing Systems, 48 (3): 680–692, CiteSeerX 10.1.1.150.3656, doi:10.1007/s00224-010-9254-y, MR 2770813.
  2. Byrnes, Steven (2003), "Poset game periodicity" (PDF), Integers, 3 (G3): 1–16, MR 2036487.
  3. Grier, Daniel (2012), "Deciding the Winner of an Arbitrary Finite Poset Game is PSPACE-Complete", Automata, Languages, and Programming, Lecture Notes in Computer Science, 7965, pp. 497–503, arXiv:1209.1750, Bibcode:2012arXiv1209.1750G, doi:10.1007/978-3-642-39206-1_42, ISBN 978-3-642-39205-4.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.