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 [1].

Game Play

edit

Given a Poset  , let  . A poset game on P, played between Alice and Bob is as follows:

  • Alice begins
  • The current player chooses a point   and substitutes   for  , 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

edit

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  . That is  . It is the case that any move will alter the grundy-value and that if   there must exist an   with  . Since   it must be the case that Alice has an winning strategy iff   since she might then choose x such that   forcing Bob to choose an y such that  . [2]


Complexity

edit

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


Notes

edit
  1. ^ a b Soltys, Michael & Wilson, Craig.On the Complexity of Computing Winning Strategies for Finite Poset Games. Springer New York, 2011
  2. ^ Byrnes, S. Poset game periodicity, 2003