5 ms·

I think you're confused -- they went the other way around, using the algorithm to find the optimal number. Search techniques that can quickly solve any cube wi

I think you're confused -- they went the other way around, using the algorithm to find the optimal number. Search techniques that can quickly solve any cube with a small (near-optimal) number of moves have been known for a while, mainly due to the work of Kociemba: http://www.jaapsch.net/puzzles/compcube.htm#kocal http://www.jaapsch.net/puzzles/compcube.htm#kocal The techniques used are standard AI tree/graph search algorithms with lots of Rubik's cube-specific optimizations. A few years ago, these methods became good enough to solve almost any cube quickly within 20 moves (which was conjectured to be God's number.) So the algorithm as well as a fast implementation already existed. Here's Kociemba's page http://kociemba.org/cube.htm http://kociemba.org/cube.htm and here's an iPhone app with a neat twist: you can photograph your physical cube to solve it http://www.wired.com/epicenter/2009/01/iphone-app-solv/ http://www.wired.com/epicenter/2009/01/iphone-app-solv/ What these guys did was to make further optimizations and run it on a cluster to search through all possible position sets. As they say, they can solve about 4000 positions/s (in 20 moves or less) on a single machine.

jacquesm 16y ago
I re-read the whole article once more, and I think I may be not as confused as you make it out to be. They explicitly state that they did not generate the optimal number of moves for each of those inputs, only a number <= 20. So, the question is, does a god-algorithm exist or does it not, and how will this help in finding such an algorithm?
- randomwalker 16y ago
  Your original question was whether they have an algorithm to solve in <= 20 moves or not. I answered that. Now you changed your question to whether they can solve each position optimally or not. Fine. Why don't you re-read the article once again? They state that they can solve random positions optimally at the rate of 0.36/sec, in the same table where they say 3,900/sec for solving it in 20 moves or less.
  - jacquesm 16y ago
    I clarified my question because I think that it wasn't clearly stated, and I marked my edit to make sure that it was clear that I did so (unlike others here). As for the re-reading, they don't solve the positions optimally, they brute force them so they're not in the possession of a god algorithm as far as I can see, they're using a highly optimized search strategy and that's a different beast. A 'god' algorithm would take the faces as an input and would produce the minimal number of moves without a search component. So each configuration would be processed to give you the next without evaluation of 'wrong' moves or back-tracking. That would be the 'god' algorithm. Anything else is (highly) optimized search.
    - by 16y ago
      They seem to have two different algorithms. One is given a position and it gives you the optimal solution, the fewest moves to solve that position. This is the God Algorithm. And a different, much faster, algorithm that given a position finds a solution with 20 moves or less - lets call it a Mortal Algorithm. (It does not always give you the optimal solution, with the fewest moves, just one with 20 moves or less.) My understanding is that they have just run the Mortal Algorithm against every position to prove that it can solve every position in 20 moves or less. Their God Algorithm is much too slow to run against every position. According to Wikipedia a God Algorithm only has to be 'practical', find the optimal solution to a position with a sensible amount of processing. So it can use search and back-tracking. We could term your algorithm that works without search and back-tracking as a God God Algorithm because it is an optimal sequence of processor moves that find the optimal sequence of cube moves. A God God Algorithm would be awesome, but a much more difficult thing to create. I imagine it would run orders of magnitude faster than their God Algorithm. (PS. I don't think we can entirely rule out the possibility that the God God Algorithm might contain some small amount of search or back-tracking.)
      - jacquesm 16y ago
        Ok, that sounds like a sensible summary of the positions. If I understand you correctly a god algorithm is allowed to produce the required result using whatever strategy, including partial brute forcing/searching, backtracking in order to arrive at its solution as long as it does so in a reasonable time, so is not 'brute force' per se. The reason why that didn't sit right with me (I accept your wikipedia quote as what construes a god algorithm) is that for me the 'god' algorithm would imply there is no better one, since with omniscience you don't need to make any false moves and I could not imagine a true god algorithm would be allowed to make false moves. But I guess I was wrong there. Thanks for digging that up!

jacquesm 16y ago

I re-read the whole article once more, and I think I may be not as confused as you make it out to be. They explicitly state that they did not generate the optimal number of moves for each of those inputs, only a number <= 20. So, the question is, does a god-algorithm exist or does it not, and how will this help in finding such an algorithm?

randomwalker 16y ago
Your original question was whether they have an algorithm to solve in <= 20 moves or not. I answered that. Now you changed your question to whether they can solve each position optimally or not. Fine. Why don't you re-read the article once again? They state that they can solve random positions optimally at the rate of 0.36/sec, in the same table where they say 3,900/sec for solving it in 20 moves or less.
- jacquesm 16y ago
  I clarified my question because I think that it wasn't clearly stated, and I marked my edit to make sure that it was clear that I did so (unlike others here). As for the re-reading, they don't solve the positions optimally, they brute force them so they're not in the possession of a god algorithm as far as I can see, they're using a highly optimized search strategy and that's a different beast. A 'god' algorithm would take the faces as an input and would produce the minimal number of moves without a search component. So each configuration would be processed to give you the next without evaluation of 'wrong' moves or back-tracking. That would be the 'god' algorithm. Anything else is (highly) optimized search.
  - by 16y ago
    They seem to have two different algorithms. One is given a position and it gives you the optimal solution, the fewest moves to solve that position. This is the God Algorithm. And a different, much faster, algorithm that given a position finds a solution with 20 moves or less - lets call it a Mortal Algorithm. (It does not always give you the optimal solution, with the fewest moves, just one with 20 moves or less.) My understanding is that they have just run the Mortal Algorithm against every position to prove that it can solve every position in 20 moves or less. Their God Algorithm is much too slow to run against every position. According to Wikipedia a God Algorithm only has to be 'practical', find the optimal solution to a position with a sensible amount of processing. So it can use search and back-tracking. We could term your algorithm that works without search and back-tracking as a God God Algorithm because it is an optimal sequence of processor moves that find the optimal sequence of cube moves. A God God Algorithm would be awesome, but a much more difficult thing to create. I imagine it would run orders of magnitude faster than their God Algorithm. (PS. I don't think we can entirely rule out the possibility that the God God Algorithm might contain some small amount of search or back-tracking.)
    - jacquesm 16y ago
      Ok, that sounds like a sensible summary of the positions. If I understand you correctly a god algorithm is allowed to produce the required result using whatever strategy, including partial brute forcing/searching, backtracking in order to arrive at its solution as long as it does so in a reasonable time, so is not 'brute force' per se. The reason why that didn't sit right with me (I accept your wikipedia quote as what construes a god algorithm) is that for me the 'god' algorithm would imply there is no better one, since with omniscience you don't need to make any false moves and I could not imagine a true god algorithm would be allowed to make false moves. But I guess I was wrong there. Thanks for digging that up!