Checkers, also known as draughts, is a group of strategy board games for two players which involve diagonal moves of uniform game pieces and mandatory captures by jumping over opponent pieces. Checkers is developed from alquerque. The term "checkers" derives from the checkered board which the game is played on, whereas "draughts" derives from the verb "to draw" or "to move".
A solved game is a game whose outcome can be correctly predicted from any position, assuming that both players play perfectly. This concept is usually applied to abstract strategy games, and especially to games with full information and no element of chance; solving such a game may use combinatorial game theory and/or computer assistance.
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.
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.
Connect Four is a game in which the players choose a color and then take turns dropping colored tokens into a six-row, seven-column vertically suspended grid. The pieces fall straight down, occupying the lowest available space within the column. The objective of the game is to be the first to form a horizontal, vertical, or diagonal line of four of one's own tokens. It is therefore a type of M,n,k-game with restricted piece placement. Connect Four is a solved game. The first player can always win by playing the right moves.
Combinatorial game theory measures game complexity in several ways:
- State-space complexity,
- Game tree size,
- Decision complexity,
- Game-tree complexity,
- Computational complexity.
An m,n,k-game is an abstract board game in which two players take turns in placing a stone of their color on an m-by-n board, the winner being the player who first gets k stones of their own color in a row, horizontally, vertically, or diagonally. Thus, tic-tac-toe is the 3,3,3-game and free-style gomoku is the 15,15,5-game. An m,n,k-game is also called a k-in-a-row game on an m-by-n board.
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 computational complexity theory, a generalized game is a game or puzzle that has been generalized so that it can be played on a board or grid of any size. For example, generalized chess is the game of chess played on an board, with pieces on each side. Generalized Sudoku includes Sudokus constructed on an grid.
Teeko is an abstract strategy game invented by John Scarne in 1937 and rereleased in refined form in 1952 and again in the 1960s. Teeko was marketed by Scarne's company, John Scarne Games Inc.; its quirky name, he said, borrowed letters from Tic-tac-toe, Chess, Checkers, and Bingo.
English draughts or checkers, also called straight checkers or simply draughts, is a form of the strategy board game checkers. It is played on an 8×8 checkerboard with 12 pieces per side. The pieces move and capture diagonally forward, until they reach the opposite end of the board, when they are crowned and can thereafter move and capture both backward and forward.
An endgame tablebase is a computerized database that contains precalculated exhaustive analysis of chess endgame positions. It is typically used by a computer chess engine during play, or by a human or computer that is retrospectively analysing a game that has already been played.
Chinook is a computer program that plays checkers. It was developed between the years 1989 to 2007 at the University of Alberta, by a team led by Jonathan Schaeffer and consisting of Rob Lake, Paul Lu, Martin Bryant, and Norman Treloar. The program's algorithms include an opening book which is a library of opening moves from games played by checkers grandmasters; a deep search algorithm; a good move evaluation function; and an end-game database for all positions with eight pieces or fewer. All of Chinook's knowledge was programmed by its creators, rather than learned using an artificial intelligence system.
God's algorithm is a notion originating in discussions of ways to solve the Rubik's Cube puzzle, but which can also be applied to other combinatorial puzzles and mathematical games. It refers to any algorithm which produces a solution having the fewest possible moves. The allusion to the deity is based on the notion that an omniscient being would know an optimal step from any given configuration.
The game of Go is one of the most popular games in the world. As a result of its elegant and simple rules, the game has long been an inspiration for mathematical research. Shen Kuo, an 11th century Chinese scholar, estimated in his Dream Pool Essays that the number of possible board positions is around 10172. In more recent years, research of the game by John H. Conway led to the development of the surreal numbers and contributed to development of combinatorial game theory (with Go Infinitesimals being a specific example of its use in Go).
Anti-computer tactics are methods used by humans to try to beat computer opponents at various games, most typically board games such as chess and Arimaa. They are most associated with competitions against computer AIs that are playing to their utmost to win, rather than AIs merely programmed to be an interesting challenge that can be given intentional weaknesses and quirks by the programmer. Such tactics are most associated with the era when AIs searched a game tree with an evaluation function looking for promising moves, often with Alpha–beta pruning or other minimax algorithms used to narrow the search. Against such algorithms, a common tactic is to play conservatively aiming for a long-term advantage. The theory is that this advantage will manifest slowly enough that the computer is unable to notice in its search, and the computer won't play around the threat correctly. This may result in, for example, a subtle advantage that eventually turns into a winning chess endgame with a passed pawn.
In chess, there is a consensus among players and theorists that the player who makes the first move (White) has an inherent advantage, albeit not one large enough to win under perfect play. This view has been the consensus since at least 1889, when the first World Chess Champion, Wilhelm Steinitz, addressed the issue, although chess has not yet been solved.
Computer Othello refers to computer architecture encompassing computer hardware and computer software capable of playing the game of Othello. It was notably included in Microsoft Windows from 1.0 to XP, where it is simply known as Reversi.
In game theory, Zermelo's theorem is a theorem about finite two-person games of perfect information in which the players move alternately and in which chance does not affect the decision making process. It says that if the game cannot end in a draw, then one of the two players must have a winning strategy. An alternate statement is that for a game meeting all of these conditions except the condition that a draw is now possible, then either the first-player can force a win, or the second-player can force a win, or both players can at least force a draw. The theorem is named after Ernst Zermelo, a German mathematician and logician, who proved the theorem for the example game of chess in 1913.
Solving chess consists of finding an optimal strategy for the game of chess; that is, one by which one of the players can always force a victory, or either can force a draw. It is also related to more generally solving chess-like games such as Capablanca chess and infinite chess. In a weaker sense, solving chess may refer to proving which one of the three possible outcomes is the result of two perfect players, without necessarily revealing the optimal strategy itself.
