Solved game
this wiki
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". The game-theoretic value is the outcome of a game, when played perfectly from its initial position. In a two-player game it can be a win (W), loss (L) or draw (D) for the first player.
A few mancala games have been solved. The game-theoretic value is known for Awari (draw), Kalah (depending on the instance), MiniMancala (draw), Ohvalhu (first-player win). Some trivial games have also been completely analyzed: Micro-Wari and Nano-Wari.
A two-player game 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-constructive proof (possibly involving a strategy stealing argument) that may not actually help determine this perfect play. Any game using the pie rule is either a draw or a second-player win.
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 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.
Solved Mancala Games
Awari
Romein and Bal proved in 2002 that the game-theoretic value of Awari is a draw. The only perfect move to start a game is pit 6 (the last pit). The following move can be pit 2, 5 or 6. All the other moves are losing.
Víktor Bautista i Roca claimed on his now defunct homepage manqala.org that several Awari endgames were incorrectly analyzed by the "Awari Oracle" based on Romein's and Bal's research. Therefore it seems that the programming of Romein and Bal had major flaws and that their results are not valid. However, both sites (manqala.org and the Oracle) have been taken off the internet and no further research appears to be possible. This reveals a major problem: Most research done in solving games is not really peer-reviewed. Minor mistakes in the programming, which nevertheless can give quite different results, will usually go unnoticed.
Kalah
Donkers strongly solved (according to Allis definition) Kalah for small instances using full-game databases and weakly for larger instances by Geoffrey Irving et al. in 2001. If played perfectly, the game-theoretic value depends on the number of seeds in each hole and the number of holes per row. However, this research was based on the "Empty Capture" variant.
Game-theoretic values for different instances of Kalah
Mark Rawlings, of Gaithersburg, MD, has quantified the magnitude of the first player win in Kalah(6/6) with the "empty capture" rule (October 2015). After creation of 39 GB of endgame databases (all positions with 34 or fewer seeds), searches totaling 106 days of CPU time and over 55 trillion nodes, it was proven that, with perfect play, the first player wins by 2.
Anders Carstensen solved four variants of Kalah(6/6) including the standard game in 2011. However, he did not not publish any deeper analysis such as which moves win by which margin, so his results are of limited importance for real play. However, he made a reference player avaible for those who want to play against a perfect opponent.
MiniMancala
MiniMancala was solved by Freeling the game's inventor, in 2001 and was then implemented by Ed van Zon with two Java applications called Lite-8 and MiniMancala. With perfect play the game is a draw.
Ohvalhu
The game is weakly solved by humans, but proven by computers. It is a first player's win. "Dakon" is a misnomer because it denotes a game not identical to Ohvalhu, the game which actually had been observed by de Voogt.
See also
External Links
References
- Christensen, B. M.
- Kalaha - Nu med endnu flere kugler og huller. In: Famøs 2012 (22); 1: 34-36.
- Deledicq, A. & Popova, A.
- Wari et Solo: Le Jeu de Calcul Africain. Cedic, Paris (France) 1977
- Donkers, J., Uiterwijk, J. & Irving, G.
- Solving Kalah. In: ICGA Journal 2000; 23 (3): 139-147.
- Donkers, H. H. L. M., Voogt, A. J. de & Uiterwijk, J. W. H. M.
- Human versus Machine Problem-Solving: Winning Openings in Dakon. In: Board Games Studies 2000; 3: 79-88.
- Donkers, J.
- Comments on the Awari Solution. In: ICGA Journal 2002; 25 (3).
- Nielsen, H. S.
- Studerende løser gåden om Kalaha. In: Jyllands-Posten June 3, 2011.
- Romein, J. W. & Bal, H. E.
- Awari Is Solved. In: ICGA Journal 2002; 25 (3).
Copyright
Adapted from the Wikipedia article, "Solved game" http://en.wikipedia.org/wiki/Solved_game, used under the GNU Free Documentation License (with major contributions from Ralf Gering).