Tic-tac-toe, noughts and crosses, or Xs and Os/“X’y O’sies” (Ireland), is a paper-and-pencil game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The player who succeeds in placing three of their marks in a diagonal, horizontal, or vertical row is the winner. It is a solved game with a forced draw assuming best play from both players.
Combinatorial game theory (CGT) 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. CGT 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.
Combinatorial game theory has several ways of measuring game complexity. This article describes five of them: state-space complexity, game tree size, decision complexity, game-tree complexity, and computational complexity.
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".
Time Machine is an American game show where contestants compete to answer trivia questions about popular culture and recent history to win prizes. The show aired on NBC from January 7 through April 26, 1985, and was hosted by John Davidson. Charlie Tuna was the announcer, with Rich Jeffries as his substitute. Reg Grundy Productions produced the series, and upon its premiere Time Machine was one of three Grundy series airing on NBC.
Tic-Tac-Dough is an American television game show based on the paper-and-pencil game of tic-tac-toe. Contestants answer questions in various categories to put up their respective symbol, X or O, on the board. Three versions were produced: the initial 1956–59 run on NBC, a 1978–86 run initially on CBS and then in syndication, and a syndicated run in 1990. The show was produced by Barry & Enright Productions.
SOS is paper and pencil game for two or more players. It is similar to tic-tac-toe and dots and boxes, but has greater complexity.
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.
Quantum tic-tac-toe is a "quantum generalization" of tic-tac-toe in which the players' moves are "superpositions" of plays in the classical game. The game was invented by Allan Goff of Novatia Labs, who describes it as "a way of introducing quantum physics without mathematics", and offering "a conceptual foundation for understanding the meaning of quantum mechanics".
Harary's generalized tic-tac-toe or animal tic-tac-toe is a generalization of the game tic-tac-toe, defining the game as a race to complete a particular polyomino on a square grid of varying size, rather than being limited to "in a row" constructions. It was devised by Frank Harary in March 1977, and is a broader definition than that of an m,n,k-game.
Zillions of Games is a commercial general game playing system developed by Jeff Mallett and Mark Lefler in 1998. The game rules are specified with S-expressions, Zillions rule language. It was designed to handle mostly abstract strategy board games or puzzles. After parsing the rules of the game, the system's artificial intelligence can automatically play one or more players. It treats puzzles as solitaire games and its AI can be used to solve them.
Takuzu, also known as Binairo, is a logic puzzle involving placement of two symbols, often 1s and 0s, on a rectangular grid. The objective is to fill the grid with 1s and 0s, where there is an equal number of 1s and 0s in each row and column and no more than two of either number adjacent to each other. Additionally, there can be no identical rows or columns. Similar to Sudoku, each puzzle begins with several squares in the grid already filled.
Hip Hop Squares is an American television game show originally hosted by Peter Rosenberg, which debuted on MTV2 on May 22, 2012. The show is a licensed format of CBS Television Distribution's Hollywood Squares featuring mostly rappers. The MTV2 version of the show was taped in Brooklyn, New York. The VH1 version is taped in Hollywood, California.
The Fairchild Channel F is a home video game console released by Fairchild Camera and Instrument in November 1976. It has the distinction of being the first programmable ROM cartridge–based video game console, and the first console to use a microprocessor. It was launched as the Fairchild Video Entertainment System, or Fairchild VES for short, but when Atari released their Atari Video Computer System, Atari VCS, later Atari 2600 the next year, Fairchild renamed its machine.
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 in the smaller tic-tac-toe boards until one of them wins in the larger tic-tac-toe 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.
Wild tic-tac-toe is a game similar to tic-tac-toe. However, in this game players can choose to place either X or O on each move. This game can also be played in its misere form where if a player creates a three-in-a-row of marks, that player loses the game.
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.
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).
