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.
The Shannon switching game is a connection game for two players, invented by American mathematician and electrical engineer Claude Shannon, the "father of information theory", some time before 1951. Two players take turns coloring the edges of an arbitrary graph. One player has the goal of connecting two distinguished vertices by a path of edges of their color. The other player aims to prevent this by using their color instead. The game is commonly played on a rectangular grid; this special case of the game was independently invented by American mathematician David Gale in the late 1950s and is known as Gale or Bridg-It.
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.
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 combinatorics, an abstract simplicial complex (ASC), often called an abstract complex or just a complex, is a family of sets that is closed under taking subsets, i.e., every subset of a set in the family is also in the family. It is a purely combinatorial description of the geometric notion of a simplicial complex. For example, in a 2-dimensional simplicial complex, the sets in the family are the triangles, their edges, and their vertices.
In graph theory, a haven is a certain type of function on sets of vertices in an undirected graph. If a haven exists, it can be used by an evader to win a pursuit–evasion game on the graph, by consulting the function at each step of the game to determine a safe set of vertices to move into. Havens were first introduced by Seymour & Thomas (1993) as a tool for characterizing the treewidth of graphs. Their other applications include proving the existence of small separators on minor-closed families of graphs, and characterizing the ends and clique minors of infinite graphs.
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.
The graph coloring game is a mathematical game related to graph theory. Coloring game problems arose as game-theoretic versions of well-known graph coloring problems. In a coloring game, two players use a given set of colors to construct a coloring of a graph, following specific rules depending on the game we consider. One player tries to successfully complete the coloring of the graph, when the other one tries to prevent him from achieving it.
Ultimate tic-tac-toe is a board game composed of nine tic-tac-toe boards arranged in a 3 × 3 grid. Players take turns playing on the smaller tic-tac-toe boards until one of them wins on the larger board. Compared to traditional tic-tac-toe, strategy in this game is conceptually more difficult and has proven more challenging for computers.
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.
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.
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 mathematics, the Graham–Rothschild theorem is a theorem that applies Ramsey theory to combinatorics on words and combinatorial cubes. It is named after Ronald Graham and Bruce Lee Rothschild, who published its proof in 1971. Through the work of Graham, Rothschild, and Klaus Leeb in 1972, it became part of the foundations of structural Ramsey theory. A special case of the Graham–Rothschild theorem motivates the definition of Graham's number, a number that was popularized by Martin Gardner in Scientific American and listed in the Guinness Book of World Records as the largest number ever appearing in a mathematical proof.
