combinatorial game theory 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 player ...

, a two-player deterministic perfect information

turn-based game In video and other games, the passage of time must be handled in a way that players find fair and easy to understand. This is usually done in one of the two ways: real-time and turn-based. Real-time Real-time games have game time progress con ...

is a first-player-win if with

perfect play A solved game is a game whose outcome (win, lose or draw) 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 informa ...

the first player to move can always force a win. Similarly, a game is second-player-win if with perfect play the second player to move can always force a win. With perfect play, if neither side can force a win, the game is a

draw Draw, drawing, draws, or drawn may refer to: Common uses * Draw (terrain), a terrain feature formed by two parallel ridges or spurs with low ground in between them * Drawing (manufacturing), a process where metal, glass, or plastic or anything ...

. Some games with relatively small

game tree 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, ch ...

s have been proven to be first or second-player wins. For example, the game of nim with the classic 3–4–5 starting position is a first-player-win game. However, Nim with the 1-3-5-7 starting position is a second-player-win. The classic game of

Connect Four Connect Four (also known as Connect 4, Four Up, Plot Four, Find Four, Captain's Mistress, Four in a Row, Drop Four, and Gravitrips in the Soviet Union) is a two-player connection board game, in which the players choose a color and then take tur ...

has been mathematically proven to be first-player-win. With perfect play,

checkers Checkers (American English), also known as draughts (; British English), 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 ...

has been determined to be a draw; neither player can force a win. Another example of a game which leads to a draw with perfect play is

tic-tac-toe Tic-tac-toe (American English), noughts and crosses (Commonwealth English), or Xs and Os (Canadian or Irish English) 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''. ...

, and this includes play from any opening move. Significant theory has been completed in the effort to solve chess. It has been speculated that there may be first-move advantage which can be detected when the game is played imperfectly (such as with all humans and all current

chess engine In computer chess, a chess engine is a computer program that analyzes chess or chess variant positions, and generates a move or list of moves that it regards as strongest. A chess engine is usually a back end with a command-line interface wit ...

s). However, with perfect play, it remains unsolved as to whether the game is a first-player win (White), a second player win (Black), or a forced draw.

References

Game theory Mathematical games {{Mathapplied-stub

See also

References