[guicho271828]

That idea is nearly 30 yrs old, it is the whole point of IDA* (Korf 85) and maybe Frontier Search (Korf 99) too. Their benefits, drawbacks and the cure are all well studied. I'm surprised some people who discuss AI do not know these famous algorithms.

MCTS's playouts do not need to backtrack (they are just the greedy probes), so it is irrelevant. By backtrack, do not confuse it with the backpropagaton in MCTS.

I do not see the connection to TPU.

[Radim]

Reversible state updates have nothing to do with IDA.

The concept is completely orthogonal to choosing which node (next state) to expand next. It's about managing the internal representation of a state.

[guicho271828]

OK, reversible updates. You need to somehow store the parent state information in order to backtrack. And the natural way to do this is to push the edge/diff info in the stack. By doing so you only have to maintain one state at a time, keeping the backtrack information compact. But when to backtrack? You surely use iterative deepening, otherwise it returns a suboptimal path or may not backtrack forever on the state space graph. You also want to prune the states? Use the sum of the depth and the heuristic lower bound. This is IDA＊. You can call a blind IDA＊ as IDDFS too, but I generally just call them IDA＊. A plain DFS is not viable in complex problems, so let's forget about it.

> choosing which node (next state) to expand next

I know this is "heuristic search", a broader class of algorithms which includes A＊ and IDA＊ and many more. But the core selling point of IDA＊ is not the "heuristic search", but its compact linear-space memory usage (thus fast) compared to A＊. So I did not suggested IDA＊ because of its heuristic search aspect.

For an efficient implementation, reversible updates are just natural and common in IDA＊. Below is an excerpt from [1]. I believe this is equivalent to what you call reversible state updates.

    * In-place Modification

    The main source of remaining overhead in the expansion function is
    the copy performed when generating each new successor (line 12 in Figure 1).
    Since IDA＊ only considers a single node for expansion at a time, and because
    our recursive implementation of depth-first search always backtracks to the
    parent before considering the next successor, it is possible to avoid copying entirely.
    We will use an optimization called in-place modification where the search 
    only uses a single state that is modified to generate each successor and
    reverted upon backtracking.

[1] Burns, E. A., Hatem, M., Leighton, M. J., & Ruml, W. (2012, July). "Implementing fast heuristic search code". In Fifth Annual Symposium on Combinatorial Search.

[Radim]

Yep, that's the one.

By the way, this "local-changes-only" approach crops up in many other places too. In CS and nature, because it's just so damn energy-efficient.

For example, check out this (recent, July 2017) paper:

Gomez, Ren, Urtasun & Grosse: "The Reversible Residual Network: Backpropagation Without Storing Activations", https://arxiv.org/abs/1707.04585.

You can't help but think of the ancient programmer's trick for swapping two variables without a temp storage...

  a = a + b;
  b = a - b;
  a = a - b;