Solved game
Encyclopedia
A solved game is a game
whose outcome can be correctly predicted from any position when each side plays optimally. Games which have not been solved are said to be "unsolved". This article focuses on two-player games that have been solved.
A two-player game
can be "solved" on several levels:
Ultra-weak
Weak
Strong
Given the rules of any two-person game with a finite number of positions, one can always trivially construct a minimax
algorithm that would exhaustively traverse the game tree
. However, since for many non-trivial games such an algorithm would require an infeasible amount of time to generate a move in a given position, a game is not considered to be solved weakly or strongly unless the algorithm can be run by existing hardware in a reasonable time. Many algorithms rely on a huge pre-generated database, and are effectively nothing more than that.
As an example, the game of tic-tac-toe
is solvable as a draw for both players with perfect play (a result even manually determinable by schoolchildren). Games like nim
also admit of a rigorous analysis using combinatorial game theory
.
Whether a game is solved is not necessarily the same as whether it remains interesting for humans to play. Even a strongly solved game can still be interesting if the solution is too complex to be memorized; conversely, a weakly solved game may lose its attraction if the winning strategy is simple enough to remember (e.g. Maharajah and the Sepoys
). An ultra-weak solution (e.g. Chomp
or Hex
on a sufficiently large board) generally does not affect playability.
, perfect play is the behavior or strategy of a player which leads to the best possible outcome for that player regardless of the response by the opponent. Based on the rules of a game, every possible final position can be evaluated (as a win, loss or draw). By backward reasoning
, one can recursively evaluate a non-final position as identical to that of the position that is one move away and best valued for the player whose move it is. Thus a transition between positions can never result in a better evaluation for the moving player and a perfect move in a position would be a transition between positions that are equally evaluated. As an example, a perfect player in a drawn position would always get a draw or win, never a loss. If there are multiple options with the same outcome, perfect play is sometimes considered the fastest method leading to a good result, or the slowest method leading to a bad result.
Perfect play can be generalized to non-perfect information
games, as the strategy that would guarantee the highest minimal expected outcome
regardless of the strategy of the opponent. As an example, the perfect strategy for Rock, Paper, Scissors
would be to randomly choose each of the options with equal (1/3) probability. The disadvantage in this example is that this strategy will never exploit non-optimal strategies of the opponent, so the expected outcome of this strategy versus any strategy will always be equal to the minimal expected outcome.
Although the optimal strategy of a game may not (yet) be known, a game-playing computer might still benefit from solutions of the game from certain endgame positions (in the form of endgame tablebase
s), which will allow it to play perfectly after some point in the game. Computer chess
programs are well-known for doing this.
(a game of the Mancala
family)
Chopsticks
Connect Four
Draughts, English
(i.e. checkers)
Fanorona
Free Gomoku
Ghost
Hex
Kalah
L game
Maharajah and the Sepoys
Nim
Nine Men's Morris
Ohvalhu
Pentomino
es
Quarto
Qubic
Free Renju
Sim
Teeko
Three Musketeers
Three Men's Morris
Tic-tac-toe
Tigers and Goats
International Draughts
Go
Reversi
(Othello)
m,n,k-game
Game
A game is structured playing, usually undertaken for enjoyment and sometimes used as an educational tool. Games are distinct from work, which is usually carried out for remuneration, and from art, which is more often an expression of aesthetic or ideological elements...
whose outcome can be correctly predicted from any position when each side plays optimally. Games which have not been solved are said to be "unsolved". This article focuses on two-player games that have been solved.
A two-player game
Two-player game
A two-player game is a game played by just two players. This is distinct from a solitaire game which is played by only one player, or a multiplayer game played by more than two players. Two unofficial but logical ways of grouping and categorizing games could be by Type and by what it is Based In,...
can be "solved" on several levels:
Ultra-weak
- In the weakest sense, solving a game means proving whether the first player will win, lose, or draw from the initial position, given perfect play on both sides. This can be a non-constructiveConstructive proofIn mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object with certain properties by creating or providing a method for creating such an object...
proof (possibly involving a strategy stealingStrategy-stealing argumentIn combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many games, that the second player cannot have a winning strategy .The strategy-stealing argument applies to any symmetric game In combinatorial game theory, the strategy-stealing argument is a...
argument) that may not actually help determine this perfect play.
Weak
- More typically, solving a game means providing an algorithm that secures a win for one player, or a draw for either, against any possible moves by the opponent, from the beginning of the game.
Strong
- The strongest sense of solution requires an algorithm which can produce perfect play from any position, i.e. even if mistakes have already been made on one or both sides.
Given the rules of any two-person game with a finite number of positions, one can always trivially construct a minimax
Minimax
Minimax is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case scenario. Alternatively, it can be thought of as maximizing the minimum gain...
algorithm that would exhaustively traverse the game tree
Game tree
In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that...
. However, since for many non-trivial games such an algorithm would require an infeasible amount of time to generate a move in a given position, a game is not considered to be solved weakly or strongly unless the algorithm can be run by existing hardware in a reasonable time. Many algorithms rely on a huge pre-generated database, and are effectively nothing more than that.
As an example, the game of tic-tac-toe
Tic-tac-toe
Tic-tac-toe, also called wick wack woe and noughts and crosses , is a pencil-and-paper game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The X player usually goes first...
is solvable as a draw for both players with perfect play (a result even manually determinable by schoolchildren). Games like nim
Nim
Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap....
also admit of a rigorous analysis using combinatorial game theory
Combinatorial game theory
Combinatorial game theory is a branch of applied mathematics and theoretical computer science that studies sequential games with perfect information, that is, two-player games which have a position in which the players take turns changing in defined ways or moves to achieve a defined winning...
.
Whether a game is solved is not necessarily the same as whether it remains interesting for humans to play. Even a strongly solved game can still be interesting if the solution is too complex to be memorized; conversely, a weakly solved game may lose its attraction if the winning strategy is simple enough to remember (e.g. Maharajah and the Sepoys
Maharajah and the Sepoys
Maharajah and the Sepoys, originally called Shatranj Diwana Shah, is a popular chess variant with different armies for white and black. It was first played in the 19th century in India....
). An ultra-weak solution (e.g. Chomp
Chomp
Chomp is a 2-player game of strategy played on a rectangular "chocolate bar" made up of smaller square blocks . The players take it in turns to choose one block and "eat it" , together with those that are below it and to its right...
or Hex
Hex (board game)
Hex is a board game played on a hexagonal grid, theoretically of any size and several possible shapes, but traditionally as an 11x11 rhombus. Other popular dimensions are 13x13 and 19x19 as a result of the game's relationship to the older game of Go...
on a sufficiently large board) generally does not affect playability.
Perfect play
In game theoryGame theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
, perfect play is the behavior or strategy of a player which leads to the best possible outcome for that player regardless of the response by the opponent. Based on the rules of a game, every possible final position can be evaluated (as a win, loss or draw). By backward reasoning
Backward chaining
Backward chaining is an inference method that can be described as working backward from the goal...
, one can recursively evaluate a non-final position as identical to that of the position that is one move away and best valued for the player whose move it is. Thus a transition between positions can never result in a better evaluation for the moving player and a perfect move in a position would be a transition between positions that are equally evaluated. As an example, a perfect player in a drawn position would always get a draw or win, never a loss. If there are multiple options with the same outcome, perfect play is sometimes considered the fastest method leading to a good result, or the slowest method leading to a bad result.
Perfect play can be generalized to non-perfect information
Perfect information
In game theory, perfect information describes the situation when a player has available the same information to determine all of the possible games as would be available at the end of the game....
games, as the strategy that would guarantee the highest minimal expected outcome
Expected value
In probability theory, the expected value of a random variable is the weighted average of all possible values that this random variable can take on...
regardless of the strategy of the opponent. As an example, the perfect strategy for Rock, Paper, Scissors
Rock-paper-scissors
Rock-paper-scissors is a hand game played by two people. The game is also known as roshambo, or another ordering of the three items ....
would be to randomly choose each of the options with equal (1/3) probability. The disadvantage in this example is that this strategy will never exploit non-optimal strategies of the opponent, so the expected outcome of this strategy versus any strategy will always be equal to the minimal expected outcome.
Although the optimal strategy of a game may not (yet) be known, a game-playing computer might still benefit from solutions of the game from certain endgame positions (in the form of endgame tablebase
Endgame tablebase
An endgame tablebase is a computerized database that contains precalculated exhaustive analysis of a chess endgame position. 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.The tablebase...
s), which will allow it to play perfectly after some point in the game. Computer chess
Computer chess
Computer chess is computer architecture encompassing hardware and software capable of playing chess autonomously without human guidance. Computer chess acts as solo entertainment , as aids to chess analysis, for computer chess competitions, and as research to provide insights into human...
programs are well-known for doing this.
Solved games
AwariOware
Oware is an abstract strategy game of Akan origin. Part of the mancala family, it is played throughout West Africa and the Caribbean. Among its many names are Ayò , Awalé , Wari , Ouri, Ouril or Uril , Warri , Adji , and Awélé...
(a game of the Mancala
Mancala
Mancala is a family of board games played around the world, sometimes called "sowing" games, or "count-and-capture" games, which describes the game-play. Mancala games play a role in many African and some Asian societies comparable to that of chess in the West, or the game of Go in Eastern Asia...
family)
- The variant of OwareOwareOware is an abstract strategy game of Akan origin. Part of the mancala family, it is played throughout West Africa and the Caribbean. Among its many names are Ayò , Awalé , Wari , Ouri, Ouril or Uril , Warri , Adji , and Awélé...
allowing game ending "grand slams" was strongly solved by Henri BalHenri BalHenri Elle Bal is a professor of Computer Science at the Vrije Universiteit, Amsterdam in the Netherlands. He is a well-known researcher in computer systems with a specialization in parallel computer systems, languages, and applications....
and John Romein at the Vrije UniversiteitVrije UniversiteitThe Vrije Universiteit is a university in Amsterdam, Netherlands. The Dutch name is often abbreviated as VU and in English the university uses the name "VU University". The university is located on a compact urban campus in the southern part of Amsterdam in the Buitenveldert district...
in AmsterdamAmsterdamAmsterdam is the largest city and the capital of the Netherlands. The current position of Amsterdam as capital city of the Kingdom of the Netherlands is governed by the constitution of August 24, 1815 and its successors. Amsterdam has a population of 783,364 within city limits, an urban population...
, NetherlandsNetherlandsThe Netherlands is a constituent country of the Kingdom of the Netherlands, located mainly in North-West Europe and with several islands in the Caribbean. Mainland Netherlands borders the North Sea to the north and west, Belgium to the south, and Germany to the east, and shares maritime borders...
(2002). Either player can force the game into a draw.
Chopsticks
- The second player can always force a win.
Connect Four
Connect Four
Connect Four is a two-player game in which the players first choose a color and then take turns dropping their colored discs from the top into a seven-column, six-row vertically-suspended grid...
- Solved first by James D. Allen (Oct 1, 1988), and independently by Victor AllisVictor AllisLouis Victor Allis is a Dutch computer scientist working in the artificial intelligence field. In his graduate work, he revealed AI solutions for Connect Four, Qubic, and Gomoku. His dissertation introduced two new game search techniques: proof-number search and dependency-based search...
(Oct 16, 1988). First player can force a win. Strongly solved by John Tromp's 8-ply database (Feb 4, 1995). Weakly solved for all boardsizes where width+height is at most 15 (Feb 18, 2006).
Draughts, English
English draughts
English draughts or checkers , also called American checkers or straight checkers or in Israel damka, is a form of draughts board game. Unlike international draughts, it is played on an eight by eight squared board with twelve pieces on each side...
(i.e. checkers)
- This 8x8 variant of draughtsDraughtsDraughts is a group of abstract strategy board games between two players which involve diagonal moves of uniform pieces and mandatory captures by jumping over the enemy's pieces. Draughts developed from alquerque...
was weakly solved on April 29, 2007 by the team of Jonathan SchaefferJonathan SchaefferJonathan Herbert Schaeffer is a Canadian researcher and professor at the University of Alberta and the Canada Research Chair in Artificial Intelligence....
, known for ChinookChinook (draughts player)Chinook is a computer program that plays English draughts , developed around 1989 at the University of Alberta, led by Jonathan Schaeffer. Other developers are Rob Lake, Paul Lu, Martin Bryant, and Norman Treloar. In July 2007, Chinook's developers announced that the program has been improved to...
, the "World Man-Machine Checkers Champion". From the standard starting position, both players can guarantee a draw with perfect play. Checkers is the largest game that has been solved to date, with a search space of 5x1020. The number of calculations involved was 1014, and those were done over a period of 18 years. The process involved from 200 desktop computerDesktop computerA desktop computer is a personal computer in a form intended for regular use at a single location, as opposed to a mobile laptop or portable computer. Early desktop computers are designed to lay flat on the desk, while modern towers stand upright...
s at its peak down to around 50.
Fanorona
Fanorona
Fanorona is an abstract strategy board game indigenous to Madagascar.-Introduction:Fanorona has three standard versions: Fanoron-Telo, Fanoron-Dimy, and Fanoron-Tsivy. The difference between these variants is the size of board played on. Fanoron-Telo is played on a 3×3 board and the difficulty of...
- Weakly solved by Maarten Schadd. The game is a draw.
Free Gomoku
Gomoku
Gomoku is an abstract strategy board game. Also called Gobang or Five in a Row, it is traditionally played with go pieces on a go board ; however, because once placed, pieces are not moved or removed from the board, gomoku may also be played as a paper and pencil game...
- Solved by Victor AllisVictor AllisLouis Victor Allis is a Dutch computer scientist working in the artificial intelligence field. In his graduate work, he revealed AI solutions for Connect Four, Qubic, and Gomoku. His dissertation introduced two new game search techniques: proof-number search and dependency-based search...
(1993). First player can force a win without opening rules.
Ghost
Ghost (game)
Ghost is a spoken word game in which players take turns adding letters to a growing word fragment, trying not to be the one to complete a valid word. Each fragment must be the beginning of an actual word, and usually some minimum is set on the length of a word that counts, such as three or four...
- Solved by Alan Frank using the Official Scrabble Dictionary in 1987.
Hex
Hex (board game)
Hex is a board game played on a hexagonal grid, theoretically of any size and several possible shapes, but traditionally as an 11x11 rhombus. Other popular dimensions are 13x13 and 19x19 as a result of the game's relationship to the older game of Go...
- A strategy-stealing argumentStrategy-stealing argumentIn combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many games, that the second player cannot have a winning strategy .The strategy-stealing argument applies to any symmetric game In combinatorial game theory, the strategy-stealing argument is a...
(as used by John Nash) will show that all square board sizes cannot be lost by the first player. Combined with a proof of the impossibility of a draw this shows that the game is ultra-weak solved as a first player win. - Strongly solved by several computers for board sizes up to 6×6.
- Jing Yang has demonstrated a winning strategy (weak solution) for board sizes 7×7, 8×8 and 9×9.
- A winning strategy for Hex with swappingPie ruleThe pie rule, sometimes referred to as the swap rule, is a meta-rule used to balance abstract strategy board games. Its use has been first reported in 1909 for a game from the Mancala family. Among recent games, Hex uses this rule...
is known for the 7×7 board. - Strongly solving hex on an N×N board is unlikely as the problem has been shown to be PSPACE-completePSPACE-completeIn complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time...
. - If Hex is played on an N × N+1 board then the player who has the shorter distance to connect can always win by a simple pairing strategy, even with the disadvantage of playing second.
- A weak solution is known for all opening moves on the 8x8 board.
Kalah
Kalah
Kalah, also called Kalaha or Mancala, is a game in the mancala family invented by William Julius Champion Jr in 1940. This game heavily favors the starting player, who will always win the three-seed to six-seed versions with perfect play...
- Most variants solved by Geoffrey Irving, Jeroen Donkers and Jos Uiterwijk (2000) except Kalah (6/6). The (6/6) variant was solved by Anders Carstensen (2011). Strong first-player advantage was proven in most cases.
L game
L game
The L game is a simple strategic game invented by Edward de Bono.The L game is a two-player turn-based game played on a board of 4×4 squares. Each player has a 3×2 L-shaped piece, and there are two 1×1 neutral pieces. On each turn, a player first must move their L piece, and then...
- Easily solvable. Either player can force the game into a draw.
Maharajah and the Sepoys
Maharajah and the Sepoys
Maharajah and the Sepoys, originally called Shatranj Diwana Shah, is a popular chess variant with different armies for white and black. It was first played in the 19th century in India....
- This asymmetrical game is a win for the sepoys player with correct play.
Nim
Nim
Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap....
- Strongly solved.
Nine Men's Morris
Nine Men's Morris
Nine Men's Morris is an abstract strategy board game for two players that emerged from the Roman Empire. The game is also known as Nine Man Morris, Mill, Mills, Merels, Merelles, and Merrills in English....
- Solved by Ralph Gasser (1993). Either player can force the game into a draw
Ohvalhu
- Weakly solved by humans, but proven by computers. (Dakon is, however, not identical to Ohvalhu, the game which actually had been observed by de Voogt)
Pentomino
Pentomino
A pentomino is a polyomino composed of five congruent squares, connected along their edges ....
es
- Weakly solved by H. K. Orman. It is a win for the first player.
Quarto
Quarto (board game)
Quarto is a board game for two players invented by Swiss mathematician Blaise Müller.It is played on a 4×4 board. There are 16 unique pieces, each of which is either:* tall or short;...
- Solved by Luc Goossens (1998). Two perfect players will always draw.
Qubic
Qubic
Qubic is the brand name of a four-in-a-row game played in a 4×4×4 matrix sold by Parker Brothers starting in 1953. The original box, and the 1972 reissue, described the game as "Parker Brothers 3D Tic Tac Toe Game." Players take turn placing pieces to get four in a row horizontally or...
- Weakly solved by Oren PatashnikOren PatashnikOren Patashnik is a computer scientist. He is notable for co-creating BibTeX, and co-writing Concrete Mathematics: A Foundation for Computer Science...
(1980) and Victor AllisVictor AllisLouis Victor Allis is a Dutch computer scientist working in the artificial intelligence field. In his graduate work, he revealed AI solutions for Connect Four, Qubic, and Gomoku. His dissertation introduced two new game search techniques: proof-number search and dependency-based search...
. The first player wins.
Free Renju
Renju
Renju is the professional variant of Gomoku, a board game originated from Japan in Heian Period. It was named Renju by Japanese journalist Ruikou Kuroiwa on December 6, 1899 in a Japanese newspaper Yorozu chouhou . It is played with black and white stones on a 15x15 intersection Go board...
- (Without opening rules) claimed to be solved by János Wagner and István Virág (2001). A first-player win.
Sim
Sim (pencil game)
The game of Sim is played by two players on a board consisting of six dots . Each dot is connected to every other dot by a line.Two players take turns coloring any uncolored lines...
- Weakly solved: win for the second player.
Teeko
Teeko
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.....
- Solved by Guy SteeleGuy L. Steele, Jr.Guy Lewis Steele Jr. , also known as "The Great Quux", and GLS , is an American computer scientist who has played an important role in designing and documenting several computer programming languages.-Biography:...
(1998). Depending on the variant either a first-player win or a draw.
Three Musketeers
Three Musketeers (game)
Three Musketeers is an abstract strategy board game by Haar Hoolim. It was published in Sid Sackson's A Gamut of Games. The game is notable in that, like the traditional Fox and geese, it uses the principle of unequal forces; the two players neither use the same types of pieces nor the same...
- Strongly solved by Johannes Laire in 2009. It is a win for the blue pieces (Cardinal Richelieu's men, or, the enemy).
Three Men's Morris
- Trivially solvable. Either player can force the game into a draw.
Tic-tac-toe
Tic-tac-toe
Tic-tac-toe, also called wick wack woe and noughts and crosses , is a pencil-and-paper game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The X player usually goes first...
- Trivially solvable. Either player can force the game into a draw.
Tigers and Goats
- Weakly solved by Yew Jin Lim (2007). The game is a draw.
Partially solved games
ChessChess
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
- Solved by retrograde computer analysisRetrograde analysisIn chess, retrograde analysis is a computational method used to solve game positions for optimal play by working backward from known outcomes , such as the construction of endgame tablebases. In game theory at large, this method is called backward induction...
for all three- to six-piece, and some seven-piece endgames, counting the two kingsKing (chess)In chess, the king is the most important piece. The object of the game is to trap the opponent's king so that its escape is not possible . If a player's king is threatened with capture, it is said to be in check, and the player must remove the threat of capture on the next move. If this cannot be...
as pieces. It is solved for all 3–3 and 4–2 endgames with and without pawns, where 5-1 endgames are assumed to be won with some trivial exceptions (see endgame tablebaseEndgame tablebaseAn endgame tablebase is a computerized database that contains precalculated exhaustive analysis of a chess endgame position. 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.The tablebase...
for an explanation). The full game has 32 pieces. Chess on a 3x3 boardMinichessMinichess is a family of chess variants played with regular chess pieces and standard rules, but on a smaller board.The motivation for these variants is to make the game simpler and shorter than the standard chess. Martin Gardner recommended 5x5 chess variant to fill short breaks during the work...
is strongly solved by Kirill Kryukov (2004). The question of whether or not chess can be perfectly solved in the future is controversial.
International Draughts
Draughts
Draughts is a group of abstract strategy board games between two players which involve diagonal moves of uniform pieces and mandatory captures by jumping over the enemy's pieces. Draughts developed from alquerque...
- All positions with two through seven pieces were solved. Positions with 4x4 and 5x3 pieces where each side had one king or less. Positions with five men versus four men, five men versus three men and one king, and four men and one king versus four men. Solved in 2007 by Ed Gilbert of the United States, computer analysis show that highly likely it always end in a draw if both players play perfectly.
Go
- Board sizes up to 4×4 are strongly solved. The 5×5 board is weakly solved for all opening moves. Humans usually play on a 19×19 board which is over 145 orders of magnitude more complex than 7x7.
Reversi
Reversi
Reversi is a board game involving abstract strategy and played by two players on a board with 8 rows and 8 columns and a set of distinct pieces for each side. Pieces typically are disks with a light and a dark face, each face belonging to one player...
(Othello)
- Strongly solved on a 4×4 and 6×6 board as a second player win in July 1993 by Joel Feinstein. On an 8×8 board (the standard one) it is mathematically unsolved, though computer analysis shows a likely draw. No strongly supposed estimates other than increased chances for the starting player (black) on 10×10 and greater boards exist.
m,n,k-game
- It is trivial to show that the second player can never win; see strategy-stealing argumentStrategy-stealing argumentIn combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many games, that the second player cannot have a winning strategy .The strategy-stealing argument applies to any symmetric game In combinatorial game theory, the strategy-stealing argument is a...
. Almost all cases have been solved weakly for k ≤ 4. Some results are known for k = 5. The games are drawn for k ≥ 8.
See also
- Computer chessComputer chessComputer chess is computer architecture encompassing hardware and software capable of playing chess autonomously without human guidance. Computer chess acts as solo entertainment , as aids to chess analysis, for computer chess competitions, and as research to provide insights into human...
- Computer OthelloComputer Othellois a reversi-based video arcade game developed and published by Nintendo. It is one of their earliest video arcade games along with Block Fever and after they did release a dedicated console called Color TV Game 6 and a variety of electromechanical arcade games earlier in the 1970s. It was...
- Game complexityGame complexityCombinatorial 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.-Measures of game complexity:...
- God's algorithmGod's algorithmGod'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...
- Zermelo's theorem (game theory)Zermelo's theorem (game theory)In game theory, Zermelo’s theorem, named after Ernst Zermelo, says that in any finite two-person game of perfect information in which the players move alternatively and in which chance does not affect the decision making process, if the game cannot end in a draw, then one of the two players must...
Further reading
- Allis, Beating the World Champion? The state-of-the-art in computer game playing. in New Approaches to Board Games Research.
External links
- Computational Complexity of Games and Puzzles by David Eppstein.
- GamesCrafters - on solving two-person games with perfect information and no chance