AlphaBeta is not as good as you think: a simple random games model for a better analysis of deterministic game-solving algorithms

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.

On the limitations of the work

“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.”

This 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.

The 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:

1. 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.
2. 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.

The 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.

On the parametrization of the forward model.

“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.”

1. What are “realistic” parameterizations for the forward model?
2. In light of 1, can the authors please justify their parameterizations?
3. Are there mu where AlphaBeta outperforms the other algorithms?

These questions are linked, so we will address them together.

First, 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.

Our choice of distributions for the figures was deliberate, aiming to test the algorithms under diverse and informative conditions:

• The uniform distribution is a natural starting point, representing the case with the maximum possible diversity (entropy) in game values.
• 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.

Regarding "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.

On the applicability of our work to Neurips

"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."

The 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.

While 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.

Search 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.

Our 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.

We 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.

On the Continuous Case

“Can the authors elaborate on the modifications or additional assumptions needed for the continuous case?”

We 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.

This has two main consequences:

• 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).
• 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.

In summary, the framework extends directly, but the mathematical machinery required is more challenging.

References

[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).

We thank the reviewer for their feedback and the opportunity to elaborate on our work's motivation and context.

On the Realism of the Forward Model

“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.”

This 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.

A 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.

Our 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).

On the literature review

"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."

We 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.

To 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.

On the difference in the tree distribution

“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?”

The 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.

Let'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.

In 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.

References

[1] Nau, D. S. (1982). An investigation of the causes of pathology in games. Artificial Intelligence, 19(3), 257-278.

[2] Knuth, D. E., & Moore, R. W. (1975). An analysis of alpha-beta pruning. Artificial intelligence, 6(4), 293-326.

Thank you for engaging in the discussion with us. You are absolutely right saying that parent-children value correlation always exists in any game, and in particular in instances of the standard model. This is the case because the parent minimax value is a deterministic function of the children values. What we wanted to illustrate with the chess example (and we reckon it was poorly phrased in our rebuttal) is the fact that in real-world games there is typically correlation among siblings, e.g. two children of the same node are likely to hold similar values, this property is not modeled at all by the standard model. This exact point has been clearly articulated by Nau in 82’ (but also by Knuth in 75’). We include relevant quotes in the comment below due to character limits.

Can quantitative comparisons show that the proposed forward model better aligns with empirical game dynamics than the standard models?

This relates closely to our earlier discussion with reviewer cYDt on the limitations of our work. Our model is likely too simple to model a real-world game: they typically have a more complex tree structure, e.g. with early terminations; and the way children depend on parents is more varied than what we encode in the forward model (we use the same conditional distribution at each level, with a simple truncation method). This is the case because we wanted our model to retain some form of mathematically tractability.

That being said, we can illustrate that a real-world game typically has correlation between siblings, i.e. ancestor dependencies as we originally meant it. These correlations are inherently impossible to model under i.i.d assumption. For simplicity we choose a simpler version of Tic-Tac-Toe, modified such that no draw is possible: in case of a draw, the second player wins. This simplification allows us to set ourselves in a convenient binary-valued setting while keeping the same game dynamics.

We want to measure sibling correlation: if we randomly pick two children of the same position, how correlated are their values? For this:

• We enumerate all positions after 3 moves (i.e., subgames where 6 actions remain), of which there are 252 (we chose this setting to obtain a large enough number of subgames).

• For each position, we randomly pick two children, compute their values, and store these values across all 252 positions.

• We repeat this 256 times (sampling different child pairs), and compute the average Pearson correlation between the two series of 252 values.

• The result is a sibling correlation of 0.109 ± 0.004 in Tic-Tac-Toe (mean$\pm$standard error).

Now consider the standard model. We generate 32 random instances with 252 subtrees each (using varying values of the parameter p), and perform the same sibling-correlation analysis. Unsurprisingly, in all cases, the average correlation is near zero, regardless of $p$, because sibling values are independent by construction.

And what about the forward model? We can repeat the exact same experiment. The numerical results show that depending on the parameter $q$, the forward model generates instances with increasing sibling correlations. See the table below.

We do not claim that the forward model effectively models the Tic-Tac-Toe game, but at least, it can generate games with this kind of ancestor dependencies (sibling correlations), which is not the case of the standard model. As we show in the paper, this translates into the theoretical capacity of the forward model to generate richer distributions of root values and a wider range of game difficulty, including maximally hard instances.

We thank you for raising this point. We agree that clarifying what we mean by "ancestor dependencies" will improve the paper’s presentation, and we hope this concrete example helps clarify both our motivation and our contributions. Please tell us if you have more questions.

We thank the reviewer for their positive assessment and insightful comments. We are glad they found the paper clearly written and the results significant.

On the Analysis of MCTS

“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.”

We 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.

First, 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.

Second, 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.

On Leaf-Disjoint Strategies

“Does the level dependence in the forward model increase probability of leaf-disjoint strategies (as defined in [1]), compared to to the standard model?”

This 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.

As 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.

Our 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.

Applying this concept to our binary-valued forward model provides an interesting perspective on game difficulty:

• 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.
• 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.

This 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.

Regarding 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.

The 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.

References

[1] Coquelin, P. A., & Munos, R. (2007). Bandit algorithms for tree search. arXiv preprint cs/0703062.

[2] Orseau, L., & Munos, R. (2024). Super-exponential regret for UCT, AlphaGo and variants. arXiv preprint arXiv:2405.04407.

We thank the reviewer for the review and the opportunity to clarify and expand on several points.

On the 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.”

We believe that this summary doesn't fully capture the scope of our work. Our primary contributions are:

1. 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.
2. 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.
3. 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.

On the lack of novelty

“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.”

We 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.

On the “unclear analysis”

Unclear analysis in Section 5.1 (lines 178–180). The manuscript states: “… but under the assumption that the special child—which inherits the root’s value owing to the negamax formulation—has already been identified.” I 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.

There 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.

On the “missing citations”

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.

We 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]).

The same approach is also employed in Levente Kocsis and Csaba Szepesvári, Bandit-Based Monte-Carlo Planning,” ECML 2006.

Regarding 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. That 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.

On the analysis of MTD(f) and PVS

Simply listing MTD(f) and PVS in the checklist is insufficient; a full discussion should be in the main text of the paper.

We 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.

Our 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.

Nevertheless, 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.

References

[1] Nau, D. S. (1982). An investigation of the causes of pathology in games. Artificial Intelligence, 19(3), 257-278.

[2] Pearl, J. (1980). Asymptotic properties of minimax trees and game-searching procedures. Artificial Intelligence, 14(2), 113-138.

[3] Knuth, D. E., & Moore, R. W. (1975). An analysis of alpha-beta pruning. Artificial intelligence, 6(4), 293-326.

[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.

We thank the reviewer for the thoughtful comments and valuable suggestions, which helped us clarify and improve the presentation of our work.

On the realism of the forward model

“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.”

We 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.

In 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.

On obtaining more precise characterization of the complexity of the different algorithms

“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.”

We 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.

Nevertheless, 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.

To 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.

On the independence of leaf values.

“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.”

Yes, 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.

For 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.

On the confusion of discrete vs continuous variables.

“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].”

We 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.

We 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.

Regarding 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.

References

[1] Nau, D. S. (1982). An investigation of the causes of pathology in games. Artificial Intelligence, 19(3), 257-278.

[2] Knuth, D. E., & Moore, R. W. (1975). An analysis of alpha-beta pruning. Artificial intelligence, 6(4), 293-326.