Recently, Approximate Policy Iteration (API) algorithms have achieved super-human proficiency in two-player zero-sum games such as Go, Chess, and Shogi without human data. These API algorithms iterate between two policies: a slow policy (tree search), and a fast policy (a neural network). In these two-player games, a reward is always received at the end of the game. However, the Rubik’s Cube has only a single solved state, and episodes are not guaranteed to terminate. This poses a major problem for these API algorithms since they rely on the reward received at the end of the game. We introduce Autodidactic Iteration: an API algorithm that overcomes the problem of sparse rewards by training on a distribution of states that allows the reward to propagate from the goal state to states farther away. Autodidactic Iteration is able to learn how to solve the Rubik’s Cube and the 15-puzzle without relying on human data. Our algorithm is able to solve 100% of randomly scrambled cubes while achieving a median solve length of 30 moves — less than or equal to solvers that employ human domain knowledge. The Rubik's Cube is a classic combination game that poses unique and interesting challenges for AI and machine learning. Although the state space is astronomically large (4.2 × 10 19 different states for the 3x3x3 cube), only a single state is considered solved. Furthermore, unlike the game of Go or Chess, the Rubik's Cube is a single-player game and a sequence of random moves, no matter how long, is unlikely to end in the solved state. Developing reinforcement learning algorithms to deal with this property of the Rubik's Cube might provide insight into other sparse-reward environments. While methods for solving the Rubik's Cube have been developed, only relatively recently have methods been derived that can compute the minimal number of moves required to solve the cube from any given starting configuration BID22 . In addition, the Rubik's Cube and its solutions are deeply rooted in group theory, raising interesting and broader questions about the applicability of machine learning methods to complex symbolic systems, including mathematics. Finally, the classical 3x3x3 Rubik's Cube is only one representative of a much larger family of possible combination puzzles, broadly sharing the characteristics described above and including: (1) Rubik's Cubes with longer edges (e.g. 4x4x4); (2) Rubik's Cubes in higher dimensions (e.g. 2x2x2x2); as well as (3) Rubik's cube on non-cubic geometries (Pyriminix, etc) and their combinations. As the length of the sides and dimensions are increased, the complexity of the underlying combinatorial problems rapidly increases and, for instance, God's numbers for the 4x4x4 cube is not known. In short, for all these reasons, the Rubik's Cube and its variations pose interesting challenges for machine learning. Here we develop deep reinforcement learning methods, in particular a new form of Approximate Policy Iteration (API), for addressing these challenges.Figure 1: An illustration of DeepCube. The training and solving process is split up into ADI and MCTS. First, we iteratively train a DNN by estimating the true value of the input states using breadth-first search. Then, using the DNN to guide exploration, we solve cubes using Monte Carlo Tree Search. See methods section for more details.Approximate Policy Iteration BID5 BID2 BID13 BID25 BID18 ) is a core Reinforcement Learning (RL) algorithm. Recently, a new type of API algorithm, called Dual Policy Iteration BID33 , has achieved success in two player zero-sum games such as Go, Chess, Shogi and Hex BID0 BID28 BID9 . AlphaZero BID30 and ExIt BID0 are examples of Dual Policy Iteration. These algorithms update the policy in a more sophisticated way than traditional API methods by using two policies: a fast policy (usually a neural network) and a slow policy (usually tree search). The fast policy is trained via supervised learning on data generated from gameplay from the slow policy. The slow policy then uses the fast policy to guide the tree search. In this way, the fast policy is used to improve the slow policy, and the slow policy generates better data to train the fast policy.This work is the first to solve the Rubik's Cube with reinforcement learning. Although DPI works for two-player games, our work is the first DPI algorithm to succeed in an environment with a high number of states and a small number of reward states. A number of these "needle in a haystack" environments such as generating meaningful sentences or code are seen as long-term goals for the field of AI. There is no clear way to apply current DPI algorithms such as AlphaZero or ExIt to sparse-reward environments such as the Rubik's Cube. This is because a randomly initialized policy will be unlikely to encounter the single reward state. This will cause the value function to be biased or divergent and the fast policy will not converge to the optimal policy. In our work we overcome this problem by training the fast policy on a distribution of states that propagate the reward signal to from the goal state to the further states.Our algorithm, called Autodidactic Iteration (ADI), trains a neural network value and policy function through an iterative process. These neural networks are the "fast policy" of DPI described earlier.In each iteration, the inputs to the neural network are created by starting from the goal state and randomly taking actions. The targets seek to estimate the optimal value function by performing a breadth-first search from each input state and using the current network to estimate the value of each of the leaves in the tree. Updated value estimates for the root nodes are obtained by recursively backing up the values for each node using a max operator. The policy network is similarly trained by constructing targets from the move that maximizes the value. After the network is trained, it is combined with MCTS to effectively solve the Rubik's Cube. We call the resulting solver DeepCube. DeepCube is based on similar principles as AlphaZero and ExIt, however, these methods receive their reward when the game reaches a terminal state, which is guaranteed to occur given enough play time. On the other hand, one is not guaranteed to find a terminal state in the Rubik's Cube environment and therefore may only encounter rewards of -1, which does not provide enough information to solve the problem. DeepCube addresses this by selecting a state distribution for the training set that allows the reward to be propagated from the terminal state to other states. In addition, while AlphaZero and ExIt make use advanced tree-search algorithms to update the policy, DeepCube is able to find success using the faster and simpler depth-1 BFS.The depth-1 BFS used to improve the policy can also be viewed as doing on-policy temporal difference learning BID34 , specifically TD(0) with function approximation. In this case, the TD(0) algorithm uses a deterministic greedy policy where each episode is one step long. Off-policy methods are often used to train a deterministic policy by using a stochastic behavior policy to facilitate exploration. An alternative approach, called exploring starts, instead changes the distribution of starting states and can also be used to train a deterministic policy in an on-policy fashion BID35 . We use a similar approach to exploring starts by ensuring exploration through the selection of the starting state distribution. The Rubik's Cube can be thought of as a classical planning problem. While traditional planning algorithms, such as Dijkstra's algorithm, would require an infeasible amount of memory to work on environments a state space as large as the Rubik's Cube, we show that Dual Policy Iteration can find a solution path in such an environment. For future work, we look to apply Autodidactic Iteration to a variety of other problems with similar characteristics such as robotic manipulation, two-player games, and path finding. Léon Bottou defines reasoning as "algebraically manipulating previously acquired knowledge in order to answer a new question" BID6 . Many machine learning algorithms do not reason about problems but instead use pattern recognition to perform tasks that are intuitive to humans, such as object recognition. By combining neural networks with symbolic AI, we are able to create algorithms which are able to distill complex environments into knowledge and then reason about that knowledge to solve a problem. DeepCube is able to teach itself how to reason in order to solve a complex environment with only one positive reward state using pure reinforcement learning.A KNOWLEDGE LEARNED DeepCube discovered a notable amount of Rubik's Cube knowledge during its training process, including the knowledge of how to use complex permutation groups and strategies similar to the best human "speed-cubers". For example, DeepCube heavily uses one particular pattern that commonly appears when examining normal subgroups of the cube: aba −1 . That is, the sequences of moves that perform some action a, performs a different action b, and then reverses the first action with a −1 . An intelligent agent should use these conjugations often because it is necessary for manipulating specific cubelets while not affecting the position of other cubelets.We examine all of the solutions paths that DeepCube generated for the 640 fully scrambled cubes by moving a sliding window across the solutions strings to gather all triplets. We then compute the frequency of each triplet and separate them into two categories: matching the conjugation pattern aba −1 and not matching it. We find that the top 14 most used triplets were, in fact, the aba −1 conjugation. We also compare the distribution of frequencies for the two types of triplets. In Figure 6 , we plot the distribution of frequencies for each of the categories. We notice that conjugations appear consistently more often than the other types of triplets.We also examine the strategies that DeepCube learned. Often, the solver first prioritizes completing a 2x2x2 corner of the cube. This will occur approximately at the half way point in the solution. Then, it uses these conjugations to match adjacent edge and corner cubelets in the correct orientation, and it returns to either the same 2x2x2 corner or to an adjacent one. Once each pair of corner-edge pieces is complete, the solver then places them into their final positions and completes the cube. An example of this strategy is presented in FIG3 . This mirrors a strategy that advanced human "speed-cubers" employ when solving the cube, where they prioritize matching together corner and edge cubelets before placing them in their correct locations. Each layer is fully connected. We use elu activation on all layers except for the outputs. A combined value and policy network results in more efficient training compared to separate networks. (Silver et al., 2017b) .We used a feed forward network as the architecture for f θ as shown in Figure 7 . The outputs of the network are a 1 dimensional scalar v, representing the value, and a 12 dimensional vector p, representing the probability of selecting each of the possible moves. The network was then trained using ADI for 2,000,000 iterations. The network witnessed approximately 8 billion cubes, including repeats, and it trained for a period of 44 hours. Our training machine was a 32-core Intel Xeon E5-2620 server with three NVIDIA Titan XP GPUs.During play, the neural network prediction is the major bottleneck for performance. In order to counteract this, we implemented a parallel version of MCTS that had 32 independent workers that shared a single MCTS search tree. Each of the workers queue their prediction requests, and the neural network batches all requests and processes them simultaneously. This parallelization sped up the solver 20x compared to a single core implementation.
We solve the Rubik's Cube with pure reinforcement learning Solution to solving Rubik cube using reinforcement learning (RL) with Monte-Carlo tree search (MCTS) through autodidactic iteration.  This work solves Rubik's Cube using an approximate policy iteration method called Autodidactic iteration, overcoming the problem of sparse rewards by creating its own rewards system. Introduces a deep RL algorithm to solve the Rubik's cube that handles the huge state space and very sparse reward of the Rubik's cube