Draft ADR for phase coordinates

[lgarron]

Generic IDFS

SemiGroupActionPuzzle

Originally, twsearch assumed that:

• The only type of puzzle was KPuzzle, and
• All KPuzzle conveniences were available, including composable and invertible transformations.

This has now mostly been replaced by the SemiGroupActionPuzzle trait. It has this name because its operation are closest to a semigroup action (compared to the full group action of KPuzzle):

pub trait SemiGroupActionPuzzle: Debug + Clone {
    type Pattern: Eq + Clone + Debug;
    type Transformation: Eq + Clone + Debug;

    fn move_order(&self, r#move: &Move) -> Result<MoveCount, InvalidAlgError>;
    fn puzzle_transformation_from_move(&self, r#move: &Move) -> Result<Self::Transformation, InvalidAlgError>;

    fn do_moves_commute(&self, move1_info: &MoveTransformationInfo<Self>, move2_info: &MoveTransformationInfo<Self>) -> bool;

    fn pattern_apply_transformation(&self, pattern: &Self::Pattern, transformation_to_apply: &Self::Transformation) -> Option<Self::Pattern>;
    fn pattern_apply_transformation_into(&self, pattern: &Self::Pattern, transformation_to_apply: &Self::Transformation, into_pattern: &mut Self::Pattern) -> bool;
}

This is implemented for KPuzzle, and can be implemented for various other
puzzles. In particular, it is also implemented for specific phases of puzzle
searches so that they can use different:

• pattern/transformation representations,
• prune table implementations, and
• various other techniques like symmetry reduction.

All the methods on SemiGroupActionPuzzle take a &self parameter in order to allow information (such as implementation-specific lookup tables) to be stored on the implementation.

A vestigial GroupActionPuzzle trait remains, but it is essentially unused at the moment. It may become useful in the future when generalizing KPuzzle-specific optimizations to more puzzles.

TPuzzle

By convention, the generic type of puzzle implementing SemiGroupActionPuzzle is called a TPuzzle (since T is a common name for such a type). For example:

IDFSearchAPIData<TPuzzle: SemiGroupActionPuzzle> { /* … */ }

IDFSearch

The core engine of every search is IDFSearch, an iterative deepening
depth-first search, which takes a TPuzzle generic. It also takes a second
generic struct that allows for the "zero-cost" abstraction of compile-time
dispatch for search optimizations:

pub struct IDFSearch<
    TPuzzle: SemiGroupActionPuzzle + DefaultSearchOptimizations<TPuzzle>,
    Optimizations: SearchOptimizations<TPuzzle>,
>

pub trait SearchOptimizations<TPuzzle: SemiGroupActionPuzzle> {
    type PatternValidityChecker: PatternValidityChecker<TPuzzle>;
    type PruneTable: PruneTable<TPuzzle>;
}

pub trait PatternValidityChecker<TPuzzle: SemiGroupActionPuzzle> {
    fn is_valid(pattern: &TPuzzle::Pattern) -> bool;
}

pub trait PruneTable<TPuzzle: SemiGroupActionPuzzle> {
    fn new(/* … */) -> Self;
    fn lookup(&self, pattern: &TPuzzle::Pattern) -> Depth;
    fn extend_for_search_depth(&mut self, search_depth: Depth, approximate_num_entries: usize);
}

The generics on IDFSearch default to KPuzzle with a HashPruneTable. Also note that the name "optimizations" should probably also be revised, as (for example) bandaged puzzles may rely on them for correctness.

PhaseCoordinatePuzzle

PhaseCoordinatePuzzle is an implementation of SemiGroupActionPuzzle that is used to construct a view of a puzzle where all patterns are enumerable, such as:

• Square-1 patterns where only the shape and parity are taken into account.
• A view of 3x3x3 where only edge orientation is take into account.
• A coordinate for a 4x4x4 search phase.

Since it implements SemiGroupActionPuzzle, it can itself be passed to IDFSearch.

This construction is facilitated by at SemanticCoordinate trait implementation:

pub trait SemanticCoordinate</* … */>: /* … */
{
    fn try_new(puzzle: &TPuzzle, pattern: &TPuzzle::Pattern) -> Option<Self>;
}

This coordinate specifies the "meaning" of each pattern that will be transformed into a low-level representation (a numeric index). For example, for Square-1 phase 1 this is implemented as:

#[derive(PartialEq, Eq, Hash, Clone, Debug)]
pub(crate) struct Square1Phase1Coordinate {
    masked_pattern: KPattern,
    parity: BasicParity,
}

impl SemanticCoordinate<KPuzzle> for Square1Phase1Coordinate {
    fn try_new(_kpuzzle: &KPuzzle, full_pattern: &KPattern) -> Option<Self> {
	    if /* fails sliceability check */ {
            return None;
        }
        Some(Self {
            masked_pattern: /* pattern with all edges indistinguishable and all corners indistinguishable */,
            parity, /* conventional permutation parity */
        })
    }
}

PhaseCoordinate::new(…) enumerates the full graph of SemanticCoordinate values by:

• assigning each pattern an index when it is first seen, and
• building a fully cached move application table.

This is flexible and fast enough for our current prototyping, but we will want to go faster in the future. This can (and should) allow for more optimized mathematical implementations when possible, particularly for some 4x4x4 phases.

Composing PhaseCoordinatePuzzles

PhaseCoordinatePuzzle is designed to be composed. For example, for Square-1 phase 2 we implement SemanticCoordinate for three independent views of the square-square puzzle, and then compose them as follows:

pub(crate) type Square1Phase2Puzzle = TriplePhaseCoordinatePuzzle<
    KPuzzle,
    Phase2EdgesCoordinate,
    Phase2CornersCoordinate,
    Phase2EquatorCoordinate,
>;

Composing multiple phases

While the APIs are designed to allow automatic/ergonomic connection of multiple phases of searching, this currently requires the implementation to manually call multiple IDFSearch implementations.