Algorithms

PATHOS algorithms are organized by family. The auto-solver picks the most powerful compatible algorithm via Algorithm.score_for — see the Modes & Anytime delivery guide for how mode="auto" makes AnytimeAStar the default on A*-family problems.

Base

Algorithm

Algorithm(space: Space)

Bases: ABC

Source code in pathos/algorithms/base.py

def __init__(self, space: Space) -> None:
    missing = self.requires - space.capabilities
    if missing:
        raise ValueError(
            f"{self.__class__.__name__} requires capabilities: "
            f"{', '.join(c.name for c in missing)}"
        )
    self.space = space
    self._n_workers: int = space._n_workers

score_for classmethod

score_for(space: Space) -> float

Context-aware preference score for space. Higher = preferred.

The auto-solver picks the compatible algorithm with the highest score_for(space). Defaults to float(power_rank), so any algorithm that doesn't care about problem context keeps its existing fixed-rank behavior.

Override to encode self-knowledge that isn't captured by the coarse static rank — for example, "I work well on small problems but lose to a sibling on large ones", or "without @successors I degenerate to a no-op, so cede to siblings that don't need it".

Returning a value below power_rank lets the algorithm cede to better-suited siblings without changing its global ordering.

Source code in pathos/algorithms/base.py

@classmethod
def score_for(cls, space: Space) -> float:
    """Context-aware preference score for `space`. Higher = preferred.

    The auto-solver picks the compatible algorithm with the highest
    `score_for(space)`. Defaults to `float(power_rank)`, so any
    algorithm that doesn't care about problem context keeps its
    existing fixed-rank behavior.

    Override to encode self-knowledge that isn't captured by the
    coarse static rank — for example, "I work well on small problems
    but lose to a sibling on large ones", or "without `@successors`
    I degenerate to a no-op, so cede to siblings that don't need it".

    Returning a value below `power_rank` lets the algorithm cede to
    better-suited siblings without changing its global ordering.
    """
    return float(cls.power_rank)

Meta-algorithms

Meta-algorithms compose base algorithms. Four ship in v0.2.0 — one per family — and each wins selection under mode="auto" on its capability shape. See the Modes & Anytime delivery guide for the cascade tables.

AnytimeAStar

AnytimeAStar(space: Space)

Bases: Algorithm

Anytime A* — meta-algorithm that delivers best-effort under a wall-clock budget.

Runs a cascade of progressively-tighter A* variants [GreedyBestFirst, WeightedAStar(5), WeightedAStar(3), WeightedAStar(2), WeightedAStar(1.5), AStar], keeping the best incumbent across phases. Exits cleanly when space._cancel_requested() is set (either by the Solver's SIGALRM or by an outer meta-algorithm).

Wins auto-selection only when space._mode == "auto" — its score_for returns -inf otherwise so users explicitly opting into "exact" or "approximate" keep the base-algorithm pick.

Requires the same capabilities as AStar (the heaviest of the cascade).

Source code in pathos/algorithms/base.py

def __init__(self, space: Space) -> None:
    missing = self.requires - space.capabilities
    if missing:
        raise ValueError(
            f"{self.__class__.__name__} requires capabilities: "
            f"{', '.join(c.name for c in missing)}"
        )
    self.space = space
    self._n_workers: int = space._n_workers

AnytimeLocal

AnytimeLocal(space: Space)

Bases: Algorithm

Anytime Local Search — meta-algorithm that delivers best-effort under a wall-clock budget for pure-optimization spaces.

Runs a cascade [HillClimbing, SimulatedAnnealing, TabuSearch]: HillClimbing is a cheap fast-probe (greedy descent, gets stuck in local optima); SimulatedAnnealing and TabuSearch are escape phases that explore around the incumbent. The best (lowest-cost) result across all phases is returned — UNLIKE AnytimeCSP, lower-cost semantics is meaningful for local search, so the AnytimeAStar incumbent rule applies.

Wins auto-selection only when space._mode == "auto" — score_for returns -inf otherwise so users explicitly opting into "exact" or "approximate" keep the base-algorithm pick.

Requires only the intersection of HC/SA/Tabu: SUCCESSORS+EVALUATE. Does NOT declare GOAL, so on goal-bearing spaces the goal-honoring filter in Solver._select keeps AnytimeLocal out — letting AnytimeAStar (with HEURISTIC) or uninformed goal algorithms win instead. This is intentional: pure-optimization is AnytimeLocal's lane.

Source code in pathos/algorithms/base.py

def __init__(self, space: Space) -> None:
    missing = self.requires - space.capabilities
    if missing:
        raise ValueError(
            f"{self.__class__.__name__} requires capabilities: "
            f"{', '.join(c.name for c in missing)}"
        )
    self.space = space
    self._n_workers: int = space._n_workers

AnytimeCSP

AnytimeCSP(space: Space)

Bases: Algorithm

Anytime CSP — meta-algorithm that delivers best-effort under a wall-clock budget for CSP-shaped spaces.

Runs a cascade [MinConflicts (if EVALUATE present), Backtracking]. MinConflicts is fast but incomplete; Backtracking is complete but may exhaust the budget on hard instances. The first phase that finds a consistent complete assignment wins — for CSPs, any solution is a solution (there is no further "improvement" to chase), so the cascade exits early instead of running all phases.

Wins auto-selection only when space._mode == "auto" AND the space is CSP-shaped (initial state is a dict — partial assignment). Requires only SUCCESSORS+GOAL (the Backtracking floor); EVALUATE is used to extend the cascade with MinConflicts when available.

Mirrors the AnytimeAStar pattern in pathos/algorithms/informed.py.

Source code in pathos/algorithms/base.py

def __init__(self, space: Space) -> None:
    missing = self.requires - space.capabilities
    if missing:
        raise ValueError(
            f"{self.__class__.__name__} requires capabilities: "
            f"{', '.join(c.name for c in missing)}"
        )
    self.space = space
    self._n_workers: int = space._n_workers

AnytimeAdversarial

AnytimeAdversarial(space: Any, max_depth: int = 100)

Bases: Algorithm

Anytime Adversarial Search — meta-algorithm for game spaces.

Runs iterative deepening over AlphaBeta (2-player) or Negamax (3+ player), threading the prior depth's principal variation as pv_hint into the next depth's call. Best move at deepest fully- completed depth wins.

Wins auto-selection only when space._mode == "auto" — score_for returns -inf otherwise so users explicitly opting into "exact" or "approximate" keep the base-algorithm pick.

Cancel-token cooperation at two granularities: between phases (depth-loop top), and inside the underlying recursion (AB/Negamax return (nan, None) on cancel, surfaced as not_found by their solve(), interpreted by AnytimeAdversarial as 'phase failed' and fall back to last good incumbent).

Requires the intersection of AB/Negamax: SUCCESSORS+TERMINAL+UTILITY.

Source code in pathos/algorithms/adversarial.py

def __init__(self, space: Any, max_depth: int = 100) -> None:
    super().__init__(space)
    self.max_depth = max_depth

Uninformed

BFS

BFS(space: Space)

Bases: Algorithm

Breadth-First Search — complete, optimal for unit-cost graphs.

Requires: successors, goal.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		10.

Source code in pathos/algorithms/base.py

def __init__(self, space: Space) -> None:
    missing = self.requires - space.capabilities
    if missing:
        raise ValueError(
            f"{self.__class__.__name__} requires capabilities: "
            f"{', '.join(c.name for c in missing)}"
        )
    self.space = space
    self._n_workers: int = space._n_workers

DFS

DFS(space: Space)

Bases: Algorithm

Depth-First Search — memory-efficient but incomplete on infinite graphs.

Requires: successors, goal.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		5.

Source code in pathos/algorithms/base.py

def __init__(self, space: Space) -> None:
    missing = self.requires - space.capabilities
    if missing:
        raise ValueError(
            f"{self.__class__.__name__} requires capabilities: "
            f"{', '.join(c.name for c in missing)}"
        )
    self.space = space
    self._n_workers: int = space._n_workers

IDDFS

IDDFS(space: Space)

Bases: Algorithm

Iterative Deepening DFS — optimal memory with BFS-like completeness.

Requires: successors, goal.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		8.

Source code in pathos/algorithms/base.py

def __init__(self, space: Space) -> None:
    missing = self.requires - space.capabilities
    if missing:
        raise ValueError(
            f"{self.__class__.__name__} requires capabilities: "
            f"{', '.join(c.name for c in missing)}"
        )
    self.space = space
    self._n_workers: int = space._n_workers

UCS

UCS(space: Space)

Bases: Algorithm

Uniform-Cost Search (Dijkstra) — optimal for weighted graphs.

Requires: successors, goal, evaluate.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		12.

Source code in pathos/algorithms/base.py

def __init__(self, space: Space) -> None:
    missing = self.requires - space.capabilities
    if missing:
        raise ValueError(
            f"{self.__class__.__name__} requires capabilities: "
            f"{', '.join(c.name for c in missing)}"
        )
    self.space = space
    self._n_workers: int = space._n_workers

Informed

AStar

AStar(space: Space)

Bases: Algorithm

A* search — optimal pathfinding with admissible heuristic.

Requires: successors, goal, heuristic, evaluate. Selects the path minimizing g(n) + h(n) where g is actual cost and h is an admissible heuristic estimate to goal.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		30 (preferred over BFS/DFS/Greedy when available).

Source code in pathos/algorithms/base.py

def __init__(self, space: Space) -> None:
    missing = self.requires - space.capabilities
    if missing:
        raise ValueError(
            f"{self.__class__.__name__} requires capabilities: "
            f"{', '.join(c.name for c in missing)}"
        )
    self.space = space
    self._n_workers: int = space._n_workers

GreedyBestFirst

GreedyBestFirst(space: Space)

Bases: Algorithm

Greedy Best-First search — fast but not optimal; follows heuristic greedily.

Requires: successors, goal, heuristic.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		20.

Source code in pathos/algorithms/base.py

def __init__(self, space: Space) -> None:
    missing = self.requires - space.capabilities
    if missing:
        raise ValueError(
            f"{self.__class__.__name__} requires capabilities: "
            f"{', '.join(c.name for c in missing)}"
        )
    self.space = space
    self._n_workers: int = space._n_workers

WeightedAStar

WeightedAStar(space: Any, weight: float = 2.0)

Bases: Algorithm

Weighted A* — trades optimality for speed via inflated heuristic.

Requires: successors, goal, heuristic, evaluate.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		28.

Source code in pathos/algorithms/informed.py

def __init__(self, space: Any, weight: float = 2.0) -> None:
    super().__init__(space)
    self.weight = weight

IDAstar

IDAstar(space: Space)

Bases: Algorithm

IDA* — iterative deepening A*, memory-efficient optimal search.

Requires: successors, goal, heuristic, evaluate.

NOTE: Recursive shape; v1 does not implement cancel-token checks (deferred to v2). The Solver's watchdog SIGALRM-TimeoutError backstop kills runaway IDA* searches and returns not_found. To use IDA* under mode="auto" cooperatively, wait for v2 or pin candidates=[IDAstar] with the mode="exact" semantics.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		25.

Source code in pathos/algorithms/base.py

def __init__(self, space: Space) -> None:
    missing = self.requires - space.capabilities
    if missing:
        raise ValueError(
            f"{self.__class__.__name__} requires capabilities: "
            f"{', '.join(c.name for c in missing)}"
        )
    self.space = space
    self._n_workers: int = space._n_workers

BidirectionalAStar

BidirectionalAStar(space: Space)

Bases: Algorithm

Bidirectional A* — searches from both ends to meet in the middle.

Requires: successors, goal, heuristic, evaluate, reverse_successors.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		35.

Source code in pathos/algorithms/base.py

def __init__(self, space: Space) -> None:
    missing = self.requires - space.capabilities
    if missing:
        raise ValueError(
            f"{self.__class__.__name__} requires capabilities: "
            f"{', '.join(c.name for c in missing)}"
        )
    self.space = space
    self._n_workers: int = space._n_workers

Local Search

HillClimbing

HillClimbing(space: Any, max_restarts: int = 1, max_sideways: int = 0)

Bases: Algorithm

Hill Climbing local search — greedily improves state via neighbors.

Requires: successors, evaluate.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		15.

Source code in pathos/algorithms/local.py

def __init__(self, space: Any, max_restarts: int = 1, max_sideways: int = 0) -> None:
    super().__init__(space)
    self.max_restarts = max_restarts
    self.max_sideways = max_sideways

score_for classmethod

score_for(space: Any) -> float

Bump HC above TabuSearch (18) on vector-state pure-optimization problems. Empirically (benchmarks/FINDINGS.md §2b) HC matches or beats TS on every TourSpace size from 5 to 25 cities and is 4-5× faster — the rigorous-sounding "TS escapes local optima" argument doesn't pay off on smooth 2-opt landscapes. Goal-bearing problems are unaffected because the goal-preference filter in Solver._select already eliminates HC there.

Source code in pathos/algorithms/local.py

@classmethod
def score_for(cls, space: Any) -> float:
    """Bump HC above TabuSearch (18) on vector-state pure-optimization
    problems. Empirically (benchmarks/FINDINGS.md §2b) HC matches or
    beats TS on every TourSpace size from 5 to 25 cities and is
    4-5× faster — the rigorous-sounding "TS escapes local optima"
    argument doesn't pay off on smooth 2-opt landscapes. Goal-bearing
    problems are unaffected because the goal-preference filter in
    Solver._select already eliminates HC there.
    """
    if (
        Capability.GOAL not in space.capabilities
        and isinstance(space._initial, (list, tuple))
    ):
        return float(cls.power_rank) + 5  # 15+5=20, above TabuSearch=18
    return float(cls.power_rank)

TabuSearch

TabuSearch(space: Any, max_iter: int = 100, tabu_size: int = 10)

Bases: Algorithm

Tabu Search — escapes local optima via short-term memory of visited states.

Requires: successors, evaluate.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		18.

Source code in pathos/algorithms/local.py

def __init__(self, space: Any, max_iter: int = 100, tabu_size: int = 10) -> None:
    super().__init__(space)
    self.max_iter = max_iter
    self.tabu_size = tabu_size

LocalBeamSearch

LocalBeamSearch(space: Any, k: int = 5, max_iter: int = 100)

Bases: Algorithm

Local Beam Search — maintains k parallel states and expands best neighbors.

Requires: successors, evaluate.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		16.

Source code in pathos/algorithms/local.py

def __init__(self, space: Any, k: int = 5, max_iter: int = 100) -> None:
    super().__init__(space)
    self.k = k
    self.max_iter = max_iter

Evolutionary / Metaheuristic

SimulatedAnnealing

SimulatedAnnealing(space: Any, max_iter: int = 1000, T0: float = 100.0, cooling: float = 0.99)

Bases: Algorithm

Simulated Annealing — probabilistic local search with cooling schedule.

Requires: successors, evaluate.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		17.

Source code in pathos/algorithms/evolutionary.py

def __init__(self, space: Any, max_iter: int = 1000,
             T0: float = 100.0, cooling: float = 0.99) -> None:
    super().__init__(space)
    self.max_iter = max_iter
    self.T0 = T0
    self.cooling = cooling

GeneticAlgorithm

GeneticAlgorithm(space: Any, pop_size: int = 50, generations: int = 100, crossover_fn: Callable[..., Any] | None = None, mutate_fn: Callable[..., Any] | None = None, mutation_rate: float = 0.1)

Bases: Algorithm

Genetic Algorithm — population-based evolutionary optimization.

Requires: evaluate. Caller must supply crossover_fn and mutate_fn for non-trivial state types.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		14.

Source code in pathos/algorithms/evolutionary.py

def __init__(self, space: Any, pop_size: int = 50, generations: int = 100,
             crossover_fn: Callable[..., Any] | None = None,
             mutate_fn: Callable[..., Any] | None = None,
             mutation_rate: float = 0.1) -> None:
    super().__init__(space)
    self.pop_size = pop_size
    self.generations = generations
    self.crossover_fn = crossover_fn
    self.mutate_fn = mutate_fn
    self.mutation_rate = mutation_rate

score_for classmethod

score_for(space: Any) -> float

Without @successors AND without user-supplied operators (which the auto-selector can't inspect), GA degenerates to deepcopy children with no variation — see commit ddd85dd. Cede the auto-pick to DifferentialEvolution/ParticleSwarm on pure- {evaluate} spaces by penalizing the rank there. A user who wants GA on a pure-{evaluate} space passes it through solver(candidates=[GeneticAlgorithm]) with real operators.

Source code in pathos/algorithms/evolutionary.py

@classmethod
def score_for(cls, space: Any) -> float:
    """Without @successors AND without user-supplied operators (which
    the auto-selector can't inspect), GA degenerates to deepcopy
    children with no variation — see commit ddd85dd. Cede the
    auto-pick to DifferentialEvolution/ParticleSwarm on pure-
    {evaluate} spaces by penalizing the rank there. A user who
    wants GA on a pure-{evaluate} space passes it through
    `solver(candidates=[GeneticAlgorithm])` with real operators.
    """
    if Capability.SUCCESSORS not in space.capabilities:
        return float(cls.power_rank) - 10  # 14 → 4, below DE(13)/PSO(12)
    return float(cls.power_rank)

DifferentialEvolution

DifferentialEvolution(space: Any, pop_size: int = 20, generations: int = 100, F: float = 0.8, CR: float = 0.9)

Bases: Algorithm

Differential Evolution — vector-based evolutionary optimization for continuous spaces.

Requires: evaluate. State must be a list/vector.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		13.

Source code in pathos/algorithms/evolutionary.py

def __init__(self, space: Any, pop_size: int = 20, generations: int = 100,
             F: float = 0.8, CR: float = 0.9) -> None:
    super().__init__(space)
    self.pop_size = pop_size
    self.generations = generations
    self.F = F
    self.CR = CR

ParticleSwarm

ParticleSwarm(space: Any, pop_size: int = 30, generations: int = 100, w: float = 0.7, c1: float = 1.5, c2: float = 1.5, bounds: list[tuple[float, float]] | None = None)

Bases: Algorithm

Particle Swarm Optimization — population of particles guided by personal best and global best with inertia.

Each particle has a position vector and a velocity vector. The velocity is updated each generation by an inertia component, a cognitive pull toward the particle's own historical best, and a social pull toward the swarm's global best. Position then advances by the velocity.

Requires: evaluate. State must be a numeric vector (list/tuple of int/float). Bounds are estimated from the initial swarm (per-dimension min/max expanded by 50%) unless supplied explicitly; positions are clamped to bounds on each step.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		12 — sibling of DifferentialEvolution (13), kept below DE so a registered tie doesn't reshuffle existing auto-picks.

Source code in pathos/algorithms/evolutionary.py

def __init__(
    self,
    space: Any,
    pop_size: int = 30,
    generations: int = 100,
    w: float = 0.7,           # inertia weight
    c1: float = 1.5,          # cognitive coefficient
    c2: float = 1.5,          # social coefficient
    bounds: list[tuple[float, float]] | None = None,
) -> None:
    super().__init__(space)
    self.pop_size = pop_size
    self.generations = generations
    self.w = w
    self.c1 = c1
    self.c2 = c2
    self.bounds = bounds

Adversarial

Minimax

Minimax(space: Any, max_depth: int = 100, pv_hint: list[tuple[Any, Any]] | None = None)

Bases: Algorithm

Minimax search for two-player zero-sum games.

Requires: successors, terminal, utility.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		40.

Source code in pathos/algorithms/adversarial.py

def __init__(
    self,
    space: Any,
    max_depth: int = 100,
    pv_hint: list[tuple[Any, Any]] | None = None,
) -> None:
    super().__init__(space)
    self.max_depth = max_depth
    self.pv_hint = pv_hint

AlphaBeta

AlphaBeta(space: Any, max_depth: int = 100, pv_hint: list[tuple[Any, Any]] | None = None)

Bases: Algorithm

Alpha-Beta pruning — Minimax with branch pruning for efficiency.

Requires: successors, terminal, utility.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		45 (preferred over Minimax when available).

Source code in pathos/algorithms/adversarial.py

def __init__(
    self,
    space: Any,
    max_depth: int = 100,
    pv_hint: list[tuple[Any, Any]] | None = None,
) -> None:
    super().__init__(space)
    self.max_depth = max_depth
    self.pv_hint = pv_hint

Negamax

Negamax(space: Any, max_depth: int = 100, pv_hint: list[tuple[Any, Any]] | None = None)

Bases: Algorithm

Negamax — Minimax variant using score negation for multi-player support.

Requires: successors, terminal, utility.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		42 (bumped to 52 by score_for when _players > 2).

Source code in pathos/algorithms/adversarial.py

def __init__(
    self,
    space: Any,
    max_depth: int = 100,
    pv_hint: list[tuple[Any, Any]] | None = None,
) -> None:
    super().__init__(space)
    self.max_depth = max_depth
    self.pv_hint = pv_hint

MCTS

MCTS(space: Any, iterations: int = 1000)

Bases: Algorithm

Monte Carlo Tree Search — simulation-based game tree exploration.

Requires: successors, terminal, utility.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		43.

Source code in pathos/algorithms/adversarial.py

def __init__(self, space: Any, iterations: int = 1000) -> None:
    super().__init__(space)
    self.iterations = iterations

CSP

Backtracking

Backtracking(space: Space)

Bases: Algorithm

Backtracking search — systematic recursive CSP solver.

Uses the space's successors as CSP expansion (typically via CSPSpace).

Requires: successors, goal.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		9.

Source code in pathos/algorithms/base.py

def __init__(self, space: Space) -> None:
    missing = self.requires - space.capabilities
    if missing:
        raise ValueError(
            f"{self.__class__.__name__} requires capabilities: "
            f"{', '.join(c.name for c in missing)}"
        )
    self.space = space
    self._n_workers: int = space._n_workers

ForwardChecking

ForwardChecking(space: Space)

Bases: Algorithm

Forward Checking — Backtracking with look-ahead pruning.

Before recursing, checks that each child has at least one valid successor.

The current look-ahead is shallow (a child is pruned only when it has no successors and is not itself a goal), so node counts match plain Backtracking and the constant factor is higher. Until real domain-level pruning is implemented, FC is ranked below Backtracking so the auto- solver picks the faster of the two.

Requires: successors, goal.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		8 (below Backtracking's 9).

Source code in pathos/algorithms/base.py

def __init__(self, space: Space) -> None:
    missing = self.requires - space.capabilities
    if missing:
        raise ValueError(
            f"{self.__class__.__name__} requires capabilities: "
            f"{', '.join(c.name for c in missing)}"
        )
    self.space = space
    self._n_workers: int = space._n_workers

MinConflicts

MinConflicts(space: Any, max_iter: int = 1000)

Bases: Algorithm

Min-Conflicts heuristic — local repair CSP solver.

Repeatedly selects the neighbor that minimizes constraint violations.

Requires: successors, goal, evaluate.

Attributes:

Name	Type	Description
requires		Capability set needed.
power_rank		19.

Source code in pathos/algorithms/csp.py

def __init__(self, space: Any, max_iter: int = 1000) -> None:
    super().__init__(space)
    self.max_iter = max_iter