Solved game

A random free two -person game with perfect information can be solved in different ways:

  • Very weak acid ( engl. ultra- weakly solved ) is a game, if you can determine the one score for the starting position of the game, which can force each of the two players regardless of the style of play of his opponent at least. A related proof must worry about the playing styles required for this assertion.
  • Solved vulnerability is a game where, in addition, a practically realizable algorithm can be specified with the optimal ways of playing both sides can be determined from the starting position of the game.
  • Solved Stark is a game, if a general, practical feasible algorithm exists, with the for each position, an optimal train can be calculated. In contrast to weak dissolved games of this algorithm must also work for those items that occur starting from the initial position only in case of faulty play.

It is important to request a practically realizable ( on a computer ) algorithm, as with the Minimax algorithm always exists a general method theoretically for each position of a finite two-person game with complete information, an optimal train can be calculated with the.

Dissolved Games

  • Checkers, the American lady version was dissolved rubbish of Jonathan Schaeffer, 2007: A perfect player never loses accordingly.
  • Five in a row ( Free -style Gomoku without opening rules ): Strongly solved by Victor Allis (1993). The attractive player has a winning strategy, ie he can force a win.
  • Hex was solved by John Nash in 1947 very weak: For the attractive player has a winning strategy must exist, because on the one hand can not match end in a draw and the other, the subsequently immigrating player can not have a winning strategy, otherwise the attractive player could transfer them (argument of the so-called strategy Klaus ).
  • L-Title: Strongly solved. Starting from the initial position of two perfect players can play endlessly without losing.
  • Nim game: Strongly solved by methods of combinatorial game theory, for all variants in which the last withdrawing player wins ( set of Sprague- Grundy ).
  • Mill: Weak solved by Ralph Gasser (1993 ): A perfect player never loses.
  • Pentago: Strongly solved by Geoffrey Irving (2014). The first player wins.
  • Pentominoes: Weak solved. The attractive player has a winning strategy.
  • Sim: The second player wins.
  • Tic Tac Toe: Highly resolved. Obviously, no player has to lose.
  • Four wins: solved weaknesses, namely independently by Victor Allis ( published in 1988 ) and James D. Allen ( published in 1990 ). The attractive player has a winning strategy if it starts in the middle column. If it starts in the column to the left or right of it, the game is a draw with perfect play on both sides; he throws his first stone in one of the four remaining columns, he loses against a perfect opponent.

Partially dissolved Games

  • Checkers (10x10 board ) Playoffs with 8 stones, to some 9 -Steiner are highly resolved.
  • Go 5x5 was dissolved. Human calculations of up to 6x7 and 7x7 by Ted Drange Kudo Norio and Nakayama Noriyuki are probably no solutions in the mathematical sense.
  • Othello ( Reversi) 4 × 4 - and 6 × 6 game boards was strongly solved, while the subsequently immigrating player has a winning strategy. For the standard 8 × 8 board and larger game boards with an even number of rows and columns is believed that two perfect players can cause a draw. The usual game on an 8 × 8 board is almost completely investigated.
  • Chess Finals with 2-7 stones ( kings included) are highly resolved.
  • Sprouts For up to 6 points to winning strategies can be determined manually, with computer assistance strategies for up to 11 items were examined.

Swell

  • Game theory
  • Dissolved game
Randomness Hex (board game) Sprague–Grundy theorem Sim (pencil game)
262742
de