Spaces:
Running
Running
File size: 9,010 Bytes
2719bf4 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 | 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)
|