Talk:God's algorithm

Old discussion

Okay, the following claims need citations:

1. God's algorithm is a notion originating in discussions of ways to solve the Rubik's Cube puzzle
2. ...but which can also be applied to other combinatorial puzzles
3. ...and mathematical games.
4. The notion applies to puzzles that can assume a finite number of "configurations"... God's algorithm, then, for a given puzzle, is an algorithm that solves the puzzle and produces only optimal solutions.
5. For the notion of "God's algorithm" to be meaningful, it must further be required that the algorithm be practical...
6. For the Towers of Hanoi puzzle, a God's algorithm exists for any given number of disks.

These are all reasonable ideas, but where do they come from? Melchoir 21:36, 23 September 2006 (UTC)

I believe that the claim that "For the notion of "God's algorithm" to be meaningful, it must further be required that the algorithm be practical" is in fact incorrect. The normal usage of the term "God's algorithm" is precisely the opposite; it's the theoretically best algorithm, whether or not it is practical. For example, in this 1995 essay by Peter Suber, he says "That is, we do not know whether "God's Algorithm" is a family of methods with some learnable structure, or whether it is a chaotic tangle of disconnected pathways.", implying that he would consider a tangle of disconnected pathways to be a "God's algorithm". Indeed, the very name "God's algorithm" seems to me to have been invented to indicate that this was the best algorithm, neglecting considerations of practicality to a mere mortal. I have never, outside this page, seen a requirement that an algorithm be practical to be considered a "God's algorithm". I will wait a week to see if such a reference is posted, then edit the main page to correct this if there is no such reference posted. Andylatto 15:59, 29 January 2007 (UTC)

Fine. I added some references but left in {{unreferenced}} since not all of your concerns have been addressed. I removed {{OR}} since there appears to be no original research in the page. CRGreathouse (t | c) 01:47, 25 September 2006 (UTC)

Well, it still looks like original research to me. The Towers of Hanoi reference doesn't speak of "God's algorithms" or any other concept that is claimed to have historically arisen from the Rubik's cube. How is it relevant to this article? Melchoir 02:14, 25 September 2006 (UTC)

The reference shows a "practical algorithm that produces a solution having the least possible number of moves" for the generalized Tower of Hanoi puzzle. You're right, it doesn't use the term, but I was just trying to get the soircing started. There are no sources on the origin of the term -- for all I know the term started with the Tower of Hanoi and was later applied to Rubik's Cube. (I've read otherwise, but I have no references handy. We already agree that the article needs references, though, so there's no argument there.)

I've numbered your claims, above. (1) needs a reference. That the concept can be applied to other puzzles and games is sufficiently obvious that it needs no reference, but I'm sure one can be found if needed for (2) and (3). (4) and (5) follow directly from the definition, and as such need no source; of course you may be pointing out that no reference actually gives a sufficient definition (I haven't read the reference that was already in the article, it probably has a definition but I don't know) in which case I agree. (6) I have addressed with a reference. CRGreathouse (t | c) 06:40, 25 September 2006 (UTC)

again, I don't think it's correct that (5) follows from the definition. Every usage I've seen of the term "God's algorithm" refers to the theoretically best algorithm, whether practical to those who are not gods or not. Andylatto 15:59, 29 January 2007 (UTC)

The problem of terminology and definitions is troubling to me. It's way too easy to extend concepts to wider and wider contexts, but without any nontrivial results addressing an extension, it's not so easy to demonstrate that it's the right one or that it's useful or notable. And on Wikipedia, extending a definition beyond its verifiable meanings violates WP:NOR. I suspect that Cube enthusiasts on the Internet are reinventing the square wheel with this concept. But I'm not familiar with the established body of research on algorithms, so I could be wrong. I'll just urge everyone to be skeptical about things that seem obvious or seem to follow directly, but which might have been made up here. Melchoir 07:43, 25 September 2006 (UTC)

Googling "God's algorithm" gives plenty of early hits that show where the term comes from, such as this 1992 posting by Dik T. Winter to the cube-lovers list, this 1995 essay by Peter Suber on a variation to the game, and this 1996 posting to sci.math. All hits of an early date use the term in connection with Rubik's cube. It is also easy to find many hits that show how the term is presently commonly understood, such as this announcement of an optimal solver. The way-back machine shows the term in use like that on that page on July 25, 2003. Other examples: Kociemba's solver, Jaap's puzzle site.

The text in the referenced Joyner book seems to be the same as this text from a draft of a book called "Applied Abstract Algebra", namely: "Let $G$ be the group of a permutation puzzle. Find the diameter of the Cayley graph of $G$. Sometimes this is called God's algorithm, though here that term is reserved for a harder version of the problem, stated below. This diameter problem is unsolved for must puzzles (including the $3\times 3$ Rubik's cube) and appears to be very difficult computationally (see [J1] for a discussion of similar problems). [...] Let $G$ be the group of a permutation puzzle and let $v$ be a vertex in the Cayley graph of $G$. Find an algorithm for determining a path from $v$ to the vertex $v_{0}$ associated to the identity having length equal to the distance from $v$ to $v_{0}$. This problem is much harder. The algorithm, if it exists, is called God's algorithm." This definition is more restricted since it only applies to permutation puzzles. The earliest use I found, the posting by Dik T. Winter mentioned, above discusses upper bounds on the lengths of optimal solutions for Rubik's cube, which corresponds to the diameter in the associated graph -- which happens to be a Cayley graph for this puzzle. The essay by Peter Suber really discusses algorithms, not just diameters. Although I don't have evidence to back this up, it is clear from the Winter posting that the term was already in use, and it is eminently reasonable to assume that the term originally was introduced for some notion of solving algorithm instead of "just" for a graph diameter. Most of the web references I gave illustrating present use, even when in the context of Rubik's cube, give a definition that does not explicitly apply specifically to the cube but is more general.

Can these web references used as references adressing Melchoir's concerns (1) and (2)?

My personal feeling is, if anyone who cares (and has access to a browser) can easily verify out that the term comes from discussions on optimal solutions to Rubik's cube, and see for themselves that the present use has a more general definition, then we need not insist on references to "reliable sources" stating this as a fact. --Lambiam^Talk 13:13, 25 September 2006 (UTC)

Unclear

While reading this it was not clear to me if that was a notion or an specific algorithm. At first I thought that it was a real algorithm called god's algorithm, by the end of the article I began to think that in a fact that an algorithm can be called a "god algorithm" if it fit the definition. May be the blurb at beginning should be adapted to make this more clear.

The first two sentences of the introductory paragraph go like this:

God's algorithm is a notion [...]. It stands for any practical algorithm that [...].

(my italics). I'd think that this clinches it that God's algorithm is a notion and not a specific algorithm.  --Lambiam^Talk

???

But you must take our "knowledege" of these known algorithms to create the God's algorithm. really god's algorithm is the least number of moves to solve a Puzzle from any state. we already in theory can say that the cube can always be solve in Sub20 moves using a 2phrase algorithm, but gods algorithm is a test of all possible moves from any given state. lets say we use god's algorithm, we still have to test every other set of moves from 20 to 19 and so on untill we can asume we have found the shortest algorithm. so even knowing the meaning or use of "God's algorithm" this set of algoithms would still take years to find the best solution for all possible scrambles. —Preceding unsigned comment added by 70.94.48.44 (talk) 22:55, 6 November 2008 (UTC)

On algorithms

Although the notion of "practicality" for algorithms makes a useful distinction, it is not common in computer science. Algorithms are required to be finite on any input. As Rubik's Cube and similar puzzles have a finite set of states, there are no problems in the puzzle that can not be answered by algorithms. In fact, we know God's algorithm, because we know algorithms that solve the shortest-path algorithm in any finite graph. What we do not know is the result of running the algorithm on the Rubik's Cube puzzle. This is a subtle but important distinction.

The article is quite imprecise and not well-sourced. 21:13, 26 November 2007 (UTC)

Towers of Hanoi and Gods algorithm

relevance of Towers of Hanoi could be explained a bit. There is one specific and well known solution, and *any* other solution would be a less efficient solution ,and could be reduced to the one true solution by removal of "incorrect move- reverse incorrect move" pairs —Preceding unsigned comment added by 202.92.33.210 (talk) 01:45, 6 June 2008 (UTC)

Coined by David Singmaster or John Conway or someone else?

I'm copying a quote contained in an article in another language version:

John Conway, one of the world's greatest group theorists, observed that the Cube obeys what are known as conservation (or parity) laws, meaning that some moves are simply not possible. Either Conway or one of his colleagues at Cambridge defined the shortest route from any given position back to the starting position as „God's Algorithm.“

I do not at the moment have at hands the book this quote is taken from (second footnote in the current revision), but it seems to be a 2009 book with Singmaster as one of authors. Could someone double-check this (or find another source)? stannic 09:39, 24 May 2017 (UTC)

The above quote appears in Jerry Slocum, David Singmaster, Wei-Hwa Huang, Dieter Gebhardt, Geert Hellings (2009). The Cube: The Ultimate Guide to the World's Bestselling Puzzle — Secrets, Stories, Solutions. p. 26. ISBN 978-1-57912-805-0.{{cite book}}: CS1 maint: multiple names: authors list (link). It is in the chapter "The History of the Cube" by Singmaster. stannic 03:55, 27 May 2017 (UTC)

@Stannic: It looks like I'm to blame for putting that in. I thought I remembered Singmaster making the claim of coining in Notes on Rubik's Cube, but it is over thirty years since I have owned that and it looks like it was a bad idea to rely on memory that far back. I did do some WP:BEFORE when I put it in and found a 1980 paper by Singmaster where he uses the term in quotes, thus implying it is a newly coined term. That does not, of course, necessarily mean that Singmaster did the coining, but it was enough to convince me that I had reemembered right. SpinningSpark 15:10, 27 May 2017 (UTC)

On page 34 of "Notes on Rubik's Magic Cube", under section "Minimum Number of Moves", Singmaster writes "...one is tempted to conjecture that every position can be achieved in at most 20 moves. This minimax value might be called the length of God's algorithm." This is in "Addendum number four" (London, 16 January 1980; slightly revised on 3 August 1980).

On page 53, under title "Cayley graphs and antipodes", it is written "Holroyd wonders if the whole group of the cube has a unique antipode. Resolving this may require the complete description of God's algorithm (p 34)."

Without seeing the 2009 book, it indeed seems reasonable to read this as if Singmaster actually coined the term. Based on what I read in these two books, I guess Singmaster might heard of the term "God's algorithm" somewhere between the summer of 1978 (the International Congress of Mathematicians in Helsinki) and the August of 1980. stannic 02:13, 28 May 2017 (UTC)

Give algorithms in simple cases?

Would it be interesting, or not, to give God's algorithm in some of the simplest cases? e.g., for the Tower of Hanoi it can be formulated as: UNTIL solved DO: IF disk(last_move) != smallest THEN move(disk = smallest, direction = one_further_clockwise) ELSE move(disk = other_than_smallest, destination = only_possible_choice) END_IF END_DO. — MFH:Talk 14:40, 14 December 2020 (UTC)

That is not only unsourced, it is incorrect. It will only work for an even number of discs, not an odd number (depending on what you mean by clockwise). And to answer your actual question, no I don't think it would benefit this article to give algorithms. Several are already given on the Tower of Hanoi page which is a mote suiteable place for them. SpinningSpark 13:56, 16 December 2020 (UTC)

NP-hardness of Towers of Hanoi

Under unsolved games, it is stated that the solution to Towers of Hanoi is NP-hard, but the given citation makes no reference to the optimal solution being NP-hard, only that it is O(2^n). Which is only sufficient to prove that it is not NP. 128.187.116.8 (talk) 17:30, 1 April 2022 (UTC)

Fixed. SpinningSpark 17:41, 3 April 2022 (UTC)

Practicality

It seems obvious to me that throughout the article, it is assumed that God's algorithms should be possible to run within a practical length of time. For example, it is mentioned that God's algorithm for chess is not known. However, I can easily produce an algorithm which is guaranteed to always produce a perfect move since the game tree is finite (min-max algorithm with no depth limit). Only problem is the running time, which would be longer than the lifetime of the universe.

This should be reflected in the article somehow. 94.44.252.205 (talk) 18:21, 21 March 2024 (UTC)