Documentation
¶
Overview ¶
Package algorithms provides pure function implementations for the MCTS system.
Architecture:
Algorithms are pure functions that process immutable snapshots and produce deltas. They are designed for concurrent execution via goroutines. ┌─────────────────────────────────────────────────────────────────────────────┐ │ ALGORITHM EXECUTION │ ├─────────────────────────────────────────────────────────────────────────────┤ │ │ │ Activity (Orchestrator) │ │ │ │ │ ▼ │ │ ┌─────────────────────────────────────────────────────────────────────┐ │ │ │ Runner │ │ │ │ Executes algorithms in goroutines, collects results via channels │ │ │ └───────────────────────┬─────────────────────────────────────────────┘ │ │ │ │ │ ┌───────────────┼───────────────┐ │ │ ▼ ▼ ▼ │ │ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │ │ │ Algorithm │ │ Algorithm │ │ Algorithm │ ← Goroutines │ │ │ PN-MCTS │ │ Transposition│ │ UnitProp │ │ │ └──────┬──────┘ └──────┬──────┘ └──────┬──────┘ │ │ │ │ │ │ │ ▼ ▼ ▼ │ │ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │ │ │ Result │ │ Result │ │ Result │ ← Channels │ │ │ (out,delta) │ │ (out,delta) │ │ (out,delta) │ │ │ └──────┬──────┘ └──────┬──────┘ └──────┬──────┘ │ │ │ │ │ │ │ └───────────────┴───────────────┘ │ │ │ │ │ ▼ │ │ ┌─────────────┐ │ │ │ Composite │ ← Merged deltas │ │ │ Delta │ │ │ └─────────────┘ │ │ │ └─────────────────────────────────────────────────────────────────────────────┘
Algorithm Contract:
Algorithms MUST: 1. Be pure functions - no side effects, no mutation of inputs 2. Check ctx.Done() at regular intervals (every 100ms max) 3. Report progress via ReportProgress() to avoid deadlock detection 4. Return partial results when cancelled (if SupportsPartialResults) 5. Return typed deltas describing state changes 6. Implement eval.Evaluable for testing and metrics Algorithms MUST NOT: 1. Mutate the snapshot or input 2. Access global state 3. Perform I/O operations 4. Ignore cancellation for more than 100ms
Hard/Soft Signal Boundary:
Algorithms respect the hard/soft signal boundary: - Hard signals (compiler, tests): Can set node status to DISPROVEN - Soft signals (LLM, heuristics): Cannot set DISPROVEN, only guide search
Algorithm Categories:
┌─────────────────────────────────────────────────────────────────────────────┐ │ SEARCH │ PN-MCTS, Transposition, UnitProp │ │ LEARNING │ CDCL, Watched Literals │ │ CONSTRAINTS │ TMS, AC-3, Semantic Backprop │ │ PLANNING │ HTN, Blackboard │ │ GRAPH │ Tarjan SCC, Dominators, VF2 │ │ STREAMING │ AGM Sketch, Count-Min, HyperLogLog, MinHash, LSH, L0, WL │ └─────────────────────────────────────────────────────────────────────────────┘
Example Usage:
// Create a runner
runner := algorithms.NewRunner(10) // capacity for 10 results
// Get snapshot
snapshot := crs.Snapshot()
// Run algorithms in parallel
runner.Run(ctx, pnmcts, snapshot, &pnmcts.Input{NodeID: "root"})
runner.Run(ctx, zobrist, snapshot, &zobrist.Input{})
// Collect results
delta, results, err := runner.Collect(ctx)
if err != nil {
return err
}
// Apply merged delta
_, err = crs.Apply(ctx, delta)
Index ¶
Constants ¶
This section is empty.
Variables ¶
View Source
var ( // ErrNilContext is returned when context is nil. ErrNilContext = crs.ErrNilContext // ErrNilSnapshot is returned when snapshot is nil. ErrNilSnapshot = crs.ErrIndexNotFound // ErrNilInput is returned when input is nil. ErrNilInput = crs.ErrNilDelta // ErrInvalidConfig is returned when configuration is invalid. ErrInvalidConfig = crs.ErrDeltaValidation // ErrTimeout is returned when the algorithm times out. ErrTimeout = context.DeadlineExceeded // ErrCancelled is returned when the algorithm is cancelled. ErrCancelled = context.Canceled )
Common algorithm errors.
Functions ¶
This section is empty.
Types ¶
type Algorithm ¶
type Algorithm interface {
eval.Evaluable
// Process executes the algorithm's core logic.
//
// Description:
//
// This is the pure function core. It MUST NOT mutate snapshot or input.
// It MUST respect context cancellation and SHOULD return partial results
// when cancelled.
//
// Inputs:
// - ctx: Context for cancellation. Must not be nil.
// - snapshot: Immutable view of CRS. Must not be nil.
// - input: Algorithm-specific input. Type determined by InputType().
//
// Outputs:
// - any: Algorithm-specific output. Type determined by OutputType().
// - crs.Delta: State changes to apply. May be nil if no changes.
// - error: Non-nil on failure. May include partial results.
Process(ctx context.Context, snapshot crs.Snapshot, input any) (any, crs.Delta, error)
// Timeout returns the maximum execution time.
//
// Description:
//
// After this duration, the algorithm will be auto-cancelled by the runner.
// Algorithms should choose conservative timeouts.
//
// Outputs:
// - time.Duration: Maximum allowed execution time.
Timeout() time.Duration
// InputType returns the expected input type.
//
// Description:
//
// Used for validation before calling Process().
//
// Outputs:
// - reflect.Type: The expected input type.
InputType() reflect.Type
// OutputType returns the output type.
//
// Description:
//
// Used for validation and type-safe result handling.
//
// Outputs:
// - reflect.Type: The output type.
OutputType() reflect.Type
// ProgressInterval returns how often progress should be reported.
//
// Description:
//
// If no progress is reported for 3x this interval, deadlock is assumed
// and the algorithm is cancelled.
//
// Outputs:
// - time.Duration: Progress reporting interval. Default: 1 second.
ProgressInterval() time.Duration
// SupportsPartialResults returns whether partial results are meaningful.
//
// Description:
//
// If true, the algorithm can return useful partial results when cancelled.
// This is used by the runner to decide whether to wait for results.
//
// Outputs:
// - bool: True if partial results are supported.
SupportsPartialResults() bool
}
Algorithm is a pure function that processes CRS state.
Description:
Algorithms are the core computational units of the MCTS system. They: - Read from immutable snapshots - Produce typed deltas describing state changes - Run in goroutines with timeout enforcement - Support cancellation and partial results
CANCELLATION CONTRACT:
- Algorithms MUST check ctx.Done() at regular intervals (every 100ms)
- Algorithms MUST call ReportProgress() to avoid deadlock detection
- Algorithms SHOULD return partial results when cancelled
- Algorithms MUST NOT ignore cancellation for more than 100ms
Thread Safety: Must be safe for concurrent execution.
type AlgorithmError ¶
AlgorithmError wraps an error with algorithm context.
func NewAlgorithmError ¶
func NewAlgorithmError(algorithm, operation string, err error) *AlgorithmError
NewAlgorithmError creates a new algorithm error.
func (*AlgorithmError) Error ¶
func (e *AlgorithmError) Error() string
func (*AlgorithmError) Unwrap ¶
func (e *AlgorithmError) Unwrap() error
type Config ¶
type Config struct {
// Timeout overrides the algorithm's default timeout.
Timeout time.Duration
// ProgressInterval overrides the default progress interval.
ProgressInterval time.Duration
// MaxIterations limits the number of iterations.
MaxIterations int
// EnableMetrics enables detailed metrics collection.
EnableMetrics bool
// EnableTracing enables OpenTelemetry tracing.
EnableTracing bool
}
Config provides common configuration for algorithms.
func DefaultConfig ¶
func DefaultConfig() *Config
DefaultConfig returns the default algorithm configuration.
type Execution ¶
Execution pairs an algorithm with its input.
func NewExecution ¶
NewExecution creates a new execution pair.
type Result ¶
type Result struct {
// Name is the algorithm name (from Algorithm.Name()).
Name string
// Output is the algorithm-specific output.
Output any
// Delta is the state changes to apply.
Delta crs.Delta
// Err is non-nil if the algorithm failed.
Err error
// Duration is how long the algorithm ran.
Duration time.Duration
// StartTime is when the algorithm started (Unix milliseconds UTC).
StartTime int64
// EndTime is when the algorithm finished (Unix milliseconds UTC).
EndTime int64
// Cancelled is true if the algorithm was cancelled.
Cancelled bool
// Partial is true if the result is a partial result.
Partial bool
// Metrics contains algorithm-specific metrics.
Metrics map[string]float64
}
Result wraps the output of an algorithm execution.
Description:
Result is returned by the Runner and contains the algorithm's output, delta, timing information, and any errors.
Thread Safety: Immutable after creation.
func RunParallel ¶
func RunParallel(ctx context.Context, snapshot crs.Snapshot, executions ...Execution) (crs.Delta, []*Result, error)
RunParallel runs multiple algorithms in parallel and returns merged results.
Description:
Convenience function that creates a runner, runs all algorithms, and collects results.
Inputs:
- ctx: Context for cancellation.
- snapshot: Immutable CRS snapshot.
- executions: Pairs of (Algorithm, input).
Outputs:
- crs.Delta: Merged delta from all successful algorithms.
- []*Result: All results.
- error: Non-nil if any critical failure.
type Runner ¶
type Runner struct {
// contains filtered or unexported fields
}
Runner executes algorithms in goroutines and collects results via channels.
Description:
Runner is the central coordinator for algorithm execution. It: - Spawns goroutines for each algorithm - Enforces timeouts and cancellation - Collects results via channels - Merges deltas into a composite
Thread Safety: Safe for concurrent use.
func NewRunner ¶
NewRunner creates a new algorithm runner.
Inputs:
- capacity: Buffer size for results channel. Default: 10.
Outputs:
- *Runner: The new runner.
func (*Runner) Collect ¶
Collect waits for all algorithms to complete and returns merged results.
Description:
Waits for all running algorithms, then collects results and merges deltas into a composite delta.
Inputs:
- ctx: Context for cancellation.
Outputs:
- crs.Delta: Merged delta from all successful algorithms.
- []*Result: All results (including failures).
- error: Non-nil if collection failed or context cancelled.
Thread Safety: Must be called after all Run() calls.
func (*Runner) Run ¶
Run starts an algorithm in a goroutine.
Description:
The algorithm runs with timeout enforcement. Results are sent to the internal channel for collection.
Inputs:
- ctx: Parent context. Algorithm runs with derived context.
- algo: The algorithm to run.
- snapshot: Immutable CRS snapshot.
- input: Algorithm-specific input.
Thread Safety: Safe for concurrent calls.
type RunnerStats ¶
RunnerStats contains runner execution statistics.
Source Files
Directories
Click to show internal directories.
Click to hide internal directories.