FatUnc6969's picture
Publish reviewed Borderland v8 research artifact
2719bf4 verified
Raw History Blame Contribute Delete
9.01 kB
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)