In combinatorial game theory, poset games are mathematical games of strategy, generalizing many well-known games such as Nim and Chomp. [1] 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 Px, x ∈ P. That is, [2]
This number may be used to describe the optimal game play in a poset game. In particular, the Grundy value is nonzero when the player whose turn it is has a winning strategy, and zero when the current player cannot win against optimal play from his or her opponent. A winning strategy in the game consists of moving to a position whose Grundy value is zero, whenever this is possible.
A strategy-stealing argument shows that the Grundy value is nonzero for every poset that has a supremum. For, let x be the supremum of a partially ordered set P. If Px has Grundy value zero, then P itself has a nonzero value, by the formula above; in this case, x is a winning move in P. If, on the other hand, Px has a nonzero Grundy value, then there must be a winning move y in Px, such that the Grundy value of (Px)y is zero. 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. [1]
For more trivial reasons a poset with an infimum also has a nonzero Grundy value: moving to the infimum is always a winning move.
Deciding the winner of an arbitrary finite poset game is PSPACE-complete. [3] This means that unless P=PSPACE, computing the Grundy value of an arbitrary poset game is computationally difficult.
Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps or piles. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap or pile. Depending on the version being played, the goal of the game is either to avoid taking the last object or to take the last object.
In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a one-heap game of nim, or to an infinite generalization of nim. It can therefore be represented as a natural number, the size of the heap in its equivalent game of nim, as an ordinal number in the infinite generalization, or alternatively as a nimber, the value of that one-heap game in an algebraic system whose addition operation combines multiple heaps to form a single equivalent heap in nim.
In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum (join) and an infimum (meet). A lattice that satisfies at least one of these properties for bounded subsets is known as a conditionally complete lattice. For comparison, in a general lattice, only pairs of elements need to have a supremum and an infimum. Every non-empty finite lattice is complete, but infinite lattices may be incomplete.
In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric. In other words, the only difference between player 1 and player 2 is that player 1 goes first. The game is played until a terminal position is reached. A terminal position is one from which no moves are possible. Then one of the players is declared the winner and the other the loser. Furthermore, impartial games are played with perfect information and no chance moves, meaning all information about the game and operations for both players are visible to both players.
In mathematics, the nimbers, also called Grundy numbers, are introduced in combinatorial game theory, where they are defined as the values of heaps in the game Nim. The nimbers are the ordinal numbers endowed with nimber addition and nimber multiplication, which are distinct from ordinal addition and ordinal multiplication.
Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and provides basic definitions. A list of order-theoretic terms can be found in the order theory glossary.
This is a glossary of some terms used in various branches of mathematics that are related to the fields of order, lattice, and domain theory. Note that there is a structured list of order topics available as well. Other helpful resources might be the following overview articles:
A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum and a unique infimum. An example is given by the power set of a set, partially ordered by inclusion, for which the supremum is the union and the infimum is the intersection. Another example is given by the natural numbers, partially ordered by divisibility, for which the supremum is the least common multiple and the infimum is the greatest common divisor.
In the mathematical area of order theory, one often speaks about functions that preserve certain limits, i.e. certain suprema or infima. Roughly speaking, these functions map the supremum/infimum of a set to the supremum/infimum of the image of the set. Depending on the type of sets for which a function satisfies this property, it may preserve finite, directed, non-empty, or just arbitrary suprema or infima. Each of these requirements appears naturally and frequently in many areas of order theory and there are various important relationships among these concepts and other notions such as monotonicity. If the implication of limit preservation is inverted, such that the existence of limits in the range of a function implies the existence of limits in the domain, then one obtains functions that are limit-reflecting.
In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set (poset). The most familiar example is the completeness of the real numbers. A special use of the term refers to complete partial orders or complete lattices. However, many other interesting notions of completeness exist.
In combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many two-player games, that the second player cannot have a guaranteed winning strategy. The strategy-stealing argument applies to any symmetric game in which an extra move can never be a disadvantage. A key property of a strategy-stealing argument is that it proves that the first player can win the game without actually constructing such a strategy. So, although it might prove the existence of a winning strategy, the proof gives no information about what that strategy is.
In the mathematical fields of order and domain theory, a Scott domain is an algebraic, bounded-complete and directed-complete partial order (dcpo). They are named in honour of Dana S. Scott, who was the first to study these structures at the advent of domain theory. Scott domains are very closely related to algebraic lattices, being different only in possibly lacking a greatest element. They are also closely related to Scott information systems, which constitute a "syntactic" representation of Scott domains.
Chomp is a two-player strategy game played on a rectangular grid made up of smaller square cells, which can be thought of as the blocks of a chocolate bar. The players take it in turns to choose one block and "eat it", together with those that are below it and to its right. The top left block is "poisoned" and the player who eats this loses.
Hackenbush is a two-player game invented by mathematician John Horton Conway. It may be played on any configuration of colored line segments connected to one another by their endpoints and to a "ground" line.
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum. Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing. Every Boolean algebra A has an essentially unique completion, which is a complete Boolean algebra containing A such that every element is the supremum of some subset of A. As a partially ordered set, this completion of A is the Dedekind–MacNeille completion.
In mathematics, the mex of a subset of a well-ordered set is the smallest value from the whole set that does not belong to the subset. That is, it is the minimum value of the complement set.
In mathematics, in the branch of combinatorics, a graded poset is a partially-ordered set (poset) P equipped with a rank functionρ from P to the set N of all natural numbers. ρ must satisfy the following two properties:
In the mathematical theory of games, in particular the study of zero-sum continuous games, not every game has a minimax value. This is the expected value to one of the players when both play a perfect strategy.
The octal games are a class of two-player games that involve removing tokens from heaps of tokens. They have been studied in combinatorial game theory as a generalization of Nim, Kayles, and similar games.
In combinatorial game theory, a subtraction game is an abstract strategy game whose state can be represented by a natural number or vector of numbers and in which the allowed moves reduce these numbers. Often, the moves of the game allow any number to be reduced by subtracting a value from a specified subtraction set, and different subtraction games vary in their subtraction sets. These games also vary in whether the last player to move wins or loses. Another winning convention that has also been used is that a player who moves to a position with all numbers zero wins, but that any other position with no moves possible is a draw.
