AlphaBeta is not as good as you think: a simple class of synthetic games for a better analysis of deterministic game-solving algorithms
Authors: Raphael Boige
Amine Boumaza
Bruno Scherrer
Venue: NeurIPS 2025 poster ()
Keywords: Algorithmic Game Theory
Probabilistic Models
Minimax
Planning
Synthetic Game
Complexity Analysis
Primary area: theory
TL;DR: We specify and analyze a class of synthetic games generated by a simple probabilistic model to analyze the average-case complexitiy of deterministic game-solving algorithms, adressing limitations of previous independence-based models.

Abstract: Deterministic game-solving algorithms are conventionally analyzed in the light of their average-case complexity against a distribution of random game-trees, where leaf values are independently sampled from a fixed distribution. This simplified model enables uncluttered mathematical analysis, revealing two key properties: root value distributions asymptotically collapse to a single fixed value for finite-valued trees, and all reasonable algorithms achieve global optimality. However, these findings are artifacts of the model’s design: its long criticized independence assumption strips games of structural complexity, producing trivial instances where no algorithm faces meaningful challenges. To address this limitation, we introduce a class of synthetic games generated by a probabilistic model that incrementally constructs game-trees using a fixed level-wise conditional distribution. By enforcing ancestor dependencies, a critical structural feature of real-world games, our framework generates problems with adjustable difficulty while retaining some form of analytical tractability. For several algorithms, including AlphaBeta and Scout, we derive recursive formulas characterizing their average-case complexities under this model. These allow us to rigorously compare algorithms on deep game-trees, where Monte-Carlo simulations are no longer feasible. While asymptotically, all algorithms seem to converge to identical branching factor (a result analogous to that of independence-based models), deep finite trees reveal stark differences: AlphaBeta incurs a significantly larger constant multiplicative factor compared to algorithms like Scout, leading to a substantial practical slowdown. Our framework sheds new light on classical game-solving algorithms, offering rigorous evidence and analytical tools to advance the understanding of these methods under a richer, more challenging, and yet tractable model.

AlphaBeta is not as good as you think: a simple class of synthetic games for a better analysis of deterministic game-solving algorithms
Bruno Scherrer Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
Raphaël Boige" Amine Boumaza
Abstract
Deterministic game-solving algorithms are conventionally amalyzed in the light of their average-case complexity against a distribution of random game-trees, where leaf values are independently sampled from fixed distribution. This simplified model enables uncluttered mathematical analysis, revealing two key properties: root value distributions asymptotically collapse single fixed value for finite- valued trees, and all reasonable algorithms achieve global optimality. However, these findings are artifacts of the model's 's design: its long criticized independence assumption strips games of structural complexity, producing trivial instances where no algorithm faces meaningful challenges. To address this limitation, we introduce a class of synthetic games generated by probabilistic model that incrementally constructs game-trees using a fixed level-wise conditional distribution. By enforcing ancestor dependencies, a critical structural feature of real-world games, our framework generates problems with adjustable difficulty while retaining some form of analytical tractability. For several algorithms, including AlphaBeta and Scout, we derive recursive formulas characterizing their average-case complexities under this model. These allow us to rigorously compare algorithms on deep game- trees, where Monte-Carlo simulations are no longer feasible. While asymptotically, all algorithms seem to converge to identical branching factor (a result analogous to that of independence- based models), deep finite trees reveal stark differences: AlphaBeta incurs a significantly larger constant multiplicative factor compared algorithms like Scout, leading to a substantial practical slowdown. Our framework sheds new light classical game-solving algorithms, offering rigorous evidence and analytical tools to advance the understanding of these methods under a richer, more challenging, and yet tractable model.
Introduction
In this work, consider class of deterministic two-player zero-sum games represented by trees of height h, where each node has a uniform branching degree i, as illustrated in Figure Each level alternates between decision points for the maximizing and minimizing players (with the root always being max node). Internal nodes propagate values from their children via alternating min/max operators, reflecting optimal play. Clearly, the entire tree is determined by its leaf values, and solving it involves recursively applying min and max operations until the root value is resolved.
Game-solving algorithms are conventionally evaluated 140 by the number of leaf evaluations required. For example, brute-force search evaluates all 8 leaves, corresponding to a branching factor of b-the average nodes evaluated per level, see Section 2 for formal definitions. Notably, even with prior knowledge of the root value, verifying it requires evaluating at least one node per
*Corresponding author: {name} (surnnna)eeiniii....
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

Standard model
h=2
Forward model level 2
MAX
b=2
3
3
-2
level 1
MIN
?
-2
3*
level 0
?
0 2 2 o
2
3
723
Figure 1: Illustration of a game-tree of height h = 2 and branching degree b 2. (Left) In the standard model, leaf values are independently sampled from a distribution. (Right) In the forward model, intermediate values are sampled progressively, level by level, until leaf nodes are reached. One random child is chosen to inherit the root value, illustrated by a star symbol, and the remaining ones are sampled according to a fixed distribution, truncated to respect the minimax constraints.
max level and all nodes per min level. This results in a complexity of b², or a branching factor of vb, establishing global upper and lower bounds for all algorithms. ALPHA-BETA, shown in (2). achieves these bounds under optimally ordered worst-case and best-case trees. This has motivated the emergence of average-case analyses, which aim to understand how game-solving algorithms perform on a diverse collection of random trees. The classical approach, hereafter called the standard mode T samples leaf values independently from a fixed distribution. While mathematically tractable, this model exhibits critical flaws: when leaf values are restricted to a finite set, Pearl (5) proved that the root value asymptotically collapses to a single fixed value for all distributions. This collapse renders algorithm comparisons questionable: instances become trivial, as methods merely confirm a predetermined value shared among trees.
A practical consequence is the standard model's s assignment of global optimality to multiple algorithms. ALPHA-BETA, for instance, provably achieves the vb branching factor asymptotically when h and b tend to infinity, except for one rare case discussed later. This is remarkable, since no alternative algorithm, even in principle, can outperform them asymptotically. While this has been interpreted as a sign of algorithmic maturity, we believe instead that it reflects deficiencies in the evaluation framework. When trees homogenize to trivial instances with a single root value, comparisons lose meaning as algorithms face no substantive challenges to distinguish their performance. Previous works have pinpointed that these limitations stem from the model's independence assumption [6] 2]. which can't 't model dependencies between sibling nodes. Real-world games like chess possess an important type of ancestor dependencies: correlation among sibling nodes. In average a winning position for the white player should have many wins (and few losses) in the subtree emanating from it. Crucially, the independence assumption eliminates such complexity, rendering the standard model a poor proxy for practical scenarios, and poor benchmark for comparing algorithms.
In this work, we specify and analyze a synthetic game-tree model: the forward mode that addresses these limitations. By constructing trees level-by-level with conditional distribution that enforces ancestor dependencies, our approach captures two critical properties: (I) sibling values correlate conditioned on their parent value, coarsely mimicking the strategic continuity of real games, and (2) game difficulty can be better modulated, enabling more challenging benchmarks for algorithm analysis. In Section 3 we further detail our forward model. Within this framework, we characterize the behavior of classic algorithms with recursive formulas for their average-case complexity, including ALPHA-BETA, which we develop in Section These formulas are convenient for asymptotic analysis as well as limit-depth evaluations, as they allow simulating the behavior of algorithms on deep trees much more efficiently than Monte-Carle simulations. Our findings reveal that in the asymptotic regime, all algorithms share the same branching factor, as function of the distribution chosen. Theoretically. this suggests that there is little reason to prefer one algorithm over another. However, finite-depth analysis, in Section 6 reveals critical practical differences masked by asymptotics. Specifically, ALPHA-BES BETA incurs a larger multiplicative constant, and needs in average to evaluated more leaf nodes compared to other algorithms like SCOUT. Finally, to allow reproduction of the numerical results presented
The standard model often referred to as the Pearl- game or P-game model the literature. 'In the rest of this work, we freely use the terms Forward game or F F-game to designate game generated by the forward model.

---

in this paper, we open-source our codebase which permits the precise computation of average-case complexities of several algorithms and for game-trees up height h 5000
2 Notations and background
In this section, we formalize the framework for analyzing deterministic game-solving algorithms, focusing on average-cast complexity under probabilistic tree generation model.
Game formalism We model games as complete b-ary trees of height h, where leaf nodes hold values from a space V. Formally, a minimax node value V,, with children values (V/ (V%=))ss can be written VA= = max;<a (V)=1) (resp. min, (V the root. However, in two-playe zero-sum games, by using the identity min(a, b) = max(-ax b). we can formulate an equivalent negamax view where the alternate min/max are replaced by single operator. This defines a negamax node value Wn, with children values (Wi as:
(1) )) level h is at an even (resp. odd) distance from
W₁ max (exxx-WW;,)) +<b
We can see the two views are equivalent, as W = V. (resp. - -V,) if level h is at an even (resp. odd) distance from the root. In the rest of this work, we use the negamax view, as it often simplifies algorithmic descriptions and formal analysis, conveniently halving the number of cases to study.
Algorithmic complexity and branching factor To measure the efficiency of deterministic algorithm A, the main value of interest is its average-case complexity [h),, i.e. the expected number- over distribution of trees generated randomly-of leaf node inspections required by the algorithm A to terminate.
The asymptotic branching factor A quantifies the complexity growth of the algorithm with the height of the tree:
lim (hx 1-+00
(2)
This represents the effective branching rate per level. As stated before, global lower and upper bounds
known for these quantities, for all algorithms A: bă < lahh) s 6a and vb S rA S b.
3 The forward model
This section formally introduces the forward model: simple synthetic game model that recursively generates game-trees, down from the root node, through level-wise sampling process that enforces the negamax constraint from Equation [ at each step. This model resembles previous synthetic game models that generate trees in a top-down fashion [17] 20 Still, to the best of our knowledge, this work provides the first analysis of this conceptually simple yet rich game model. The sampling process can be described as follows: starting from the root node, assuming it holds value v, one of its b children is uniformly selected to inherit the parent's negated value -r, ensuring compliance with the negamax constraint. The remaining (b - 1) children are then sampled from the level-wise distribution with support dynamically truncated conditionally on x. For instance, if μt's initial support is (-n,... n for an integer n, it gets truncated (and normoazll to { f..,...,
Algorithm 1: FORWARD-SAMPLEEOE SAMPLE
Input:
Node value x, tree height h, branching degree b.
Output: Children values list.
if h = 0 then return [] // Leaf nodes Tlist + []
ksample ~ ((1
for k= I...b do
if k: = ksample then x' = - else x' ~ - -x) Lfist. append(())
end return 2'jst
This procedure, dubbed
FORWARD-SAMPLR and formally described in Algorithm T is first called on the root node, and recursively applied to each node until all leaves have been generated. For simplicity, we choose the same distribution y for each node, and we draw the root value of the tree according to μ as well.
Unlike traditional models that first assign leaf values and propagate them backward through min/max rules, our approach builds values progressively from the root downward, hence the "forward" designation. As demonstrated in the next section, this property simplifies the complexity analysis for game-solving algorithms, as intermediate outcomes are conditionally known during tree construction.
Link to the repository: https//gittbb.com///pooaaaaapppt
3

---

4 A binary-valued example: the analysis of the SOLVE algorithm
In this section, we consider binary-valued trees that represent two-outcome games, loss or win (i.e.. V = {0, 1)). We focus on SOLVE, canonical algorithm for two-outcome games, and contrast its behavior under the standard model versus our forward model. Key derivations appear in Appendix C
Algorithm description and standard model limitations The SOLVE algorithm (pseudo-code in Appendix [C) determines win/loss (1/0) outcomes by iteratively scanning through children and evaluating them until an opponent loss (0) is found, in this case it early stops and returns a win (1), if none is found, it returns a loss (0). Under the standard model, with probability qo of drawing 0 for leaf node, SOLVE almost always achieves globally optimal branching factor:
Vb E O
if 4o # 1 - E. (very easy instances)
STANDARD SOLVE
b log
if qo
Eb (special case)
(I-E+)
where & is the positive root of x² non-trivial instances, it has been thoroughly analyzed in the literature [.. However, even this hardest regime generates much easier instances than those of an wrdering-invarion worst-case model
+ x
- 1 0
5 Since only this exceptional regime generates
b-1+ / + 14b +1 (b).
RAND-WC
SOLVE
The standard model's abrupt transition between vb and log b/b regimes, described in Equation 3 reveals its inability to generate smoothly tunable or maximally hard instances.
Complexity analysis Under the forward model, where μ B(g) (Bernoulli distribution with q the probability of drawing a 0), we derive (Appendix C a closed-form expression for SOLVE'S 's branching
factor:
(g + Mg, 6)2h + 45
b-1 (+ 1aa 9)*
((g,b)
SOLLVE
If 1 the model collapses to trivial tree (alternating levels full of zeros and full of ones) leading to a vb branching factor. However, if q O. it matches exactly the worst-case complexity of Equation 4 For values of q in-between, the monotonicity of Tsouve with respect to q guarantees that any branching factor from easiest to hardest case can be reached, allowing adjustable difficulty calibration (unattainable under the standard model). In particular, a continuous range of values leads to asymptotically hardest instances as stated in the following theorem, the proof of which is in Appendix A.1
Theorem 4.1. For b e N and for all q E [0, }. the branching factor of sOLVE satisfies Tsouve O(b).
In the next section, we analyze classical algorithms more general type of trees under original forward tree model.
5 Average-case analysis of classic algorithms
Even though binary-valued games offer simplified analysis, they cannot reflect the diversity of real games, which are best modeled using broader value range. In this section, we analyze the algorithms TEST, ALPHA-BETA and SCOUT, on trees with values in {-n..... n), i.e. i is categorical distribution Pn).
Algorithm 2: TEST(N, h, s), negamax form
Input: Current node N, search depth h,
5.1 Analysis of TEST
threshold
Output: Certificate value determining if N's value is greater or equal than if h = 0 then return N.value
Algorithm description Described in Algo- rithm2] TEST answers, given a threshold s, whether the root value z satisfies x2s. Like SOLVE, TEST iteratively evaluates every child node by calling a negated version of itself and terminates early whenever it finds a value validating the condition x28. is almost identical to applying SOLVE to a binarized version of the same tree where leaves 1; are converted to 222 8 and otherwise- wwth the main difference being TEST not only returns the
best + -o0
foreach
in N.chldrenn do value + - TEST(N', h-1, + best < max (best, value) if best then break
end return best.

---

binary result of the assertion but also returns a certificate value determining whether x2s or not. This makes it a useful building block for other game-solving algorithms. For instance, a simple algorithm could brute-force over all possible thresholds to identify v, note that this approach can be optimized via bisection. In Section[6 we compare these TEST-BRUTEPORCE and Test-BISECTION approaches to the ALPHAA-BET and SCOUT algorithms. In the standard model, if leaf values are drawn according to a distribution Mo with cumulative distribution F then:
T STTANDAAD (Vo, s) = T StANeAR (go (+))
This equivalence suggests that games with discrete values are not fundamentally asymptotically harder than games with binary values. In the following we characterize TEST under the forward model and show that its branching factor coincides with that of SOLVE on a worst-case distribution.
we are interested in the verage-complexity of TEST(s) defined as T=ss7(1 (h) Ex==p [Tas (h)], where Fust (h) denotes the expected complexity of TEST when the root value is E {-n,.... ...,, n... To model intermediate evaluation states, we extend this definition to / (h, c). representing the complexity when the current node (with value x) has S remaining children to evaluate (all other nodes still have 6 children). Thus, the base case satisfies: 1is (h) = Ii c= b). A necessary tool for expressing List (h) is the auxiliary function Jusn (h, c), which represents the same complexity value, but conditioned on the probabilistic event that the "special child" (inheriting the root's 's value, enforced by the negamax constraint) has already been identified. A recursive system characterizing the average-case dynamics of TEST can be derived by analyzing its execution flow under the forward model. Upon evaluating the first child (c b): (1) with probability 1/c, TEST encounters the "special child", inheriting the root value =.. The algorithm must then fully evaluate this child node by a recursive call to a negated 1, if no cutoff occurs (i.e. I < s) continues evaluating the root node (height h), but with only c - 1 remaining children, and knowing the "special child" has been found (cost of Jus (h, c 1) instead of I (h, c 1)): (2) with probability (c - 1)/c, TEST encounters "normal" child whose value X' is sampled from j truncated to {-z,.... n) and in the absence of cutoff (i.e. -X' < s), the algorithm proceeds to evaluate the remaining children of the root node (cost of Fis (h, 1)). This gives the following equation for :
Complexity analysis For a given threshold value
{-n 1,,1,,,111, I,...,n) n)
version of TEST at height
Special child X'
1 (h, c)
-zz.st (h- 1, + 1 (1SS) Pii (h, Jusi
(7)
E Kmu X'2-2
I 1x xx,-++1 (h (h- 1, + 1 12 (h,
Normal child X" 1
The auxiliary function (h, c) follows the same logic, but being conditioned on the event "the special child already has been found", it only allows one of the branches, so the equation simplifies to:
J (h, c)
E
Xx -x
(h- 1,b) + (- Juie (h, c 1)
(8)
X X' X'2-x
TITT
Note that for the end case h = O, both and equal (a tree with only one node incurs a cost of 1). and for c 0. both I and J equal O (because no remaining child incurs no additional costs).
Equations and 8 characterizing the complexity of TEST- as well as Equations and 10 (resp.
Equations and 12p characterizing the complexity of ALPHA-BETA (resp. SCOUT)-wert numerically validated through an extensive comparison with Monte-Carie simulations, see Appendix
Conveniently, the intrinsic linear nature of Equations 7 and g makes it possible to write the system in matrix form. This facilitates the efficient numerical computation of the complexity of TEST(S) by matrix iteration and that of its branching factor as the spectral radius (eigenvalue with highest magnitude) of this matrix. Additionally, we define a global branching factor for the TEST algorithm, corresponding to the complexity of the average TEST, or equivalently, the complexity of the hardest TEST (over all threshold values s): Frast = max, Pres ( (s). Interestingly, against a worst-case distribution 8, (all probability mass concentrated on n) Trest exactly attains the bound of Equation 4 As a consequence, following the conclusions from the analysis of SOLVE in Section 4 the F-gamex are typically harder problems than the games generated under standard model, even for discrete-valued trees. That makes Trest an interesting and easy-to-compute quantity to gauge the difficulty induced by the choice of a distribution μ. We use this property in Section 6 as measure of difficulty: if Frest
5

---

is large (resp. small) the game-trees are considered hard (resp. easy). In the following section, we characterize the average-case complexity of ALPHA-BETA and compare its branching factor to that of TEST.
5.2 Analysis of ALPHA-BETA
Algorithm 3: ALPHABETA(N, h, a. 3), negamax
form
Algorithm description The ALPHA- BETA algorithm improves upon classical full negamax search by pruning branches that cannot influence the root value. It tracks two evolving bounds: a (the worst- case guarantee for the maximizing player) and 3 (the best-case allowance for the minimizing player). As described in Algo- rithm upon a child evaluation, achieved through recursive call with negated pa- rameters a' = -B and 3 = -a, ALPHA- BETA updates the current best value and early terminates whenever it exceeds B. and it potentially updates for next sibling evaluation. While typically invoked with a full-window (a = -0000 3 = +00) to compute the root value z exactly, ALPHA-BETA can also operate with bounded intervals, in this case if is not comprised in [a, 3). it will return certificate value (like TEST) asserting whether z 3 or a A well-known (14) connection to TEST appears with a so-called null-window (a
Input: Current node N, search depth h, lower-bound
a, upper-bound | Output: Value of node N.
if h = then return value
best
foreach N' in N.children do
value +- -ALPHABBEAA h. 1,- -0) best <- max (best, value)
if best 2 then break a - max(ar best)
end return best
s), in this case, ALPHA-BETA becomes functionally equivalent to TEST(s), incurring the same complexity and producing identical certificates.
Complexity analysis We define Ix Th (h, c) the average-case complexity of ALPHA-BETA called with parameters a<3 and using same notations as before. We are interested in (h) = Ex-,, !A." (h)]. the average complexity of ALPHA-BETA called with a full-window, and in Tua- its branching factor. The derivation of this complexity follows closely the one for TEST and yields similar system of recursive equations. For node with value X', where ALPHA-BETA is called with parameters a and B, the main differences with TEST are: (1) the cutoff condition now becomes -X<<,, (2) the recursive calls to ALPHA-BER are made with parameters -3 and -a and (3) unlike TEST, further calls the same level may use an updated value of if the current child has the best value encountered so far. Assuming JAn follows similar definition to that of J
Ta.0., (h,
T- 8, 8.-a ((h b, + (a<B) J. Ja.max(( (h, c C0,
AB
(9)
E
fa.mx xx -.--B--a a(h 11, + 1 ( /5. X'),8 (h)
1)
c
Xaa
2'2-
/ama mx (h, 10] (10)
and 8 (h,
E Ap
1 a 1,6) + --xx
This system of equations resembles Equations 7 and 8 and allows us to run comprehensive numerical simulations, which lead to the remarkable observation that TEST and ALPHA-BETA share the same branching factor. We find that the equality of the branching factor holds theoretically, as indicated in the following theorem (proof in Appendix (A.2):
Theorem 5.1. ALPHA-BETA called with full window (-n,...,,) n. is more efficient than the approach consisting in testing every possible value with the TEST procedure (iee, rEST-RRUTtFORRE) and ALPHA-BETA and TEST share the same asymptotic branching factor, in the precise sense that for h and x E [-
1
(h) S
Σ
TEST (h) and TA
Trnst-
This result shows that there is asymptotic gain of using ALPHA-BETA over a simple TEST-BRUTEFORCE approach, that calls TEST 2n times. Moreover, numerical results, presented in Section suggest that these two algorithms present deeper identical behavior: both for the asymptotic limit and the

---

multiplicative constant characterizing the convergence rate. This result is quite remarkable, since the question answered by ALPHA-BETA BETAA-ettermiinng the precise value of the game-inee intne--iiiiivlly seems to be much harder than the question answered by TEST, that only solves a binary problem. In the next section, we conduct similar average-case analysis of the SCOUT algorithm.
5.3 Analysis of SCOUT
Algorithm 4: SCOUT(N, h, 3)
Input: Current node N, search depth h,
Algorithm description SCOUT incorporates the TEST algorithm into procedure similar to ALPHA-BETA, described in Algorithm 4 Before evaluating any node, SCOUT first per- forms a call to TEST to check whether the child's value strictly exceeds a. Only if this test returns true, indicating potential for im- provement, does SCOUT proceed evaluate the node in full, by a negated recursive call itself, and updates a to the current (higher) value. Like ALPHA-BETA, it is most often called with a oc, but can also be called end return a
lower-bound a, upper-bound /
Output: Value of node N if h O then return N.vauue if 2 3 then return a
foreach N' in N.children do test + TE'T if test > then
-a)
-- -SCOUTNN -,,, -a-
end
if a 2 8 then break
with any value of a and potentially a parame-
ter 3 too (triggering a cutoff whenever a25). At first glance. this approach may appear inefficient: when a TEST returns true, subsequent evaluations revisit some leaf nodes already examined during the threshold check. However, previous experimental results [2 suggest that the waste incurred by SCOUt's reevaluation of some nodes is not substantial. Furthermore, improved variants of sCouT Principal Variation Search (PVS) and NegaScout [10,9] are still used in modern game engines (24). In this work we focus on the original SCOUT algorithm, which has a simpler formal analysis: unlike its improved variants, it does not use the certificate value v but only the boolean outcome 1l 1, of the TEST procedure. We believe that PVS and NegaScout improvements should not change the asymptotic behavior of SCOUT, and we leave their formal analysis for future work.
Complexity analysis Mirroring the ALPHA-BETA analysis, we define scuur(h.e) as the complexity of scoUT conditioned on and a<3 and we are interested in the complexity and branching factor for a full-window [scoUT(h)) Ex mull (-X"-- -n,n1] and Tscour- We can write the following recursive equations:
1 -I--a 1,8 + +1 4acert 12--8,--11 + 1 (x< scour(h. +
1. scouT((e,e)
(11)
Ex-2-r
x-
+ fase 1190
+ +1 1-x scout(h.
j.maalaa X x'),8
scout(b-11))
C
j sccuu((h,c)
Ex
1,1((--1,)) 1|sc /
+ +1 (
x.max(a,-" scoux(h,c-1)
(12)
This defines a system very similar to that of ALPHA-RETA, and extensive numerical studies that conducted suggest that the branching factor of SCOUT coincides with that of TEST and ALPHA-BETA. We state here an analogous result to the
obtained for ALPHA-BETA (proof in Appendix (A.3):
Theorem 5.2. scOUT called with a full window (-n,...,,) n) more efficient than the approach consisting in testing every possible value with the TEST procedure (ie.. TEST-BRUTEFORCE) For h 2 0 and x E (-,,... n):
n
IZ.-nAn (h)
S
Σ
Ie and Tscour S TreST
This result is weaker than Theorem 5.T in the sense that we did not manage to prove that scoUT is asympiotically equivalent to TEST. The missing part is to show that rscour 2 Tusss which is suggested by numerical simulations.
In the next section, we experimentally compare all presented algorithms for deep trees and different parametrizations of the forward model.
'Though this is not standard in the description of sCOUT, it seems that we can freely increment a by one each time a strict test is proven true, because if then jax 1, 3). facilitating formal analysis of SCOUT.
7

---

Finite-depth numerical analysis
uniform
triangular
bimodal-unifarm
probability distributton (x)
node volue
node value
node value
node value
difficulty: easy
difficulty: easy
difficulty:
difficulty: hard
asymptotic branching factor
upper
apper
lowes bound
lower bound
lowar bourd
Jomer bound
250
200 400
400
600
branching degree (b)
branching degree (b)
branching degree (b)
branchiing degree (b)
relative average test
average complexity
tree height (h) TEST-BRUTEFORCE
tree height (h)
tree height (1)
tree height (h)
ALPHA-BEL BETA
TEST-BISECTION
TEST-HARDEST
SCOUT
Figure 2: Finite-depth comparison of average-comen cerrage-ommllxxitiess Each column corresponds to parametriza-
tion of the forward model, consisting in the choice of the distribution μ.. (Top) Probability mass function of μ (Middle) Difficulty of the generated instances induced by the choice of measured as the dependency the branching factor r to the branching degree (Bottom) Relative average-complexity w.r.t. the average performance of the algorithm TEST, this allows to visualize the sub-exponential multiplicative factor as a function of the height h (with = 10, n 5). For each parametrization ALPHA-BETA demonstrates the same convergence rate TEST-BRUTEFORCE Conversely, sCOUT and TEST-BISECTION exhibit faster convergence, and remarkably SCOUT even seems to incur a smaller
multiplicative constant than TEST- HARDEST. In Section we have established that TEST and ALPHAA-ETA shared the same asymptotic branching factor, which also coincides with that of scoUT numerically. To gain more insights into the behavior of these algorithms, and especially better understand their sub-exponential convergence rates, we conduct finite-depth experimental analysis, using the recursive equations derived earlier in this work.
Baselines addition to ALPHA-BETA and SCOUT, we choose to consider two TEST-based basclines: (1) TEST-BRUTEFFORE. which comprehensively applies TEST for every threshold E {-n + 1, 1,... n) and (2) rEST-nISECTION, which uses a binary search approach to reduce the number of TEST trials from (nn) Ollog n.. We also introduce the TEST-HARDEST baseline which corresponds to the most expensive call to TEST across all threshold s values.
Parametrization To best compare the algorithms, design diverse instantiations of the forward model, with different distributions fs. Ideally, we want these parametrizations to cover a wide range of problem difficulty, from the simplest to the hardest case. We suggest that the asymptotic branching factor (common to all algorithms) r can be interpreted as a measure of the intrinsic game's difficulty, We propose an arbitrary and informal way of classifying the difficulty: for given distribution μl, value range and branching degree b, if the branching factor is close to vb (the lower bound) then we classify as easy, similarly it's close to b (the upper bound) we classify it as hard, otherwise we classify it medium. For the specific choice of these distributions we start with a uniform distribution-ag natural choice that maximizes the diversity (entropy) root values. Then, we choose distributions that assign increasing probability mass on positive atoms, because we have found empirically that this leads to produce problems of increased difficulty. The intuition is with value z will draw children in {=I,..., n). thus the larger x, the wider the interval, and the higher
node

---

the diversity of node values in the generated tree. As displayed in the top row of Figure 2 we choose a triangular distribution, a power-law (cubic) distribution and finally dimodal-unifome distribution with more than 1/b mass concentrated on positive atoms (following a criterion similar to that of Theorem
Results We present in Figure 2 the results of the finite-depth average-case complexity comparison. Each column in the figure represents, top to bottom, the probability distribution ju used, the difficulty this choice induces in the generated game-trees and finally the actual performance of the compared algorithms. To best compare the relative performance of algorithms, by that of TEST, computed as an average of all possible values of threshold 8. This allows us to easily distinguish the algorithm transient regimes by focusing on the sub-exponential multiplicative factor and ignoring the mechanical effect of the complexity increasing with the height of the tree, A striking result appears: ALPHA-BETA consistently ends up as the worst algorithm across all evaluation setups as well as for every tree size. Remarkably, it seems to mirror the performance of the naive TEST- BEST-BRUTEFORCE baseline for very deep trees. It may suggest that through recursive calls, the and [ parameters of ALPHA-BETA rapidly reduce to null-window situations where a 8 - 1, and end up comprehensively testing all possible threshold values, thus becoming equivalent to the TEST-BRUTEFORCE approach. This might be a symptom of deeper asymptotic equivalence between ALPHA-BETA and TEST-BRUTEFORCE, which seem to behave identically asymptotically as well as in their sub-exponential constant factor.
divide the average-complextty
Conversely, SCOUT seems to consistently outperform ALPHA-BETA and to achieve the best performance for every game difficulty. Unlike the conclusions drawn in fixed-depth analysis under the standard model [5). supports the practical superiority of scOUT over ALPHA-BETA as hinted in multiple numerical studies [9] 12]. TEST-BISECTION also displays strong performance, we believe this comes from its conceptual similarity to the MTD(f) algorithm, whose practical superiority over ALPHA-BETA have been suggested in the past [16). Interestingly enough, SCOUT seems to even outperform TEST- HARDEST for deeper trees. This result counter-intuitive since SCOUT's cost mostly comes from calls to TEST. This probably suggests that SCOUT behaves like an adaptive version of TEST, which updates the threshold value according to the values encountered, unlike TEST, which has a fixed threshold value, making it more sensitive to worst-case situations.
7 Related works
The average-case analysis of minimax algorithms originated from studying ALPHA-BETA under the standard model with independent leaf values (1 4). where it achieves optimality [8] [ Subsequent algorithms, SCOUT (5). MTD(f) [14] and PVS (sometimes called NegaScout) 110 were proven asymptotically equivalent. Critiques of the standard model highlight its unrealistic independence assumption 2 7. Alternative models introduce ancestor dependencies, e.g., the incremental model maintains a heuristic value at each node, and defines leaf values as the sum of values along the path to the root node. Only limited settings of this formulation of the incremental model have been successfully analyzed [15 and more general analysis is yet to be proven feasible. Prior works also explore the idea of forward tree generation [7,20 20). where values are generated top-down like in our forward model. The closest model to ours is the Prefix Value Game Tree Model (20). it is an instantiation of the incremental model where heuristic values of nodes are computed additively from their parents, and one child is always attributed zero increment, this resembles our forward model where one child inherits the value of the parent. However, to our knowledge, this model has not yet been successfully theoretically analyzed before. Moreover, we are confident that the analysis techniques we developed in this work could be very simply adapted to it.
Another popular approach in modern game solving is Monte- Carlo Tree Search (MCTS) [18] 21), however, a common theoretical everage-complexity analysis under shared framework with minimax- based game-solving algorithms is currently missing. This is explained by technical reasons. MCTS algorithms only offer asymptotic convergence guarantees (vs. deterministic guarantees) and their convergence rate can be doubly-exponential in the size of the tree [19 instead of at most exponential for minimax algorithms. Furthermore, while we believe extending our analysis to an MCTS- based algorithm is possible in principle, it presents formidable technical challenge as the algorithm's states depend on visit counts and empirical rewards at each node, this would make the equations substantially more involved, and we view it as important direction for future research. Finally,

---

although MCTS basee algorithms are Sate-of-the-ann in multiple settings, exact minimax algorithms still remain practically useful in chess engines (24) and hybrid (RL+solving) approaches [22].
Discussion and limitations
Discussion In this work, we introduced the forward model, simple synthetic game model which provably addresses limitations of previous models while retaining some form of analytical tractability, For binary-valued trees, we established closed-form expression for SOLVE's average-complest and branching factor, and showed that the F-games were of adjustable difficulty and could span from maximally easy maximally hard instances. For discrete-valuee valued trees, we characterized the behavior of the TEST, ALPHA-BETA and sCoUT algorithms with equations, allowing a fast and efficient computation of the complexity and asymptotic branching factor, intractable with Monte-Cart simulations. Unlike previous analysis under the standard model, we didn't manage to find closed-form expressions for the branching factors of all studied algorithms and we leave this open for future work. However, we established that TEST and ALPHA-BETA share the same branching factor, and we hypothesize that SCOUT shares it well. This property was numerically confirmed by extensive numerical experiments, which further revealed that ALPHA-BETA incurred a larger sub-exponential factor than other approaches, suggesting that is a poor bascline for practical scenarios.
Limitations Our work focused on discrete-valued trees, which in our opinion best represent real-world games, and are numerically cheaper solve. That being said, the equations we derived for the complexity analysis of TEST, ALPHA-BETT and SCOUT are, with small modifications, applicable to continuous values, opening avenues for an extended analysis that we do not claim that our model accurately represents real- world games dynamics: it suffers from several important limitations that are consequences of its simplicity. First, the model only generates uniform b-ary trees of constant depth, which does not reflect the variable branching degrees and depths found in real games. Extending the analysis to more complex tree structures is direction for future work. Second, the conditional distribution used to generate child values is the same for every node in the tree. depends only on the parent's ' value, not on the broader game state. Furthermore, the method of ensuring the minimax constraint (truncating the distribution) is just one of many possibilities; other, more complex transformations could be valid but may also be harder to analyze. Regarding the choice of algorithms, we focused TEST, SCOUT and ALPHA-BETA, but analysis of MTD(f) and PVS would be an insightful extension, though they may prove more difficult to conduct since they require modeling the distribution of the test certificate value (and not only its binary outcome). However, believe that sCoUT is a good proxy for PVS, and that PVS optimizations should not change asymptotic properties. Similarly, the next threshold using the certificate value of the last iterate-as as in MTD(f)-we select it with simple bisection rule. Of course, this only speculation, which why we believe it's important that PVS and MTD(f) are properly analyzed in the future under the forward model.
F-games. An important disclaimer
think TEST-BISECTION is good proxy for MTD(f) where instead of choosing
Broader impact
While our work focuses on classical deterministic game-solving algorithms, we believe contributes to ongoing discussions at the intersection of learning, planning, and decision-making, Search remains a core ingredient of modern Al systems: top-performing agents such as AlphaZero combine learning with planning. yet the theoretical understanding of deterministic search methods (e.g.. AlphaBeta) remains limited. Our analysis introduces simple average-case model that incorporates structural dependencies in search trees, bridging gap in the theoretical understanding of deterministic solvers. By providing a clearer picture of their expected behavior, our work may help guide the design of hybrid systems that integrate learning and deterministic planning.
10

---

References
[1] Samuel H Fuller, John Gaschnig, JJ Gillogly, et al. Analysis of the alpha-beta pruning algorithm. Department of Computer Science, Carnegie-Melloo University, 1973.
[2] Donald E Knuth and Ronald W Moore. "An analysis of alpha-beta pruning". In: Artificial intelligence 6,4 (1975), pp. 293-326.
[3] Monroe M. Newborn. "The efficiency of the alpha-bene beth--bet search on trees with branch-dependent terminal node scores". In: Artificial Intelligence 8.2 (1977), pp. 137-153.
[4] Gérard M Baudet. "On the branching factor of the alpha-beta pruning algorithm". In: Artificial Intelligence 10.2 (1978), pp. 173-199.
[5] Judea Pearl. "AAsyptootic properties of minimax trees and game-searching procedures". In: Artificial Intelligence 14.2 (1980), pp. 113-138.
[6] Dana S Nau. "An investigation of the causes of pathology in games". In: Artificial Intelligence 19.3 (1982), pp. 257-278.
[7] Dana S. Nau. "The last player theorem". In: Artificial Intelligence 18.1 (1982), pp. 53-65.
0004-3702. DOr: https: / org/ 10 1016 0000 0004 (82) 96010- 8 URl: wwtp::ssciinceee. https://ww..cienceddiii.
[8] Judea Pearl. "The solution for the branching factor of the alpha-beta beta pruning algorithm and its optimality". In: Communications of the ACM 25.8 (1982), pp. 559-564.
[9] Murray S Campbell and T. Anthony Marsland. "A comparison of minimax tree search algorithms". In: Artificial Intelligence 20.4 (1983), pp. 347-367.
[10] Alexander Reinefeld. "An improvement the Scout search algorithm". In: ICGA Journal
6.4 (1983), pp. 4-14.
[11] Michael Tarsi. "Optimal search some game trees". In: Journal of the ACM (JACM) 30.3 (1983), pp. 389-396.
[12] Agata Muszycka and Rajjan Shinghal. "An empirical comparison of pruning strategies in game trees". In: IEFE transactions systems, man, and cybernetics 3 (1985), pp. 389-399.
[13] Michael Saks and Avi Wigderson. "Probabilistic Boolean decision trees and the complexity of evaluating game trees". In: 27th Annual Symposium on Foundations of Computer Science (sfes
1986). IEEE. 1986, pp. 29-38.
[14]
Aske Plaat et al. "A New Paradigm for Minimax Search". In: (1994).
[15] Luc Devroye and Olivier Kamoun. "Random minimax game trees". In: Random Discrete Structures. Springer. 1996, pp. 55-80.
[16] Aske Plaat et al. "Best-first fixed-depth minimax algorithms", In: Artificial Intelligence 87.1-2 (1996), pp. 255-293,
[17] Anton Scheucher and Hermann Kaindl. "Benefits of using multivalued functions for minimax- ing". In: Artificial Intelligence 99.2 (1998), pp. 187-208.
[18] Levente Kocsis and Csaba Szepesvári. "Bandit based monte-carlo planning". In: European conference on machine learning. Springer. 2006, pp. 282-293.
[19] Pierre-Arnaud Coquelin and Rémi Munos. "Bandit algorithms for tree search". In: arXiv preprint cs/0703062 (2007).
[20] Timothy Furtak and Michael Buro. "Minimum Proof Graphs and Fastest-Cut-First Search Heuristics." In: IJCAI. Vol. 9. 2009, pp. pp. 492-498.
[21] Sylvain Delattre and Nicolas Fournier. "On Monte-Carlo tree search for deterministic games with alternate moves and complete information". In: ESAIM: Probability and Statistics 23 (2019), pp. 176-216.
[22] Quentin Cohen-Solal and Tristan Cazenave. "Minimax strikes back".. In: arXiv preprint arXiv:2012. 10700 (2020).
[23] Laurent Orseau and Remi Munos. "Supee-exponential regret for UCT, AlphaGo and variants".
In: arXiv preprint Stl::2405.04400 (2024).
[24] The Stockfish developers. Stockfish. URL: http://pp///iiiio..ooooffiaaaaaa

---

A Proof material
In this section we provide detailed proofs for the results established in the paper, that were not included in the main text due to space and readability constraints.
A.1 Proof of Theorem 4.1
We first recall the result:
Theorem 4.1 For b E N for all q E
[0, b. the branching factor of sOLVE satisfies Tsouve = O(b).
Proof. Recall that
1+ (b k 1)g k(1 kt
t(g,
By analyzing the sign of 0t (q. b) and showing it's non-positive for E [0, 1] we can establish that / is monotonically decreasing in g on [0, 1]. Then, we only have show that io t(q 1/b, b) (b)).
By
for the result to be true for g E [0, T.l First we separate positive and negative sums:
+
(b - 1) k(1
)
(13)
b
k=1
2 b-1
6-1 kkk + 1)( - ),
k(1
(14)
6
k=1
By expanding both sums (with geometrical sum expansions) and using the fact that:
(1 (1-b)) 1 1-1)0=c= ---
- o()),
(15)
we can show that:
1 )== -2
k(1
(2-4e-1 -4c-116 o(b)
(16)
and
k(k + 1)(1 - - = -2-5--
55 be= 1 o(b),
(17)
02
allowing conclude that e 1b o(b) = O(b). This terminates the proof. As side note, if consider instead q for 1, show that - + o(b), which is slightly higher than -16 (because - 0.37 +) and asymptotically reaches the same constant in Equation 4
A.2 Proof of Theorem 5.1
We start by proving an intermediate property, useful for proving Theorem 5.1
Propesition A.1. Evaluating ALPHA-BETA with given window is always more efficient than splitting this window into two sub-windows and evaluating these sub-windows separately.
For h 2 0 and x E [-n,n], n), for all a, 3 N. such that < B and for all E N such that
a < 7 < 8:
1 (h) < 12.0. (h) 12. (h))
Proof. Let's recall the expression of the complexity of ALPHAA-ETA 1 I.... (h, and it's auxiliary function J 8 (h, c):
3 (h) = -- 1.0-AA-a/0 -a 1,b) + (a<0) Juh 22) (0, c- Au
(18)
X' 8.-0 ( (h- 1,b) + 11 x p2 maxia -X) (h,
X 2"2-x
12

---

E
ah 1,6) (-xx I. max -X), (h, ch, (19)
X'2 X'2-x
We conduct the proof for the function and J altogether, i.e. we want to prove that for a < < and all integers h, e we have:
p...3 (h, c) 2 _u (h, c) + 12.9,0 (h, c) (h,c) c) - J (h. c) + n (h,
and
J 2,,
Let's proceed by double induction on the integers h and c.
Base cases for all h, 1 (h, 0) 0 and 1 (h, 0) + I Th (0, (0, hold.
(h, 0) = 0. Similarly for all >> 0, and T (0, c) + T (0, c) 2. It follows identically for J. So the base cases
Induction step now we assume that the property holds for (h, 1) and (h 1h-10 1, We'll detail here the induction step for the function J. as it is less cumbersome to write, but the proof for / follows the exact same steps. First, let's remark that the expectation involves sum of terms, and let's try to prove the inequality holds term by term. Let X' 2 -z, first if (xX)) = 0, the inequality holds trivially, so we consider without loss of generality p(X') >> O. Let's define:
I (h b, 1 (-x max x²) x')x0'',, ch, ch 1)
and
B
X .7 (h - b) + (-X' Ju ma.aaxaa - X'), (h, c 1)+ Al
1x-- 1,6) (, max(m X'),0 (h, c 1)
1
and show that A B.
Case I < XX, then - 1-x<<> = 0, the property then holds using the induction hypothesis for (h 1,
Case 2 Now, ? < -X' B, (-x(c() and (-x'x>) 0. Moreover, max(y,
-X' and max(a, XX) -X' So:
A TX -B, (h b, J
X',8 .8 (hhc-1
and
B= 1 (h- 1, b) + 1xx - (h- 1, b) + J.
1or,-X',l X' (h, ch, 1).
The inequality also directly holds using the induction hypothesis for (h L,
Case 3 Now, if a < XX" < 1 (-x<0) = 1 and 1 [-x's7 1. Moreover, max(7, and max(a, -X') = -X'. So:
A =
X -8.00 - 1,b) + Jz. x',3 10, c 1)
-
AB
and
B = - b) J .8 (h, 1) rx -3.-7 b, JB.Y (h, c 1).
Here again, the inequality holds by induction hypothesis on (h, b) and using the fact j2 3 (h, - 1) is non-negative.
Case 4
Finally, if X' a. we obtain:
A J. -..--B.-- B. 1,b)-11))-11 J=.a, (h, 1)
and
= X 1-- 1,b) + a (h,c- c) xxx - 3, (h - b,,b + p (h, 1).
Here the inequality holds using both the induction steps at (h- 1, 1) and (h, c 1). We have covered all possible values of X', so the proof is concluded.
Now we recall the theorem of interest:
13

---

Theorem 5.1
ALPHA--BTA BETA called with full window {-n....,? n is more efficient than the approach
consisting testing every possible value with the TEST procedure (i.e.. BEST-BRUTEFORCE) and ALPHA-BETA and TEST share the same asymptotic branching factor, in the precise sense that for h 2 0 and x E (-
1s R. (b)
Σ
FEST (h)
and
Tan
TTeST-
Proof. The first part of the theorem obtained by iteratively applying Proposition A. with & = -n and 3 n and choosing 7 -n then ? -n 2 and on, until The second part can be deducted by remarking that we have:
max 1 TEST (h) - A -.. (h)()))))))))))))))())
Σ
FEST (b) S 2n max TEST (h).
The left-hand-side inequality reflects the fact that a smaller a-8 window results in evaluating strictly less nodes note that this doesn't hold for SCOUT, due to non- non-monotonicity of TEST'S complexity with respect to the threshold value 8. By taking power 1/h on both sides and taking the limit +00 this gives us the desired result.
A.3 Proof of Theorem
We first recall the result:
Theorem 5.2 scour called with full window (-n,...,,) is more efficient than the approach consisting in testing every possible value with the TEST procedure (i.e., TEST-BRUTEFORCE) For 2 O and x E (-n,...,..
12.-B. (h) S
1 (h)
and Tscoor S Test
Proof. The proof very similar to that of Proposition A.1 in particular it relies on the same type of induction, so we only detail here the induction step for the function JsCOuT-
We assume that
TZ,-TA SCOUT
(h)
F (l))
and
n
Jz.-n.y n., (h) S
Just (h).
SCOUT
== n+
We recall the expression for JscouTi
scour((h.)) -xx2-a
-- 1,8)
+ L [as-
X', - 18--8----- scourth- 1,b) sc0oth
1 I p.maa(a -x0 x'
(20)
A little subtlety that was not explicit in Equations 11 and 12 is that for the special case B Algoorihm instantly, incurring a cost As a consequence when called with Algorithm terminates
and f = s, sCoUT is equivalent to call to TEST(S), since scout(k--1.) loss of generality,
- X ScouT(h-111) 0. Without as the desired inequality is clearly for
consider in the following a = 3 1. Let's show the inequality holds term by term for every value of X'. We define:
x x' (E 1,b) + (ac-x') xx 1. + 1l 11( Ja x.mxx(a,-X'). scour(h-1,))
soouT(h,c-1)
and
B
xi-+11 usi(h--1
Σ (as
s=0+1
#=a+1
Let's show that A <. B in all cases.
14

---

Case 1f -XX, then 1 (a = and ( (-xie 0. So:
1x
Test(h-11,b 1,8) + 11',--.----
Ac
and
B= Σ
+ Σ (
Σ
- fEsm(A-1,b))
1,66
smat1
smat1
s
By induction hypothesis on (h 1, and variable change
+ 1, we can write:
A S - (1,b)
Σ
x (15)(1-116) 1.6)
-a 1,8) + Σ
x x 133T(A-1,b)
X' Σ
S B.
1est(h-11b)
S=-++1
So the inequality holds in this case.
Case 2 If <
< B, then 1l (ac-x1) = 1 and 1 (-xia) = and max(a, -X') = - Ix ,x',=a aa
and B become: and
nsr(h 1,bb) + + -8 + J
s0007(h-11,b
scour(h.e-1)
B Σ
X 11,7(
Σ (-
For the term in (h 1, b) it's same as in Case For the terms in (h 1), we remark that
s=0+1
s=otl
Σ
J
Σ
J us-(h.c-1)
ns1(h
==++1
8= X'+1
By induction hypothesis on (h, c- 1), with -XX, we have:
j X
Σ
scor((h,
mss((h.--1) 1)'
== X1+1
So the inequality holds term by term for this case.
Case
If -X-Xs < a, we have then:
A 1xX'=a nsr(h--1 1,6) scmm((,,c-))
+ J=.-X',
and
8
B =
Σ
x x
Σ [
Test(h- 1,6)
s=a+1
s=a+t1
By reusing arguments from the two previous cases, we can see easily that this case holds as well, thus concluding the proof.
15

---

B Monte-Carlo Simulations
In this section we provide results of Monte-Carie simulations, experimentally validating the equations characterizing the different algorithms in the paper. All experiments here, and in the main text, were run in couple of hours of CPU time on consumer-grade laptop.
In Figure 3 5] we represent the evolution of the Monte-Carlo mean estimator of the TEST, SCOUT and ALPHA-BETA complexities, respectively. The Monte-Carlo estimator represented function of the number trials, for different settings of distribution branching degree b, value range n and tree height h. In every scenario, the Monte-Carlo estimator converges the oracle computed using equations derived in Section 5 The settings were chosen to showcase a high diversity of parameters, reasonable. Results are averaged over 5 independent random seeds. Shaded areas represent bootstrapped 95% confidence interval.
while maintaining the computational
#=uniform
μ=uniform n=1, b=2, h=3
#=uniform n=2, b=3, h=3
u=uniform n=2, b= h=3
u=uniformm n= b=5, h=3
uuumiform n= b=5, h=d
Average-case complexity
n=1, b=2, h=2
15.6
2.40
3.15
7.00
60
20.0
2.32
6.75 15.0
3,00
14.4
μ=trianguulrr n=1, b=2, h=2
u-ttrinnuular n=1, b=2, h=3
u=triangular n=2, b=3, h=3
j=trianguulrr n=2, b= h=3
petriangular n= b=5, h=3
p=triangular
n=5, b=5, h=4
Everage-case complexity
8.1
24,8
3.45
77.5
2.5
19.2
24.0
3.30
18.4
72.5
7.5
μи=power bm2, h=2
μ=рower n=1, hm3
μ=рowee bm3,
μ==ower n=2, hm3
μ=powed b=5,
μ=power
b=5, hm4
Average-case complexity
2.7
28
3,90
31.5
2.6
27
3,75
104
9.2
2.5
30.0
100
u-bi-uniform 1=1. b=2, h=2
j=biiunnform n=1, b=2, h=3
u=bi-unlform n=2, b=3, h=3
u=bi-uniform n=2, b=5, h=3
u=bi-unlform n=5, b=5, h=3
p=bl-unttom
Average-car complexity
n=5, b=5, h=4
30
2.40
8.1
29
7.8
28
2.24
0
5000
5000 Monte-Cario trials
5000
5000 Monte-Carlo trials Monte-Cario trials
5000
5000
Monte-Carle trials
Monte-Cario trials
Monte-Cario
MC estimate
Forward model oracle
Figure 3: Evolution of the Monte-Carlo mean estimator of the TEST complexity, as a function of the number of trials, for different settings. Results are averaged over 5 independent random seeds and shaded areas represent bootstrapped 95% confidence interval. The oracle is computed using Equations and
16

---

#=uniform n=1, b=2, h=2
u=uniform n=1, b=2, h=3
#=uniform n=2, b=3, h=3
u=uniform n=2, b=S, h=3
y=uniform n=5, b=5, h=3
u=uniform n=s, b=S, h=4
Average complexity
162
3.30
56
156
3.15
15.0
54
y=triangular n-1, b-2, h-2
u=triangular n-1, b-2, h-3
p=triangular n-2, b-3, h-3
u-triangular n-2, b- h-3
petriangular n-5, b-5, h-3
u=triangular n b- h-4
Average complexity
54
3.45
6.0
16.8
62.5
52
5.8
3.30
16.2
184
μ=роwe n=1, b=2, h=2
μ=рowee
μ=рower n=2, b=3, h=3
μ=роwee n=2, b= h=3
μ=powwer n= b=5, h=3
μ==owwe n=5, b=5, h=4
n=1, b=2, h=3
Average-Caa complexity
18.0
70.0
17.4
6.00
60.0
67.5
724
jr-bi-uniform n=1, b=2, h=2
bi-uiunnfoomm n=1, b=2, h=3
u-bii-unfform n=2, b= h=3
g=bii-unforrm n=2, b=5, h=3
bi-uniforrm n= b=5, h=3
j--bi-uffform
n= b=5, h=4
Average: complexity
16.8
58
208
16.2
56
65.0
3.15
200
62.5
0
5000
5000
5000
5000
5000
5000
Monte-Carte Care--Caloo trials
Monte-Carto trials
Monte-Carie trials
Monte-Carto trials
Monte-Cal Conte-Carlo trials
Monte-Carlo trials
MC estimate
Forward model oracle
Figure 4: Evolution of the Monte-Carle mean estimator of the ALPHA-BETA complexity, function of the number of trials, for different settings. Results are averaged over independent random seeds and shaded areas represent bootstrapped 95% confidence interval. The oracle is computed using Equations and 10
17

---

u=unnform b=2,
p=uniform n=1, b=2, h=3
Aeunfform n=2, h=3
u=uniform n=2, b=5,
uzuniform n=5, b=5, h=3
u=unfform n=5, h=4
Average complexity
24.0
224
4.6
23.2
216
4.4
7.00
54
75
22.4
208
g=triangular b-2, h-2
u=triangular n=1, b=2, h-3
u=triangular n=2, b-3, h=3
u=triangular b=5, h=3
u=trianguular b= h=3
Ir gatriangular n= b= h=4
Average case complexity
4.8
7.75
67
62.5
84
250
7.25
24
61
240
μ=рowee n=1, b=2, h=2
μ=power n=1, b=2, h=3
μ=powwe n=2, b=3, h=3
μ=рowee n=2, b=5, h=3
μ=powwe n=5, b=5, h=3
ы=рowee
Average complexity
n=5, b=5, h=4
5.0
315
75.0
8.1
96
4.8
72.5
300
26
92
70.0
4.6
j--bi-uniform n=1, b-2, h=2
bi-bi-unforrm n=1, b=2, h=3
j--bi-unfform n=2, b-3, h-3
j-bii-unfoorm n=2, b=5, h-3
μ/ bi-uniform n=5, b=5, h=3
I bi-uniforrm
n b= h=4
Average case complexity
4.6
7.25
70.0
290
280
7.00
24
5000
5000
5000
5000
5000
5000
Monte-Cart Carlo trials Monte-Carlo trials
Monte-Carlo trials
Monte-Cate trials
Monte-Carlo trials Monte-Carlo trials
MC estimate
Forward model oracle
Figure 5: Evolution of the Monte-Carlo mean estimator of the sCOUT complexity, as a function of the number of trials, for different settings. Results averaged over 5 independent random seeds and shaded areas represent bootstrapped 95% confidence interval. The oracle is computed using
Equations II and [2
18

---

C Derivation details for the SOLVE analysis
Algorithm 5: SOLVE(N, binary-valued tree
Input: Current node N, search depth
Output: Value of node N. then return N. value
best 0
foreach N' in N.children do value 1 SOLVE(N', h 1) best < max(best, value)
if best = 1 then break
end
return best
In the following, we provide additional details for the analysis of the SoLVE algorithm.
We analyze the average-case complexity (h) of soLvE depth-h tree generated by the forward model where μl ((4) (Bernoulli distribution with q the probability of drawing a 0). Clearly, souve (h) Ex x-= vo (h) where Sorve (h) denotes the complexity of SOLVE, but conditioned on
the evaluated node value x E {0, 1]. By capturing in equations the execution flow described in Algorithm [ for every encountered case, can characterize the dynamies of SOLVE. If all children values x/s are 1. In this case SOIVE will recursively evaluate all children:
(h) bl (h 1).
(21)
Now, if x 1, at least one child x will hold the value 0, and whenever solve finds it, it will terminate early. Hence, SOLVE will incur the cost of evaluating this x 0 child plus the expected number of failed trials needed to find it, multiplied by the cost of evaluating a x = child:
I J (h) - (h- 1) t(q. I
1),
(22)
where l(g, b) is the expected number of trials before finding child with value O. Note that can write these equations because by design, the distribution is independent from the height h (given the knowledge of the value r). Under the forward model, can derived by compounding the individual probabilities of finding child with value O on the first (b - 1) trials, leading to the expression in Equation 5
1+ (b - 1)g k(1 - -)**
t(g, b)
Σ k=1
b
Equations 21 and 22 together define recursive linear system, with initial conditions Ie (0) (a tree with only one node always incurs cost of 1). Luckily, closed-for solution for I (h) can be derived, first we define:
t(q. b) + Vtlg. 6)2 4b
F1,2
(23)
allowing us to write:
SSOEE (h) q Art (1- A)rá) + b(1 /) (Arr + (1-- (-))rr -
(Arrt1+(11
(24)
where A E [0, 1] is defined
1 1 b/g
2 Vt(g, 6)2 4b
Clearly the branching factor is determined by the larger of and hence the expression in Equation
7 Sorve =r b( /t/g, 8)2 4b
2
19

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction accurately describe the paper's is main contributions: the critique of the standard model, the proposal of the forward model, the derivation of recursive complexity equations for specific algorithms under this model, and the key finding regarding differing finite-depth performance despite similar asymptotic branching factors. The scope (analysis of classical deterministic game solvers) is also clearly stated.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The discussion section explicitly discusses limitations. including the lack of closed-form expressions for branching factors for all algorithms, the focus on specific classical algorithms (AlphaBeta, Scout, Test) while leaving others like MTD(ff and PVS for future work, and the current focus on discrete-valued trees.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
20

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The paper states its main theoretical results and indicates that proofs provided in the appendix. The core derivations of complexity recurrences proceed from the definition of the forward model and the algorithms. Key assumptions about the model (uniform special child selection, fixed distribution μ)) are stated. Theorems and formulas are numbered and referenced.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
The main "experimental" results numerical computations based the derived theoretical recurrence relations. The paper provides these equations, describes the method for solving them (matrix iteration, spectral radius), specifies the parameters used, and describes/plots the distributions used in the figures. Additionally, code is included in the supplementary material.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, if the contribution
specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g.. in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility. which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution primarily new model architecture, the paper should describe the architecture clearly and fully.
21

---

(c) If the contribution is a new model (e.g., large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited some way (e.g., to registered users), but it should be possible for other researchers to have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Python code included in the supplementary material. No external data is used.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.c/)
jublicc/guides/Cddettbmti wwwillmmsssioPPaaa ssionPolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results, See the NeurIPS code and data submission guidelines htte://odSemiiissiooooooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer:
[Yes]
Justification:
All parameters and settings are described.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
22

---

The main results in Figure are exact calculations of expected values from the theoretical model, not empirical results subject sampling variance. Therefore, statistical error bars are not applicable to these central findings. For the Monte-Carlo simulations in the Appendix number of seeds and confidence intervals are included. Guidelines:
Justification:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question: each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer:
[Yes]
Justification: Compute resources are provided in Appendix B
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics htttss///eeerrssssccoallllcccccl
Answer: [Yes]
Justification:
The research involves theoretical modeling and algorithmic analysis. It does involve human subjects, sensitive data, or direct applications with obvious ethical concerns related to fairness, privacy, or potential misuse outlined in the Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
23

---

The authors should make sure to preserve anonymity (e.g., if there is a special consideration due laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper focuses on foundational theoretical analysis of algorithms and does not include discussion of potential broader societal impacts. The work is not directly tied to specific applications where such impacts would be immediate.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not release data or models that pose a high risk for misuse. The released asset is code for theoretical analysis.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
24

---

Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssii thcooee com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Ye]]
Justification: The paper introduces new code for complexity calculations, included in supplementary material and released upon acceptance. The code is concise and documented.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification:
The research does not involve crowdsourcing human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
25

---

Question: Does the puper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The research does not involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer[[NA]
Justification: LLMs only used for proofreading and editing purposes.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy htcpss///eerrsssscccooofferrrers for what should or should not be described.
26


Reviews:
[{"review_id": "cjn58lthgz", "reviewer": "Reviewer_aS2E", "summary": "This paper critiques standard analyses of game-solving algorithms that assume game-tree leaf values are independent, arguing that this simplification makes problems unrealistically easy. To address this, the authors introduce a new probabilistic model that enforces ancestor dependency, better capturing the structure of real-world games while remaining analytically tractable. Using this model, they derive average-case complexity formulae for classical algorithms like AlphaBeta and Scout, enabling rigorous comparisons, even on deep trees where simulations fail.\n\nTheir key finding is that although all algorithms share the same asymptotic branching factor, finite-depth analysis reveals major differences: AlphaBeta suffers from a large multiplicative constant, slowing it down compared to alternatives like Scout. This suggests that prior claims of universal optimality were artifacts of an oversimplified model, and that more realistic frameworks are crucial for meaningful algorithm evaluation.", "questions": "54: Real-world games, from chess to Go, exhibit intricate dependencies between positions: the value of a leaf is inherently tied to the sequence of moves leading to it.\n\nI'm not sure I follow this criticism, and it's not clear to me what independence means here. \nIt seems to me that in games like chess and go, it doesn't matter how a position is reached, once we are there, we are there. So in that sense, the value of a leaf is not a function of the sequence of operations that were used to reach it. \nAre you referring to independence in a statistical sense? It seems later that you want to propose sampling in a way that the destination leaf depends on some structure higher up in the tree. This seems totally reasonable, but the term “independence” is still quite confusing to me. Exactly which sense did you mean? I suppose it would help me to clarify whether we are talking about mathematical or functional independence of a quantity on another quantity, as opposed to independence of random variables.", "limitations": "One of the big claims is that for games with $n$ distinct utility values, alpha-beta search has a factor $O(n)$ overhead as compared to scout.\n\nSpecifically,\n70: “However, finite-depth analysis, in Section 6, reveals critical practical differences masked by asymptotics. Specifically, alpha-beta incurs a multiplicative constant proportional to the game’s value range, causing significant slowdowns compared to other algorithms like scout.”\n\nThis makes it seem like a theorem is proved that shows that, in some sense, alpha-beta is less efficient than scout. Perhaps it's difficult, because we have to consider the asymptotics of multiple variables (depth and range), but I would like to see this theorem formally shown, rather than just plots and empirical results.\n\n\nThe discussion of a game's “value range”, beginning on line 72, is quite confusing, and notation seems to change between discrete {-n, …, n} and continuous [-n, n]. \n\nFrom the name, it sounds like we are talking about the difference between maximum and minimum value, which would be perfectly fine with continuous value sets. But then, on line 149, you use a discrete value range of 2n + 1 elements. If it’s inherently about discreteness, I’d use terms like “cardinality” or “size” instead of range. So far, this is section 5 rather than section 6, but section 5 doesn't yet distinguish between alpha-beta and scout.\n\n\n\nThen in section 6, e.g., on line 314, we are no longer in the discrete world, as we sample continuous random variables. It seems like there is some discretization happening here in the test brute force and test by section algorithms, but it's not clear that alpha beta or scout are also being discretized. \n\nIt seems to me like with this discretization, these are actually approximation algorithms, and you implicitly set the approximation parameter to one. Is this the case? Are you identifying $n/\\epsilon$ overhead? I'm reading a lot into the paper here, it would be very helpful if this were made explicit.\n\nTheorem 5.1 also seems to mix continuous and discrete notation.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "This paper re-examines how deterministic two-player zero-sum games, represented as uniform min/max trees, are used to evaluate game-solving algorithms. The authors introduce the forward model, which builds trees level-by-level using conditional distributions that preserve ancestor dependency. This better reflects the strategic coherence and the structural dependencies found in real games, and allows difficulty to be tuned.\n\n\nThis seems intuitive, but it is not always clear exactly how this model results in more realistic games. This is somewhat subjective, and more examples would help.\n\nA big positive is that, using this model, they derive recursive formulas for the average-case complexity of algorithms like AlphaBeta and Scout. These formulas offer both asymptotic insight and tractable simulation of deep trees (up to height ~5000), unlike expensive Monte Carlo methods. However, I'd like more precise theoretical characterization, ideally in terms of distribution properties and abstract characterizations of games under their model, rather than empirical plots of limited ranges with specific distributions.", "was_revised": true, "final_justification": "They definitely answered most of my questions, which I appreciate, but their clarifications don't really make me too much more excited about the paper. I don't dislike the paper, but I do feel like it's a bit thin on results, and in particular, I'm disappointed they couldn't use their framework to theoretically characterize the difference between alpha beta and scout.", "rebuttal": "We thank the reviewer for the thoughtful comments and valuable suggestions, which helped us clarify and improve the presentation of our work.\n\n**On the realism of the forward model**\n\n> “This seems intuitive, but it is not always clear exactly how this model results in more realistic games. This is somewhat subjective, and more examples would help.”\n\nWe appreciate this feedback. To clarify, our intent was not to claim that the forward model generates realistic games in an **absolute sense**, but rather that it generates instances that are richer and more challenging than those produced by the *standard model*. The standard model, as we discuss, exhibits several *pathological* simplifications: (1) root values are deterministic in almost all cases, (2) all algorithms solve these instances in globally optimal time outside of the critical case, and (3) even in the critical case, the games remain not maximally hard.\n\nIn contrast, the *forward model* introduces controllable randomness and structure by design. Specifically, root values become genuinely stochastic (tuned by the input distribution $\\mu$), and we are able to span the **full difficulty spectrum**, from trivial to maximally hard games. Given that this terminology (“more realistic”) caused confusion among reviewers, we revised the manuscript to replace it with “richer” in the relevant instances.\n\n\n**On obtaining more precise characterization of the complexity of the different algorithms**\n\n> “However, I'd like more precise theoretical characterization, ideally in terms of distribution properties and abstract characterizations of games under their model, rather than empirical plots of limited ranges with specific distributions.”\n\nWe fully agree with the reviewer that deeper theoretical characterization would be valuable. In the binary-valued setting, we were indeed able to obtain a **closed-form** expression for average-case complexity and branching factor (see Section 4 and Appendix C). However, for more general discrete-valued trees, such closed-form solutions remain out of reach for us.\n\nNevertheless, we provide a characterization of the branching factor $r$ as the **spectral radius** of a matrix associated with our recursive system (see Section 5). While this does not yield a closed-form expression for arbitrary $\\mu$, it allows efficient and precise numerical evaluation over extremely deep trees, far beyond what Monte Carlo methods can achieve.\n\nTo give an idea of why it may be harder to obtain a closed form in the forward model than in the standard model, we point out that in the standard model the branching factor **can only take two values**. Regardless of the exact distribution $\\mu$, what only matters is whether $\\mu$ is critical or not. In our model, and it is very clear in the binary-valued case, the branching factor depends continuously on the distribution (Section 4, Equation 5), so it can take an **infinite number of values** between theoretical lower and upper bounds. \n\n\n**On the independence of leaf values.**\n\n> “I'm not sure I follow this criticism, and it's not clear to me what independence means here. It seems to me that in games like chess and go, it doesn't matter how a position is reached, once we are there, we are there.”\n\nYes, we are referring specifically to **statistical** independence of leaf values, as assumed in the standard model. The critique is not that the value of a state depends on the path in a functional sense (e.g., due to move repetition), but rather that in real games, the distribution of terminal outcomes in a subtree is strongly shaped by the position from which it originates.\n\nFor instance, in chess, if a player is a queen up in a given position, we expect the downstream leaves to overwhelmingly favor that player (see [1] and [2] for similar examples). This reflects a statistical correlation between the position and the outcomes that follow from it. The standard model breaks this structure by assuming independent sampling at the leaves, leading to unrealistic and overly uniform game trees. Our forward model aims to reintroduce this type of correlation, while remaining simple enough to allow a **tractable analysis**.\n\n\n**On the confusion of discrete vs continuous variables.**\n\n> “The discussion of a game's “value range”, beginning on line 72, is quite confusing, and notation seems to change between discrete {-n, …, n} and continuous [-n, n].”\n\nWe thank the reviewer for pointing this out. All occurrences of “[-n, n]” were indeed **typographical errors**; our model and experiments use only discrete values from the set {-n, ..., n}. These have now been corrected throughout the manuscript.\n\nWe chose to work in the discrete setting primarily for clarity and analytical tractability. As noted in response to *Reviewer cYDt*, extending the model to continuous values is conceptually straightforward (replacing sums with integrals in the recursive equations), but significantly complicates formal results like Theorem 5.1. Furthermore, most classical games of interest (e.g., chess, Go) have discrete outcomes, justifying this choice for the scope of our study.\n\nRegarding the approximation concern: the algorithms we study (AlphaBeta, Scout, etc.) are not approximating the value of the game. The discretization is not an approximation artifact but rather an inherent property of the value space used in our experiments.\n\n**References**\n\n[1] Nau, D. S. (1982). An investigation of the causes of pathology in games. Artificial Intelligence, 19(3), 257-278.\n\n[2] Knuth, D. E., & Moore, R. W. (1975). An analysis of alpha-beta pruning. Artificial intelligence, 6(4), 293-326."}, {"review_id": "JJuWdzOaIt", "reviewer": "Reviewer_j2Zu", "summary": "This paper introduces a new method for constructing a virtual game tree and compares the standard Alpha–Beta algorithm with several alternatives, including SCOUT. The results confirm the empirically observed advantage of SCOUT over Alpha–Beta.", "questions": "I raised a question in the weaknesses section (second bullet). Could you please clarify this point so I can better understand your analysis?", "limitations": "Simply listing MTD(f) and PVS in the checklist is insufficient; a full discussion should be in the main text of the paper.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The proposed \"forward model\" seems new.\n\nWeaknesses:\n- Lack of novelty. It has long been established that algorithms more efficient than Alpha–Beta exist—most notably MTD(f)—and that SCOUT generally outperforms the standard Alpha–Beta search. Demonstrating this well-known result again does not, by itself, constitute a new contribution.\n\n- Unclear analysis in Section 5.1 (lines 178–180). The manuscript states:\n\n> “… but under the assumption that the special child—which inherits the root’s value owing to the negamax formulation—has already been identified.”\n\nI do not see how the **special child** can be identified **during** the search.\nWhat exactly is being assumed in the subsequent analysis? For example, does the study first run a complete search to discover which move is the special child, and then use that information to analyse node counts? Please clarify the procedure and the underlying assumptions.\n\n- Missing citations on forward-model tree generation. The paper does not reference earlier work that generates non-pathological game trees using techniques closely related to the forward model. A well-known example is the P-game described by Stephen J. J. Smith and Dana S. Nau, “An Analysis of Forward Pruning,” AAAI 1994. The same approach is also employed in Levente Kocsis and Csaba Szepesvári, “Bandit-Based Monte-Carlo Planning,” ECML 2006. Moreover, if the edge costs to child nodes are constrained to be non-positive, with the edge to the optimal move set to zero, the analysis becomes much simpler—a common trick whose original source, however, appears undocumented.", "was_revised": true, "final_justification": "I have raised my score based on the authors' rebuttal. My primary concerns about the paper's contribution and novelty have been addressed, as the authors have agreed to incorporate the suggested citations. Their response also cleared up some of my own misunderstandings.", "rebuttal": "We thank the reviewer for the review and the opportunity to clarify and expand on several points.\n\n**On the summary**\n>“This paper introduces a new method for constructing a virtual game tree and compares the standard Alpha–Beta algorithm with several alternatives, including SCOUT. The results confirm the empirically observed advantage of SCOUT over Alpha–Beta.”\n\nWe believe that this summary doesn't fully capture the scope of our work. Our primary contributions are:\n1. The introduction of a probabilistic **forward model** for generating random game trees that are richer and less pathological than those generated by the standard model commonly studied in the literature.\n2. A formal, average-case complexity analysis of Solve, AlphaBeta, Scout, and Test algorithms **under this new model**. This involves deriving novel recursive equations, a closed-form for Solve and establishing a formal characterization of the branching factor for the other algorithms.\n3. A numerical study on deep, finite trees generated under our model. Our analysis reveals that Scout consistently outperforms AlphaBeta across various game difficulties. This result, under a richer game generation model, is novel. To our knowledge, prior comparisons were limited to specific game instances or conducted under the standard model, which often produces degenerate trees.\n\n**On the lack of novelty**\n\n>“Lack of novelty. It has long been established that algorithms more efficient than Alpha–Beta exist—most notably MTD(f)—and that SCOUT generally outperforms the standard Alpha–Beta search. Demonstrating this well-known result again does not, by itself, constitute a new contribution.”\n\nWe respectfully disagree that demonstrating this result is the sole contribution of our paper. As outlined above, our main contribution is the theoretical analysis of these algorithms under a new, richer game generation model. The conclusion that Scout outperforms Alpha-Beta is a *consequence* of this deeper analysis, not its starting premise. While it is true that Scout and other algorithms have long been known to outperform AlphaBeta in certain cases, the analyses supporting this were generally either small-scale and empirical, or restricted to the standard model, whose limitations we critique in the paper.\n\n**On the “unclear analysis”**\n\n>Unclear analysis in Section 5.1 (lines 178–180). The manuscript states:\n“… but under the assumption that the special child—which inherits the root’s value owing to the negamax formulation—has already been identified.”\nI do not see how the special child can be identified during the search. What exactly is being assumed in the subsequent analysis? For example, does the study first run a complete search to discover which move is the special child, and then use that information to analyze node counts? Please clarify the procedure and the underlying assumptions.\n\nThere seems to be a misunderstanding here. None of the algorithms **ever** have access to intermediate node values prior to computing them from leaves: **algorithms only have access to leaf values**. The assumption mentioned is made purely for the purpose of the theoretical analysis, not as a feature of the algorithm. To derive the recursive equations for average-case complexity, we partition the analysis based on possible **probabilistic events**. We analyze the complexity conditioned on whether the \"special child\" (i.e., the one that will determine the parent's value) is the first one explored, the second one, and so on. By considering all possibilities and leveraging the properties of our forward model, we can formulate a recursive relationship for the expected number of nodes visited. This is a standard technique in the probabilistic analysis of algorithms.\n\n**On the “missing citations”**\n\n> Missing citations on forward-model tree generation. The paper does not reference earlier work that generates non-pathological game trees using techniques closely related to the forward model. A well-known example is the P-game described by Stephen J. J. Smith and Dana S. Nau, “An Analysis of Forward Pruning,” AAAI 1994. \n\nWe believe there is a misunderstanding here. The P-game mentioned in Smith and Nau (1994) refers to the so-called **Pearl game** (named after Judea Pearl, see [1] for instance), which is exactly what we call the *standard model* throughout our paper. This model, based on i.i.d. leaf values, is indeed discussed extensively is the main text, and we chose to cite the relevant foundational work (including Pearl [2], and earlier work by Knuth & Moore [3] or Fuller [4]).\n\n> The same approach is also employed in Levente Kocsis and Csaba Szepesvári, Bandit-Based Monte-Carlo Planning,” ECML 2006.\n\nRegarding the Kocsis and Szepesvári (2006) paper, while the authors mention using P-games for evaluation, their description of reward calculation (\"summing up the values along the path\") is closer to what is sometimes called the incremental or N-game model, where values are assigned to edges and aggregated along the path. We discuss this line of work in the related work section, although we avoid using the P-game/N-game terminology since it is inconsistently applied in the literature.\nThat said, we understand that this terminology may cause confusion and have added a footnote in the revised manuscript noting that the standard model is sometimes referred to as the P-game and the incremental model as the N-game.\n\n**On the analysis of MTD(f) and PVS**\n\n>Simply listing MTD(f) and PVS in the checklist is insufficient; a full discussion should be in the main text of the paper.\n\nWe agree that the rationale for not including MTD(f) and PVS in our main analysis could be made clearer, as we only briefly discuss them in Section 6 and 7 (and the checklist). We provide the reasoning here and will include this explanation in the appendix of the revised manuscript.\n\nOur reasoning for excluding MTD(f) and PVS from the main analysis was primarily due to technical challenges in the derivation of the recursive complexity equations. The complexity of these algorithms depends not only on the parent node's value (as with AlphaBeta and Scout) but also on the specific certificate value returned by the TEST algorithm. This introduces an additional state variable that makes the recursive formulation significantly more difficult, and it was not clear if a closed-form analysis was feasible. In particular, while we control the nodes’ values with the distribution mu, we typically do not control the nodes’ test certificate values, it is plausible that their distributions can be computed and incorporated into the equations, but we didn’t manage to do it properly yet, and we leave this open for future work.\n\nNevertheless, we believe our analysis provides strong proxies. Scout is closely related to PVS; the main difference is that PVS can sometimes use the certificate value from a TEST call to prune immediately, an optimization we believe has a minor impact on the asymptotic behavior. Similarly, our TEST-BISECTION algorithm is a simple variant of MTD(f), where the next search window is chosen by a bisection rule rather than by the certificate value from the previous search; here again we believe it shouldn’t impact the asymptotic behavior. Of course, this is only speculation, which is why we believe it’s important that PVS and MTD(f) are properly analyzed in the future.\n\n**References**\n\n[1] Nau, D. S. (1982). An investigation of the causes of pathology in games. Artificial Intelligence, 19(3), 257-278.\n\n[2] Pearl, J. (1980). Asymptotic properties of minimax trees and game-searching procedures. Artificial Intelligence, 14(2), 113-138.\n\n[3] Knuth, D. E., & Moore, R. W. (1975). An analysis of alpha-beta pruning. Artificial intelligence, 6(4), 293-326.\n\n[4] Fuller, S. H., Gaschnig, J. G., & Gillogly, J. J. (1973). Analysis of the alpha-beta pruning algorithm (No. AFOSRTR731549). Department of Computer Science, Carnegie-Mellon University."}, {"review_id": "FrU4SffY7O", "reviewer": "Reviewer_8x4a", "summary": "This paper proposes a new model for analyzing average-case complexity of determinsitic game-solving algorithms.\nPreviously, the \"standard\" model sampled leaf values to a tree of branching factor $b$ and depth $d$ from a fixed distribution.\nThe paper proposes a new \"forward\" model, where intermediate values are sampled progressively, level by level, until leaf nodes are reached.\n\nThe standard model is too simplistic, as shown by previous works, as the value asymptotically collapses to a single fixed value for all distributions. The new forward model allows for asymptotic analysis on deep trees much more efficiently than Monte-Carlo simulations.\nAuthors show in the asymptotic regime a result analogous to those of the standard model.\nHowever, Alpha-Beta incurs a multiplicative constant proportional to the game’s value range, compared to other algorithms like Scout.", "questions": "Does the level dependence in the forward model increase probability of leaf-disjoint strategies (as defined in [1]), compared to to the standard model?\n\n[1] Lorenz, U. and Monien, B. (2002). The secret of selective game tree search, when using random-error evaluations. \nIn STACS 2002: 19th Annual Symposium on Theoretical Aspects of Computer Science Antibes-Juan les Pins, France, March 14–16, 2002 Proceedings 19, pages 203–214. Springer.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I am not very familiar with the existing literature, so I can't comment on the novelty of the result.\n\nStrenghts\n\n- The paper is very clearly written. It confirms superiority of Scout over alpha-beta as predicted in multiple numerical studies.\n\nWeaknesses\n\n- I believe the results are significant as-is, but they could be greatly improved if there was analysis of MCTS, as that is the leading algorithm for large deterministic games. The lack of MCTS analysis is pointed out in the related works section.", "was_revised": true, "final_justification": "All raised comments were resolved and I maintain score 5: accept.", "rebuttal": "We thank the reviewer for their positive assessment and insightful comments. We are glad they found the paper clearly written and the results significant.\n\n**On the Analysis of MCTS**\n>“I believe the results are significant as-is, but they could be greatly improved if there was analysis of MCTS, as that is the leading algorithm for large deterministic games. The lack of MCTS analysis is pointed out in the related works section.”\n\nWe agree that an analysis of Monte-Carlo Tree Search (MCTS) would be a valuable and significant extension to this line of work. Our decision to focus on minimax-based algorithms in this paper was based on two primary considerations.\n\nFirst, while MCTS is indeed the state-of-the-art for many games, its theoretical guarantees differ from those of minimax algorithms. Algorithms like Alpha-Beta provide **deterministic guarantees** on finding the optimal move within a finite search. In contrast, MCTS algorithms like UCT offer **asymptotic convergence**, but their convergence rate can be extremely slow in certain worst-case scenarios (e.g., doubly exponential in the tree depth $h$), whereas minimax algorithms are at most exponential in $h$. See [1] or [2] for instance.\n\nSecond, from a technical standpoint, the average-case analysis we perform is not straightforward to extend to MCTS. The recursive equations needed to characterize the complexity of UCT would be substantially more involved, as the algorithm's state depends on **visit counts and empirical rewards at each node**. While we believe such an analysis is possible in principle, it presents a formidable technical challenge that we view as an important direction for future research.\n\n**On Leaf-Disjoint Strategies**\n>“Does the level dependence in the *forward model* increase probability of leaf-disjoint strategies (as defined in [1]), compared to to the standard model?”\n\nThis is an excellent question. We thank the reviewer for pointing us to this relevant work by Lorenz and Monien, which we were not previously aware of.\n\nAs we understand it, Lorenz and Monien study the robustness of minimax search when applied with noisy leaf evaluations. Their key insight is that when multiple leaf-disjoint strategies (LDS) exist (i.e., alternative, non-overlapping paths that yield the same game-theoretic value) the algorithm becomes more robust to evaluation errors. In binary-valued games (Win = 1, Lose = 0), flipping a few outcomes is less likely to affect the minimax value if there are many such disjoint strategies.\n\nOur interpretation of a \"leaf-disjoint strategy\" is a set of moves that independently **proves** the value of the game. The existence of multiple such strategies (even in an exact solving setting) should make a game easier to solve for a minimax search algorithm, as a proof can be found more quickly, leading to more *aggressive pruning*.\n\nApplying this concept to our binary-valued *forward model* provides an interesting perspective on **game difficulty**:\n\n- When $q=1$ (the probability of a child being a 'loss' given the parent is a 'win'), any move for the MAX player is optimal. This corresponds to a maximum number of leaf-disjoint strategies ($b^{h/2}$), and it is precisely the easiest case for the algorithms we analyze, resulting in the smallest branching factor.\n- Conversely, when $q=0$, there is only one optimal move at each node for the MAX player. This results in a single leaf-disjoint strategy and represents the most difficult case for the search algorithm.\n\nThis suggests that the number of leaf-disjoint strategies is **inversely correlated with the game's difficulty** for minimax search, mirroring the dynamics of the branching factor in our model.\n\nRegarding the *standard model,* the well-known value-collapse phenomenon means that for deep trees, game values tend to polarize. This behavior closely resembles the $q=1$ case in our forward model. We can therefore infer that the standard model tends to generate games with a very large number of leaf-disjoint strategies, at least for non-critical parameter settings.\n\nThe connection between the number of leaf-disjoint strategies and minimax game-solving complexity looks promising and we believe there is something to investigate and to formalize here. We thank the reviewer again for highlighting this promising avenue for further investigation and framing the properties of our model in a new light.\n\n**References**\n\n[1] Coquelin, P. A., & Munos, R. (2007). Bandit algorithms for tree search. arXiv preprint cs/0703062.\n\n[2] Orseau, L., & Munos, R. (2024). Super-exponential regret for UCT, AlphaGo and variants. arXiv preprint arXiv:2405.04407."}, {"review_id": "jbiHonuPT0", "reviewer": "Reviewer_zdYH", "summary": "This paper introduces a forward model for analyzing deterministic game-solving algorithms, addressing the limitations of the standard model (e.g., independence assumption) by enforcing ancestor dependencies in game-tree construction. The authors derive recursive complexity equations for algorithms like AlphaBeta and Scout, showing that while all algorithms converge to the same asymptotic branching factor, finite-depth analysis reveals AlphaBeta incurs a larger constant factor, making it less efficient than Scout in practice. The model enables adjustable problem difficulty and rigorous comparisons via recursive formulas, validated by Monte Carlo simulations.", "questions": "Since this paper introduces a new forward model, which is claimed to be more \"realistic\", how does its tree distribution differ from that of standard random models?", "limitations": "The authors have discussed the limitations.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strength**\n\n- Theoretical Innovation: The paper introduces a novel forward model that addresses the long-criticized independence assumption in standard game-tree analysis. By enforcing ancestor dependencies, the authors claim that the model captures structural complexities of real-world games (e.g., chess, Go) more realistically, enabling adjustable difficulty calibration for algorithm evaluation.\n\n- Rigorous Analysis: The recursive complexity equations for algorithms like AlphaBeta and Scout under the forward model provide a solid framework for theoretical comparison. The numerical validation via Monte Carlo simulations enhances the credibility of results.\n\n**Weakness**\n\n- The authors claim the forward model better represents real-world games by introducing ancestor dependencies, but fail to Provide concrete examples or case studies (e.g., in chess endgame search) to illustrate how ancestor dependencies mirror actual game dynamics. Thus, there no idea whether the introducing of the forward model is important.\n\n- The literature review focuses on classic studies (mostly pre-2000) and the authors need to check if there are new works in this area. More discussion and comparison may need to be conducted.", "was_revised": true, "final_justification": "The authors have addressed my concerns. And I raise my score to 4.", "rebuttal": "We thank the reviewer for their feedback and the opportunity to elaborate on our work's motivation and context.\n\n**On the Realism of the Forward Model**\n>“The authors claim the forward model better represents real-world games by introducing ancestor dependencies, but fail to Provide concrete examples or case studies (e.g., in chess endgame search) to illustrate how ancestor dependencies mirror actual game dynamics. Thus, there is no idea whether the introducing of the forward model is important.”\n\n\nThis is a crucial point, and we appreciate the chance to clarify the role of our model. The importance of *ancestor dependencies* for modeling real-world games has been a long-standing topic in the literature (see [1] and [2] for instance). The standard model's i.i.d. assumption is widely acknowledged as its primary limitation.\n\nA classic example, as the reviewer suggests, comes from chess. If White is in a clearly winning position (e.g., up a queen), one expects that the vast majority of reachable terminal states in the subsequent subgame will be wins for White. The standard model fails to capture this strong **correlation** between a parent node's value and its children's values.\n\nOur forward model was designed as a **mathematically tractable** way to introduce exactly this type of correlation. While it does not pretend to generate real-world games per se, its purpose is to create a richer benchmark than the often-degenerate trees produced by the standard model, while preserving the ability to perform rigorous mathematical analysis (a feature that other proposals, like the incremental model, have struggled with).\n\n**On the literature review**\n\n>\"The literature review focuses on classic studies (mostly pre-2000) and the authors need to check if there are new works in this area. More discussion and comparison may need to be conducted.\"\n\nWe agree that a broader literature review would strengthen the paper. The reason we primarily cited older works is that the critiques we build upon were most clearly formulated in the earlier literature (e.g., Knuth & Moore, Pearl, Nau). In fact, our model can be seen as a response to issues that were already well-known at the time, and which inspired alternative approaches like the  *incremental model* which has proven hard to analyze formally.\n\nTo our knowledge, no recent works have revisited this line of theoretical average-case analysis for deterministic game-solving algorithms. In contemporary game-playing research, the focus has shifted toward empirical algorithm design (e.g., MCTS, neural search policies), which tends to avoid formal models altogether. That said, if the reviewers are aware of relevant recent work that we may have missed, we would be grateful to include and discuss it in the final version.\n\n**On the difference in the tree distribution**\n>“Since this paper introduces a new forward model, which is claimed to be more \"realistic\", how does its tree distribution differ from that of standard random models?”\n\nThe most significant difference lies in the distribution of the root value of the generated game trees. It is arguably logical to focus on the root-value distribution, as this is the output of a game-solving algorithm, and a robust testbed should include trees with diverse root values.\n\nLet's consider the binary-valued case for a clear comparison. Under the standard model, the root value distribution is highly constrained. For any leaf value distribution, as the tree depth grows, the root value distribution collapses to one of two outcomes: it is either deterministic (always 0 or always 1) or, at a single critical probability $q*$, it is a Bernoulli($q*$). The standard model is therefore unable to generate a wider spectrum of tree distributions.\n\nIn contrast, our forward model is explicitly designed to generate a richer variety of trees. The root value distribution is directly parameterized and can be set to a Bernoulli($q$) for any $q$ between 0 and 1. As we demonstrate in Section 4, varying $q$ allows us to span the **full spectrum of game difficulty**, from the easiest case to the hardest. This shows that the forward model can generate a much larger diversity of game instances, making it an arguably richer model.\n\n**References**\n\n[1] Nau, D. S. (1982). An investigation of the causes of pathology in games. Artificial Intelligence, 19(3), 257-278.\n\n[2] Knuth, D. E., & Moore, R. W. (1975). An analysis of alpha-beta pruning. Artificial intelligence, 6(4), 293-326."}, {"review_id": "fNYovWhTXg", "reviewer": "Reviewer_cYDt", "summary": "The authors propose a new probabilistic model for constructing game trees to evaluate deterministic solvers. In the standard model, leaf values are independently sampled from a fixed distribution and propagated up the tree according to minimax constraints. The authors argue that this strips the games of structural complexity and results in less meaningful analysis. The proposed forward model instead samples a game value at the root and recursively samples child values from a conditional distribution on the parent's value, while still ensuring minimax constraints are respected. This leads to more realistic and harder games for average-case analysis. This analysis leads to the interesting result that AlphaBeta search incurs a large multiplicative constant on its expected branching factor, which seems to have significant practical performance implications.", "questions": "1. What are “realistic” parameterizations for the forward model?\n2. In light of 1, can the authors please justify their parameterizations?\n3. Are there $\\mu$ where AlphaBeta outperforms the other algorithms?\n3. Can the authors elaborate on the modifications or additional assumptions needed for the continuous case?", "limitations": "The authors discuss certain limitations about the work related to the analysis of the forward model and the discrete setting. However, as mentioned in the Weaknesses section, the authors do not discuss the potential limitations of the forward model itself.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n* The paper is well-written and generally very easy to follow.\n* The forward model is simple to understand, implement, and seems to offer convenient analysis for very large trees. I see it as a significant contribution to the area.\n* The numerical analysis offers a hypothesis which validates long-standing observations about the practical advantages to using Scout over AlphaBeta.\n* Though I have some questions/comments about limitations and I’m not completely familiar with all of the cited literature, I think the authors have somewhat accomplished the title goal of providing a new model that enables better analysis of deterministic game-solving algorithms.\n\n**Weaknesses**\n* The major weakness I feel this works has is its lack of discussion related to the limitations of the forward model. Similar to how the standard model does not enforce “ancestor dependency”, are there important structural game tree properties not present under the forward model? I feel some discussion on this could be added to the paper.\n* One area where this shows up is the experiments in Section 6. The parameterization of the forward model starts with, in my opinion, a relatively unrealistic set of distributions. Fairly or not, this may have a significant effect on AlphaBeta, because the distribution choice may influence how frequently and rapidly AlphaBeta degenerates to the null window. I think this is worth investigating further as I noticed that AlphaBeta seems to suffer less in the bimodal-uniform case.\n* The paper would be stronger if the analysis was extended to include a real game, even just to justify parameterization choices for the forward model.\n* Though this work seems to make progress toward answering important questions about deterministic solvers, it is worth mentioning that its applicability to the broader community at NeurIPS may be somewhat limited.", "was_revised": true, "final_justification": "Upon reading the final reviews and discussion, I would be fine with the paper being accepted. Concerns with broader impact still stand, so I will maintain my borderline rating.", "rebuttal": "We thank the reviewer for the thoughtful and constructive feedback. We are particularly grateful for the recognition of our model’s simplicity, analytical convenience, and its implications for practical algorithm evaluation. \n\n**On the limitations of the work**\n\n>“The major weakness I feel this works has is its lack of discussion related to the limitations of the forward model. Similar to how the standard model does not enforce “ancestor dependency”, are there important structural game tree properties not present under the forward model? I feel some discussion on this could be added to the paper.”\n\nThis is a fair point. We agree that our initial submission focused more on the limitations of our **analysis** than on the limitations of the **forward model itself**. We have added a paragraph to the manuscript to address this, and we will summarize the key limitations here.\n\nThe forward model was intentionally designed to be **simple**, as this is a crucial requirement to enable a tractable mathematical analysis. This simplicity naturally imposes some limitations:\n\n1. **Fixed Tree Structure:** The model only generates uniform $b$-ary trees of constant depth, which does not reflect the variable branching factors and depths found in real games. Extending the analysis to more complex tree structures is a direction for future work.\n2. **Simplified Dependencies:** The conditional distribution used to generate child values is the same for every node in the tree. It depends only on the parent's value, not on the broader game state. Furthermore, the method of ensuring the minimax constraint (truncating the distribution) is just one of many possibilities; other, more complex transformations could be valid but may also be harder to analyze.\n\nThe goal of the forward model is not to perfectly replicate the complexity of real-world games, but to capture a crucial property (ancestor dependency) missing from the standard model, while remaining analyzable.\n\n**On the parametrization of the forward model.**\n>“The parameterization of the forward model starts with, in my opinion, a relatively unrealistic set of distributions. Fairly or not, this may have a significant effect on AlphaBeta, because the distribution choice may influence how frequently and rapidly AlphaBeta degenerates to the null window. I think this is worth investigating further as I noticed that AlphaBeta seems to suffer less in the bimodal-uniform case.”\n\n\n>1. What are “realistic” parameterizations for the forward model?\n>2. In light of 1, can the authors please justify their parameterizations?\n>3. Are there mu where AlphaBeta outperforms the other algorithms?\n\nThese questions are linked, so we will address them together.\n\nFirst, to clarify our experimental findings: across all distributions we tested (including many randomly generated ones not shown in the paper), we did not find any where the fundamental conclusion changed and AlphaBeta outperformed Scout.\n\nOur choice of distributions for the figures was deliberate, aiming to test the algorithms under diverse and informative conditions:\n- The **uniform distribution** is a natural starting point, representing the case with the maximum possible diversity (entropy) in game values.\n- The **triangular, power and bi-modal distributions** were chosen to create problems of **increasing theoretical difficulty**, pushing the algorithms' performance closer to their asymptotic worst-case. The observation that AlphaBeta suffers less here is interesting, but it still does not outperform Scout.\n\nRegarding \"realistic\" parameterizations, it is an open question whether any parameterization of our simple model could accurately capture a specific real-world game. As discussed above, the model is likely **too simple for that** (and this should have been made clearer in the paper). However, its strength lies in its ability to generate a continuous spectrum of game difficulties. We can tune its parameters to create games that are maximally easy, maximally hard (from a theoretical standpoint), and everything in between. This makes it a useful tool for stress-testing algorithms in a controlled manner.\n\n\n\n**On the applicability of our work to Neurips**\n>\"Though this work seems to make progress toward answering important questions about deterministic solvers, it is worth mentioning that its applicability to the broader community at NeurIPS may be somewhat limited.\"\n\nThe reviewer is right in pointing out the fact that the broader applicability of our work to NeurIPS may seem limited to some readers. To clarify that, we added a *Broader Impact* statement to the paper.\n\nWhile our work is centered on classical deterministic game-solving algorithms, we believe it is **timely and relevant** for the NeurIPS community for the following reasons. \n\nSearch remains a key component of today’s top-performing agents in RL and game-solving, e.g. AlphaZero, MuZero, and others **combine learning with planning**. Even though MCTS is dominant, we believe deterministic methods like AlphaBeta still have value (see [1] for instance), especially when lower variance or stronger guarantees are needed.\n\nOur main contribution is a new average-case analysis model that, we hope, fills a **longstanding gap**. Despite decades of use, there hasn’t been much rigorous analysis of how these algorithms behave on more realistic trees. Our forward model brings in some structure (like ancestor dependencies) while staying simple enough to analyze. Hopefully, this helps uncover practical differences between algorithms that aren’t visible in the standard model.\n\nWe believe this kind of theoretical insight could inform future hybrid systems that mix learning with deterministic planning. It also connects with broader NeurIPS themes around **decision-making**, **optimization**, and understanding the foundations of **intelligent behavior**.\n\n\n**On the Continuous Case**\n>“Can the authors elaborate on the modifications or additional assumptions needed for the continuous case?”\n\nWe believe that no significant additional assumptions are needed to extend the analysis to the continuous case, though the analysis itself becomes more complex. The recursive equations are conceptually the same, with the main difference being that expectations become **integrals** over continuous variables rather than discrete sums.\n\nThis has two main consequences:\n- The boundary conditions in the equations simplify slightly (e.g., in the discrete case $x > -s$ is equivalent to $x >= -s+1$, whereas in the continuous case they are the same event regardless of the inequality being strict or not, up to a set of measure zero).\n- The analysis becomes more difficult because we now have a system of **integral equations**. Solving these may require finding a closed-form solution or using numerical approximation methods (like discretization), which would effectively return us to a scenario similar to the discrete case.\n\nIn summary, the framework extends directly, but the mathematical machinery required is more challenging.\n\n**References**\n\n[1] Cohen-Solal, Q., & Cazenave, T. (2023, May). Minimax Strikes Back. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems (pp. 1923-1931)."}]

Author rebuttal:

Meta-review: This paper addresses a fundamental issue in the average-case analysis of game-solving algorithms, specifically the assumption that game-tree leaf values are independent. The authors argue that this simplification renders problems unrealistically easy. To tackle this issue, they propose the "forward model," a new probabilistic framework that enforces ancestor dependency. This model more accurately reflects the structure of real-world games while remaining analytically tractable. Using this framework, the authors derive average-case complexity formulas for classical algorithms such as Alpha-Beta and Scout, enabling rigorous comparisons even in deep game trees where simulations typically fail.

The paper has received five reviews with scores ranging from weak rejection to clear acceptance. All reviewers recognize the novelty of the forward model, the rigorous analysis of deterministic strategies, and the clarity of the writing. However, there is debate over the theoretical significance of the results; a formal characterization of the advantages of Scout compared to Alpha-Beta would further highlight the strengths of this forward-model analysis.

Overall, the strengths of this paper outweigh its weaknesses, and I recommend acceptance. Still, I suggest taking into account the constructive discussions during the rebuttal phase for further revisions.
Decision: Accept (poster)