Neural Solvers

Training data: generate_walk()

Every example starts with random walks away from the solved cube. generate_walk() returns each walk together with the moves it took, so the way back is known in advance. That makes it useful both for training and for checking a solver against a known answer.

g <- cube_group(3)
set.seed(1)
w <- generate_walk(g, n = 3, n_moves = 6)
w$moves[[1]]
#> [1] "F"  "D"  "B"  "S"  "R'" "S"
w$solution[[1]]
#> [1] "S'" "R"  "S'" "B'" "D'" "F'"

# the solution really does solve the state
identical(group_apply(g, w$states[1, ], w$solution[[1]]), group_identity(g))
#> [1] TRUE

A walk’s length is only an upper bound on the true distance, because a shorter way back may exist. Two options make the bound tighter: no_undo (on by default) refuses a move that undoes the one before, and no_cancel also refuses moves like U D U', which walk three moves and travel one.

For training, exact = FALSE draws walk lengths uniformly, so every depth is equally represented:

generate_walk(g, n = 8, n_moves = 10, exact = FALSE)$depth
#> [1] 4 2 1 9 8 5 1 4

Learning without labels: autodidactic iteration

The obvious label for a scrambled state is the length of the scramble. That label is wrong, because a scramble of 15 moves may be solvable in 12. Autodidactic iteration (ADI, from DeepCubeA) avoids the problem. The target of a state is

1 + the smallest value the network gives to any of its children

and a solved child counts as exactly 0. States one move from solved get exact targets right away, their neighbours learn from them, and correctness spreads outward as training goes on.

net <- cube_adi_model(g, arch = "resnet", encoding = "piece")
net

net <- cube_adi_train(net, iterations = 200, batch_states = 10000,
                      max_depth = 20)
tail(net$history)

cube_adi_save(net, "adi_cube3")

net <- cube_adi_load("adi_cube3", backend = "cpu")
net <- cube_adi_train(net, iterations = 100)   # carries on training
cube_adi_save(net, "adi_cube3")

Solving

There are two ways to use a trained network.

Greedy: cube_adi_solve() takes the best-looking move at every step. It never revisits a state, but it never reconsiders a choice either. It is fast, and works well near solved, where the network is accurate.

A* search: cube_adi_astar() keeps the moves it passed over and returns to them when the chosen branch stops paying. A wrong estimate then costs time rather than the solve.

set.seed(7)
s <- generate_walk(g, n = 1, n_moves = 15)$states[1, ]

greedy <- cube_adi_solve(net, s, budget = 200)
greedy$solved
length(greedy$path)

astar <- cube_adi_astar(net, s, weight = 0.6, batch = 1000)
astar$solved
astar$length
astar$nodes      # states expanded

A* orders states by weight * moves_so_far + estimated_distance.

• weight = 1 is classic A*: shorter paths, much slower.
• weight = 0 is pure greedy best-first.
• 0.6 is DeepCubeA’s choice and the default.

batch expands that many states per step and scores all their children in one call. This keeps a GPU busy, but a very large batch can make solutions longer.

Measuring a solver

Because generate_walk() knows the way back, it is easy to see how a solver behaves as the scramble gets deeper:

depths <- 4:16
rate <- sapply(depths, function(d) {
  w <- generate_walk(g, n = 50, n_moves = d, no_cancel = TRUE)
  mean(apply(w$states, 1, function(s) cube_adi_solve(net, s)$solved))
})
data.frame(depth = depths, solved = rate)

Q-models: the example scripts

The package also ships scripts for a different kind of network, a Q-model. A Q-model scores all 18 moves of a state at once instead of one distance per state. It is trained on generate_walk(pivot = TRUE): a point in the middle of a walk, plus the two moves whose value is known there, the move back and the move forward.

• inst/examples/train_cube3_q_online.R trains a transformer Q-model on fresh walks at every step, so no state is seen twice. It saves checkpoints with ckpt=, continues an interrupted run with resume=, and trains a saved model further with init=:

  Rscript inst/examples/train_cube3_q_online.R steps=20000 ckpt=1000
  Rscript inst/examples/train_cube3_q_online.R init=<model dir> depth=16 steps=8000 lr=5e-4

• inst/examples/diag_cube3_q.R takes a model and solves scrambles of falling depth, greedily and by beam search side by side. That shows at which depth the model starts to fail.