G16：Game of 24 的搜索与确定性 Verifier
Game of 24 是一个小而完整的可搜索任务：从四个数字出发，通过有限算术动作构造 24，适合从零观察状态表示、组合爆炸、路径去重和确定性验证怎样共同决定搜索质量。
内容类型：预习教材（不代表已完成）
日期：2027-03-09
阶段：P3 · AGI Foundations 90
总路线：Day 196 / 360
周次 / 节奏：W3 · 周二最小机制
状态：教材已备；学习未完成
主题：state representation、合法动作、去重、搜索与表达式验证
一句话定义
Game of 24 是一个小而完整的可搜索任务：从四个数字出发，通过有限算术动作构造 24，适合从零观察状态表示、组合爆炸、路径去重和确定性验证怎样共同决定搜索质量。
学习目标
- 能把 Game of 24 定义成状态、动作、转移、目标和非法条件。
- 能用 DFS/BFS 或 best-first search 枚举表达式，不依赖模型自评答案。
- 能实现或手推一个防浮点误差、检查数字使用次数的 deterministic verifier。
- 能构造搜索成功但 verifier 拒绝、表达式看似正确但违反规则的反例。
核心知识
状态不能只保存当前数值集合，还要保存每个值对应的表达式与使用过的原始数字。初始状态如 [(4,"4"),(7,"7"),(8,"8"),(8,"8")]。一次动作从两个元素 a,b 选择 +,-,*,/，产生新元素并替换原二者，直到只剩一个数。减法和除法非交换，必须考虑 a-b/b-a 与 a/b/b/a。
搜索存在大量对称重复。加法和乘法交换顺序相同；相同数值可能由不同表达式产生。如果只按数值 multiset 去重，可减少节点，却可能丢失需要审计的表达式差异；如果完全不去重，树快速膨胀。可分别设置 state-key 和 trace：key 用规范化有理数 multiset，trace 保留首次或若干表达式。
Verifier 应解析表达式、检查只使用给定数字且各一次、只含允许运算、无除零，最后精确等于 24。Python/JS 浮点可能让 1/3*72 出现近似误差；toy 实现更适合使用分数 (numerator, denominator) 并约分。
机制与推导
若当前状态有 n 个数，选择无序对有 n(n-1)/2 种，考虑运算方向后最多约六个结果。粗略分支因子随层变化，深度固定为 3。虽然任务很小，重复状态仍多，足以展示剪枝。
有理数操作：
[ \frac{a}{b}+\frac{c}{d}=\frac{ad+bc}{bd},\quad \frac{a}{b}\div\frac{c}{d}=\frac{ad}{bc} ]
每次用 gcd 约分，并规范分母为正。状态 key 将每个 fraction 写成约分后的 (num,den)，排序后序列化。目标测试是状态只剩 (24,1)。
DFS 容易快速找到一个解，但不能保证最有解释性的表达式；BFS 在每步代价一致时系统遍历；best-first 可以用启发式 h=min_i |v_i-24|，但这个启发式不一定与组合可解性一致。语言模型可作为 proposal 生成候选动作，但正确性仍由相同 transition 与 verifier 决定。
反例：表达式 8/(4-8/8)=8/3 并非 24，即使文本声称成功；表达式重复使用一个 8 或引入平方也违反任务规则。另一个边界是允许中间负数或分数与否会改变可解集合，必须在 specification 中明确。
最小练习或观察步骤
- 写出 state tuple、allowed operators、数字使用规则与是否允许分数/负数。
- 手推输入
[4,7,8,8]的前两层至少六个不同状态，并标记交换对称。 - 设计 fraction 类型或伪代码，确保加减乘除与约分准确。
- 为 verifier 准备四类 fixture：正确、数值错误、重复数字、非法运算。
- 比较无去重与规范 key 去重的理论节点数；若运行，只记录观察，不预设减少比例。
常见误区与边界
- 使用
eval直接执行任意字符串，留下安全和语法边界问题。 - 只检查表达式结果接近 24，不检查输入数字使用次数。
- 浮点容差太宽，把错误表达式判为正确。
- 去重 key 忽略任务要求，错误合并了语义不同状态。
- 把搜索器能穷举找到答案说成模型具备推理能力。
- 把 Game of 24 上的搜索效率外推到开放、不可验证任务。
研究/系统场景连接
金融规则组合也可表示成搜索：从可用条件、阈值和动作构造一个满足约束的决策方案。与算术不同，现实规则可能有冲突、优先级和不可量化目标，verifier 不再完美。因此 Game of 24 教会的是接口和证据边界，而不是直接迁移一个算法。
Agent 的工具计划可借鉴“动作必须由 transition 接受、最终状态由 verifier 检查”。例如本地模拟支付流程时，每个动作检查余额、权限和幂等键，语言模型只能提出动作，不决定它是否合法。真实资金操作仍不在本实验范围内。
自检问题
- 为什么状态需要同时保存数值与表达式来源？
- 加法/乘法与减法/除法的对称性有什么不同？
- Fraction 表示解决了什么问题，又没有解决什么？
- State dedup 可能丢失哪类信息？
- 搜索成功能支持什么算法结论，不能支持什么智能主张？
专业课程对齐
- 阅读 Tree of Thoughts 中 Game of 24 的状态、候选与评价，注意论文方法与确定性穷举基线的区别。
- 参考 Berkeley CS188 教材 的 Search 章节中 state space、frontier、graph search 与 heuristic 基础，把语言任务还原为标准搜索问题。
- 对照 Scaling LLM Test-Time Compute Optimally Can Be More Effective than Scaling Model Parameters，思考固定任务上预算增加何时转化为状态覆盖。
深入学习提示
先让纯算法 baseline 正确，再把模型加入 proposal 或 heuristic；否则无法判断收益来自哪里。可进一步比较 DFS、BFS、beam 与 A*，但 Game of 24 的深度很小，性能差异未必代表一般搜索。更有价值的扩展是故意制造错误 heuristic，观察剪枝怎样删除正确路径，再连接到 verifier 风险。
学后填写区
- 我的任务 specification：
- 状态 key 与 trace 的区别：
- 四类 verifier fixture：
- 一个错误 heuristic 反例：
- 本实验的外推边界：