- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper introduces Strautomata, a framework that evaluates models as builders of autonomous artifacts within well-known strategic board games. Across 20 distinct games, the authors sample 5,200 Python-based automata generated by 52 LLMs and execute over 2,500,000 offline, head-to-head matches to establish Elo ratings. The authors report that separating code generation from execution enables highly cost-efficient evaluation and places the benchmark on the cost-alignment Pareto frontier.
Critical strengths
- Extensive experiments are conducted on various frontier models across 20 games, with comparisons against human-written engines and live LLM play.
- The authors examine ranking stability across repeated runs and different numbers of sampled policies.
- The reasoning-level experiments show that additional reasoning during code generation can improve the strength of policies that later run without further model intervention.
Critical weaknesses
- The intra-model qualifier over five sampled programs is not sufficiently motivated, as it only captures minor variations caused by random seeds. The candidates are generated independently, without any negotiation. A more reasonable approach would allow five subagents to collaborate or challenge each other's solutions, revise their programs, and then select the most suitable program.
- The paper does not establish what the full cross-model tournament adds over evaluation against a small set of opponents. If a simpler evaluation produces similar model rankings, the additional value of the proposed tournament would be limited.
- The paper provides limited analysis of why stronger LLMs produce better policies. The code-length correlations do not establish how much of the performance gap comes from fewer errors and timeouts, and how much comes from better strategies.
Questions for authors
- In Go and Checkers, what proportion of the random baseline's wins comes from opponents making illegal moves or timing out, and what proportion comes from normally completed games?
- Were all models evaluated using the same agent harness? Were they allowed to execute their generated programs and revise them based on execution feedback?
- What model does each point in Figure 7 represent?
5 comments
Discussion with 1Lxh (2/3)
W3: The paper provides limited analysis of why stronger LLMs produce better policies. The code-length correlations do not establish how much of the performance gap comes from fewer errors and timeouts, and how much comes from better strategies.
The rankings in the paper show that stronger LLMs produce stronger automata but here we tackle the reviewer's two main questions: how much of the gap between models comes from execution failures vs better strategy and which design choices in the generated code are associated with stronger play. Throughout, we split the models into thirds based on median Elo (top, middle, bottom) and analyze the 2,080 automata that entered the tournament.
Failures versus play
Each tournament match ends either normally (win, loss, draw) or with a failure from an automaton. Failure rates differ by a large margin depending on which third of the leaderboard we look at. In the top third automata only lose 2.4% of games due to failures, in the middle it's 11.6% and in the bottom third it is 23.6%. To separate failures from play in the final score, we re-fit Elo using only completed games where no failure happened. This no-failure Elo measures how well automata play when failure isn't considered and this leaderboard is nearly identical to the paper's leaderboard (Spearman ρ = 0.983, we illustrate this change in Figure 2). Additionally, to attribute the final Elo, we regress each model's Elo in each game on its no-failure Elo and its failure rate ( = 0.88). A Shapley decomposition of this attributes 72% to no-failure Elo and 28% to failures. Thus, an automaton in the bottom of the leaderboard can raise its Elo by avoiding illegal moves but the top of the leaderboard is affected very little when failed matches are removed and is mostly decided through play strategy.
| Tier | Illegal moves | Runtime errors | Timeouts |
|---|---|---|---|
| Top | 0.38% | 0.00% | 1.98% |
| Middle | 5.71% | 1.17% | 4.68% |
| Bottom | 14.25% | 5.82% | 3.57% |
Design choices
We attempt to extract design features from automata with a mix of AST and regular expressions. We find that almost all search architectures used by the automata fall in one of four types:
- 'no recursive search' (hand-written rules or scoring)
- 'fixed-depth search' (recursive minimax/negamax/expectimax or Monte Carlo with no wall-clock control)
- 'time-based search' (similar to 2 but bounded by a deadline, typically iterative deepening)
- 'time-based search with engine enhancements' (similar to 3 but includes multiple optimization tricks such as transposition tables, move ordering, quiescence search, heuristics, etc.).
In Figure 3, we show how many automata use the different search architectures split by which third of the leaderboard that automaton is placed in. In Figure 4, we show the mean within-game standardized Elo per search architecture. And in Figure 5, we show the fraction of games lost to errors per search architecture broken down into the types of errors.
We notice several important factors in these figures that dictate strength based on the policy. First, from Figure 3 we see that almost all time-based search with enhancements is written by top-tier automata and that the majority of top automata (72%) rely on some form of time-based search unlike weaker automata that rely less on time-based search (17% for middle and 5% for bottom tiers) and rely mostly on weaker search strategies that fail to find a good move and often time out which makes them not competitive.
Analyzing the AST/regex for a specific game like Chess, we notice that many automata rely on embedded heuristics of piece-square tables (assigning values on the specific squares each piece type can land on) thus implementing a heuristic evaluation function which vastly improves the search strategy but requires a higher amount of game knowledge. We find that 20 out of 36 top automata embed such heuristic values while only 3 of 34 bottom automata attempt implementing them. Automata which use such a strategy in Chess average an Elo of 1,788 compared to automata that don't which average 1,336 Elo.
Discussion with 1Lxh (3/3)
Q1: In Go and Checkers, what proportion of the random baseline's wins comes from opponents making illegal moves or timing out, and what proportion comes from normally completed games?
In Go, Random wins 49.3% of its games: 27.3% through opponent failures and 22.0% through normal play. In Checkers it wins 50.0%: 37.1% through opponent failures and 12.9% through normal play. In Chess it wins 36.0%: 35.5% through opponent failures and only 0.4% through normal play. Random's surprisingly high rank in Chess and Checkers is mostly a statement about how often weak automata fail at legality. Go is special in that all games end due to either the 722 max game length rule (twice the number of board points) or by both players passing (thus agreeing to end the game) as opposed to other games that have a regular win condition. This means that the random policy playing white (and getting the 7.5-point komi) only loses against a competent opponent that successfully captures the dead stones that are placed by the random policy before they start accumulating and overwhelm the player with a localized pattern. We believe a visual replay of such games provides an easy understanding of what's happening, thus we'll provide a website that provides a comprehensive visualization of the games and automata battling alongside the leaderboards.
W2: The paper does not establish what the full cross-model tournament adds over evaluation against a small set of opponents. If a simpler evaluation produces similar model rankings, the additional value of the proposed tournament would be limited.
We agree with the reviewer's intuition that a simpler sampling strategy exists. Our main focus was lowering inference cost from the LLMs instead of lowering CPU cost. Thus, we did not attempt to propose any strategy other than the naive round-robin matchup. However, in the interest of making evaluation scalable, we incorporate the reviewer's idea and introduce a simple evaluation. We re-ran the tournament while making each model only match up against other models each for games. We report agreement with the full leaderboard and the alignment from Figure 2:
| Schedule | Order | Speedup | Spearman ρ vs full | Kendall τ vs full | Figure 2 Alignment |
|---|---|---|---|---|---|
| Full round robin, r=20 | 1× | 1 | 1 | 0.748 | |
| K=10, r=20 | 5.3× | 0.985 | 0.905 | 0.736 | |
| K=20, r=10 | 5.3× | 0.987 | 0.918 | 0.736 | |
| K=40, r=5 | 5.3× | 0.994 | 0.950 | 0.748 | |
| K=5, r=10 | 21.1× | 0.969 | 0.859 | 0.721 | |
| K=10, r=5 | 21.0× | 0.979 | 0.892 | 0.734 | |
| K=20, r=2 | 26.3× | 0.982 | 0.899 | 0.738 |
The reviewer is right that a much smaller evaluation recovers a similar ranking. With 20 random opponents and only 2 games per pairing, which is a 26× speedup and only , the leaderboard has ρ = 0.982 with the full one and nearly the same alignment with other benchmarks. We view this as a strength of the framework rather than a limitation of the tournament. Because automata are frozen artifacts, an offline schedule runs without further LLM calls. We use the full round robin for this paper because it is simple, precise, and affordable at the current scale. It also serves as the reference that makes the validation above possible. We will add the above to the appendix and describe the sparse schedule as a path for scaling up Strautomata.
Q3: What model does each point in Figure 7 represent?
We acknowledge the plot should have the points labeled. We thank the reviewer for pointing out the missing labels and have updated the figure to add some more data and labels for both Chess 6 and Connect4 7.
We will incorporate the additional results and experiments into the paper and upload the revised polished version.
We hope the above comments and additional experiments address the reviewer's concerns.
Discussion with 1Lxh (1/3)
We thank the reviewer for their thoughtful constructive comments. Please find below answers to your questions and concerns. We hope that these results will strengthen the reviewer's belief towards our work.
Models were all evaluated under the same conditions with zero-shot generation and no revision. We provide below results on tournaments which include Claude and Codex agents which have zero-shot automata counterparts. We note that for all agents, we provided a fresh working directory which contained the game files, a brief explanation of the task, and useful harness/tools that let them test their policies against random opponents. We conducted this agentic automata creation for seven models in five games (Chess, Go, Checkers, Othello, Connect4).
Within each model and game, the median automaton is the third of the five zero-shot automata ordered by tournament Elo while the top automaton has the highest tournament Elo. The table takes the median across the five games separately for the agent, median automaton, and top automaton.
Figure 1 shows the median Elo of agent policies, median automata, and top automata across the five games.
The two Codex models were additionally run with 5 subagents to incorporate the reviewer's suggestion since the Codex agents under the regular harness provided automata at or weaker than the median zero-shot automata. Each subagent policy enters the same tournament for all five games, and its row reuses that model's automata.
The above comparisons show that in the games we test, the difference between zero-shot automata creation and agentic automata creation is mostly significant in sonnet/opus and not Fable/Astra most likely due to the games being well known and the frontier LLMs not needing to iterate on the automata to understand the game.
We emphasize however that we think it is important for the automata to come directly from the LLM to have a fair LLM benchmark that all LLMs can compete in as opposed to pairing certain LLMs with agentic harnesses they were not optimized for. If the goal of Strautomata was to measure if a generated automaton can exceed a fixed threshold in capabilities (more akin to SWE-bench tasks) then we agree with the reviewer that it is critical to test agentic automata creation as opposed to zero-shot. However, the goal of Strautomata is to evaluate the LLMs in a pairwise fashion as opposed to finding the strongest possible automata the LLM can make under any and all circumstances, and since the evaluation is done pairwise between the LLMs and the reported scores are relative, having the unified 'zero-shot' standard amongst the LLMs is a fair evaluation that does not disrupt the final Elo scores or rankings (assuming rankings are preserved under a harness). Additionally, we spend some effort ensuring that Strautomata is cost-efficient (which ensures we are at the cost-alignment Pareto frontier) and agentic use of LLMs is heavily cost inefficient.
We hope the above experiment provides a comparison that gives stronger justification to the zero-shot generation process.