一句话：提出 BBExplorer，在有限模拟预算下高效发现非确定性游戏中平衡与不平衡的边界，用于平衡回归测试。
现代软件常具有非确定性执行与巨大行为空间，单次运行难以判断正确性，也难以界定可接受行为的终点。竞技多人游戏是典型例子：需保持无单一策略主导的平衡，参数微小变化可能引发平衡突变，而检测此类失败需在非确定结果与高维参数空间下反复模拟。本文将游戏平衡回归测试形式化为有限模拟预算下的边界发现问题，目标是高效识别靠近平衡与不平衡区域分界的输入。为此提出 BBExplorer，结合多方向候选生成、预算感知的两阶段筛选与自适应步长收缩以精化边界。在两个复杂度不同的游戏上实验表明，该方法在低维设置下表现强，在高维下仍有效，并在未见随机种子与阈值设置下保持稳定的边界行为，适用于实际平衡回归测试及更广泛的非确定、预算受限系统的边界导向测试。
Software testing often relies on assumptions such as reproducible executions and stable correctness criteria. However, many modern software systems exhibit non-deterministic executions and large behavior spaces, making exhaustive exploration impractical and single-run judgments unreliable. These characteristics make it difficult to identify where acceptable behavior ends and problematic behavior begins. Competitive multiplayer games represent a challenging instance of such systems, where balance must be maintained so that no single strategy dominates. Even small parameter changes can trigger abrupt balance disruption, yet detecting such failures requires repeated simulations under non-deterministic outcomes and high-dimensional parameter spaces. In this paper, we formulate game balance regression testing as a boundary-discovery problem under a finite simulation budget. The objective is to efficiently identify inputs near the boundary that separates balanced and unbalanced regions. To address this problem, we propose BBExplorer, which combines multi-directional candidate generation, budget-aware two-stage screening, and adaptive step-size shrinkage for boundary refinement. Experimental results on two games with different levels of complexity show that the approach is strong in low-dimensional settings and remains effective in higher-dimensional ones. It also exhibits stable boundary behavior across unseen random seeds and threshold settings. These results indicate that BBExplorer is effective for practical balance regression testing and, more broadly, for boundary-oriented testing in non-deterministic, budget-constrained systems.
@inproceedings{paperbot12346,
title = {Where Does Balance Break? Boundary Discovery for Game Balance Testing under a Finite Simulation Budget},
author = {Hiroki Mukai and Yusaku Kato and Norihiro Yoshida and Erina Makihara and Katsuro Inoue},
booktitle = {ASE},
year = {2026},
doi = {10.1145/3832783.3834407}
}