User:Haskellelephant/PosetGames

Poset Games are mathematical games of strategy where two players alternate on choosing one point and removing it and and all points that are greater. The player who is left with no point to choose, looses.

Several popular specializations exists such as, Nim, Hackendot, Chomp and Hackenbush .

Game Play

Given a Poset $(P,<)$, let $P_{x}=P-\{a|a\geq x\}$. A poset game on P, played between Alice and Bob is as follows:

• Alice begins
• The current player chooses a point $x\in P$ and substitutes $P$ for $P_{x}$, then passes the turn.
• A player looses if it is his/her turn and have no points to choose.

The Grundy Value of Poset Games

Poset games are subject to the Sprague-Grundy theorem. The essential property of this theorem is the grundy-value. We define the Grundy Value of a Poset to be the least natural number not the grundy-value of any $P_{x},x\in P$. That is $G(P)=min(\mathbb {N} -\{G(P_{x})|x\in P\})$. It is the case that any move will alter the grundy-value and that if $G(P)>0$ there must exist an $P_{x}$ with $G(P_{x})=0$. Since $G(\emptyset )=0$ it must be the case that Alice has an winning strategy iff $G(P)>0$ since she might then choose x such that $G(P_{x})=0$ forcing Bob to choose an y such that $G(y)>0$.

Complexity

It has been shown that Poset Games in general are in PSPACE .