en>Headbomb: Various citation cleanup (identifiers mostly) using AWB

2011-09-05T07:42:40Z

Various citation cleanup (identifiers mostly) using AWB

New page

In [[combinatorial game theory]], '''poset games''' are [[mathematical game|mathematical]] [[game of strategy|games of strategy]], generalizing many well-known games such as [[Nim]] and [[Chomp]].<ref name="MSCW2011" /> 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
:<math> P_x = P - \{ a\mid a \geq x\} </math>
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 ''P''''x'', and then passes the turn to Bob who plays on ''P''''x'', 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 set|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 [[tree (graph theory)|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'' [[covering relation|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 order|product]] of total orders from which the [[infimum]] has been removed.

==Grundy value==
Poset games are [[impartial game]]s, meaning that every move available to Alice would also be available to Bob if Alice were allowed to [[Null move|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 ''P''''x'', ''x'' ∈ ''P''. That is,<ref name="Byrnes2003"/>
: <math>G(P)=\min\bigl(\mathbb{N}\setminus \{G(P_x)\mid x\in P\}\bigr).</math>

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.<ref name="MSCW2011"/>

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]].<ref name="Grier2012" /> This means that unless P=PSPACE, computing the Grundy value of an arbitrary poset game is computationally difficult.

==References==
{{Reflist|refs=
<ref name="MSCW2011">{{citation
| last1 = Soltys | first1 = Michael
| last2 = Wilson | first2 = Craig
| doi = 10.1007/s00224-010-9254-y
| issue = 3
| journal = Theory of Computing Systems
| mr = 2770813
| pages = 680–692
| title = On the complexity of computing winning strategies for finite poset games
| volume = 48
| year = 2011}}.</ref>
<ref name="Byrnes2003">{{citation
| last = Byrnes | first = Steven
| issue = G3
| journal = Integers
| mr = 2036487
| pages = 1–16
| title = Poset game periodicity
| url = http://www.emis.ams.org/journals/INTEGERS/papers/dg3/dg3.pdf
| volume = 3
| year = 2003}}.</ref>
<ref name="Grier2012">{{citation
| last = Grier | first = Daniel
| journal = arXiv
| title = Deciding the Winner of an Arbitrary Finite Poset Game is PSPACE-Complete
| url = http://arxiv.org/abs/1209.1750
| year = 2012}}.</ref>
}}

[[Category:Combinatorial game theory]]
[[Category:Mathematical games]]

Q-Krawtchouk polynomials - Revision history

en>Headbomb: Various citation cleanup (identifiers mostly) using AWB