Poset game
Wikipedia on Answers.com:
Top
Poset game
Poset games are mathematical games of strategy where, given a poset P, two players alternate on choosing one point in P, removing it and and all points that are greater. The player who is left with no point to choose, loses.
Several popular specializations exist, such as Nim, Hackendot, Chomp, and Hackenbush.[1]
|
Contents
|
Game play
Given a poset (P, <), let
A poset game on P, played between Alice and Bob, is as follows:
- Alice chooses a point x ∈ P, replaces P with Px, and then passes the turn to Bob.
- A player loses if it is his/her turn and there are 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 which is not the Grundy value of any Px, x ∈ P. That is,
Since G(P) ≠ G(Px) for any x∈P, making a move in a poset game alters the Grundy value. If G(P) > 0, there must exist Px with G(Px) = 0. Since G(∅) = 0, it must be the case that Alice has a winning strategy if G(P) > 0, since she might then choose x such that G(Px) = 0, forcing Bob to choose y such that G(y) > 0.[2]
Complexity
It has been shown that poset games are in PSPACE[1] and that they are NC1-hard. [3]
Notes
- ^ a b Soltys, Michael & Wilson, Craig.On the Complexity of Computing Winning Strategies for Finite Poset Games. Springer New York, 2011
- ^ Byrnes, S. Poset game periodicity, 2003
- ^ Kalinich, Adam O. Flipping the Winner of a Poset Game, 2012
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
Post a question - any question - to the WikiAnswers community:
Copyrights:
Wikipedia on Answers.com
This article is licensed under the Creative Commons Attribution/Share-Alike License. It uses material from the Wikipedia article Poset game.
Read more