zefancainlp's picture
download
raw
65.1 kB
# 中文源码导读(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."""
@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.

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.