 | This article relies largely or entirely on a single source .(January 2019) |
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.
Consider the 5-by-5 variant of Tic-tac-toe. We can create 12 pairwise-disjoint pairs of board positions, denoted by 1,...,12 below: [1] : 3
| 11 | 1 | 8 | 1 | 12 |
| 6 | 2 | 2 | 9 | 10 |
| 3 | 7 | * | 9 | 3 |
| 6 | 7 | 4 | 4 | 10 |
| 12 | 5 | 8 | 5 | 11 |
Note that the central element (denoted by *) does not belong to any pair; it is not needed in this strategy.
Each horizontal, vertical or diagonal line contains at least one pair. Therefore the following pairing strategy can be used to force a draw: "whenever your opponent chooses an element of pair i, choose the other element of pair i". At the end of the game, you have an element of each winning-line. Therefore, you guarantee that the other player cannot win.
Since both players can use this strategy, the game is a draw.
This example is generalized below for an arbitrary Maker-Breaker game. In such a game, the goal of Maker is to occupy an entire winning-set, while the goal of Breaker is to prevent this by owning an element in each winning-set.
A pairing-strategy for Maker requires a set of element-pairs such that: [1] : 119
Whenever Breaker picks an element of a pair, Maker picks the other element of the same pair. At the end, Maker's set contains at least one element from each pair; by condition 2, he occupies an entire winning-set (this is true even when Maker plays second).
As an example, consider a game-board containing all vertices in a perfect binary tree except the root. The winning-sets are all the paths from the leaf to one of the two children of the root. We can partition the elements into pairs by pairing each element with its sibling. The pairing-strategy guarantees that Maker wins even when playing second. If Maker plays first, he can win even when the game-board contains also the root: in the first step he just picks the root, and from then on plays the above pairing-strategy.
A pairing-strategy for Breaker requires a set of element-pairs such that:
Whenever Maker picks an element of a pair, Breaker picks the other element of the same pair. At the end, Breaker has an element in each pair; by condition 2, he has an element in each winning-set.
An example of such pairing-strategy for 5-by-5 tic-tac-toe is shown above. [1] : 2–3 show other examples for 4x4 and 6x6 tic-tac-toe.
Another simple case when Breaker has a pairing-strategy is when all winning-sets are pairwise-disjoint and their size is at least 2.
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.
In the context of combinatorial game theory, which typically studies sequential games with perfect information, a game tree is a graph representing all possible game states within such a game. Such games include well-known ones such as chess, checkers, Go, and tic-tac-toe. This can be used to measure the complexity of a game, as it represents all the possible ways a game can pan out. Due to the large game trees of complex games such as chess, algorithms that are designed to play this class of games will use partial game trees, which makes computation feasible on modern computers. Various methods exist to solve game trees. If a complete game tree can be generated, a deterministic algorithm, such as backward induction or retrograde analysis can be used. Randomized algorithms and minmax algorithms such as MCTS can be used in cases where a complete game tree is not feasible.
3D tic-tac-toe, also known by the trade name Qubic, is an abstract strategy board game, generally for two players. It is similar in concept to traditional tic-tac-toe but is played in a cubical array of cells, usually 4×4×4. Players take turns placing their markers in blank cells in the array. The first player to achieve four of their own markers in a row wins. The winning row can be horizontal, vertical, or diagonal on a single board as in regular tic-tac-toe, or vertically in a column, or a diagonal line through four boards.
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.
Determinacy is a subfield of set theory, a branch of mathematics, that examines the conditions under which one or the other player of a game has a winning strategy, and the consequences of the existence of such strategies. Alternatively and similarly, "determinacy" is the property of a game whereby such a strategy exists. Determinacy was introduced by Gale and Stewart in 1950, under the name "determinateness".
Toss Across is a game first introduced in 1969 by the now defunct Ideal Toy Company. The game was designed by Marvin Glass and Associates and created by Hank Kramer, Larry Reiner and Walter Moe, and is now distributed by Mattel. It is a game in which participants play tic-tac-toe by lobbing small beanbags at targets in an attempt to change the targets to their desired letter. As in traditional tic-tac-toe, the first player to get three of their letters in a row wins the game. There are other similar games to Toss Across known under different names, such as Tic Tac Throw.
A positional game is a kind of a combinatorial game for two players. It is described by:
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.
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.
Notakto is a tic-tac-toe variant, also known as neutral or impartial tic-tac-toe. The game is a combination of the games tic-tac-toe and Nim, played across one or several boards with both of the players playing the same piece. The game ends when all the boards contain a three-in-a-row of Xs, at which point the player to have made the last move loses the game. However, in this game, unlike tic-tac-toe, there will always be a player who wins any game of Notakto.
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 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.
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).