Autodidactic Iteration (ADI)

Autodidactic Iteration (ADI) is the learning procedure used in DeepCube to train a neural network that evaluates Rubik’s Cube states (and provides move priors) without hand-crafted cube features or human demonstrations.^[1] The trained model is then used as guidance inside Monte Carlo Tree Search (MCTS).^[1:1]

Objective

ADI trains a parameterized function

f_\theta(s) = (v_\theta(s),\, p_\theta(s)),

where:

• v_\theta(s) is a scalar value function estimate for state s (progress toward the solved state),
• p_\theta(s) is a policy prior over moves (which actions are promising).^[1:2]

Why ADI is needed

Rubik’s Cube is an extreme sparse-reward environment: only the solved state provides a positive reward signal, and random interaction almost never reaches it at meaningful depths.^[1:3] ADI avoids this failure mode by:

• generating training states by scrambling from the solved cube (curriculum),
• using shallow search to construct targets (dense supervision),
• repeating this process to cover harder states.^[1:4]

ADI loop

1) Training state generation (curriculum)

Training inputs are created by starting from s_{\text{solved}} and applying random moves to obtain states at increasing scramble distances.^[1:5]

2) Target construction via shallow search

For each training state x, ADI performs a depth-1 breadth-first search (BFS) expansion over all actions a \in A and evaluates the current network on the children:

(v_x(a), p_x(a)) := f_\theta\!\bigl(A(x,a)\bigr).

Targets are defined using a max-backup rule:

y^v(x) := \max_{a \in A}\Bigl(R(A(x,a)) + v_x(a)\Bigr),

y^p(x) := \arg\max_{a \in A}\Bigl(R(A(x,a)) + v_x(a)\Bigr).

This yields a supervised-learning dataset of (x, y^v(x), y^p(x)) pairs that approximates an improvement step in classic dynamic programming / value-based learning.^[1:6][2][3]

3) Supervised training

The network is updated to fit the value targets (regression) and policy targets (classification). DeepCube reports using RMSProp, mean-squared error for value, and softmax cross-entropy for policy.^[1:7]

4) Stabilization (sample weighting)

To reduce divergence, the DeepCube implementation weights samples closer to the solved state more strongly (inverse-distance weighting).^[1:8]

Relationship to planning (DeepCube)

ADI does not directly produce a solver on its own. Its role is to produce a model whose outputs are used to guide planning:

• p_\theta biases exploration toward plausible moves,
• v_\theta reduces required depth by providing a learned estimate of progress.^[1:9]

DeepCube then combines these signals with an asynchronous MCTS procedure to obtain explicit move sequences on fully scrambled cubes.^[1:10]

References