Poset game

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.

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

A strategy-stealing argument shows that the Grundy value is nonzero for every poset that has a supremum.

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.

Deciding the winner of an arbitrary finite poset game is PSPACE-complete.