First-player and second-player win

Last updated
Diagram showing optimal strategy for tic-tac-toe. With perfect play, and from any initial move, both players can always force a draw. Tictactoe-X.svg
Diagram showing optimal strategy for tic-tac-toe. With perfect play, and from any initial move, both players can always force a draw.

In game theory, a two-player deterministic perfect information turn-based game is a first-player-win if with perfect play 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.

Some games with relatively small game trees 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 has been mathematically proven to be first-player-win.

With perfect play, checkers has been determined to be a draw; neither player can force a win. [1] Another example of a game which leads to a draw with perfect play is tic-tac-toe, 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 engines). 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. [2] [3] [4]


See also

Related Research Articles

<i>Hex</i> (board game) board game

Hex is a strategy board game for two players played on a hexagonal grid, theoretically of any size and several possible shapes, but traditionally as an 11×11 rhombus. Players alternate placing markers or stones on unoccupied spaces in an attempt to link their opposite sides of the board in an unbroken chain. One player must win; there are no draws. The game has deep strategy, sharp tactics and a profound mathematical underpinning related to the Brouwer fixed-point theorem. It was invented in the 1940s independently by two mathematicians, Piet Hein and John Nash. The game was first marketed as a board game in Denmark under the name Con-tac-tix, and Parker Brothers marketed a version of it in 1952 called Hex; they are no longer in production. Hex can also be played with paper and pencil on hexagonally ruled graph paper.

Draughts board game

Draughts or Checkers 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. Draughts developed from alquerque. The name 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.

Computer chess computer hardware and software capable of playing chess

Computer chess includes both hardware and software capable of playing chess. Computer chess provides opportunities for players to practice even in the absence of human opponents, and also provides opportunities for analysis, entertainment and training.

This page explains commonly used terms in chess in alphabetical order. Some of these have their own pages, like fork and pin. For a list of unorthodox chess pieces, see Fairy chess piece; for a list of terms specific to chess problems, see Glossary of chess problems; for a list of chess-related games, see List of chess variants.

Combinatorial game theory branch of game theory about two-player sequential games with perfect information

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 in which 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.

Connect Four game

Connect Four is a two-player connection game in which the players first choose a color and then take turns dropping one colored disc from the top into a seven-column, six-row 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 discs. Connect Four is a solved game. The first player can always win by playing the right moves.

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.

Jonathan Schaeffer Canadian researcher and professor

Jonathan Herbert Schaeffer is a Canadian researcher and professor at the University of Alberta and the former Canada Research Chair in Artificial Intelligence.

English draughts board game draughts

English draughts or checkers, also called American checkers or straight checkers, is a form of the strategy board game draughts. It is played on an 8×8 chequered board 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.

Endgame tablebase

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.

Computer bridge is the playing of the game contract bridge using computer software. After years of limited progress, since around the end of the 20th century the field of computer bridge has made major advances. In 1996 the American Contract Bridge League (ACBL) established an official World Computer-Bridge Championship, to be held annually along with a major bridge event. The first championship took place in 1997 at the North American Bridge Championships in Albuquerque. Since 1999 the event has been conducted as a joint activity of the American Contract Bridge League and the World Bridge Federation. Alvin Levy, ACBL Board member, initiated this championship and has coordinated the event annually since its inception. The event history, articles and publications, analysis, and playing records can be found at the official website.

A pawnless chess endgame is a chess endgame in which only a few pieces remain and none of them is a pawn. The basic checkmates are types of pawnless endgames. Endgames without pawns do not occur very often in practice except for the basic checkmates of king and queen versus king, king and rook versus king, and queen versus rook. Other cases that occur occasionally are (1) a rook and minor piece versus a rook and (2) a rook versus a minor piece, especially if the minor piece is a bishop.

Go and mathematics

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, a Chinese scholar in 11th century, estimated that the number of possible board positions is around 10172 in The Dream Pool Essays. In more recent years, research of the game by John H. Conway led to the invention of the surreal numbers and contributed to development of combinatorial game theory (with Go Infinitesimals being a specific example of its use in Go).

First-move advantage in chess Advantage of White (plays first) over Black (plays second) in chess

The first-move advantage in chess is the inherent advantage of the player (White) who makes the first move in chess. Chess players and theorists generally agree that White begins the game with some advantage. Since 1851, compiled statistics support this view; White consistently wins slightly more often than Black, usually scoring between 52 and 56 percent. White's winning percentage is about the same for tournament games between humans and games between computers; however, White's advantage is less significant in blitz games and games between novices.

Computer Othello abstract strategy game

Computer Othello refers to computer architecture encompassing computer hardware and computer software capable of playing the game of Othello.

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 not possible, then either the first-player can force a win, or the second-player can force a win, or both players can force a draw. The theorem is named after Ernst Zermelo.

Solving chess means finding an optimal strategy for playing chess, i.e. one by which one of the players can always force a victory, or both can force a draw. It also means more generally solving chess-like games, such as infinite chess. According to Zermelo's theorem, a hypothetically determinable optimal strategy does exist for chess and chess-like games.

Outline of chess Overview of and topical guide to chess

The following outline is provided as an overview of and topical guide to chess:

References

  1. Schaeffer, J.; Burch, N.; Bjornsson, Y.; Kishimoto, A.; Muller, M.; Lake, R.; Lu, P.; Sutphen, S. (2007). "Checkers Is Solved". Science. 317 (5844): 1518–1522. doi:10.1126/science.1144079. PMID   17641166 . Retrieved 2008-11-24.
  2. J.W.H.M. Uiterwijk, H.J. van den Herik. "The Advantage of the Initiative". (August 1999).
  3. Shannon, C. (March 1950). "Programming a Computer for Playing Chess" (PDF). Philosophical Magazine . 7. 41 (314). Archived from the original (PDF) on 2010-03-15. Retrieved 2008-06-27.
  4. Victor Allis (1994). "PhD thesis: Searching for Solutions in Games and Artificial Intelligence" (PDF). Department of Computer Science. University of Limburg . Retrieved 2012-07-14.