God's algorithm

Last updated

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 allusion to the deity is based on the notion that an omniscient being would know an optimal step from any given configuration.

Contents

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. The highest value of this, among all initial configurations, 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 such as Rubik's Cube, the Tower 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 are the arcs.

Mechanical puzzles

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] so it is not known whether there is a practical God's algorithm.

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 increases exponentially with the number of disks (). [9]

Rubik's Cube

A scrambled Rubik's Cube 2021-01-14 18 25 51 A scrambled Rubik's Cube in the Franklin Farm section of Oak Hill, Fairfax County, Virginia.jpg
A scrambled 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, Tom Rokicki proved in 2010 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 5×1044 [13] for chess and 10180 (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×1019 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 1017. [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, though neural networks trained through reinforcement learning can provide evaluations of a position that exceed human ability. [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) 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, providing a God's algorithm for all end games of draughts which was used to prove that all perfectly played games of draughts end in a draw. [20] However, draughts with only 5×1020 positions [21] and even fewer, 3.9×1013, in the database, [22] is a much easier problem to solve –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 . Nevertheless, the solution algorithm is applicable to any size problem, with a running time scaling as . [23]

See also

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. 1 2 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 Research90 (1999), pp. 45–63.
  7. ↑ Norskog, Bruce; Davidson, Morley (December 8, 2010). "The Fifteen Puzzle can be solved in 43 moves". Domain of the Cube Forum. Retrieved March 15, 2022.
  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. ↑ Rueda, Carlos (August 2000). "An optimal solution to the Towers of Hanoi Puzzle". Universidad Autónoma de Manizales [Autonomous University of Manizales]. Manizales, Colombia. Archived from the original on 2004-06-05. Retrieved March 15, 2022.
  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. ↑ Rokicki, Tomas; Kociemba, Herbert; Davidson, Morley; Dethridge, John (2010). "God's Number is 20". Cube20.org. Retrieved March 15, 2022.
  12. ↑ Rothenberg, p. 11
  13. ↑ John Tromp. "Chess Position Ranking". GitHub .
  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

Related Research Articles

<span class="mw-page-title-main">Rubik's Cube</span> 3D combination puzzle

The Rubik's Cube is a 3D combination puzzle invented in 1974 by Hungarian sculptor and professor of architecture Ernő Rubik. Originally called the Magic Cube, the puzzle was licensed by Rubik to be sold by Pentangle Puzzles in the UK in 1978, and then by Ideal Toy Corp in 1980 via businessman Tibor Laczi and Seven Towns founder Tom Kremer. The cube was released internationally in 1980 and became one of the most recognized icons in popular culture. It won the 1980 German Game of the Year special award for Best Puzzle. As of January 2024, around 500 million cubes had been sold worldwide, making it the world's bestselling puzzle game and bestselling toy. The Rubik's Cube was inducted into the US National Toy Hall of Fame in 2014.

<span class="mw-page-title-main">Tower of Hanoi</span> Mathematical puzzle game

The Tower of Hanoi is a mathematical game or puzzle consisting of three rods and a number of disks of various diameters, which can slide onto any rod. The puzzle begins with the disks stacked on one rod in order of decreasing size, the smallest at the top, thus approximating a conical shape. The objective of the puzzle is to move the entire stack to one of the other rods, obeying the following rules:

  1. Only one disk may be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
  3. No disk may be placed on top of a disk that is smaller than it.

A solved game is a game whose outcome can be correctly predicted from any position, assuming that both players play perfectly. This concept is usually applied to abstract strategy games, and especially to games with full information and no element of chance; solving such a game may use combinatorial game theory and/or computer assistance.

<span class="mw-page-title-main">Rubik's Revenge</span> 4×4×4 Rubiks cube variation

The Rubik's Revenge is a 4×4×4 version of the Rubik's Cube. It was released in 1981. Invented by Péter Sebestény, the cube was nearly called the Sebestény Cube until a somewhat last-minute decision changed the puzzle's name to attract fans of the original Rubik's Cube. Unlike the original puzzle, it has no fixed faces: the center faces are free to move to different positions.

<span class="mw-page-title-main">Optimal solutions for the Rubik's Cube</span>

Optimal solutions for the Rubik's Cube are solutions that are the shortest in some sense. There are two common ways to measure the length of a solution. The first is to count the number of quarter turns. The second is to count the number of outer-layer twists, called "face turns". A move to turn an outer layer two quarter (90°) turns in the same direction would be counted as two moves in the quarter turn metric (QTM), but as one turn in the face metric.

<span class="mw-page-title-main">Rubik's Magic</span> Mechanical puzzle created by Erno Rubik

Rubik's Magic, like the Rubik's Cube, is a mechanical puzzle invented by Ernő Rubik and first manufactured by Matchbox in the mid-1980s.

<span class="mw-page-title-main">15 puzzle</span> Sliding puzzle with fifteen pieces and one space

The 15 puzzle is a sliding puzzle. It has 15 square tiles numbered 1 to 15 in a frame that is 4 tile positions high and 4 tile positions wide, with one unoccupied position. Tiles in the same row or column of the open position can be moved by sliding them horizontally or vertically, respectively. The goal of the puzzle is to place the tiles in numerical order.

<span class="mw-page-title-main">Pocket Cube</span> 2x2x2 combination puzzle

The Pocket Cube is a 2×2×2 combination puzzle invented in 1970 by American puzzle designer Larry D. Nichols. The cube consists of 8 pieces, which are all corners.

<span class="mw-page-title-main">Speedcubing</span> Solving Rubiks Cubes or other "twisty puzzles" with speed

Speedcubing, also referred to as speedsolving, is a competitive mind sport centered around the rapid solving of various combination puzzles. The most prominent puzzle in this category is the N×N×N (n=3) puzzle, commonly known as the Rubik's Cube. Participants in this sport are known as "speedcubers", who focus specifically on solving these puzzles at high speeds to get low clock times. The essential aspect of solving these puzzles typically involves executing a series of predefined algorithms in a particular sequence with eidetic prediction and finger tricks.

<span class="mw-page-title-main">Pyraminx</span> Variant of Rubiks Cube

The Pyraminx is a regular tetrahedron puzzle in the style of Rubik's Cube. It was made and patented by Uwe Mèffert after the original 3 layered Rubik's Cube by Ernő Rubik, and introduced by Tomy Toys of Japan in 1981.

<span class="mw-page-title-main">David Singmaster</span> British mathematician (1938–2023)

David Breyer Singmaster was an American-British mathematician who was emeritus professor of mathematics at London South Bank University, England. He had a huge personal collection of mechanical puzzles and books of brain teasers. He was most famous for being an early adopter and enthusiastic promoter of the Rubik's Cube. His Notes on Rubik's "Magic Cube" which he began compiling in 1979 provided the first mathematical analysis of the Cube as well as providing one of the first published solutions. The book contained his cube notation which allowed the recording of Rubik's Cube moves, and which quickly became the standard.

<span class="mw-page-title-main">Square-1 (puzzle)</span> Shape-shifting puzzle similar to Rubiks Cube

The Square-1 is a variant of the Rubik's Cube. Its distinguishing feature among the numerous Rubik's Cube variants is that it can change shape as it is twisted, due to the way it is cut, thus adding an extra level of challenge and difficulty. The Super Square One and Square Two puzzles have also been introduced. The Super Square One has two additional layers that can be scrambled and solved independently of the rest of the puzzle, and the Square Two has extra cuts made to the top and bottom layer, making the edge and corner wedges the same size.

<span class="mw-page-title-main">Rubik's Cube group</span> Mathematical group

The Rubik's Cube group is a group that represents the structure of the Rubik's Cube mechanical puzzle. Each element of the set corresponds to a cube move, which is the effect of any sequence of rotations of the cube's faces. With this representation, not only can any cube move be represented, but any position of the cube as well, by detailing the cube moves required to rotate the solved cube into that position. Indeed with the solved position as a starting point, there is a one-to-one correspondence between each of the legal positions of the Rubik's Cube and the elements of . The group operation is the composition of cube moves, corresponding to the result of performing one cube move after another.

Informed Search is a strategy of searching for solutions in a state space that uses knowledge specific to the given problem. Informed methods usually provide a more efficient search compared to uninformed methods.

<i>The Simple Solution to Rubiks Cube</i> 1981 book by James G. Nourse

The Simple Solution to Rubik's Cube by James G. Nourse is a book that was published in 1981. The book explains how to solve the Rubik's Cube. The book became the best-selling book of 1981, selling 6,680,000 copies that year. It was the fastest-selling title in the 36-year history of Bantam Books.

The original Rubik's cube was a mechanical 3×3×3 cube puzzle invented in 1974 by the Hungarian sculptor and professor of architecture Ernő Rubik. Extensions of the Rubik's cube have been around for a long time and come in both hardware and software forms. The major extension have been the availability of cubes of larger size and the availability of the more complex cubes with marked centres. The properties of Rubik’s family cubes of any size together with some special attention to software cubes is the main focus of this article. Many properties are mathematical in nature and are functions of the cube size variable.

<span class="mw-page-title-main">Superflip</span> Rubiks Cube configuration

The superflip or 12-flip is a special configuration on a Rubik's Cube, in which all the edge and corner pieces are in the correct permutation, and the eight corners are correctly oriented, but all twelve edges are oriented incorrectly ("flipped").

<span class="mw-page-title-main">Pyraminx Duo</span> Twisty puzzle

The Pyraminx Duo is a tetrahedral twisty puzzle in the style of the Rubik's Cube. It was suggested by Rob Stegmann, invented by Oskar van Deventer, and has now been mass-produced by Meffert's.

<span class="mw-page-title-main">Gear Cube</span> 3D combination puzzle based on the Rubiks Cube

The Gear Cube is a 3-D combination puzzle designed and created by Dutch puzzle maker Oskar van Deventer based on an idea by Bram Cohen. It was initially produced by Shapeways in 2009 and known as "Caution Cube" due to the likelihood of getting one's fingers stuck between the gears while speedcubing. Later, in 2010, it was mass-produced by Meffert's as the "Gear Cube".

<span class="mw-page-title-main">Dino Cube</span>

The Dino Cube is a cubic twisty puzzle in the style of the Rubik's Cube. It was invented in 1985 by Robert Webb, though it was not mass-produced until ten years later. It has a total of 12 external movable pieces to rearrange, compared to 20 movable pieces on the Rubik's Cube.

References


This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.