Poset game

In combinatorial game theory, poset games are mathematical games of strategy, generalizing many well-known games such as Nim and Chomp. 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.

Given a partially ordered set (P, <), let

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:

If P is a 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 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. 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 of total orders from which the infimum has been removed.

Poset games are impartial games, meaning that every move available to Alice would also be available to Bob if Alice were allowed to 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,

...
Wikipedia