Tic-tac-toe, noughts and crosses, or Xs and Os is a paper-and-pencil game for two players who take turns marking the spaces in a three-by-three grid with X or O. The player who succeeds in placing three of their marks in a horizontal, vertical, or diagonal row is the winner. It is a solved game, with a forced draw assuming best play from both players.
Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a position that the players take turns changing in defined ways or moves to achieve a defined winning condition. Combinatorial game theory has not traditionally studied games of chance or those that use imperfect or incomplete information, favoring games that offer perfect information in which the state of the game and the set of available moves is always known by both players. However, as mathematical techniques advance, the types of game that can be mathematically analyzed expands, thus the boundaries of the field are ever changing. Scholars will generally define what they mean by a "game" at the beginning of a paper, and these definitions often vary as they are specific to the game being analyzed and are not meant to represent the entire scope of the field.
In general topology, set theory and game theory, a Banach–Mazur game is a topological game played by two players, trying to pin down elements in a set (space). The concept of a Banach–Mazur game is closely related to the concept of Baire spaces. This game was the first infinite positional game of perfect information to be studied. It was introduced by Stanisław Mazur as problem 43 in the Scottish book, and Mazur's questions about it were answered by Banach.
In mathematics, the Hales–Jewett theorem is a fundamental combinatorial result of Ramsey theory named after Alfred W. Hales and Robert I. Jewett, concerning the degree to which high-dimensional objects must necessarily exhibit some combinatorial structure; it is impossible for such objects to be "completely random".
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.
A Maker-Breaker game is a kind of positional game. Like most positional games, it is described by its set of positions/points/elements and its family of winning-sets. It is played by two players, called Maker and Breaker, who alternately take previously untaken elements.
In mathematics, a selection principle is a rule asserting the possibility of obtaining mathematically significant objects by selecting elements from given sequences of sets. The theory of selection principles studies these principles and their relations to other mathematical properties. Selection principles mainly describe covering properties, measure- and category-theoretic properties, and local properties in topological spaces, especially function spaces. Often, the characterization of a mathematical property using a selection principle is a nontrivial task leading to new insights on the characterized property.
Tic-tac-toe is an instance of an m,n,k-game, where two players alternate taking turns on an m×n board until one of them gets k in a row. Harary's generalized tic-tac-toe is an even broader generalization. The game can also be generalized as a nd game. The game can be generalised even further from the above variants by playing on an arbitrary hypergraph where rows are hyperedges and cells are vertices.
A nd game (or nk game) is a generalization of the combinatorial game tic-tac-toe to higher dimensions. It is a game played on a nd hypercube with 2 players. If one player creates a line of length n of their symbol (X or O) they win the game. However, if all nd spaces are filled then the game is a draw. Tic-tac-toe is the game where n equals 3 and d equals 2 (3, 2). Qubic is the (4, 3) game. The (n > 0, 0) or (1, 1) games are trivially won by the first player as there is only one space (n0 = 1 and 11 = 1). A game with d = 1 and n > 1 cannot be won if both players are playing well as an opponent's piece will block the one-dimensional line.
In mathematics, a Hurewicz space is a topological space that satisfies a certain basic selection principle that generalizes σ-compactness. A Hurewicz space is a space in which for every sequence of open covers of the space there are finite sets such that every point of the space belongs to all but finitely many sets .
A discrepancy game is a kind of positional game. Like most positional games, it is described by its set of positions/points/elements and a family of sets. It is played by two players, called Balancer and Unbalancer. Each player in turn picks an element. The goal of Balancer is to ensure that every set in is balanced, i.e., the elements in each set are distributed roughly equally between the players. The goal of Unbalancer is to ensure that at least one set is unbalanced.
A strong positional game is a kind of positional game. Like most positional games, it is described by its set of positions and its family of winning-sets. It is played by two players, called First and Second, who alternately take previously untaken positions.
A Waiter-Client game is a kind of positional game. Like most positional games, it is described by its set of positions/points/elements, and its family of winning-sets. It is played by two players, called Waiter and Client. Each round, Waiter picks two elements, Client chooses one element and Waiter gets the other element.
An Avoider-Enforcer game is a kind of positional game. Like most positional games, it is described by a set of positions/points/elements and a family of subsets, which are called here the losing-sets. It is played by two players, called Avoider and Enforcer, who take turns picking elements until all elements are taken. Avoider wins if he manages to avoid taking a losing set; Enforcer wins if he manages to make Avoider take a losing set.
A biased positional game is a variant of a positional game. Like most positional games, it is described by a set of positions/points/elements and a family of subsets, which are usually called the winning-sets. It is played by two players who take turns picking elements until all elements are taken. While in the standard game each player picks one element per turn, in the biased game each player takes a different number of elements.
The clique game is a positional game where two players alternately pick edges, trying to occupy a complete clique of a given size.
A box-making game is a biased positional game where two players alternately pick elements from a family of pairwise-disjoint sets ("boxes"). The first player - called BoxMaker - tries to pick all elements of a single box. The second player - called BoxBreaker - tries to pick at least one element of all boxes.
In a positional game, a pairing strategy is a strategy that a player can use to guarantee victory, or at least force a draw. It is based on dividing the positions on the game-board into disjoint pairs. Whenever the opponent picks a position in a pair, the player picks the other position in the same pair.
Combinatorial Games: Tic-Tac-Toe Theory is a monograph on the mathematics of tic-tac-toe and other positional games, written by József Beck. It was published in 2008 by the Cambridge University Press as volume 114 of their Encyclopedia of Mathematics and its Applications book series (ISBN 978-0-521-46100-9).
In the mathematical study of combinatorics on words, a parameter word is a string over a given alphabet having some number of wildcard characters. The set of strings matching a given parameter word is called a parameter set or combinatorial cube. Parameter words can be composed, to produce smaller subcubes of a given combinatorial cube. They have applications in Ramsey theory and in computer science in the detection of duplicate code.
