提出半强求解新范式，平衡计算成本与最优性保障。
Semi-Strongly solved: a New Definition Leading Computer to Perfect Gameplay
- 定义半强求解：假设一方最优时，保证另一方任意走法下的最优应对
- 6×6奥赛罗游戏实现精确值查询与最优走法选择，节点数仅4×10¹²
- 比传统强求解节省9074倍计算量，支持第三方验证
强求解要求对所有可达状态给出最优策略，但状态空间过大难以实现。弱求解成本低，但仅保证初始位置最优，无法确保任意偏离后的最优响应。本文提出半强求解：在已知至少一方采取最优策略的前提下，对可到达区域R内的状态保证最优性。通过固定最优走法的平局规则使目标确定。提出重启α-β算法，仅在需要精确值和唯一最优动作时使用全窗口搜索，其余情况采用空窗反驳与标准剪枝。该框架输出可部署解决方案及第三方验证的证明证书。在理想条件下，节点扩展量为O(d b^(d/2))。在6×6奥赛罗（得分收益）上，实现了区域R内精确值查询与最优走法选择；强枚举法在突破4×10¹²个规则可达状态后即耗尽存储。在7×6连珠（胜负平收益）上，半强认证所需状态数仅为已有强基线的1/9074，符合相同计数约定。半强求解提供基于假设范围的可验证最优性保证，连接弱求解与强求解，并支持显式的资源-精度权衡。
原文摘要 · Abstract (English)
Strong solving of perfect-information games certifies optimal play from every reachable position, but the required state-space coverage is often prohibitive. Weak solving is far cheaper, yet it certifies correctness only at the initial position and provides no formal guarantee for optimal responses after arbitrary deviations. We define semi-strong solving, an intermediate notion that certifies correctness on a certified region R: positions reachable from the initial position under the explicit assumption that at least one player follows an optimal policy while the opponent may play arbitrarily. A fixed tie-breaking rule among optimal moves makes the target deterministic. We propose reopening alpha-beta, a node-kind-aware Principal Variation Search/Negascout scheme that enforces full-window search only where semi-strong certification requires exact values and a canonical optimal action, while using null-window refutations and standard cut/all reasoning elsewhere. The framework exports a deployable solution artifact and, when desired, a proof certificate for third-party verification. Under standard idealizations, we bound node expansions by O(d b^(d/2)). On 6x6 Othello (score-valued utility), we compute a semi-strong solution artifact supporting exact value queries on R and canonical move selection. An attempted strong enumeration exhausts storage after exceeding 4x10^12 distinct rule-reachable positions. On 7x6 Connect Four (win/draw/loss utility), an oracle-value experiment shows that semi-strong certification is 9,074x smaller than a published strong baseline under matched counting conventions. Semi-strong solving provides an assumption-scoped, verifiable optimality guarantee that bridges weak and strong solving and enables explicit resource-guarantee trade-offs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。