God's algorithm is a notion originating in discussions of ways to solve the
Rubik's Cube
The Rubik's Cube is a Three-dimensional space, 3-D combination puzzle originally invented in 1974 by Hungarians, Hungarian sculptor and professor of architecture Ernő Rubik. Originally called the Magic Cube, the puzzle was licensed by Rubik t ...
puzzle, but which can also be applied to other
combinatorial
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...
puzzle
A puzzle is a game, Problem solving, problem, or toy that tests a person's ingenuity or knowledge. In a puzzle, the solver is expected to put pieces together (Disentanglement puzzle, or take them apart) in a logical way, in order to arrive at th ...
s and
mathematical game
A mathematical game is a game whose rules, strategies, and outcomes are defined by clear mathematical parameters. Often, such games have simple rules and match procedures, such as Tic-tac-toe and Dots and Boxes. Generally, mathematical games ne ...
s. It refers to any algorithm which produces a solution having the fewest possible moves. The allusion to the Deity is based on an assumption that only an
omniscient
Omniscience () is the capacity to know everything. In Hinduism, Sikhism and the Abrahamic religions, this is an attribute of God. In Jainism, omniscience is an attribute that any individual can eventually attain. In Buddhism, there are diffe ...
being would know an optimal step from any given configuration.
Scope
Definition
The notion applies to
puzzle
A puzzle is a game, Problem solving, problem, or toy that tests a person's ingenuity or knowledge. In a puzzle, the solver is expected to put pieces together (Disentanglement puzzle, or take them apart) in a logical way, in order to arrive at th ...
s that can assume a
finite
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marke ...
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, or, more formally, the minimax value.
[ 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
In computer science, a lookup table (LUT) is an array that replaces runtime computation with a simpler array indexing operation. The process is termed as "direct addressing" and LUTs differ from hash tables in a way that, to retrieve a value v wi ...
indexed by initial configurations would allow solutions to be found very quickly, but would require an extraordinary amount of memory.
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 puzzle
A mechanical puzzle is a puzzle presented as a set of mechanically interlinked pieces in which the solution is to manipulate the whole object or parts of it. While puzzles of this type have been in use by humanity as early as the 3rd century BC ...
s like Rubik's Cube
The Rubik's Cube is a Three-dimensional space, 3-D combination puzzle originally invented in 1974 by Hungarians, Hungarian sculptor and professor of architecture Ernő Rubik. Originally called the Magic Cube, the puzzle was licensed by Rubik t ...
, Towers of Hanoi
The Tower of Hanoi (also called The problem of Benares Temple or Tower of Brahma or Lucas' Tower and sometimes pluralized as Towers, or simply pyramid puzzle) is a mathematical game or puzzle consisting of three rods and a number of disks of v ...
, and the 15 puzzle. The one-person game of peg solitaire
Peg solitaire, Solo Noble or simply Solitaire is a board game for one player involving movement of pegs on a board with holes. Some sets use marbles in a board with indentations. The game is known as solitaire in Britain and as peg solitaire in ...
is also covered, as well as many logic puzzle
A logic puzzle is a puzzle deriving from the mathematics, mathematical field of deductive reasoning, deduction.
History
The logic puzzle was first produced by Charles Lutwidge Dodgson, who is better known under his pen name Lewis Carroll, the au ...
s, such as the missionaries and cannibals problem
The missionaries and cannibals problem, and the closely related jealous husbands problem, are classic river-crossing logic puzzles. The missionaries and cannibals problem is a well-known toy problem in artificial intelligence, where it was used b ...
. These have in common that they can be modeled mathematically as a directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
, in which the configurations are the vertices, and the moves the arcs.
Mechanical puzzles
''n''-Puzzles
The Fifteen puzzle
The 15 puzzle (also called Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square and many others) is a sliding puzzle having 15 square tiles numbered 1–15 in a frame that is 4 tiles high and 4 tiles wide, leaving one unoccupied tile position ...
can be solved in 80 single-tile moves or 43 multi-tile moves in the worst case. For its generalization the ''n''-puzzle, the problem of finding an optimal solution is NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
. Therefore, whether a practical God's algorithm for this problem exists remains unknown, but appears unlikely.
Towers of Hanoi
For the Towers of Hanoi
The Tower of Hanoi (also called The problem of Benares Temple or Tower of Brahma or Lucas' Tower and sometimes pluralized as Towers, or simply pyramid puzzle) is a mathematical game or puzzle consisting of three rods and a number of disks of v ...
puzzle, a God's algorithm is known for any given number of disks. The number of moves is exponential in the number of disks .
Rubik's Cube
An algorithm to determine the minimum number of moves to solve Rubik's Cube was published in 1997 by Richard Korf. 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. Thus 20 is a sharp
Sharp or SHARP may refer to:
Acronyms
* SHARP (helmet ratings) (Safety Helmet Assessment and Rating Programme), a British motorcycle helmet safety rating scheme
* Self Help Addiction Recovery Program, a charitable organisation founded in 19 ...
upper bound
In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of .
Dually, a lower bound or minorant of is defined to be an element ...
on the length of optimal solutions. Mathematician David Singmaster
David Breyer Singmaster (born 1938) is an emeritus professor of mathematics at London South Bank University, England. A self-described metagrobologist, he has a huge personal collection of mechanical puzzles and books of brain teasers. He is mo ...
had "rashly conjectured" this number to be 20 in 1980.[Singmaster, p. 311, 1980]
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
Chess is a board game for two players, called White and Black, each controlling an army of chess pieces in their color, with the objective to checkmate the opponent's king. It is sometimes called international chess or Western chess to disti ...
and Go. Both these games have a rapidly increasing number of positions with each move. The total number of all possible positions, approximately 10154 for chess and 10180 (on a 19×19 board) for Go, 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 positions). 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
Deep Blue may refer to:
Film
* ''Deep Blues: A Musical Pilgrimage to the Crossroads'', a 1992 documentary film about Mississippi Delta blues music
* Deep Blue (2001 film), ''Deep Blue'' (2001 film), a film by Dwight H. Little
* Deep Blue (2003 ...
, for instance, searched only 11 moves ahead (counting a move by each player as two moves), reducing the search space to only 1017. 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. Evaluation algorithms are prone to make elementary mistakes 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 (American English), also known as draughts (; British English), is a group of strategy board games for two players which involve diagonal moves of uniform game pieces and mandatory captures by jumping over opponent pieces. Checkers ...
(checkers), with superficial similarities to chess, has long been suspected of being "played out" by its expert practitioners. 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. However, draughts with only positions and even fewer, , in Schaeffer's database, 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 . Nevertheless, the solution algorithm is applicable to any size problem, with a running time of .[Rueda]
See also
*Oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in a s ...
*Divine move
Players of the game of Go often use jargon to describe situations on the board and surrounding the game. Such technical terms are likely to be encountered in books and articles about Go in English as well as other languages. Many of these terms ...
(game of Go)
*''Proofs from THE BOOK
''Proofs from THE BOOK'' is a book of mathematical proofs by Martin Aigner and Günter M. Ziegler. The book is dedicated to the mathematician Paul Erdős, who often referred to "The Book" in which God keeps the most elegant proof of each mathema ...
''
*Rubik's Cube group
The Rubik's Cube group is a Group (mathematics), group (G, \cdot ) that represents the Mathematical structure, structure of the Rubik's Cube mechanical puzzle. Each element of the Set (mathematics), set G corresponds to a cube move, which is the ...
*Solved game
A solved game is a game whose outcome (win, lose or draw) 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 informa ...
Notes
References
* Baum, Eric B., ''What is Thought?'', MIT Press, 2004 .
* 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 .
* Fraser, Rober (ed); Hannah, W. (ed), ''The Draught Players' Weekly Magazine'', vol. 2, Glasgow: J H Berry, 1885.
*
* Moore, Cristopher; Mertens, Stephan, ''The Nature of Computation'', Oxford University Press, 2011 .
* Rothenberg, Gadi, ''Catalysis, God's Algorithm, and the Green Demon'', Amsterdam University Press, 2009 .
* Schaeffer, Jonathan; 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 .
*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 .
{{Rubik's Cube
Search algorithms
Logic puzzles
Mathematical games
Rubik's Cube