Buckets:
# 中文源码导读(2026-09-15)|阅读顺序 013|Baseline 扩展
# 来源:Baseline 扩展:官方已有同路径文件,本地实现包含改动。
# 作用:PUCT 状态档案、父节点选择、top-2 保留与恢复;还保留默认未启用的 one-bit/历史信用分支。
# 对照基准:test-time-training/discover@6c40e82;完整路线见 docs/CODE_READING_ORDER_ZH.md。
"""Centralized sampler creation for all environments."""
from __future__ import annotations
from abc import ABC, abstractmethod
from collections import Counter
import hashlib
import math
import os
import threading
import numpy as np
from ttt_discover.tinker_utils.state import State, state_from_dict
from ttt_discover.tinker_utils.best_sequence_utils import _file_lock, _atomic_write_json, _read_json_or_default
from ttt_discover.tinker_utils.one_bit_allocation import (
ONE_BIT_KL,
expanded_indices,
residual_systematic_counts,
solve_kl_gibbs,
)
# 【Baseline 上的改动】StateSampler
# baseline 采样器接口,规定选状态、接收子状态与保存边界。
class StateSampler(ABC):
"""Abstract base class for sampling states."""
@abstractmethod
def sample_states(self, num_states: int) -> list[State]:
"""Sample states to start rollouts from."""
pass
@abstractmethod
def update_states(self, states: list[State], parent_states: list[State], save: bool = True, step: int | None = None):
"""Update internal storage with new states. Sets parent info automatically."""
pass
@abstractmethod
def flush(self, step: int | None = None):
"""Force save current state to disk."""
pass
@staticmethod
def _set_parent_info(child: State, parent: State):
"""Set parent_values and parents on child state from parent."""
child.parent_values = [parent.value] + parent.parent_values if parent.value is not None else []
child.parents = [{"id": parent.id, "timestep": parent.timestep}] + parent.parents
if hasattr(child, "chart_lineage"):
chart = getattr(parent, "rollout_chart", None)
child.incoming_chart = chart
child.chart_lineage = [chart] + list(
getattr(parent, "chart_lineage", []) or []
)
@staticmethod
def _filter_topk_per_parent(states: list[State], parent_states: list[State], k: int) -> tuple[list[State], list[State]]:
"""Keep top-k children (by value) per parent. If k=0, return all."""
if not states:
return [], []
if k == 0:
return states, parent_states
# Group by parent id
parent_to_children: dict[str, list[tuple[State, State]]] = {}
for child, parent in zip(states, parent_states):
pid = parent.id
if pid not in parent_to_children:
parent_to_children[pid] = []
parent_to_children[pid].append((child, parent))
# Keep top-k children per parent (highest value)
topk_children, topk_parents = [], []
for children_and_parents in parent_to_children.values():
sorted_pairs = sorted(children_and_parents, key=lambda x: x[0].value if x[0].value is not None else float('-inf'), reverse=True)
for child, parent in sorted_pairs[:k]:
topk_children.append(child)
topk_parents.append(parent)
return topk_children, topk_parents
def _sampler_file_for_step(base_path: str, step: int) -> str:
"""Get the sampler file path for a specific step."""
base_name = base_path.replace(".json", "")
return f"{base_name}_step_{step:06d}.json"
def create_initial_state(env_type: type, problem_type: str) -> State:
"""Create initial state by delegating to the env type. Custom envs implement create_initial_state on their class."""
name = getattr(env_type, "env_name", env_type.__name__)
print(f"Creating initial state for {name}")
return env_type.create_initial_state(problem_type)
# 【Baseline 上的改动】PUCTSampler
# 核心 PUCT 选择公式来自 baseline;本地同时保留可选历史扩展,所以整个类不是逐字官方原版。
# 正式入口关闭后代价值回传、语义去重等扩展,保留 PUCT 和每个 parent 的 top-2 规则。
class PUCTSampler(StateSampler):
"""
PUCT-style sampler with state archive.
score(i) = Q(i) + c * scale * P(i) * sqrt(1 + T) / (1 + n[i])
where:
Q(i) = m[i] if n[i]>0 else R(i) (best reachable value or current reward)
P(i) = rank-based prior
scale = max(R) - min(R)
"""
def __init__(
self,
file_path: str,
env_type: type,
problem_type: str = "",
max_buffer_size: int = 1000,
batch_size: int = 1,
resume_step: int | None = None,
puct_c: float = 1.0,
topk_children: int = 2,
):
self.file_path = file_path
self.env_type = env_type
self.problem_type = problem_type
self.max_buffer_size = max_buffer_size
self.batch_size = batch_size
self.topk_children = topk_children
self.puct_c = float(puct_c)
self._states: list[State] = []
self._initial_states: list[State] = []
self._last_sampled_states: list[State] = []
self._last_sampled_indices: list[int] = []
self._lock = threading.Lock()
self._current_step = resume_step if resume_step is not None else 0
# PUCT stats
self._n: dict[str, int] = {}
self._m: dict[str, float] = {}
self._T: int = 0
self._chart_n: dict[str, int] = {}
self._chart_m: dict[str, float] = {}
self._chart_T: int = 0
self._last_scale: float = 1.0
self._last_puct_stats: list[tuple[int, float, float, float, float]] = []
self._last_chart_stats: list[tuple[str | None, int, float, float, float, float]] = []
self._policy_candidate_pool: dict[str, dict[object, list[object]]] = {}
if resume_step is not None:
self._load(resume_step)
if not self._states:
for _ in range(batch_size):
state = create_initial_state(self.env_type, self.problem_type)
self._initial_states.append(state)
self._states.append(state)
self._save(self._current_step)
def _load(self, step: int):
file_path = _sampler_file_for_step(self.file_path, step)
if not os.path.exists(file_path):
raise FileNotFoundError(f"Cannot resume from step {step}: sampler file not found: {file_path}")
with _file_lock(f"{file_path}.lock"):
store = _read_json_or_default(file_path, default=None)
if store is None:
raise ValueError(f"Failed to load sampler state from {file_path}")
state_cls = self.env_type.state_type
self._states = [state_from_dict(s, state_type=state_cls) for s in store.get("states", [])]
self._initial_states = [state_from_dict(s, state_type=state_cls) for s in store.get("initial_states", [])]
self._n = store.get("puct_n", {}) or {}
self._m = store.get("puct_m", {}) or {}
self._T = int(store.get("puct_T", 0) or 0)
self._chart_n = store.get("atlas_chart_n", {}) or {}
self._chart_m = store.get("atlas_chart_m", {}) or {}
self._chart_T = int(store.get("atlas_chart_T", 0) or 0)
def _save(self, step: int):
save_path = _sampler_file_for_step(self.file_path, step)
store = {
"step": step,
"states": [s.to_dict() for s in self._states],
"initial_states": [s.to_dict() for s in self._initial_states],
"puct_n": self._n,
"puct_m": self._m,
"puct_T": self._T,
"atlas_chart_n": self._chart_n,
"atlas_chart_m": self._chart_m,
"atlas_chart_T": self._chart_T,
}
with _file_lock(f"{save_path}.lock"):
_atomic_write_json(save_path, store)
def _refresh_random_construction(self, state: State) -> None:
"""Regenerate construction for initial states when env expects random construction (e.g. AC)."""
# For ac
if not getattr(self.env_type, "construction_length_limits", None):
return
rng = np.random.default_rng()
state.construction = [rng.random()] * rng.integers(1000, 8000)
if self.problem_type == "ac1":
from ttt_discover.tinker_utils.ac_helpers import evaluate_sequence_ac1
state.value = -evaluate_sequence_ac1(state.construction)
else:
from ttt_discover.tinker_utils.ac_helpers import evaluate_sequence_ac2
state.value = evaluate_sequence_ac2(state.construction)
def _get_construction_key(
self,
state: State,
parent_id: str | None = None,
) -> tuple | str | None:
semantic_hash = getattr(state, "semantic_hash", None)
env_type = getattr(self, "env_type", None)
if semantic_hash and getattr(
env_type,
"dedupe_semantics_within_parent",
False,
):
if parent_id is None and state.parents:
parent_id = state.parents[0].get("id")
if parent_id is not None:
return f"parent-semantic:{parent_id}:{semantic_hash}"
if semantic_hash and getattr(env_type, "dedupe_by_semantics", True):
return f"semantic:{semantic_hash}"
if hasattr(state, 'construction') and state.construction:
return tuple(state.construction)
if hasattr(state, 'code') and state.code:
return state.code
return None
def _uses_max_policy_survivors(self) -> bool:
return bool(getattr(self.env_type, "max_policy_survivors", False))
def _dedupe_rollout_semantics_within_parent(
self,
states: list[State],
parent_states: list[State],
) -> tuple[list[State], list[State]]:
if not getattr(
self.env_type,
"dedupe_semantics_within_parent",
False,
):
return states, parent_states
archived_keys = {
(str(state.parents[0]["id"]), str(state.semantic_hash))
for state in self._states
if state.parents and getattr(state, "semantic_hash", None)
}
best_by_key: dict[tuple[str, str], tuple[State, State]] = {}
passthrough: list[tuple[State, State]] = []
for child, parent in zip(states, parent_states):
semantic_hash = getattr(child, "semantic_hash", None)
if not semantic_hash:
passthrough.append((child, parent))
continue
key = (str(parent.id), str(semantic_hash))
if key in archived_keys:
continue
previous = best_by_key.get(key)
child_value = float(
child.value if child.value is not None else float("-inf")
)
previous_value = float(
previous[0].value
if previous is not None and previous[0].value is not None
else float("-inf")
)
if previous is None or child_value > previous_value:
best_by_key[key] = (child, parent)
pairs = [*passthrough, *best_by_key.values()]
return (
[child for child, _parent in pairs],
[parent for _child, parent in pairs],
)
def _action_charts(self) -> tuple[str, ...]:
return tuple(getattr(self.env_type, "action_charts", ()) or ())
@staticmethod
def _chart_key(state_id: str, chart: str) -> str:
return f"{state_id}::{chart}"
def _chart_edge_lineage(self, state: State) -> list[tuple[str, str]]:
chart = getattr(state, "rollout_chart", None)
edges: list[tuple[str, str]] = []
if chart:
edges.append((str(state.id), str(chart)))
chart_lineage = list(getattr(state, "chart_lineage", []) or [])
for parent, parent_chart in zip(state.parents or [], chart_lineage):
parent_id = parent.get("id")
if parent_id and parent_chart:
edges.append((str(parent_id), str(parent_chart)))
return edges
def _assign_action_charts(self, states: list[State], scale: float) -> None:
charts = self._action_charts()
if not charts:
self._last_chart_stats = [
(None, 0, 0.0, 0.0, 0.0, 0.0) for _ in states
]
return
prior = 1.0 / len(charts)
sqrtT = float(np.sqrt(1.0 + self._chart_T))
reserved = {chart: 0 for chart in charts}
global_visits = {
chart: sum(
int(value)
for key, value in self._chart_n.items()
if key.endswith(f"::{chart}")
)
for chart in charts
}
selected_stats = []
for state in states:
state_value = float(
state.value if state.value is not None else float("-inf")
)
entries = []
for chart in charts:
key = self._chart_key(str(state.id), chart)
n = int(self._chart_n.get(key, 0))
q = float(self._chart_m.get(key, state_value))
bonus = self.puct_c * scale * prior * sqrtT / (1.0 + n)
entries.append((chart, n, q, prior, bonus, q + bonus))
unvisited = [entry for entry in entries if entry[1] == 0]
if unvisited:
chosen = min(
unvisited,
key=lambda entry: (
global_visits[entry[0]] + reserved[entry[0]],
charts.index(entry[0]),
),
)
else:
chosen = max(
entries,
key=lambda entry: (
entry[5],
-global_visits[entry[0]],
-charts.index(entry[0]),
),
)
state.rollout_chart = chosen[0]
reserved[chosen[0]] += 1
selected_stats.append(chosen)
self._last_chart_stats = selected_stats
def _filter_topk_per_parent_chart(
self,
states: list[State],
parent_states: list[State],
k: int,
) -> tuple[list[State], list[State]]:
if not states or k == 0:
return states, parent_states
grouped: dict[tuple[str, str | None], list[tuple[State, State]]] = {}
for child, parent in zip(states, parent_states):
chart = getattr(child, "incoming_chart", None) or getattr(
parent, "rollout_chart", None
)
grouped.setdefault((str(parent.id), chart), []).append((child, parent))
kept_children, kept_parents = [], []
for pairs in grouped.values():
pairs.sort(
key=lambda pair: (
pair[0].value
if pair[0].value is not None
else float("-inf")
),
reverse=True,
)
for child, parent in pairs[:k]:
kept_children.append(child)
kept_parents.append(parent)
return kept_children, kept_parents
def _filter_archive_per_parent_chart(self) -> None:
k = int(getattr(self.env_type, "topk_children_per_chart", 1))
if k <= 0:
return
grouped: dict[tuple[str, str | None], list[State]] = {}
roots: list[State] = []
for state in self._states:
if not state.parents:
roots.append(state)
continue
parent_id = str(state.parents[0]["id"])
chart = getattr(state, "incoming_chart", None)
grouped.setdefault((parent_id, chart), []).append(state)
filtered = []
for children in grouped.values():
children.sort(
key=lambda child: (
child.value
if child.value is not None
else float("-inf")
),
reverse=True,
)
filtered.extend(children[:k])
self._states = roots + filtered
def _backed_value(self, state: State) -> float:
value = float(state.value if state.value is not None else float("-inf"))
backed = float(self._m.get(str(state.id), value))
return max(value, backed)
def _record_policy_candidate(self, child: State, parent: State, key: object) -> None:
by_key = self._policy_candidate_pool.setdefault(str(parent.id), {})
if key in by_key:
by_key[key][1] = int(by_key[key][1]) + 1
else:
by_key[key] = [child, 1]
@staticmethod
def _stable_policy_index(
parent_id: str,
step: int | None,
candidates: list[tuple[State, int]],
) -> int:
material = "|".join(
[str(step), str(parent_id)]
+ sorted(f"{state.id}:{int(weight)}" for state, weight in candidates)
)
seed = int.from_bytes(hashlib.sha256(material.encode("utf-8")).digest()[:8], "big")
rng = np.random.default_rng(seed)
weights = np.asarray([max(1, int(weight)) for _, weight in candidates], dtype=np.float64)
weights /= weights.sum()
return int(rng.choice(len(candidates), p=weights))
def _filter_max_policy_per_parent(self, step: int | None) -> None:
by_parent: dict[str, list[State]] = {}
no_parent: list[State] = []
for state in self._states:
parent_id = str(state.parents[0]["id"]) if state.parents else None
if parent_id:
by_parent.setdefault(parent_id, []).append(state)
else:
no_parent.append(state)
filtered: list[State] = []
for parent_id, children in by_parent.items():
max_child = max(children, key=self._backed_value)
max_child.survivor_role = "max"
max_child.survivor_step = step
max_child.survivor_backed_value = self._backed_value(max_child)
max_child.survivor_weight = 1
selected = [max_child]
child_ids = {str(child.id) for child in children}
policy_candidates = [
(entry[0], int(entry[1]))
for entry in self._policy_candidate_pool.get(parent_id, {}).values()
if str(entry[0].id) in child_ids and entry[0].id != max_child.id
]
policy_child = None
policy_weight = 1
if policy_candidates:
index = self._stable_policy_index(parent_id, step, policy_candidates)
policy_child, policy_weight = policy_candidates[index]
else:
prior_policy = [
child
for child in children
if child.id != max_child.id
and getattr(child, "survivor_role", None) == "policy"
]
if prior_policy:
policy_child = max(prior_policy, key=self._backed_value)
elif len(children) > 1:
policy_child = max(
(child for child in children if child.id != max_child.id),
key=self._backed_value,
)
if policy_child is not None:
policy_child.survivor_role = "policy"
policy_child.survivor_step = step
policy_child.survivor_weight = int(policy_weight)
policy_child.survivor_backed_value = self._backed_value(policy_child)
selected.append(policy_child)
filtered.extend(selected)
self._states = no_parent + filtered
self._policy_candidate_pool.clear()
def _compute_scale(self, values: np.ndarray, mask: np.ndarray | None = None) -> float:
if values.size == 0:
return 1.0
v = values[mask] if mask is not None else values
return float(max(np.max(v) - np.min(v), 1e-6)) if v.size > 0 else 1.0
# 【Baseline 原有】PUCTSampler._compute_prior
# 由候选状态分数的排序构造先验 P;不是语言模型输出某段代码的 token 概率。
def _compute_prior(self, values: np.ndarray, scale: float) -> np.ndarray:
if values.size == 0:
return np.array([])
N = len(values)
ranks = np.argsort(np.argsort(-values))
weights = (N - ranks).astype(np.float64)
return weights / weights.sum()
def get_frontier_value(self) -> float | None:
"""Return the best terminal program value currently in the archive."""
values = []
for state in self._states:
value = state.terminal_value if state.terminal_value is not None else state.value
if value is not None and np.isfinite(float(value)):
values.append(float(value))
return max(values) if values else None
def get_state_ids(self) -> set[str]:
return {str(state.id) for state in self._states}
def get_replay_state_ids(self) -> set[str]:
"""Return retained states plus the action edges in their lineages."""
state_ids = self.get_state_ids()
for state in self._states:
state_ids.update(
str(parent["id"])
for parent in (state.parents or [])
if parent.get("id")
)
return state_ids
def _attach_rollout_frontier(self, states: list[State]) -> None:
frontier = self.get_frontier_value()
for state in states:
setter = getattr(state, "set_rollout_frontier_value", None)
if callable(setter):
setter(frontier)
else:
setattr(state, "rollout_frontier_value", frontier)
def _get_lineage(self, state: State) -> set[str]:
lineage = {state.id}
for p in (state.parents or []):
if p.get("id"):
lineage.add(str(p["id"]))
return lineage
def _build_children_map(self) -> dict[str, set[str]]:
children: dict[str, set[str]] = {}
for s in self._states:
for p in (s.parents or []):
pid = p.get("id")
if pid:
children.setdefault(str(pid), set()).add(s.id)
return children
def _get_full_lineage(self, state: State, children_map: dict[str, set[str]]) -> set[str]:
lineage = self._get_lineage(state)
queue = [state.id]
visited = {state.id}
while queue:
sid = queue.pop(0)
for child_id in children_map.get(sid, []):
if child_id not in visited:
visited.add(child_id)
lineage.add(child_id)
queue.append(child_id)
return lineage
# 【Baseline 上的改动】PUCTSampler.sample_states
# 按 Q + c·scale·P·sqrt(1+T)/(1+n) 排序,再施加同批谱系屏蔽。
# 默认请求 8 个 parent slot,不等于简单取原始分数最好的 8 个;可选状态不足时数量也可能较少。
def sample_states(self, num_states: int) -> list[State]:
initial_ids = {s.id for s in self._initial_states}
candidates = list(self._states)
if not candidates:
picked = [
create_initial_state(self.env_type, self.problem_type)
for _ in range(num_states)
]
self._assign_action_charts(picked, 1.0)
self._attach_rollout_frontier(picked)
self._last_sampled_states = picked
self._last_sampled_indices = []
self._last_puct_stats = [(0, 0.0, 0.0, 0.0, 0.0) for _ in picked]
return picked
vals = np.array([float(s.value if s.value is not None else float("-inf")) for s in candidates])
non_initial_mask = np.array([s.id not in initial_ids for s in candidates])
scale = self._compute_scale(vals, non_initial_mask if non_initial_mask.any() else None)
self._last_scale = scale
P = self._compute_prior(vals, scale)
sqrtT = np.sqrt(1.0 + self._T)
scores = []
for i, s in enumerate(candidates):
n = self._n.get(s.id, 0)
m = self._m.get(s.id, vals[i])
Q = m if n > 0 else vals[i]
bonus = self.puct_c * scale * P[i] * sqrtT / (1.0 + n)
score = Q + bonus
scores.append((score, vals[i], s, n, Q, P[i], bonus))
scores.sort(key=lambda x: (x[0], x[1]), reverse=True)
if num_states > 1:
children_map = self._build_children_map()
picked, top_scores, blocked_ids = [], [], set()
for entry in scores:
s = entry[2]
if s.id in blocked_ids:
continue
picked.append(s)
top_scores.append(entry)
blocked_ids.update(self._get_full_lineage(s, children_map))
if len(picked) >= num_states:
break
else:
top_scores = scores[:num_states]
picked = [t[2] for t in top_scores]
state_id_to_idx = {s.id: i for i, s in enumerate(self._states)}
self._last_sampled_states = picked
self._last_sampled_indices = [state_id_to_idx.get(s.id, -1) for s in picked]
self._last_puct_stats = [(t[3], t[4], t[5], t[6], t[0]) for t in top_scores]
for s in picked:
if s.id in initial_ids:
self._refresh_random_construction(s)
if self._uses_max_policy_survivors():
s.survivor_expansions = int(getattr(s, "survivor_expansions", 0)) + 1
self._assign_action_charts(picked, scale)
self._attach_rollout_frontier(picked)
return picked
# 【Baseline 上的改动】PUCTSampler.update_states
# 先用有效候选更新访问/结果统计,再进行入树过滤;失败候选由 record_failed_rollout 记录尝试。
def update_states(self, states: list[State], parent_states: list[State], save: bool = True, step: int | None = None):
if not states:
return
assert len(states) == len(parent_states)
# Update PUCT stats for ALL states
parent_max: dict[str, float] = {}
parent_obj: dict[str, State] = {}
for child, parent in zip(states, parent_states):
if child.value is None:
continue
pid = parent.id
parent_obj[pid] = parent
parent_max[pid] = max(parent_max.get(pid, float("-inf")), float(child.value))
for pid, y in parent_max.items():
parent = parent_obj[pid]
anc_ids = [pid] + [str(p["id"]) for p in (parent.parents or []) if p.get("id")]
backup_ids = anc_ids if getattr(self.env_type, "backup_descendant_values", False) else [pid]
for aid in backup_ids:
self._m[aid] = max(self._m.get(aid, y), y)
for aid in anc_ids:
self._n[aid] = self._n.get(aid, 0) + 1
self._T += 1
chart_edges = self._chart_edge_lineage(parent)
chart_backup_edges = (
chart_edges
if getattr(self.env_type, "backup_descendant_values", False)
else chart_edges[:1]
)
for state_id, chart in chart_backup_edges:
key = self._chart_key(state_id, chart)
self._chart_m[key] = max(self._chart_m.get(key, y), y)
for state_id, chart in chart_edges:
key = self._chart_key(state_id, chart)
self._chart_n[key] = self._chart_n.get(key, 0) + 1
if chart_edges:
self._chart_T += 1
if not states:
return
# Canonical duplicates from the same parent are one action outcome.
# Keep the best representative before top-k admission so a duplicate
# cannot consume both survivor slots. Identical graphs from different
# parents remain separate lineages.
states, parent_states = self._dedupe_rollout_semantics_within_parent(
states,
parent_states,
)
# Max-policy admission needs the full rollout group until flush.
if not self._uses_max_policy_survivors():
if getattr(self.env_type, "chart_balanced_survivors", False):
states, parent_states = self._filter_topk_per_parent_chart(
states,
parent_states,
int(getattr(self.env_type, "topk_children_per_chart", 1)),
)
else:
states, parent_states = self._filter_topk_per_parent(
states,
parent_states,
self.topk_children,
)
existing_by_key = {
self._get_construction_key(state): state
for state in self._states
if self._get_construction_key(state) is not None
}
new_states = []
for child, parent in zip(states, parent_states):
if child.value is None:
continue
limits = getattr(self.env_type, "construction_length_limits", None)
if limits and child.construction:
lo, hi = limits
if not (lo <= len(child.construction) <= hi):
continue
max_len = getattr(self.env_type, "max_construction_len", None)
if max_len is not None and child.construction and len(child.construction) > max_len:
continue
key = self._get_construction_key(child, parent_id=str(parent.id))
if key is not None and key in existing_by_key:
existing_state = existing_by_key[key]
if (
self._uses_max_policy_survivors()
and existing_state.parents
and str(existing_state.parents[0].get("id")) == str(parent.id)
and int(existing_state.timestep) == int(child.timestep)
):
self._record_policy_candidate(existing_state, parent, key)
continue
self._set_parent_info(child, parent)
new_states.append(child)
if key is not None:
existing_by_key[key] = child
if self._uses_max_policy_survivors():
self._record_policy_candidate(child, parent, key)
if not new_states:
return
with self._lock:
self._states.extend(new_states)
if save:
self._finalize_and_save(step)
def _finalize_and_save(self, step: int | None = None):
if len(self._states) > self.max_buffer_size:
actual_values = [s.value if s.value is not None else float('-inf') for s in self._states]
by_actual = list(np.argsort(actual_values)[::-1])
initial_ids = {s.id for s in self._initial_states}
initial_indices = {i for i, s in enumerate(self._states) if s.id in initial_ids}
keep = set(initial_indices)
for i in by_actual:
if len(keep) >= self.max_buffer_size:
break
keep.add(i)
self._states = [self._states[i] for i in sorted(keep)]
if step is not None:
self._current_step = step
self._save(self._current_step)
# 【Baseline 上的改动】PUCTSampler.flush
# 在完整批次边界统一裁剪档案并保存。topk_children=2 限制的是每个 parent 的子节点。
def flush(self, step: int | None = None):
with self._lock:
if self._uses_max_policy_survivors():
self._filter_max_policy_per_parent(step)
elif getattr(self.env_type, "chart_balanced_survivors", False):
self._filter_archive_per_parent_chart()
elif self.topk_children > 0:
by_parent: dict[str, list[State]] = {}
no_parent: list[State] = []
for s in self._states:
pid = s.parents[0]["id"] if s.parents else None
if pid:
by_parent.setdefault(pid, []).append(s)
else:
no_parent.append(s)
filtered = []
for children in by_parent.values():
children.sort(key=lambda x: x.value if x.value is not None else float('-inf'), reverse=True)
filtered.extend(children[:self.topk_children])
self._states = no_parent + filtered
self._finalize_and_save(step)
# 【Baseline 上的改动】PUCTSampler.record_failed_rollout
# 即使没有合法 child,也记录此次尝试,避免失败 rollout 不计访问成本。
def record_failed_rollout(self, parent: State):
anc_ids = [parent.id] + [str(p["id"]) for p in (parent.parents or []) if p.get("id")]
for aid in anc_ids:
self._n[aid] = self._n.get(aid, 0) + 1
self._T += 1
chart_edges = self._chart_edge_lineage(parent)
for state_id, chart in chart_edges:
key = self._chart_key(state_id, chart)
self._chart_n[key] = self._chart_n.get(key, 0) + 1
if chart_edges:
self._chart_T += 1
def reload_from_step(self, step: int):
with self._lock:
self._states = []
self._initial_states = []
self._current_step = step
self._load(step)
if not self._states:
for _ in range(self.batch_size):
state = create_initial_state(self.env_type, self.problem_type)
self._initial_states.append(state)
self._states.append(state)
def get_sample_stats(self) -> dict:
def _stats(values, prefix):
arr = np.array([v for v in values if v is not None])
if len(arr) == 0:
return {}
return {
f"{prefix}/mean": float(np.mean(arr)),
f"{prefix}/std": float(np.std(arr)),
f"{prefix}/min": float(np.min(arr)),
f"{prefix}/max": float(np.max(arr)),
}
buffer_values = [s.value for s in self._states]
buffer_terminal_values = [
getattr(s, "terminal_value", None) if getattr(s, "terminal_value", None) is not None else s.value
for s in self._states
]
buffer_timesteps = [s.timestep for s in self._states]
buffer_constr_lens = [len(s.construction) if hasattr(s, 'construction') and s.construction else 0 for s in self._states]
sampled_values = [s.value for s in self._last_sampled_states]
sampled_timesteps = [s.timestep for s in self._last_sampled_states]
sampled_constr_lens = [len(s.construction) if hasattr(s, 'construction') and s.construction else 0 for s in self._last_sampled_states]
buffer_roles = [getattr(s, "survivor_role", None) for s in self._states]
sampled_roles = [getattr(s, "survivor_role", None) for s in self._last_sampled_states]
sampled_charts = [getattr(s, "rollout_chart", None) for s in self._last_sampled_states]
stats = {
"puct/buffer_size": len(self._states),
"puct/sampled_size": len(self._last_sampled_states),
"puct/T": self._T,
"puct/scale_last": float(self._last_scale),
"survivor/buffer_max": int(sum(role == "max" for role in buffer_roles)),
"survivor/buffer_policy": int(sum(role == "policy" for role in buffer_roles)),
"survivor/sampled_max": int(sum(role == "max" for role in sampled_roles)),
"survivor/sampled_policy": int(sum(role == "policy" for role in sampled_roles)),
"survivor/policy_expansions_total": int(
sum(
int(getattr(state, "survivor_expansions", 0))
for state in self._states
if getattr(state, "survivor_role", None) == "policy"
)
),
}
if self._action_charts():
stats["atlas/chart_T"] = self._chart_T
stats["atlas/chart_edges"] = len(self._chart_n)
for chart in self._action_charts():
stats[f"atlas/sampled_{chart}"] = int(
sum(sampled == chart for sampled in sampled_charts)
)
stats[f"atlas/visits_{chart}"] = int(
sum(
value
for key, value in self._chart_n.items()
if key.endswith(f"::{chart}")
)
)
stats.update(_stats(buffer_values, "puct/buffer_value"))
stats.update(_stats(buffer_terminal_values, "puct/buffer_terminal_value"))
stats.update(_stats(buffer_timesteps, "puct/buffer_timestep"))
stats.update(_stats(buffer_constr_lens, "puct/buffer_construction_len"))
stats.update(_stats(sampled_values, "puct/sampled_value"))
stats.update(_stats(sampled_timesteps, "puct/sampled_timestep"))
stats.update(_stats(sampled_constr_lens, "puct/sampled_construction_len"))
return stats
def get_sample_table(self) -> tuple[list[str], list[tuple]]:
columns = ["buffer_idx", "timestep", "value", "terminal_value", "parent_value", "construction_len", "observation_len", "survivor_role", "survivor_expansions", "survivor_backed_value", "n", "Q", "P", "bonus", "score", "atlas_chart", "atlas_n", "atlas_Q", "atlas_P", "atlas_bonus", "atlas_score"]
rows = []
if not self._last_sampled_states:
return columns, rows
indices = self._last_sampled_indices if len(self._last_sampled_indices) == len(self._last_sampled_states) else [-1] * len(self._last_sampled_states)
stats = self._last_puct_stats if len(self._last_puct_stats) == len(self._last_sampled_states) else [(0, 0.0, 0.0, 0.0, 0.0)] * len(self._last_sampled_states)
chart_stats = self._last_chart_stats if len(self._last_chart_stats) == len(self._last_sampled_states) else [(None, 0, 0.0, 0.0, 0.0, 0.0)] * len(self._last_sampled_states)
for idx, state, (n, Q, P, bonus, score), (chart, chart_n, chart_Q, chart_P, chart_bonus, chart_score) in zip(indices, self._last_sampled_states, stats, chart_stats):
parent_val = state.parent_values[0] if state.parent_values else None
constr = getattr(state, 'construction', None)
constr_len = len(constr) if constr is not None else 0
obs_len = len(state.observation) if state.observation else 0
terminal_value = getattr(state, "terminal_value", None)
if terminal_value is None:
terminal_value = state.value
rows.append((idx, state.timestep, state.value, terminal_value, parent_val, constr_len, obs_len, getattr(state, "survivor_role", None), int(getattr(state, "survivor_expansions", 0)), getattr(state, "survivor_backed_value", None), n, Q, P, bonus, score, chart, chart_n, chart_Q, chart_P, chart_bonus, chart_score))
return columns, rows
# 【本地新增】OneBitPopulationSampler
# 历史 one-bit 预算分配 sampler,正式 parent_selection_policy=puct 路径未启用。
class OneBitPopulationSampler(StateSampler):
"""Fixed-budget PFG parent allocator with two reference measures.
``local_one_bit`` treats every current particle as one unit of reference
mass. A founder that produced many current children consequently receives
more base mass in the next generation.
``persistent_founder_one_bit`` keeps the initial valid rollout states as
permanent founders. It stores one incumbent descendant per founder and
always constrains the Gibbs distribution relative to the original uniform
founder measure. Descendant multiplicity can improve a founder's value but
cannot silently enlarge its reference mass.
The first generation is special in both modes: all requested rollouts start
from the environment root, and every valid child becomes a founder. Failed
initial rollouts are useful RL observations but are not executable roots.
In later local generations, a failed mutation leaves that particle at its
executable parent so the population budget remains fixed.
"""
POLICIES = {"local_one_bit", "persistent_founder_one_bit"}
def __init__(
self,
file_path: str,
env_type: type,
problem_type: str = "",
batch_size: int = 1,
resume_step: int | None = None,
policy: str = "local_one_bit",
kl_budget_nats: float = ONE_BIT_KL,
seed: int = 0,
):
del batch_size # The rollout budget is supplied to sample_states().
if policy not in self.POLICIES:
raise ValueError(
f"Unknown one-bit policy {policy!r}; expected one of {sorted(self.POLICIES)}"
)
if not math.isfinite(float(kl_budget_nats)) or kl_budget_nats < 0.0:
raise ValueError("kl_budget_nats must be finite and non-negative")
self.file_path = file_path
self.env_type = env_type
self.problem_type = problem_type
self.policy = policy
self.kl_budget_nats = float(kl_budget_nats)
self.seed = int(seed)
self._lock = threading.RLock()
self._current_step = resume_step if resume_step is not None else 0
self._generation = 0
self._sample_round = 0
self._states: list[State] = []
self._initial_states: list[State] = []
self._archive_by_id: dict[str, State] = {}
self._population_ids: list[str] = []
self._founder_ids: list[str] = []
self._founder_by_state: dict[str, str] = {}
self._incumbent_by_founder: dict[str, str] = {}
self._founders_initialized = False
self._pending_parent_ids: list[str] = []
self._pending_selected_counts: Counter[str] = Counter()
self._pending_resolved_counts: Counter[str] = Counter()
self._pending_failed_counts: Counter[str] = Counter()
self._pending_children: list[tuple[State, str, str]] = []
self._last_sampled_states: list[State] = []
self._last_sample_stats: dict[str, float] = {}
self._last_candidate_rows: list[tuple] = []
if resume_step is not None:
self._load(resume_step)
if not self._archive_by_id:
root = create_initial_state(self.env_type, self.problem_type)
self._initial_states = [root]
self._archive_by_id[str(root.id)] = root
self._population_ids = [str(root.id)]
self._refresh_state_view()
self._save(self._current_step)
def _load(self, step: int) -> None:
path = _sampler_file_for_step(self.file_path, step)
if not os.path.exists(path):
raise FileNotFoundError(
f"Cannot resume one-bit sampler from step {step}: {path} does not exist"
)
with _file_lock(f"{path}.lock"):
store = _read_json_or_default(path, default=None)
if store is None:
raise ValueError(f"Failed to load one-bit sampler state from {path}")
stored_policy = store.get("policy", self.policy)
if stored_policy != self.policy:
raise ValueError(
f"Snapshot policy is {stored_policy!r}, requested {self.policy!r}"
)
stored_budget = float(store.get("kl_budget_nats", self.kl_budget_nats))
if not math.isclose(stored_budget, self.kl_budget_nats, rel_tol=0.0, abs_tol=1e-12):
raise ValueError(
f"Snapshot KL budget is {stored_budget}, requested {self.kl_budget_nats}"
)
stored_seed = int(store.get("seed", self.seed))
if stored_seed != self.seed:
raise ValueError(f"Snapshot seed is {stored_seed}, requested {self.seed}")
state_cls = self.env_type.state_type
states = [
state_from_dict(payload, state_type=state_cls)
for payload in store.get("states", [])
]
initial_states = [
state_from_dict(payload, state_type=state_cls)
for payload in store.get("initial_states", [])
]
self._archive_by_id = {str(state.id): state for state in states}
for state in initial_states:
self._archive_by_id.setdefault(str(state.id), state)
self._initial_states = initial_states
self._population_ids = [str(value) for value in store.get("population_ids", [])]
self._founder_ids = [str(value) for value in store.get("founder_ids", [])]
self._founder_by_state = {
str(key): str(value)
for key, value in (store.get("founder_by_state", {}) or {}).items()
}
self._incumbent_by_founder = {
str(key): str(value)
for key, value in (store.get("incumbent_by_founder", {}) or {}).items()
}
self._founders_initialized = bool(store.get("founders_initialized", False))
self._generation = int(store.get("generation", 0))
self._sample_round = int(store.get("sample_round", self._generation))
self._current_step = int(store.get("step", step))
self._validate_snapshot_references()
self._refresh_state_view()
def _save(self, step: int) -> None:
path = _sampler_file_for_step(self.file_path, step)
store = {
"type": "OneBitPopulationSampler",
"step": int(step),
"policy": self.policy,
"kl_budget_nats": self.kl_budget_nats,
"seed": self.seed,
"generation": self._generation,
"sample_round": self._sample_round,
"founders_initialized": self._founders_initialized,
"states": [
self._archive_by_id[state_id].to_dict()
for state_id in sorted(self._archive_by_id)
],
"initial_states": [state.to_dict() for state in self._initial_states],
"population_ids": list(self._population_ids),
"founder_ids": list(self._founder_ids),
"founder_by_state": dict(self._founder_by_state),
"incumbent_by_founder": dict(self._incumbent_by_founder),
}
with _file_lock(f"{path}.lock"):
_atomic_write_json(path, store)
def _validate_snapshot_references(self) -> None:
missing_population = set(self._population_ids) - set(self._archive_by_id)
missing_incumbents = set(self._incumbent_by_founder.values()) - set(
self._archive_by_id
)
if missing_population or missing_incumbents:
raise ValueError(
"One-bit sampler snapshot contains missing state references: "
f"population={sorted(missing_population)}, "
f"incumbents={sorted(missing_incumbents)}"
)
if self._founders_initialized:
missing_founders = set(self._founder_ids) - set(
self._incumbent_by_founder
)
if self.policy == "persistent_founder_one_bit" and missing_founders:
raise ValueError(
f"Persistent sampler is missing incumbents for {sorted(missing_founders)}"
)
def _refresh_state_view(self) -> None:
keep_ids = {str(state.id) for state in self._initial_states}
if self.policy == "persistent_founder_one_bit" and self._founders_initialized:
keep_ids.update(self._incumbent_by_founder.values())
else:
keep_ids.update(self._population_ids)
self._archive_by_id = {
state_id: state
for state_id, state in self._archive_by_id.items()
if state_id in keep_ids
}
self._founder_by_state = {
state_id: founder_id
for state_id, founder_id in self._founder_by_state.items()
if state_id in self._archive_by_id
}
ordered_ids = []
seen = set()
for state in self._initial_states:
state_id = str(state.id)
if state_id in self._archive_by_id and state_id not in seen:
ordered_ids.append(state_id)
seen.add(state_id)
for state_id in sorted(self._archive_by_id):
if state_id not in seen:
ordered_ids.append(state_id)
seen.add(state_id)
self._states = [self._archive_by_id[state_id] for state_id in ordered_ids]
def _candidate_ids(self) -> list[str]:
if not self._founders_initialized:
return [str(state.id) for state in self._initial_states]
if self.policy == "local_one_bit":
return list(self._population_ids)
return [self._incumbent_by_founder[founder] for founder in self._founder_ids]
@staticmethod
def _finite_state_value(state: State) -> float:
value = state.value
if value is None or not np.isfinite(float(value)):
raise ValueError(f"One-bit candidate {state.id} has non-finite value {value}")
return float(value)
def _founder_label(self, state_id: str) -> str:
if not self._founders_initialized:
return "__initial_root__"
return self._founder_by_state[state_id]
def get_frontier_value(self) -> float | None:
values = []
for state in self._states:
value = state.terminal_value if state.terminal_value is not None else state.value
if value is not None and np.isfinite(float(value)):
values.append(float(value))
return max(values) if values else None
def _attach_rollout_frontier(self, states: list[State]) -> None:
frontier = self.get_frontier_value()
for state in states:
setter = getattr(state, "set_rollout_frontier_value", None)
if callable(setter):
setter(frontier)
else:
setattr(state, "rollout_frontier_value", frontier)
def sample_states(self, num_states: int) -> list[State]:
if num_states <= 0:
return []
with self._lock:
if self._pending_parent_ids:
raise RuntimeError(
"Cannot sample a new one-bit generation before flushing the previous one"
)
candidate_ids = self._candidate_ids()
if not candidate_ids:
raise RuntimeError("One-bit sampler has no executable candidates")
candidates = [self._archive_by_id[state_id] for state_id in candidate_ids]
if len(candidates) == 1:
values = np.asarray([0.0], dtype=np.float64)
solution = solve_kl_gibbs(values, kl_budget_nats=self.kl_budget_nats)
else:
values = np.asarray(
[self._finite_state_value(state) for state in candidates],
dtype=np.float64,
)
solution = solve_kl_gibbs(
values,
kl_budget_nats=self.kl_budget_nats,
)
rng = np.random.default_rng(
np.random.SeedSequence([self.seed, self._sample_round])
)
counts = residual_systematic_counts(
solution.probabilities,
num_states,
rng,
)
indices = expanded_indices(counts, rng=rng)
picked = [candidates[int(index)] for index in indices]
picked_ids = [str(state.id) for state in picked]
self._pending_parent_ids = picked_ids
self._pending_selected_counts = Counter(picked_ids)
self._pending_resolved_counts = Counter()
self._pending_failed_counts = Counter()
self._pending_children = []
self._last_sampled_states = picked
self._sample_round += 1
candidate_founders = [self._founder_label(state_id) for state_id in candidate_ids]
sampled_founders = [self._founder_label(state_id) for state_id in picked_ids]
founder_counts = Counter(sampled_founders)
top8_mass = float(
np.sort(solution.probabilities)[::-1][:8].sum()
)
self._last_sample_stats = {
"one_bit/generation": float(self._generation),
"one_bit/reference_particles": float(len(candidate_ids)),
"one_bit/reference_founders": float(len(set(candidate_founders))),
"one_bit/archived_founders": float(len(self._founder_ids)),
"one_bit/allocated_rollouts": float(num_states),
"one_bit/active_states": float(len(set(picked_ids))),
"one_bit/active_founders": float(len(founder_counts)),
"one_bit/dominant_founder_share": float(
max(founder_counts.values()) / num_states
),
"one_bit/beta": float(solution.beta),
"one_bit/kl_nats": float(solution.kl_nats),
"one_bit/kl_bits": float(solution.kl_nats / math.log(2.0)),
"one_bit/shannon_perplexity": float(solution.entropy_perplexity),
"one_bit/renyi_ess": float(solution.renyi_ess),
"one_bit/top8_mass": top8_mass,
"one_bit/max_allocation": float(np.max(counts)),
}
self._last_candidate_rows = [
(
self.policy,
index,
candidate_ids[index],
candidate_founders[index],
None if len(candidates) == 1 else float(values[index]),
float(solution.probabilities[index]),
float(num_states * solution.probabilities[index]),
int(counts[index]),
)
for index in range(len(candidate_ids))
]
self._attach_rollout_frontier(picked)
return picked
def _resolve_parent(self, parent_id: str, *, failed: bool) -> None:
selected = self._pending_selected_counts.get(parent_id, 0)
resolved = self._pending_resolved_counts.get(parent_id, 0)
if selected <= resolved:
raise RuntimeError(
f"Received an unexpected or duplicate result for one-bit parent {parent_id}"
)
self._pending_resolved_counts[parent_id] += 1
if failed:
self._pending_failed_counts[parent_id] += 1
def update_states(
self,
states: list[State],
parent_states: list[State],
save: bool = True,
step: int | None = None,
) -> None:
if len(states) != len(parent_states):
raise ValueError("states and parent_states must have the same length")
with self._lock:
for child, parent in zip(states, parent_states):
parent_id = str(parent.id)
if child.value is None or not np.isfinite(float(child.value)):
self._resolve_parent(parent_id, failed=True)
continue
if self._founders_initialized:
founder_id = self._founder_by_state.get(parent_id)
if founder_id is None:
raise RuntimeError(
f"Parent {parent_id} has no founder in initialized one-bit population"
)
else:
founder_id = str(child.id)
self._set_parent_info(child, parent)
self._resolve_parent(parent_id, failed=False)
child_id = str(child.id)
self._archive_by_id[child_id] = child
self._founder_by_state[child_id] = founder_id
self._pending_children.append((child, parent_id, founder_id))
if save and self._all_pending_resolved():
self._finalize_generation(step)
def record_failed_rollout(self, parent: State) -> None:
with self._lock:
self._resolve_parent(str(parent.id), failed=True)
def _all_pending_resolved(self) -> bool:
return sum(self._pending_resolved_counts.values()) >= len(
self._pending_parent_ids
)
def _finalize_generation(self, step: int | None) -> None:
if not self._pending_parent_ids:
if step is not None:
self._current_step = step
self._save(self._current_step)
return
for parent_id, selected in self._pending_selected_counts.items():
unresolved = selected - self._pending_resolved_counts.get(parent_id, 0)
if unresolved > 0:
self._pending_failed_counts[parent_id] += unresolved
if not self._founders_initialized:
initial_children = sorted(
(child for child, _parent, _founder in self._pending_children),
key=lambda child: str(child.id),
)
if initial_children:
self._founder_ids = [str(child.id) for child in initial_children]
self._population_ids = list(self._founder_ids)
self._incumbent_by_founder = {
founder_id: founder_id for founder_id in self._founder_ids
}
self._founders_initialized = True
elif self.policy == "local_one_bit":
next_population = [
str(child.id) for child, _parent, _founder in self._pending_children
]
for parent_id, failed_count in self._pending_failed_counts.items():
next_population.extend([parent_id] * int(failed_count))
if next_population:
if len(next_population) != len(self._pending_parent_ids):
raise RuntimeError(
"Local one-bit generation did not conserve its particle budget: "
f"expected {len(self._pending_parent_ids)}, got {len(next_population)}"
)
self._population_ids = next_population
else:
for child, _parent_id, founder_id in self._pending_children:
incumbent_id = self._incumbent_by_founder[founder_id]
incumbent = self._archive_by_id[incumbent_id]
if self._finite_state_value(child) > self._finite_state_value(incumbent):
self._incumbent_by_founder[founder_id] = str(child.id)
self._generation += 1
if step is not None:
self._current_step = step
self._pending_parent_ids = []
self._pending_selected_counts = Counter()
self._pending_resolved_counts = Counter()
self._pending_failed_counts = Counter()
self._pending_children = []
self._refresh_state_view()
self._save(self._current_step)
def flush(self, step: int | None = None) -> None:
with self._lock:
self._finalize_generation(step)
def reload_from_step(self, step: int) -> None:
with self._lock:
self._states = []
self._initial_states = []
self._archive_by_id = {}
self._population_ids = []
self._founder_ids = []
self._founder_by_state = {}
self._incumbent_by_founder = {}
self._pending_parent_ids = []
self._load(step)
def get_state_ids(self) -> set[str]:
return set(self._archive_by_id)
def get_replay_state_ids(self) -> set[str]:
state_ids = self.get_state_ids()
for state in self._states:
state_ids.update(
str(parent["id"])
for parent in (state.parents or [])
if parent.get("id")
)
return state_ids
def get_founder_id(self, state: State | str) -> str | None:
state_id = str(state.id) if hasattr(state, "id") else str(state)
return self._founder_by_state.get(state_id)
def get_founder_ids(self) -> tuple[str, ...]:
return tuple(self._founder_ids)
def get_sample_stats(self) -> dict[str, float]:
return dict(self._last_sample_stats)
def get_sample_table(self) -> tuple[list[str], list[tuple]]:
return (
[
"policy",
"candidate_index",
"state_id",
"founder_id",
"value",
"probability",
"expected_allocation",
"allocated_rollouts",
],
list(self._last_candidate_rows),
)
# 【Baseline 上的改动】create_sampler
# 按配置选择采样器;数学 ours 还可以通过环境提供 bootstrap 专用 PUCT 子类。
def create_sampler(
log_path: str,
env_type: type,
problem_type: str = "",
batch_size: int = 1,
resume_step: int | None = None,
parent_selection_policy: str = "puct",
one_bit_kl_nats: float = ONE_BIT_KL,
one_bit_seed: int = 0,
fixed_forest_size: int = 8,
forest_ucb_c: float = 0.015,
forest_inner_puct_c: float = 1.0,
forest_root_rollouts_per_tree: int = 64,
) -> StateSampler:
"""Create the configured parent sampler."""
if not log_path:
raise ValueError("log_path is required when using a state sampler")
if parent_selection_policy in OneBitPopulationSampler.POLICIES:
sampler_path = os.path.join(log_path, "one_bit_sampler.json")
return OneBitPopulationSampler(
file_path=sampler_path,
env_type=env_type,
problem_type=problem_type,
batch_size=batch_size,
resume_step=resume_step,
policy=parent_selection_policy,
kl_budget_nats=one_bit_kl_nats,
seed=one_bit_seed,
)
if parent_selection_policy == "fixed_forest_ucb":
# Import lazily because fixed_forest builds on the StateSampler API in
# this module. The fixed forest is a separate policy, not a one-bit
# population variant.
from ttt_discover.tinker_utils.fixed_forest import FixedForestUCBSampler
sampler_path = os.path.join(log_path, "fixed_forest_sampler.json")
return FixedForestUCBSampler(
file_path=sampler_path,
env_type=env_type,
problem_type=problem_type,
batch_size=batch_size,
resume_step=resume_step,
forest_size=fixed_forest_size,
tree_ucb_c=forest_ucb_c,
inner_puct_c=forest_inner_puct_c,
root_rollouts_per_tree=forest_root_rollouts_per_tree,
)
if parent_selection_policy != "puct":
raise ValueError(
f"Unknown parent_selection_policy {parent_selection_policy!r}; expected "
"'puct', 'fixed_forest_ucb', or one of "
f"{sorted(OneBitPopulationSampler.POLICIES)}"
)
sampler_path = os.path.join(log_path, "puct_sampler.json")
sampler_type = getattr(env_type, "state_sampler_type", None) or PUCTSampler
if not issubclass(sampler_type, PUCTSampler):
raise TypeError("env_type.state_sampler_type must extend PUCTSampler")
return sampler_type(
file_path=sampler_path,
env_type=env_type,
problem_type=problem_type,
batch_size=batch_size,
resume_step=resume_step,
)
# 【Baseline 上的改动】get_or_create_sampler_with_default
# 创建/复用任务 sampler,并传入输出目录、组数、策略和恢复信息。
def get_or_create_sampler_with_default(
log_path: str,
env_type: type,
problem_type: str = "",
batch_size: int = 1,
resume_step: int | None = None,
parent_selection_policy: str = "puct",
one_bit_kl_nats: float = ONE_BIT_KL,
one_bit_seed: int = 0,
fixed_forest_size: int = 8,
forest_ucb_c: float = 0.015,
forest_inner_puct_c: float = 1.0,
forest_root_rollouts_per_tree: int = 64,
) -> StateSampler:
"""Get sampler. Initial experience is created via env_type.create_initial_state."""
return create_sampler(
log_path=log_path,
env_type=env_type,
problem_type=problem_type,
batch_size=batch_size,
resume_step=resume_step,
parent_selection_policy=parent_selection_policy,
one_bit_kl_nats=one_bit_kl_nats,
one_bit_seed=one_bit_seed,
fixed_forest_size=fixed_forest_size,
forest_ucb_c=forest_ucb_c,
forest_inner_puct_c=forest_inner_puct_c,
forest_root_rollouts_per_tree=forest_root_rollouts_per_tree,
)
# 中文源码导读(2026-09-15)|阅读顺序 013|Baseline 扩展
# 来源:Baseline 扩展:官方已有同路径文件,本地实现包含改动。
# 作用:PUCT 状态档案、父节点选择、top-2 保留与恢复;还保留默认未启用的 one-bit/历史信用分支。
# 对照基准:test-time-training/discover@6c40e82;完整路线见 docs/CODE_READING_ORDER_ZH.md。
"""Centralized sampler creation for all environments."""
from __future__ import annotations
from abc import ABC, abstractmethod
from collections import Counter
import hashlib
import math
import os
import threading
import numpy as np
from ttt_discover.tinker_utils.state import State, state_from_dict
from ttt_discover.tinker_utils.best_sequence_utils import _file_lock, _atomic_write_json, _read_json_or_default
from ttt_discover.tinker_utils.one_bit_allocation import (
ONE_BIT_KL,
expanded_indices,
residual_systematic_counts,
solve_kl_gibbs,
)
# 【Baseline 上的改动】StateSampler
# baseline 采样器接口,规定选状态、接收子状态与保存边界。
class StateSampler(ABC):
"""Abstract base class for sampling states."""
def sample_states(self, num_states: int) -> list[State]:
"""Sample states to start rollouts from."""
pass
def update_states(self, states: list[State], parent_states: list[State], save: bool = True, step: int | None = None):
"""Update internal storage with new states. Sets parent info automatically."""
pass
def flush(self, step: int | None = None):
"""Force save current state to disk."""
pass
def _set_parent_info(child: State, parent: State):
"""Set parent_values and parents on child state from parent."""
child.parent_values = [parent.value] + parent.parent_values if parent.value is not None else []
child.parents = [{"id": parent.id, "timestep": parent.timestep}] + parent.parents
if hasattr(child, "chart_lineage"):
chart = getattr(parent, "rollout_chart", None)
child.incoming_chart = chart
child.chart_lineage = [chart] + list(
getattr(parent, "chart_lineage", []) or []
)
def _filter_topk_per_parent(states: list[State], parent_states: list[State], k: int) -> tuple[list[State], list[State]]:
"""Keep top-k children (by value) per parent. If k=0, return all."""
if not states:
return [], []
if k == 0:
return states, parent_states
# Group by parent id
parent_to_children: dict[str, list[tuple[State, State]]] = {}
for child, parent in zip(states, parent_states):
pid = parent.id
if pid not in parent_to_children:
parent_to_children[pid] = []
parent_to_children[pid].append((child, parent))
# Keep top-k children per parent (highest value)
topk_children, topk_parents = [], []
for children_and_parents in parent_to_children.values():
sorted_pairs = sorted(children_and_parents, key=lambda x: x[0].value if x[0].value is not None else float('-inf'), reverse=True)
for child, parent in sorted_pairs[:k]:
topk_children.append(child)
topk_parents.append(parent)
return topk_children, topk_parents
def _sampler_file_for_step(base_path: str, step: int) -> str:
"""Get the sampler file path for a specific step."""
base_name = base_path.replace(".json", "")
return f"{base_name}_step_{step:06d}.json"
def create_initial_state(env_type: type, problem_type: str) -> State:
"""Create initial state by delegating to the env type. Custom envs implement create_initial_state on their class."""
name = getattr(env_type, "env_name", env_type.__name__)
print(f"Creating initial state for {name}")
return env_type.create_initial_state(problem_type)
# 【Baseline 上的改动】PUCTSampler
# 核心 PUCT 选择公式来自 baseline;本地同时保留可选历史扩展,所以整个类不是逐字官方原版。
# 正式入口关闭后代价值回传、语义去重等扩展,保留 PUCT 和每个 parent 的 top-2 规则。
class PUCTSampler(StateSampler):
"""
PUCT-style sampler with state archive.
Xet Storage Details
- Size:
- 65.1 kB
- Xet hash:
- 3659735c730e950ebf649e9c07c437c4a2110967a433e1c42ebb27c08cc36b3f
·
Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.