God's algorithm

God's algorithm is a notion originating in discussions of ways to solve the Rubik's Cube puzzle,[1] but which can also be applied to other combinatorial puzzles and mathematical games.[2] It refers to any algorithm which produces a solution having the fewest possible moves, the idea being that only an omniscient being would know an optimal step from any given configuration.

Scope

Definition

The notion applies to puzzles that can assume a finite number of "configurations", with a relatively small, well-defined arsenal of "moves" that may be applicable to configurations and then lead to a new configuration. Solving the puzzle means to reach a designated "final configuration", a singular configuration, or one of a collection of configurations. To solve the puzzle a sequence of moves is applied, starting from some arbitrary initial configuration.

Solution

An algorithm can be considered to solve such a puzzle if it takes as input an arbitrary initial configuration and produces as output a sequence of moves leading to a final configuration (if the puzzle is solvable from that initial configuration, otherwise it signals the impossibility of a solution). A solution is optimal if the sequence of moves is as short as possible. This count is known as God's number,[3] or, more formally, the minimax value.[4] God's algorithm, then, for a given puzzle, is an algorithm that solves the puzzle and produces only optimal solutions.

Some writers, such as David Joyner, consider that for an algorithm to be properly referred to as "God's algorithm", it should also be practical, meaning that the algorithm does not require extraordinary amounts of memory or time. For example, using a giant lookup table indexed by initial configurations would allow solutions to be found very quickly, but would require an extraordinary amount of memory.[5]

Instead of asking for a full solution, one can equivalently ask for a single move from an initial but not final configuration, where the move is the first of some optimal solution. An algorithm for the single-move version of the problem can be turned into an algorithm for the original problem by invoking it repeatedly while applying each move reported to the present configuration, until a final one is reached. Conversely, any algorithm for the original problem can be turned into an algorithm for the single-move version by truncating its output to its first move.

Examples

Well-known puzzles fitting this description are mechanical puzzles like Rubik's Cube, Towers of Hanoi, and the 15 puzzle. The one-person game of peg solitaire is also covered, as well as many logic puzzles, such as the missionaries and cannibals problem. These have in common that they can be modeled mathematically as a directed graph, in which the configurations are the vertices, and the moves the arcs.

n-Puzzles

The Fifteen puzzle can be solved in 80 single-tile moves[6] or 43 multi-tile moves[7] in the worst case. For its generalization the n-puzzle, the problem of finding an optimal solution is NP-hard.[8] Therefore, whether a practical God's algorithm for this problem exists remains unknown, but appears unlikely.

Towers of Hanoi

For the Towers of Hanoi puzzle, a God's algorithm is known for any given number of disks. The number of moves is exponential in the number of disks (${\displaystyle 2^{n}-1}$).[9]

Rubik's Cube

An algorithm to determine the minimum number of moves to solve Rubik's Cube was published in 1997 by Richard Korf.[10] While it had been known since 1995 that 20 was a lower bound on the number of moves for the solution in the worst case, it was proven in 2010 through extensive computer calculations that no configuration requires more than 20 moves.[11] Thus 20 is a sharp upper bound on the length of optimal solutions. Mathematician David Singmaster had "rashly conjectured" this number to be 20 in 1980.[4]

Unsolved games

Some well known games with a very limited set of simple well-defined rules and moves have nevertheless never had their God's algorithm for a winning strategy determined. Examples are the board games chess and Go.[12] Both these games have a rapidly increasing number of positions with each move. The total number of all possible positions, approximately 10¹⁵⁴ for chess[13] and 10¹⁸⁰ (on a 19×19 board) for Go,[14] is much too large to allow a brute force solution with current computing technology (compare the now solved, with great difficulty, Rubik's Cube at only about 4.3×10¹⁹ positions[15]). Consequently, a brute force determination of God's algorithm for these games is not possible. While chess computers have been built that are capable of beating even the best human players, they do not calculate the game all the way to the end. Deep Blue, for instance, searched only 11 moves ahead (counting a move by each player as two moves), reducing the search space to only 10¹⁷.[16] After this, it assessed each position for advantage according to rules derived from human play and experience.

Even this strategy is not possible with Go. Besides having hugely more positions to evaluate, no one so far has successfully constructed a set of simple rules for evaluating the strength of a Go position as has been done for chess.[17] Evaluation algorithms are prone to make elementary mistakes[18] so even for a limited look ahead with the goal limited to finding the strongest interim position, a God's algorithm has not been possible for Go.

On the other hand, draughts (checkers), with superficial similarities to chess, has long been suspected of being "played out" by its expert practitioners.[19] In 2007 Schaeffer et al. proved this to be so by calculating a database of all positions with ten or fewer pieces. Thus Schaeffer has a God's algorithm for all end games of draughts and used this to prove that all perfectly played games of draughts will end in a draw.[20] However, draughts with only 5×10²⁰ positions[21] and even fewer, 3.9×10¹³, in Schaeffer's database,[22] is a much easier problem to crack and is of the same order as Rubik's cube.

The magnitude of the set of positions of a puzzle does not entirely determine whether a God's algorithm is possible. The already solved Tower of Hanoi puzzle can have an arbitrary number of pieces, and the number of positions increases exponentially as ${\displaystyle 3^{n}}$. Nevertheless, the solution algorithm is applicable to any size problem, and since the algorithm running time is ${\displaystyle O(2^{n})}$ the problem is NP-hard.[23]

See also

• Oracle machine
• Divine move
• Proofs from THE BOOK

Notes

1. Paul Anthony Jones, Jedburgh Justice and Kentish Fire: The Origins of English in Ten Phrases and Expressions, Hachette UK, 2014 ISBN 1472116224.
2. See e.g. Rubik's Cubic Compendium by Ernö Rubik, Tamás Varga, Gerzson Kéri, György Marx, and Tamás Vekerdy (1987, Oxford University Press, ISBN 0-19-853202-4), p. 207: "...the Pyraminx is much simpler than the Magic Cube... Nicholas Hammond has shown that God's Algorithm is at most 21 moves (including the four trivial vertex moves). [More recently, three people have found God's Algorithm. The maximal number of moves is 15 (including the four vertex moves).]"
3. Jonathan Fildes (August 11, 2010). "Rubik's Cube quest for speedy solution comes to an end". BBC News.
4. Singmaster, p. 311, 1980
5. Joyner, page 149
6. A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt, The parallel search bench ZRAM and its applications, Annals of Operations Research 90 (1999), pp. 45–63.
7. "The Fifteen Puzzle can be solved in 43 moves". Domain of the Cube Forum
8. Daniel Ratner, Manfred K. Warmuth (1986). "Finding a shortest solution for the N × N extension of the 15-puzzle is intractable". in Proceedings AAAI-86. National Conference on Artificial Intelligence, 1986. pp. 168–172.
9. Carlos Rueda, "An optimal solution to the Towers of Hanoi Puzzle".
10. Richard E. Korf, "Finding optimal solutions to Rubik's Cube using pattern databases", Proc. Natl. Conf. on Artificial Intelligence (AAAI-97), Providence, Rhode Island, Jul 1997, pp. 700–705.
11. "God's Number is 20". Cube20.org
12. Rothenberg, p. 11
13. Baum, p. 187
14. Baum, p. 199
15. Singmaster, 1981
16. Baum, p. 188
17. Baum, p. 197
    • Mohammadian, p. 11
18. Baum, p.197
19. Fraser & Hannah, p. 197
20. Moore & Mertens, chapter 1.3, "Playing chess with God"
21. Schaeffer et al., p. 1518
22. Moore & Mertens, "Notes" to chapter 1
23. Rueda

References

• Baum, Eric B., What is Thought?, MIT Press, 2004 ISBN 0262025485.
• Davis, Darryl N.; Chalabi, T.; Berbank-Green, B., "Artificial-life, agents and Go", in Mohammadian, Masoud, New Frontiers in Computational Intelligence and its Applications, pp. 125–139, IOS Press, 2000 ISBN 9051994761.
• Fraser, Rober (ed); Hannah, W. (ed), The Draught Players' Weekly Magazine, vol. 2, Glasgow: J H Berry, 1885.
• David Joyner (2002). Adventures in Group Theory. Johns Hopkins University Press. ISBN 0-8018-6947-1.
• Moore, Cristopher; Mertens, Stephan, The Nature of Computation, Oxford University Press, 2011 ISBN 0191620807.
• Rothenberg, Gadi, Catalysis, God's Algorithm, and the Green Demon, Amsterdam University Press, 2009 ISBN 9056295896.
• Jonathan Schaeffer, Neil Burch, Yngvi Björnsson, Akihiro Kishimoto, Martin Müller, Robert Lake, Paul Lu, Steve Sutphen, "Checkers is solved", Science, vol. 317, no. 58444, pp. 1518–1522, 14 September 2007.
• Singmaster, David, Notes on Rubik's Magic Cube, Penguin, 1981 ISBN 0-907395-00-7.
• Singmaster, David, "The educational value of the Hungarian 'Magic Cube'", Proceedings of the Fourth International Congress on Mathematical Education, held in Berkeley, California, 10–16 August 1980, pp. 307–312, Birkhauser Boston Inc, 1983 ISBN 978-0-8176-3082-9.
• ME