They want $32 for the full pdf, but you can read the first page here:Daniel Shawul wrote: ↑Thu Jul 18, 2019 3:24 pmCan it beat this guy though who solves 17x17x17 cube in about 2 hours ? https://www.youtube.com/watch?v=7ChuKKL2PpU
I would like to understand what makes it a unique challenge. From what I understood from the abstract
- single goal state
- solved in reverse with root node being that single goal state (i.e. solved state)
- finds shortest path 60% of the time
Please add more if you read the full paper.
https://www.nature.com/articles/s42256- ... rer=nature
I did not buy the paper, but from reading the first page:
- They use weighted A* search.
- They use something called "deep approximate value iteration" to train the heuristic function used by the A* algorithm.
In regular value iteration you use a big lookup table and compute the table values by iterating the Bellman equation. (In deterministic cases, like when computing tablebases, you don't even have to iterate more than once if you compute the values in the table in a suitable order.)
If the state space it too big (like for the 3x3x3 cube) you cannot store the whole table. Therefore they instead use "deep approximate value iteration", which means they use a deep neural network as an approximation to the lookup table. The training attempts to minimize the mean squared residual from the Bellman equation. Presumably the mean is taken over the states encountered by starting from the goal position and performing random walks of progressively increasing length.
If you have a complete table you don't need to perform any search to find the solution (like for a tablebase), but since they only have an approximation they use weighted A* to find an actual solution.
Maybe the fake claim was a joke, but it is clear to me that the video is not reversed. It is not really algorithmically harder to solve a large cube than say a 5x5x5 or a 4x4x4 cube, even though it is practically much harder since it requires many more moves and each move is physically more challenging to perform.
If you take a solved cube and randomly shuffle it, then reverse the video, when you look at the video it would appear that you are making random moves that magically in the end causes the cube to be solved. In contrast, in this video the guy is gradually putting pieces into the right positions and also explains what he is doing while he is doing it.
It would be very interesting to know if their algorithm could actually be trained to learn how to solve a 17x17x17 cube. The state space is very large. Just the inner pieces can be arranged in (24!/4!^6)^56 ~= 10^868 ways. My guess is that their algorithm cannot solve 17x17x17 cubes, or else they probably would have mentioned larger cubes in the abstract.