ferroplan 0.13.0

//! The barter think benchmark (0.13 Phase 3) — generates
//! `benchmarks/bazaar-thinks.md`. The corpus was the planner's measuring
//! stick; this is the game track's: bazaar thinks measured END-TO-END on
//! the vendored wants-gated chain fixture (`benchmarks/bench/
//! bazaar-chain*.pddl`), where the goal `(has a0 item-k)` forces a k-hop
//! trade-up chain (every trade crosses exactly one want-edge, so ANY plan
//! spends >= k trades; junk inventory makes wrong picks dead ends).
//!
//! One world, forked minds (Phase 1+2 in anger): the world grounds ONCE;
//! every (depth, budget) cell is a `fork` + `set_goal` + one bounded
//! think. Whatever the curves say, they ship.
//!
//! Run: cargo run --release -p ferroplan --example bazaar_thinks \
//!        > benchmarks/bazaar-thinks.md
use ferroplan::{Options, Session};
use std::time::Instant;

const DOM: &str = include_str!("../../../benchmarks/bench/bazaar-chain-domain.pddl");
const PRB: &str = include_str!("../../../benchmarks/bench/bazaar-chain.pddl");
const PRB_X2: &str = include_str!("../../../benchmarks/bench/bazaar-chain-x2.pddl");

const DEPTHS: [usize; 8] = [1, 2, 3, 4, 6, 8, 10, 11];

/// Levenshtein distance over step sequences — the churn metric: how many
/// step insertions/deletions/substitutions turn the old plan into the new.
fn edit_distance(a: &[String], b: &[String]) -> usize {
    let mut prev: Vec<usize> = (0..=b.len()).collect();
    for (i, sa) in a.iter().enumerate() {
        let mut cur = vec![i + 1];
        for (j, sb) in b.iter().enumerate() {
            let sub = prev[j] + usize::from(sa != sb);
            cur.push(sub.min(prev[j + 1] + 1).min(cur[j] + 1));
        }
        prev = cur;
    }
    prev[b.len()]
}

/// One depth x budget sweep over a grounded world: every cell is a forked
/// mind + `set_goal(goal(k))` + ONE bounded think. Returns (depth, first
/// solving budget) per depth for the onset report.
fn sweep(
    world: &Session,
    budgets: &[usize],
    goal: impl Fn(usize) -> String,
) -> Result<Vec<(usize, Option<usize>)>, String> {
    print!("| depth k |");
    for b in budgets {
        print!(" B={b} |");
    }
    println!(" think ms (max B) |");
    print!("|---|");
    for _ in budgets {
        print!("---|");
    }
    println!("---|");
    let mut onset = Vec::new();
    for k in DEPTHS {
        print!("| {k} |");
        let mut first_solving = None;
        let mut big_ms = 0.0;
        for &b in budgets {
            let mut mind = world.fork();
            mind.set_goal(&goal(k))?;
            let t = Instant::now();
            let think = mind.replan_budgeted(b, Some(256));
            let ms = t.elapsed().as_secs_f64() * 1e3;
            if b == budgets[budgets.len() - 1] {
                big_ms = ms;
            }
            if think.solved {
                first_solving.get_or_insert(b);
                print!(
                    " {} @ {} |",
                    think.plan.as_ref().unwrap().length,
                    think.statistics.evaluated_states
                );
            } else {
                print!(" -- |");
            }
        }
        println!(" {big_ms:.1} |");
        onset.push((k, first_solving));
    }
    println!();
    println!("Where budget-exhausted verdicts begin:");
    println!();
    for (k, b) in &onset {
        match b {
            Some(b) => println!("- depth {k}: solves from B={b}"),
            None => println!("- depth {k}: UNSOLVED at every budget in the ladder"),
        }
    }
    Ok(onset)
}

fn main() -> Result<(), String> {
    let t = Instant::now();
    let world = Session::new(DOM, PRB, &Options::default())?;
    let ground_s = t.elapsed().as_secs_f64();

    println!("# Bazaar thinks — the game track's scoreboard");
    println!();
    println!("Generated by `cargo run --release -p ferroplan --example bazaar_thinks`");
    println!("(0.13 Phase 3). Fixtures: `benchmarks/bench/bazaar-chain*.pddl` — 12");
    println!("holders x 40 items, wants-gated barter; goal depth k forces a k-hop");
    println!("trade-up chain (every trade crosses one want-edge, so ANY plan spends");
    println!(">= k trades per chain; junk picks strand the chain item). The world");
    println!("grounds ONCE per fixture; each cell below is an independent forked");
    println!("mind: `fork` + `set_goal` + ONE bounded think (`replan_budgeted(B,");
    println!("256 MB)`) — eval budgets, so thinks are deterministic at any thread");
    println!("count. Cell = `plan-length @ evals-spent`, `--` = honest");
    println!("budget-exhausted verdict. Whatever the curves say, they ship.");
    println!();
    println!("## Solo chains: heuristic-transparent (a finding, not a failure)");
    println!();
    println!("A single trade-up chain is EXACTLY visible to the relaxed-plan");
    println!("heuristic (relaxation never spends the offered item, but a solo");
    println!("chain never needs it back), so every depth solves at k+1 evals in");
    println!("well under a millisecond — an NPC can chase an 11-hop trade chain");
    println!("EVERY TICK. That is the game-track headline.");
    println!();
    sweep(&world, &[250, 1_000, 4_000, 16_000, 64_000], |k| {
        format!("(has a0 item{k})")
    })?;

    println!();
    println!("## Contended chains: where the curves live");
    println!();
    println!("`bazaar-chain-x2`: TWO chains cross at every vendor (v-j holds A-j");
    println!("and B-j, wants A-(j-1) and B-(j-1)), both fed from one mind's two");
    println!("seeds; goal k wants BOTH depth-k items (>= 2k trades). The");
    println!("relaxation cannot see the contention — one offered item \"advances\"");
    println!("both chains at once in relaxed space — so real search must dodge");
    println!("cross-picks that strand a chain. Budget-exhausted verdicts appear");
    println!("here.");
    println!();
    let t = Instant::now();
    let world_x2 = Session::new(DOM, PRB_X2, &Options::default())?;
    let ground_x2_s = t.elapsed().as_secs_f64();
    sweep(&world_x2, &[1_000, 4_000, 16_000, 64_000, 256_000], |k| {
        format!("(and (has a0 itemA{k}) (has a0 itemB{k}))")
    })?;

    println!();
    println!("## Plan churn under drift (follow, don't dither — 0.13 Phase 4)");
    println!();
    println!("A broken plan forces a rethink; an UNCONSTRAINED rethink can thrash");
    println!("to a structurally different plan — visible NPC dithering even when");
    println!("both plans are fine. `replan_following` replays the still-applicable");
    println!("prefix and searches only the tail. Scripted drift on the contended");
    println!("fixture: a mind plans the depth-8 double chain; then one of the");
    println!("plan's own vendor-vendor trades happens OFF-SCREEN before the mind");
    println!("moves — the world advanced along the plan but out of order, replay");
    println!("breaks, the goal stays reachable. Two scripted drifts: the FIRST");
    println!("breaking pre-trade (early hole) and the LAST (deep hole). Churn =");
    println!("Levenshtein edit distance between old and new step sequences (lower");
    println!("= steadier NPC).");
    println!();
    let mut planner = world_x2.fork();
    planner.set_goal("(and (has a0 itemA8) (has a0 itemB8))")?;
    let prior = planner.replan_budgeted(64_000, Some(256));
    assert!(prior.solved);
    let prior = prior.plan.unwrap();
    let disp = |p: &ferroplan::Plan| -> Vec<String> {
        p.steps
            .iter()
            .map(|s| format!("{} {}", s.action, s.args.join(" ")))
            .collect()
    };
    let old = disp(&prior);
    println!(
        "- prior plan: {} steps for >= 16 trades of work (vendor-vendor \
         pre-trades included)",
        old.len()
    );
    // Discover the breaking drifts by pure replay (no search): pre-execute
    // one vendor-vendor step's effects and ask plan_still_valid.
    let drifted = |step: &ferroplan::Step| -> Result<Option<Session>, String> {
        if step.args[0] == "A0" {
            return Ok(None); // the mind's own move can't happen off-screen
        }
        let (a, b, x, y) = (&step.args[0], &step.args[1], &step.args[2], &step.args[3]);
        let mut m = planner.fork();
        m.set_fact(&format!("(has {a} {x})"), false)?;
        m.set_fact(&format!("(has {b} {y})"), false)?;
        m.set_fact(&format!("(has {a} {y})"), true)?;
        m.set_fact(&format!("(has {b} {x})"), true)?;
        Ok((!m.plan_still_valid(&prior, 0)).then_some(m))
    };
    let mut breaking: Vec<(usize, Session)> = Vec::new();
    for (i, s) in prior.steps.iter().enumerate() {
        if let Some(m) = drifted(s)? {
            breaking.push((i, m));
        }
    }
    let picks: Vec<&(usize, Session)> = vec![
        breaking.first().expect("a breaking drift"),
        breaking.last().unwrap(),
    ];
    for (i, mind) in picks {
        let step = &prior.steps[*i];
        println!();
        println!(
            "Drift: `{} {}` (plan step {i}) already happened off-screen:",
            step.action,
            step.args.join(" ")
        );
        let t = Instant::now();
        let followed = mind.replan_following(&prior, 0, 64_000, Some(256));
        let follow_ms = t.elapsed().as_secs_f64() * 1e3;
        let t = Instant::now();
        let unbiased = mind.replan_budgeted(64_000, Some(256));
        let unbiased_ms = t.elapsed().as_secs_f64() * 1e3;
        let report = |label: &str, sol: &ferroplan::Solution, ms: f64| match &sol.plan {
            Some(p) => println!(
                "- {label}: {} steps, churn {} vs prior, {} evals, {ms:.1} ms{}",
                p.length,
                edit_distance(&old, &disp(p)),
                sol.statistics.evaluated_states,
                sol.notes
                    .first()
                    .map(|n| format!(" — {n}"))
                    .unwrap_or_default()
            ),
            None => println!(
                "- {label}: BUDGET-EXHAUSTED at 64k evals ({} spent, {ms:.1} ms) — \
                 the honest verdict; the biased rethink is not just steadier, it \
                 is the difference between answering and not",
                sol.statistics.evaluated_states
            ),
        };
        report("biased (`replan_following`)", &followed, follow_ms);
        report("unbiased (`replan_budgeted`)", &unbiased, unbiased_ms);
    }

    let mind = world_x2.fork();
    println!();
    println!("## Per-mind retained memory and world load");
    println!();
    println!(
        "- shared world payload (once, however many minds): ~{:.1} MB solo / \
         ~{:.1} MB contended",
        world.fork().world_bytes() as f64 / 1e6,
        mind.world_bytes() as f64 / 1e6
    );
    println!(
        "- private state per forked mind: ~{:.2} KB",
        mind.mind_bytes() as f64 / 1e3
    );
    println!(
        "- world load: {ground_s:.2} s solo / {ground_x2_s:.2} s contended, once; \
         forks are O(state-copy) — see the `many_minds` example for the \
         12-NPC load story"
    );
    Ok(())
}