Solved games

from Wikipedia, the free encyclopedia

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

  • Very weak dissolved (engl. Ultra weakly solved ) is a game, if one can determine the start position of the game the one game outcome that each of the two player can force at least independently of the play his opponent. Proof of this does not have to make any statement about the necessary playing styles.
  • A game is poorly solved if, in addition, a practically feasible algorithm can be specified with which the mutually optimal playing styles can be determined based on the starting position of the game.
  • A game is very well resolved if there is a general, practically feasible algorithm with which an optimal move can be calculated for each position. In contrast to weakly solved games, this algorithm must also work for positions that, based on the starting position, only occur if the game is played incorrectly.

It is important to have an algorithm that can be implemented in practice (on a computer), as the Minimax algorithm always provides a general method with which an optimal move can theoretically be calculated for every position in a finite two-person game with complete information.

Solved games

  • Checkers , the American checkers version, wassolved poorlyby Jonathan Schaeffer in 2007: A perfect player never loses.
  • Fanorona : Weakly resolved. Draw.
  • Five in a row (Free-style Gomoku, without opening rules): Strongly resolved by Victor Allis (1993). The attractive player has a winning strategy , that is, he can force a win.
  • Hex wassolved very weaklyby John Nash in 1947: Without an exchange rule, there must be a winning strategy for the attracting player, because on the one hand no game can end in a draw and on the other hand the player who follows cannot have a winning strategy, otherwise the attracting player could adopt it (argument of the above mentioned strategy clause ). With the exchange rule, there is a winning strategy for the player who follows.
  • L game : Strongly solved. Starting from the starting position, two perfect players can play indefinitely without losing.
  • Nim game : Strongly solved with methods of combinatorial game theory , also for all variants in which the last player to move wins ( Sprague-Grundy's theorem ).
  • Mühle : Weakly solved by Ralph Gasser (1993): A perfect player never loses.
  • Pentago : Strongly Resolved by Geoffrey Irving (2014). The first player wins.
  • Pentominos : poorly resolved. The attractive player has a winning strategy.
  • Sim : The second player wins.
  • Solitaire : Strongly resolved.
  • Tic-Tac-Toe : Strongly resolved. Obviously, no player has to lose.
  • Four in a row : poorly resolved, independently of each other by Victor Allis (published 1988) and James D. Allen (published 1990). The attractive player has a winning strategy if he starts in the middle column. If he starts in the column to the left or right of it, the game ends with a perfect game on both sides; if he throws his first stone into one of the four remaining columns, he loses against a perfect opponent.

Partially solved games

  • Checkers game (10 × 10 board)
    Endgames with 8 pieces, plus some 9-piece are solved.
  • Go
    5 × 5 was solved in 2002. 7 × 7 was solved in 2015.
  • Othello (Reversi)
    on 4 × 4 and 6 × 6 game boards has been solved strongly, with the player following a winning strategy. For the standard 8 × 8 board and larger boards with an even number of rows and columns, it is believed that two perfect players can create a tie. The usual game on an 8 × 8 board is almost completely studied.
  • Chess
    endgames with 2 to 7 pieces (including kings) are well resolved.
  • Sprouts Winning
    strategies for up to 6 points can be determined manually; strategies for up to 11 points were examined with the aid of a computer.

swell

  1. ↑ Ralph Gasser: Solving Nine Men's Morris , Games of No Chance, MSRI Publications, Volume 29, 1996, pp. 101–113 (PDF; 236 kB)
  2. ↑ Geoffrey Irving: Pentago is a first player win. Retrieved January 30, 2014 .
  3. ↑ HK Orman: Pentominoes: A First Player Win , Games of No Chance, MSRI Publications, Volume 29, 1996, pp. 339–345 (PDF; 131 kB)
  4. ↑ Eichler, Jäger, Ludwig (c't 07/1999) Spielverderber, Solitaire solving with the computer
  5. ↑ KingsRow: 8-stone database completely created ( Memento from March 8, 2010 in the Internet Archive )
  6. ↑ KingsRow: Tournament Report ( Memento from March 2, 2010 in the Internet Archive )
  7. ↑ 5x5 Go is solved by Erik van der Werf
  8. ↑ 7 × 7 Go is solved (article in Chinese)