This has shown up in a few discussions. Making this issue to keep track and coalesce ideas.
The core concept is that a given search is deterministic once it has been set up (i.e. puzzle, pattern, iterative deepening search options1 individual search options). This means that search nodes can be uniquely and consistently identified by canonical sequences, and in particular the particular recursive call state of a search can be identified by such a sequence. To avoid confusion with other concepts, I'm going to call this a "cursor".
This cursor a few good properties:
- The cursor is conveniently a list of moves, i.e. a flat alg. This is very easy to display and serialize (and we have very robust code for doing so), even across separate program invocations.
- The cursor is in fact continuation. This allows us to implement search resumption rather cleanly, without inventing any fancy new concepts.
- We can implement parallel search easily by sharding the canonical sequences (i.e. "start at prefix
U, end at prefix R") at each depth. This allows us to pause and resume parallel search by just adding a coordinator that can work with our existing IterativeDeepeningSearch. The result is a fairly low level of abstraction between single-threaded and multi-threaded search. (In fact, it even allows sharding to remote kernels à la Mathematica without too much extra work on top of what https://experiments.cubing.net/cubing.js/twsearch/text-ui.html can already do).
In terms of immediate benefits, it allows us to remove this TODO and implement multi-phase search (#73) beyond our current one-shot implementation. We need this for performant 4×4×4 searches and it will also benefit other puzzles like Square-1.
This has shown up in a few discussions. Making this issue to keep track and coalesce ideas.
The core concept is that a given search is deterministic once it has been set up (i.e. puzzle, pattern, iterative deepening search options1 individual search options). This means that search nodes can be uniquely and consistently identified by canonical sequences, and in particular the particular recursive call state of a search can be identified by such a sequence. To avoid confusion with other concepts, I'm going to call this a "cursor".
This cursor a few good properties:
U, end at prefixR") at each depth. This allows us to pause and resume parallel search by just adding a coordinator that can work with our existingIterativeDeepeningSearch. The result is a fairly low level of abstraction between single-threaded and multi-threaded search. (In fact, it even allows sharding to remote kernels à la Mathematica without too much extra work on top of what https://experiments.cubing.net/cubing.js/twsearch/text-ui.html can already do).In terms of immediate benefits, it allows us to remove this TODO and implement multi-phase search (#73) beyond our current one-shot implementation. We need this for performant 4×4×4 searches and it will also benefit other puzzles like Square-1.
Footnotes
Particularly search generators. ↩