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)