[2411.01029] Semi-Strongly solved: a New Definition Leading Computer to Perfect Gameplay

Computer Science > Artificial Intelligence arXiv:2411.01029 (cs) [Submitted on 1 Nov 2024 (v1), last revised 25 Mar 2026 (this version, v2)] Title:Semi-Strongly solved: a New Definition Leading Computer to Perfect Gameplay Authors:Hiroki Takizawa View a PDF of the paper titled Semi-Strongly solved: a New Definition Leading Computer to Perfect Gameplay, by Hiroki Takizawa View PDF HTML (experimental) Abstract: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 ...