Approaches to cube solving
Before the paper by McAleer et al. was published, there were two major directions for solving the Rubik’s cube:
-
By using group theory, it is possible to significantly reduce the state space to be checked. One of the most popular solutions using this approach is Kociemba’s algorithm (https://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik\%27s_Cube#Kociemba’s_algorithm).
-
By using brute-force search accompanied by manually crafted heuristics, we can direct the search in the most promising direction. A vivid example of this is Korf’s algorithm (https://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik\%27s_Cube#Korf’s_algorithm), which uses A* search with a large database of patterns to cut out bad directions.
McAleer et al. [McA+18] introduced a third approach (called autodidactic iteration, or ADI): by training the neural network (NN) on lots...
