4 ms·

jacquesm said: They explicitly state that they did not generate the optimal number of moves You say: They state that they can solve random positions op

jacquesm said: They explicitly state that they did not generate the optimal number of moves You say: They state that they can solve random positions optimally Those two statements contradict each other. However: AFAIK the existing algorithm, which they used, has not been proven to solve the problem optimally. It has now been shown that it can solve any position in at most 20 moves, but there's still the chance it solves a position in 20 moves that could optimally be solved in 19. Because the upper bound of 20 moves coincides with the proven lower bound of 20 moves, we know God's number. That does not mean that this must be God's algorithm.

DougBTX 16y ago
"can" is conditional, so the two statements do not contradict. They can solve random positions optimally at 0.36 positions per second. But their goal was to lower the upper bound on God's number to 20, not to find all the optimal solutions. So what they did do, for all starting positions, was find good solutions, which they can solve at a rate of 3,900 positions per second.
- Confusion 16y ago
  True, they indeed do not contradict each other. I hadn't yet heard that there actually was an algorithm that could find optimal solutions, but I admit it's been a long time since I was interested in the issue. Because of the time difference between generation a solution and generating the optimal solution, I'm guessing the algorithm bruteforces the optimal solutions, which explains part of the confusion: I was thinking about an algorithm that generates the optimal solution directly.
  - tman 16y ago
    I have the feeling you're not a programmer. An algorithm that generates the optimal solution for a given configuration is trivial. Do a breadth-first search of the results of each move until you get to a solved cube. Ta da, you're done! Now, if you want to do it fast, that's a different story.
    - Confusion 16y ago
      An algorithm that could find the optimal solution in practice. For instance, in 0.36s, as in the article. A theoretical algorithm that finds the optimal solution is trivial; you don't need to be a programmer to come up with that one.

DougBTX 16y ago

"can" is conditional, so the two statements do not contradict. They can solve random positions optimally at 0.36 positions per second. But their goal was to lower the upper bound on God's number to 20, not to find all the optimal solutions. So what they did do, for all starting positions, was find good solutions, which they can solve at a rate of 3,900 positions per second.

Confusion 16y ago
True, they indeed do not contradict each other. I hadn't yet heard that there actually was an algorithm that could find optimal solutions, but I admit it's been a long time since I was interested in the issue. Because of the time difference between generation a solution and generating the optimal solution, I'm guessing the algorithm bruteforces the optimal solutions, which explains part of the confusion: I was thinking about an algorithm that generates the optimal solution directly.
- tman 16y ago
  I have the feeling you're not a programmer. An algorithm that generates the optimal solution for a given configuration is trivial. Do a breadth-first search of the results of each move until you get to a solved cube. Ta da, you're done! Now, if you want to do it fast, that's a different story.
  - Confusion 16y ago
    An algorithm that could find the optimal solution in practice. For instance, in 0.36s, as in the article. A theoretical algorithm that finds the optimal solution is trivial; you don't need to be a programmer to come up with that one.