from __future__ import annotations from copy import deepcopy from dataclasses import dataclass, asdict from fractions import Fraction from hashlib import sha256 from pathlib import Path import pickle import sys from borderland import Campaign from borderland.domain import canonical, WorldSpec, CampaignState from borderland_eval.context import actor_view Value = tuple[Fraction, Fraction, Fraction] ZERO: Value = (Fraction(0), Fraction(0), Fraction(0)) @dataclass(frozen=True) class SearchLimits: max_states: int = 50_000 max_actions: int = 200_000 max_horizon: int = 32 def __post_init__(self): if any(type(v) is not int or v < 1 for v in asdict(self).values()): raise ValueError("Search limits must be positive integers") @dataclass(frozen=True) class InformationCertificate: status: str metadata: dict counts: dict erased: Value | None = None informed: Value | None = None gap: Value | None = None root_action: dict | None = None reason: str | None = None def to_dict(self): data = asdict(self) for key in ("erased", "informed", "gap"): if data[key] is not None: data[key] = [str(value) for value in data[key]] return data class _Incomplete(Exception): pass @dataclass(frozen=True) class _GameplaySnapshot: world: WorldSpec state: CampaignState def _gameplay_snapshot(env): if set(vars(env)) != {"_world", "_state", "_events"}: raise ValueError("Campaign attribute schema requires an audited search snapshot") return _GameplaySnapshot(env._world, env._state) def _state_bytes(env): return pickle.dumps(_gameplay_snapshot(env), protocol=5) def _clone(env): snapshot = deepcopy(_gameplay_snapshot(env)) clone = object.__new__(Campaign) clone._world, clone._state = snapshot.world, snapshot.state clone._events = [] return clone def _validate_checkpoint(env): if type(env) is not Campaign: raise ValueError("Checkpoints must be actual Campaign instances") replay = Campaign(deepcopy(env._world)) events = env._events if not events or events[0]["kind"] != "reset": raise ValueError("Checkpoint requires a complete legal event prefix") if canonical(replay.observe().to_dict()) != canonical(events[0]["transition"]): raise ValueError("Checkpoint reset does not replay") for event in events[1:]: if event["kind"] == "action": transition = replay.step(deepcopy(event["input"])) elif event["kind"] == "note": transition = replay.replace_notebook(event["input"]) else: raise ValueError("Unsupported checkpoint event") if transition.error or canonical(transition.to_dict()) != canonical(event["transition"]): raise ValueError("Checkpoint prefix is not a legal exact replay") if _state_bytes(replay) != _state_bytes(env): raise ValueError("Checkpoint state differs from its legal prefix") def _terminal(transition): if transition.outcome != "escaped": return ZERO board = transition.observation.board survivors = (len(board["boarded"]) if "boarded" in board else sum(member["available"] for member in transition.observation.team)) return Fraction(1), Fraction(survivors), Fraction(transition.observation.charge) def _mean(values): return tuple(sum((v[i] for v in values), Fraction(0)) / len(values) for i in range(3)) def certify_information(checkpoints, *, prior, scope, limits=SearchLimits()): """Compare Bayes-optimal erased and world-informed suffix policies. Each checkpoint has one equal prior mass, including duplicate checkpoints. The erased policy can remember its entire public suffix history. """ envs = list(checkpoints) if not envs or prior != "uniform" or not isinstance(scope, str) or not scope.strip(): raise ValueError("Declare a nonempty checkpoint support, uniform prior, and scope") if not isinstance(limits, SearchLimits): raise ValueError("limits must be SearchLimits") for env in envs: _validate_checkpoint(env) transitions = [env.observe() for env in envs] views = [canonical(actor_view(t)) for t in transitions] root = Path(__file__).resolve().parents[1] modules = tuple(sorted(str(p.relative_to(root)) for p in (root / "borderland").rglob("*.py"))) + ( "borderland_eval/context.py", "borderland_verify/information.py") metadata = dict( scope=scope, prior="uniform", particles=len(envs), solver_version=1, python_version=sys.version, prior_mass=str(Fraction(1, len(envs))), actor_view_equal=len(set(views)) == 1, actor_view_sha256=[sha256(v.encode()).hexdigest() for v in views], checkpoint_sha256=[sha256(_state_bytes(e)).hexdigest() for e in envs], prefix_sha256=[sha256(pickle.dumps(e._events, protocol=5)).hexdigest() for e in envs], spec_sha256=[sha256(pickle.dumps(e._world, protocol=5)).hexdigest() for e in envs], generation_versions=[e._world.generation_version for e in envs], source_sha256={p: sha256((root / p).read_bytes()).hexdigest() for p in modules}, limits=asdict(limits), objective=["escape", "survivors_on_escape", "charge_on_escape"], survivors="terminal boarded count when exposed; otherwise available terminal teammates", policy="arbitrary complete public suffix history; no private state access", actions="every advertised legal gameplay action; no notebook edits or rejected commands", checkpoint="fresh observe() after exact legal prefix replay", ) counts = dict(states=0, actions=0, transitions=0, memo_hits=0, terminal_particles=0, max_depth=0, observation_partitions=0) if not metadata["actor_view_equal"]: return InformationCertificate("rejected", metadata, counts, reason="Complete initial actor views differ") memo = {} def solve(particles, remaining): key = (remaining, tuple((_state_bytes(e), canonical(actor_view(t))) for e, t in particles)) if key in memo: counts["memo_hits"] += 1 return memo[key] if counts["states"] >= limits.max_states: raise _Incomplete("max_states reached") counts["states"] += 1 counts["max_depth"] = max(counts["max_depth"], limits.max_horizon - remaining) if any(t.truncated for _, t in particles): raise _Incomplete("Campaign continuation was truncated") if all(t.done for _, t in particles): counts["terminal_particles"] += len(particles) result = _mean([_terminal(t) for _, t in particles]), None memo[key] = result return result if remaining == 0: raise _Incomplete("max_horizon reached with a nonterminal continuation") public = [canonical(actor_view(t)) for _, t in particles] if len(set(public)) != 1: raise RuntimeError("Belief contains distinct immediate actor payloads") actions = particles[0][1].legal_actions if not actions: raise _Incomplete("Nonterminal state has no advertised gameplay action") best, selected = None, None for action in actions: if counts["actions"] >= limits.max_actions: raise _Incomplete("max_actions reached") counts["actions"] += 1 groups = {} for env, _ in particles: child = _clone(env) transition = child.step(deepcopy(action)) counts["transitions"] += 1 if transition.error: raise _Incomplete("Advertised legal gameplay action was rejected") payload = canonical(actor_view(transition)) groups.setdefault(payload, []).append((child, transition)) counts["observation_partitions"] += len(groups) values = [(Fraction(len(group), len(particles)), solve(group, remaining - 1)[0]) for group in groups.values()] value = tuple(sum((mass * v[i] for mass, v in values), Fraction(0)) for i in range(3)) if best is None or value > best: best, selected = value, action.to_dict() memo[key] = best, selected return memo[key] try: particles = list(zip((_clone(e) for e in envs), transitions)) erased, action = solve(particles, limits.max_horizon) informed = _mean([solve([particle], limits.max_horizon)[0] for particle in particles]) except _Incomplete as error: return InformationCertificate("incomplete", metadata, counts, reason=str(error)) gap = tuple(informed[i] - erased[i] for i in range(3)) return InformationCertificate("exact", metadata, counts, erased, informed, gap, action)