Mastering Board Games by External and Internal Planning with Language Models
Authors: John Schultz
Jakub Adamek
Matej Jusup
Marc Lanctot
Michael Kaisers
Sarah Perrin
Daniel Hennes
Jeremy Shar
Cannada A. Lewis
Anian Ruoss
Tom Zahavy
Petar Veličković
Laurel Prince
Satinder Singh
Eric Malmi
Nenad Tomasev
Venue: ICML 2025 spotlightposter (2025)
Keywords: search
planning
language models
games
chess
Primary area: deep_learning->large_language_models
TL;DR: We pre-trained an LLM capable of playing board games at a high level. We further introduce external and internal planning methods that achieve Grandmaster-level performance in chess while operating closer to the human search budget.

Abstract: Advancing planning and reasoning capabilities of Large Language Models (LLMs) is one of the key prerequisites towards unlocking their potential for performing reliably in complex and impactful domains. In this paper, we aim to demonstrate this across board games (Chess, Fischer Random / Chess960, Connect Four, and Hex), and we show that search-based planning can yield significant improvements in LLM game-playing strength. We introduce, compare and contrast two major approaches: In *external search*, the model guides Monte Carlo Tree Search (MCTS) rollouts and evaluations without calls to an external game engine, and in *internal search*, the model is trained to generate in-context a linearized tree of search and a resulting final choice. Both build on a language model pre-trained on relevant domain knowledge, reliably capturing the transition and value functions in the respective environments, with minimal hallucinations. We evaluate our LLM search implementations against game-specific state-of-the-art engines, showcasing substantial improvements in strength over the base model, and reaching Grandmaster-level performance in chess while operating closer to the human search budget. Our proposed approach, combining search with domain knowledge, is not specific to board games, hinting at more general future applications.

Mastering Board Games by External and Internal Planning with Language Models
John Schultz. !
Jakub Adamek" !
Matej Jusup *2 Mare Lanctot
Michael Kaisers
Sarah Perrin
Daniel Hennes'
Jeremy Shar
Cannada Lewis? Anian Ruoss'
Tom Zahavy' Petar Veličković'
Laurel Prince"
Satinder Singh
Eric Malmi **1
Nenad Tomašey"
Abstract
1. Introduction
While large language models (LLMs) perform fluently on text generation, language understanding and translation, they are prone to hallucinations and reasoning errors, espe- cially in complex contexts (Chang et al., 2024; Hadi et al., 2023). Hence, special attention has been given to the devel- opment planning and reasoning capabilities LLMs (Mi- nace al., 2024). In terms of Kahneman's 's cognitive theory of two systems (Kahneman, 2011), prior work primarily im- proved associative System inference in language models, whereas planning and reasoning now focuses on improving the more deliberate System thinking (Plaat et al., 2024).
Advancing planning and reasoning capabilities of Large Language Models (LLMs) is one of the key prerequisites towards unlocking their potential for performing reliably in complex and impact- ful domains. In this paper, we aim to demon- strate this across board games (Chess, Fischer Random Chess960, Connect Four, and Hex), and we show that bearch-based planning can yield significant improvements in LLM same-playing strength. We introduce, compare and contrast major approaches: In external search, the model guides Monte Carlo Tree Search (MCTS) roll- outs and evaluations without calls to an external game engine, and internal search, the model is trained to generate in-context a linearized tree of search and resulting final choice. Both build language model pre-trained on relevant do- main knowledge, reliably capturing the transi- tion and value functions in the respective envi- ronments, with minimal hallucinations. We eval- uate our LLM search implementations against game-specific state-of-the-arr engines, showcas- ing substantial improvements in strength over the base model, and reaching Grandmaster-level per- formance in chess while operating closer to the human search budget. Our proposed approach, combining search with domain knowledge, is not specific to board games, hinting at more general future applications.
Planning and reasoning approaches typically fall into one of two distinct categories: In internal planning the LLM develops plan in context, like Chain-of-Thought prompt- ing (Wei et al., 2022), by autoregressively considering pos- sible steps towards the goal and their consequences. By contrast, external planning uses the LLM to generate steps in a neurosymbolic system, such as in Tree of Thought (Yao et al., 2024), where an outer loop performs explicit search over possible sequences of steps. This paper presents how language models can be trained for internal and ex- ternal planning to improve reasoning in sequential decision- making, using board games an experimental domain.
Board games have historically played an important role in the development of automated dacision-making with Tor- res' automaton El Ajedrecista playing three-piece chess end- games before the advent digital computation (tor, Novem- ber 1915). Games provide diverse reasoning challenges about both environment dynamics and opponent strategies, and thus have gained significant attention in pushing the boundaries of LLM reasoning capabilities (Hu et al., 2024b; Costarelli et al., 2024; Duan et al., 2024). LLMs have in- cidentally been struggling with reliably playing common board games, like chess or even tic-tac-toe (Topsakal & Harper, 2024). This may seem somewhat surprising, con- sidering how much headway has been made in other areas. However, as games astutely expose the inability of L.MSs to consistently reason over possible futures with world mod- els, they make great testbed for planning and reasoning.
'Equal contribution "Equal senior authorship "Research conducted during an internship at Google 'Google Deep- Mind *ETH Zürich *Google. Correspondence to: Eric Malmi <emalmi goo.le.com>> Nenad Tomasev <ne- nadt @ @goggl..co..
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Mastering Board Games by External and Internal Planning with Language Models
Making progress in game-playing could inform how to best instill this ability in L.MSs going forward. We present sev- eral contributions towards this aspirational goal.
given in two ways: either directly with the $state com- mand, or as in Figure I with the commands kprev state sprev.action $state, which instruct the model to take a previous state ($prev_state) and a move played in that state (Sprev_acts pactiion on) and use these to infer and output the starting state ($state). The latter functionality makes the model act as a transition function.
Contribution 1: MAV model. We pre-train Trans- former model, the multi action-value model (MAV), capable of playing several board games (Chess, Chess960, Connect Four, Hcx) at a strong level. This model is capable of reliably tracking the board state throughout games, and makes (good) legal moves.
Value function. The Stop k command instructs the model to consider the starting state and output the best k legal moves and their action values, in order of preference from highest action value to lowest. l is configurable to allow for varying the amount of inference-ting computation MAV performs. If there are fewer legal moves than kt the model simply outputs all of them (this can also be achieved by setting & to "all"). In the case where the starting state is ter- minal, the Stop_K k command outputs the game outcome in- stead (e.g., [Stop_1 invalid first player has won).
External search. We use MAV within an external MCTS controller, as a value/implicit policy and transition function. Our Asyne MCTS reaches Grandmaster level with the number of moves considered per decision (~100 to ~1k) comparable to human players (for reference, Al- phaZero (Silver et al., 2017) used ~10k simulations and traditional engines use up to millions).
Contribution 2:
"1-0"] when the
The action value for a move corresponds to the predicted win probability for the player in the current state if this move taken. For chess, state-action values are represented similarly to Ruoss et al. (2024a): Stockfish centipawn eval- uations are mapped to win probabilities using the formula
Contribution 3: Internal search. We distill the search procedure directly into the LLM,, generalizing the Stream of Search (SoS) (Gandhi et al., 2024b) ap- proach to significantly more complex domain. The performance of the resulting agent scales smoothly with the given search budget.
2
-1)
Win % = 50 + 50
1 1 E 0.0036820S centipawns
obtained from https://1e chess org/page/ accuracy. Win probabilities are then mapped to discrete non-overlapping buckets, making the value prediction problem a classification task rather than a regression task. This has proven to be beneficial in other works (Farebrother et al., 2024). We use 64 buckets, each represented by different special token (e.g., <ctr128> for bucket 28). Figure 2 shows two win probability distributions predicted by MAV. Connect Four and Hex use game engines Fhourstones (Tromp) and neurobenzene (Gao & Pawlewicz). respectively, to obtain state-action values, which are similarly mapped to the same 64 bucket tokens.
2. Multi-Action-Valuu Model
The multi-action-value (MAV) model is a Transformer model pre-trained exclusively on textual game data that functions simultaneously as a: (i) world model, (ii) value function, and (iti) policy function for multiple perfect- information board games. Acting as world model further requires the following capabilities: (1) state- tatte-tracking (de- termining the new state of the game after a move has been played in the previous state), (ii) legal move prediction, (rii) terminal state detection. To achieve this, MAV is trained on examples following a flexible format illustrated in Figure
When producing training data we vary l randomly, making sure to include examples with h greater than the number of legal moves. We randomize the order of the moves to: (i) encourage the model to treat the moves independently. and (ti) help to prevent hallucinations. With a fixed or- der, e.g., lexicographical from ala2 to h8h7, then (4) if the model skipped a legal move ala4 and emitted a ala5, it couldn't go back and fix its mistake, and (ii) the model might learn to heavily lean on evaluations of previous moves when considering a move like 18h7,, which is late in the order. Using randomised ordering of moves in the training data, the model is steered towards an approximate permuta- tion symmetry (Bronstein et al., 2021).
Command specification. MAV input starts with header containing series of commands specifying the game being played, the inputs provided and the expected outputs.
State representation. Each game uses a different textual format to represent its state, used with the $state and $prev_state commands. All of them are designed to be easy for the model to navigate and manipulate: each field the board is separate token, and fields maintain constant relative positions in token space. For chess we additionally support using the standard FEN representation (with the & fen command).
Starting state. The starting state for the model can be
Value Definition: Scoring Methods. During inference,
2

---

Mastering Board Games by External and Internal Planning with Language Models
Game name (one of) chess chess960 hex connect_four
Input spec (one of) current state, previous state action
Output spec
(all of)
current state (if input previous state), either top-k or all moves+values, best move and state afterwards
<mav game=chess> Sprev FEN %prev action XFEN %state Stop 5 %best. action 8FEN c/mav>
promot imput output spec
[%prev__FE FEN httt:///wwoookkkooo////////////0
[%prev action e5e6]
Inputs ordor from spec
[%FEN
013]
[%state |J R K. P..
N QQQ.B.... B...... P.P...P ..P... q............................... ppppe p. wwt.pppppppp........ [00000000111] outputs from spec
1000000
[%top_5 c7b6:<ctr(28> f6f5:ctrr133> d7c5xccri128> f8h8:c a5f5:cctr129.]
bobest_actions f6f5]
[%FEN wttp:///www//gggo./////////////p
Figure 1. A complete example used for training the multi-action-value models. Robert J. Fischer (2690) - Mijo Udovčié (2460), Bled 1961, 1/2-1/2.
in Ruoss al. (2024a), which they resolved by using Stockfish to break ties when all top 5 moves lie above win probability of 99%. To eliminate reliance on game engine at inference time, we introduce the Sbest_act on on command, which instructs the model to emit the game engine's 's chosen action in the position. In this way we teach the model the tie- breaking procedure described above.
E
0.25-
13.7
1
0.20
0.10
A
A
A
A
Novelty. To summarize, MAV makes four key improve- ments over the existing state-of-the-an Transformer-basee chess engines (Ruoss et al., 2024a; Monroe & Leela Chess Zero Team, 2024; Czech et al., 2024; Farebrother et al., 2024) First, it performs world modeling, policy and action- value computation together in one model. Second, it is trained to output the best action the end of action-valle value modeling, enabling the model to reliably finish games where it has a decisive advantage. These two improvements enable MAV to play complete games without relying on an exter- nal game engine for legal moves or for finishing the game. Third, all of the above steps can be done in a single model call without having to evaluate every action separately- an important feature that guided the design of the MAV for- mat to reduce the cost and infrastructural complexity of inference. Fourth, the amount of compute performed by the model at inference time can be varied dynamically, enabling us to achieve higher quality at the cost of higher latency when performing both internal and external search, where the performance increases as we scale the planning.
0.00
0.0
0.2
0.4
0.6
0.8
1.0
Win probubiitty
Figure 2. For a safe positional move, such as Mel, MAV assigns little uncertainty and gives win probability of 40-45% since white is a pawn down. In contrast, the bishop sacrifice x (best move according to Stockfish) is riskier attacking move and thus has substantial probability mass around low, equal, and high win probabilities.
for each move the model produces a distribution over the 64 tokens that correspond to action value buckets. We ex- periment with two methods to turn this distribution into a final score for the move: max scoring, which corresponds to greedy decoding, uses the mode the model's distribution, while mean scoring uses the expectation over buckets.
Mean scoring (also used in Ruoss et al. (2024a)) utilizes more of the model's information, and is better able to distinguish actions with equal modes. In an almost tied position, the most likely outcome for many moves may be a draw, but still some moves may have a higher winning chance than others. Mean scoring will be able to pick the best move in this case, while max scoring can not. This is further illustrated in Figure 2.
Datasets. We curate dataset of diverse, relevant positions in four games: Chess, Chess960, Connect Four, and Hex. The statistics and sources for each of these datasets shown in Table 4 in Appendix B. Each position is used to produce single training example, randomly varying (i) the k action values in toop k, (ii) the presence of the initial or final state tracking commands, (ii) the use and order of sstate or $ EEN representations in chess. Further details the datasets are provided in Appendix B.
Best action prediction. In positions where the model has large advantage, it may have many moves available with ca. 100% win probability that don't 't directly lead to finishing the game by checkmate. This may cause the model to play aimlessly in such positions. This problem was encountered
3

---

Mastering Board Games by External and Internal Planning with Language Models
Models. We train two randomly initialized decoder-only Transformer models using the Gemini architecture (Gemini Team et al., 2024), called MAV and MAV-small,' with 2.7 billion and 1 billion parameters respectively?. They were trained on 1.9 and 1.2 epochs of the dataset. Except for the max scoring result for MAV-small in Table 1, all other experiments and results use the 2.7 billion MAV. In order efficiently use our models' parameters, the input part of each training example is masked out during loss computation. This means our models do not waste capacity on learning to generate game positions.
Algorithm EXTERNAL--MCTS(S))
1: Input: Initial state su, active player i, top h values,
num. simulations M
2: Output: Recommended action a'
ab. (so, ag) = MAV(su)
Compute prior P(sv, at: k) according Eq. 1.
5: Initialize root node:
No(1) + i
No(s) t 80
No(aa) +- ag
6: EXPAND(No- P)
7: for m = I,..., .M {this can be async} do SIMULATION(No, k)),k)
3. External Search
end for
External search employs MAV to generate planning steps, and applies a search algorithm direct and optimise over sequences of planning steps. In this paper, we evaluate planning on top of the previously discussed MAV, using MCTS as the search procedure.
10: a" < -NNALMOVISELLCCTIO((())
11: return a"
of action a in state under the greedy policy to be
External search is based on an AlphaZero-style MCTS (Sil- ver et al., 2017). There are two key ingredients: a prior function which returns a probability distribution over actions at each state, and value function returning a numerical value indicating value of a state or state-action pair, both extracted from the MAV output. External search is an adap- tation of MCTS; in its most basic form, as in AlphaZero, MCTS relies on an explicit world model, querying game engine (e.g., a chess implementation in OpenSpiel (Lanctot et al., 2019)) to provide legal actions, state transitions and terminal states. Inspired by MuZero (Schrittwieser al., 2020), in a subsection below we describe how remove this dependency on the game engine and instead use only MAV to track states, transitions, and provide legal actions and game outcome during planning.
exp (s.o) Cankk k exp 1 (s,a)
if a E a
To (s, a: Q()) -
otherwise,
where is temperature parameter. In practice, we dynam- ically adapt the temperature (Veličković et al., 2024) as function of the number of moves played and transform state- action values to win probabilities before computing softmax.
The probability of the uniform policy is T' a; a²)) = Ta The prior probability of taking action a in state is
P(s, az (1)) a k) = (1 () (s, (())
(I)
+ (s.""s,;;"))
The root node No is then initialized with the active player, string description of state corresponding to the node, and legal actions (respectively: NNo(1), (o(s), NN(aa The node is then expanded so that child node is added for each action and prior probability attached to the action leading to the child. Then simulations are run: each simulation starts at the root node, actions and children nodes are se- lected according to PUCT until leaf node is expanding and evaluated, and values are backpropagated through the nodes that the simulation visited. After M such simulations, final move a" is selected.
The external search algorithm guided by a learned world model is summarized in Algorithm 1, with subroutines contained in Appendix A. A search is started at an initial game state Su- First, the legal actions a/ and associated state-action values ( (sp, a from active player's perspective are obtained from MAV. The prior function is an e-greedy policy, derived entirely from state-action values comprised of greedy softmax over the top l values, mixed with a uniform distribution over all actions to encourage exploration. Specifically, let a C a be the subset of legal actions a whose values are among the top k-ranked values, or equal a if |a < k. Define the probability
3.1. External Search with State-Tracking MAV
Classical MCTS relies on several components of a game en- gine to simulate the game. MAV replaces these components by combining state tracking, legal action prediction, action value prediction, and terminal state detection in a single model. This allows us to remove the dependency on a game engine, which results in a few benefits. First, we use the board games to showease that MCTS achieves astonishing
"As of May 21, 2025, it is possible to play chess against MAV- small at https: /g/o.. www........o....oo.......eo.oee. /ehhhhhhsaappp
"Note that in practice MAV and MAVlsmall don't 't utilize many natural- lanuual- specific parameters.
4

---

Mastering Board Games by External and Internal Planning with Language Models
Root node of search
computation, we employ a commonly-used optimization in parallel MCTS: virtual counts, which temporarily increase the visit counts by some constant ne during the simulation, which are then removed during the backpropagation phase. For more details, please see Appendix A.
5
4
With low simulation counts, using the virtual losses ac- companied by the fixed virtual counts ne did not strike a satisfactory balance between exploration and exploitation. To address this, we introduce the dynamic virtual counts that dynamically assign more weight to the virtual count values closer to the Ieaf nodes. Suppose simulation m encounters leaf node N₁- We define a virtual count for states-action pairs (st, at) visited in simulation m and leaf N
W a3
b5
Px7
W x
x h1
MAV(s, a)
xe6
a = 2x06
1. New state,
no(m, = min (Amin: [2max
2 ddi [xx]] I),
2. Cluck of teminaa
Lapal muves ah Action valune (!!((),nn)
where dy, represents the depth of a child node Mr relative to the leaf node Ng reached during simulation m and [.] is floor function. As depicted in Figure 7 in Appendix A, it proved beneficial to exponentially decrease the virtual counts starting with the maximum virtual count max at the leaf node which is then halved at each parent up to the root node while maintaining a minimum virtual count memin-
g
Wal
Figure 3. State-tracking MCTS with learned world model.
performance even without access to an explicit world model, which is the case for many interesting real-world problems. Second, it is a step closer towards the internal search with LLMs.
4. Internal Search
In contrast to external search, in internal search the model does not require an external controller. Instead, the search procedure is distilled into the model so that it is capable of (i) evaluating search nodes (states), (ii) expanding nodes while updating the current state, and (iit) backpropagating the results from leaf nodes back to the root node all within single model call. The distillation is done by linearizing search trees into text format and training the model on those linearized trees.
We adapt MCTS (see Algorithm 1) to the learned MAV to predict the state transition from the string description of parent node (s) and action a:- to the child node N₁. as shown in Figure 3. We use the obtained in- formation to store a (predicted) string description 8, of the child node, which is then expanded with legal actions at and their associated state-action values Q (s,, af used compute prior according to Equation (1) and the child's value the maximum over all state-action values, i.e., ea Q10 (st, az).
Data. The prompt for internal search resembles that of MAV, but includes a preamble with search parameters (tree depth and breadth, see Figure 4). The format of the target data is inspired by depth- first order traversal of minimax trees, as an iterative and linearized sequence of minimax tree traversal. Hence, following this format corresponds to algorithmic execution task, akin to CLRS-Text (Markeeva et al., 2024).
MAV may hallucinate and return responses that are improperly-formanne formatted. To address this, for each game, a parser function responsible for translating the output into the next state, legal actions, and their values. If the parsing fails which can only happen if a response violates a pre- defined format a special value of ooo is assigned to the node to avoid future consideration. This procedure makes state-tracking MCTS robust to hallucinations, by explicitly avoiding states where the hallucination occurred.
The training data is based on target search trees, which were constructed using depth 3 (N.B., depth-zero is MAV), by annotating states (e.g., chess states being annotated with Stockfish), and expanding the top 5 moves into trees. This results in high quality target search trees, similar those internally generated by game engines. To diversify training data and enable search budget control for trained models, prompts were composed with diverse search parameters, ranging depth 1-3 and breadth 2-5, and continuations yield corresponding trees that were subsampled to match the pa- rameters while fitting into context size, This necessitated
3.2. Asyne MCTS and Dynamic Virtual Counts
Due to the heavy cost of inference in LLMs, we use an Asynchronous Monte Carlo tree search (Asyne MCTS) that queues multiple leaf evaluations simultaneously (i.e., in a "batch" of simulations). To avoid redundant concurrent
5

---

Mastering Board Games by External and Internal Planning with Language Models
Kinimax breadthe3
Evaluation
all Whest action
(Sstate 2räk) (atga///iFp/00////5555 (ttaal///////////5 tibrstaacton iettrii3> c2e2: sctr132>
sctri26>
Expand
creot::
22d6>
crost <7n?>
Evalustion for node: creat glob>
gamercheago Spray, state sprew action Setate Stop,a all Sheat,action V/eav
Diprev aataee 2r3k1/p3p3/ /0t///////////////////////////// hwtpp///////////////////// aas/st/t////// /tt///////////// /133
Diprev action g366)
A
[Setate trakk/pbpl/hgghttpp 3p/304///
X
A
[Stoppall all d5d4:cetr111
dibd detri23> e5ds seetrkaz atal:setrl1t>>
[Sbeet action d566)
Decision for rode: trest gada>
selecting: dbde "sctelaz>""
c6
xgg
c2
Evaluation for node: croot gage
0.55
saav gameschese> lorev state Sprev action Kstate Stop all Kiest.action </mave (Sprev artate 2r3k1/p3p3/4400 wwtp://///////////////////////// /tt./////mm/m// /133
Diprev action g2883
[latete httk://as///ttppppp/////// http///////////////////// v]
[Step all
d5c5:setr21> cof4:setr122 scbd:sctr1t>
[ibest action e6f4)
A
Decistinn for rode: crost 23g60
Selecting: odfe "cctr122>"
Evaluation for node: <root clu2>
A
A
A A
<aav gameschese> lorev state Spree action Kstate Stop all Thest action </mave [iprev strev 2r3k1/p3p3/4w/ P//3///1PP//B / htt////Pl//P/P////////////
A
A
A
X
A
A
Apprevacctoo c2e23
Distate httpp/////////////////////////// /PP21111/1 w]
[Stopaall --- bibb:<etril>> edre: <etri3t kite: <otrl>>>
Jibest,cction action =Sf4]
best action: Wxd6 v(e) 0.3
aestioacion: Q1 v(jo
best. action: CI
Secision for rode: crost cawt>
v(9)
selecting: adf4 "cctrlaty"
Seciition for rode: croots gldt "cctrlaD" glg Selecting p3g "Kctrl43" Playing glpsi
"Sctrlage cled: "cctrlap"
01)
0.5. ( 0g)
0.66, o(.,ag) 0.5
Selecting
xg6
Figure 4. Internal search input prompt and response (breadth=3, depth=1). The response is an actual model response, but for brevity, only show some of the stop all action-valle value pairs. The corresponding minimax search tree is visualized on the right. MAV assigns Wil d6 the highest value, while internal search identifies the only winning move, xg6.
excluding the biggest parameter combination (i.c., omitting depth 3, breadth 5 examples).
well as external Elo ratings where possible.
For chess evaluation, we rely on the state-of-the-as en- gine Stockfish at different playing strengths to estimate the widely used external Elo rating. This is done by calibrating the internal Elo with ear fit. As an additional, we include the Ext-BoN model (Ru- oss et al., 2024a), which showed Grandmaster- perfor- mance on chess with Transformers (see Appendix for details). We use set of Top Chess Engine Championship (TCEC) opening positions (tce) (see Table 5 in Appendix G). In each match-up between two agents, specific opening is used, and agents swap seats to ensure each agent plays each opening both as black and as white. Every instance of Stockfish is run with 2 seconds of search time. We delin- eate further our evaluation setting together with the closest related works in Appendix B and Appendix C.
An example internal search trace predicted by the trained in- ternal search MAV (MAV-IS), along with the corresponding search tree, is shown in Figure 4.
ratings using a lin-
Training details. We leveraged the pre-trained MAV and fine-tuned it using a mixture of 60% MAV data and 40% search data. Fine-tuning was run for 20,000 steps, using a batch size of 512. Thus the model saw an order of magnitude more tokens during the MAV pre-training compared to the fine-tuning on internal search traces.
5. Experiments
5.1. Evaluation
Evaluating LLMs in general and reasoning specifically is a broad field (Chang et al., 2024), within which games have been established as an evaluation benchmark (Costarelli al., 2024; Duan et al., 2024). We evaluate MAV language models in a gumes league which head-to-heat head match-ups, sampling combinations uniformly at random from pool of MAV and baseline agents. We report internal Elo ratings (relative Elo only between members of the population) as
An overall comparison of the playing strength of different methods is shown in Table 1. Next, we perform deeper dive into the performance of the different approaches.
5.2. Multi-Action- Value Results
In terms of chess playing strength, MAV reaches an external Elo of 2923 when using mean scoring and 2875 when using
6

---

Mastering Board Games by External and Internal Planning with Language Models
of the positions played by MAV in evaluation appear in its training data, while between moves 20 and 50, virtually no position has been seen by MAV during training. These results show that in order to avoid losing games during middlegame, MAV is required to generalize.
Table 1. Performance comparison of different agents in Chess, Chess960, Connect Four, and Hex. In refers to the number of simulations. The external Elos are esti- mated from the internal Elos achieved among agents.
agents. M
Important: The external Elos the Stockfish agents are anchored the CCLR Blitz Elos. Therefore, the Elo estimates for the MAV- MCTS agents are not accurate as those agents would not be able play at blitz time controls.
5.3. External Search Results
For our external-MCTI agents, we tune parree-arrmettrss using a combination of manual and head-to-head compar- isons and report the details in Appendix A. We also include a basic MCTS baseline, which refers to MCTS with a uniform prior and random rollouts run with 100 simulations.
Chess
Cbess960
Connect Four
Hex
Agent
Int. Elo
Ext. Elo
Int. Elo
Int. Ele
Stokhih-L200
1950
3474
2053
MAV-MCTS.M 2000)
1707
3209
1602
Stnekfic--.19
1680
3191
1645
Sisckfsh--L88
1655
3170
1604
MAV-MCTS(M- = 1000)
1633
3157
1561
499
We first analyze the performance of the scoring method for the value function when used within MAV-MCTS. We do this by running a large tournament between various models with the details, including results shown in Figure 9 in Appendix A. MAV-MCTS with mean scoring performs noticeably better in all cases. Hence, for the remainder of the external search experiments, we report results only for the mean scoring method.
Strckfish-1.11
1604
3141
1509
MAV-MCTSiM 500)
445
MAV-MCTS(M 250)
1543
3088
1433
428
1002
Streffihh-.15
1530
3069
1436
MCV-MCTS:M 100)
1435
2988
1377
342
884
Est-BoN (Ruoss
2024g)
MAY (mean sooring)
1367
2923
1278
MAY (max scoring
1517
3875
1213
98
713
(max scuring)
2820
Suckfish-L10
1225
2788
1141
Streffih--.5
808
2203
760
Stockfish-LD LO
515
1320
533
MCTS
805
We then run an even bigger tournament including Ext-BoN with the results shown in Table 1. The total number of games played in each respective tournament were 14689 for Chess, 4480 for Chess960, 2189 for Connect Four, and 6334 for Hex. In chess, MAV-MCTS with just 100 simulations achieves an internal Elo 68 higher than the searchless MAV and generally Elo performance improves logarithmically as function of the number of simulations as illustrated in Figure 5 (right).
Table 2. Error rate analysis for MAV in chess positions. We con- sider positions drawn from Lichess puzzles, and from a dataset of randomly generated boards that never occur in the course of normal gameplay, and are highly out-of-distribution compared to the training data.
Lichess puzzles
OOD
positions
In the case of Chess960, where every game begins with a random position (among a preset 960 initial positions), we obtain comparable results to Chess. In the case of Connect Four, we notice that MAV-MCTS is particularly helpful in improving upon MAV, with all agents improving by at least 244 Elo. Similarly to Chess, the improvements consistently rise with added simulations, but here we notice a relatively smaller performance gain of MAV over a basic MCTS, and larger improvements of MAV-MCTS over MAV.
$best_action legal
0.999
0.996
stop_all precision
0.999
0.997
stop_all recall
1.000
0.997
$trop_a11 F1 score
0.999
0.995
Updated FEN correct
1.000
0.996
max scoring. It thus outperforms several strong baselines, including Stockfish-LLU and performs comparably with the Ext-BoN model by Ruoss al. (2024a). For Chess960 MAV outperforms Ruoss et al. (2024a), perhaps due to being trained explicitly on Chess960 data.
Since our final model was not adequately trained with state- tracking capabilities for Hex, in the Hex results only game engine is used to determine legal actions, state transitions, and terminal states. In contrast to Connect Four, we notice a large improvement between basic MCTS and MAV in Hex, and improvements similar to chess from search. We suspect that this is due to the relative complexity of the games, but more research is needed clarify the reason for these differences. It should be possible to support the engine-free logic in Hex similarly to Chess going forward. Across all games, external MCTS performs consistently better as the number of simulations is increased.
In Table 2, we analyze the legal move rate, the precision and recall of the predicted & stop_all moves, and the accuracy of predicting the next FEN state. The results demonstrate that MAV is able to reliably perform all of these actions.
Generalization. During the opening and endgame, human players often rely on memorized opening lines and endgame theory, while middlegame requires more calculation and intuition. In Appendix D, we report the same pattern in the games of MAV and a concrete position where the model displays a creative play in unseen position. Overall, 10%
7

---

Mastering Board Games by External and Internal Planning with Language Models
2930 -
b
3200
2920
3150
d-2
2910
Elo
3100
2900
3050
2890
b=3
d=1
3000
2880
MAV
2870
10a
10a
10a Test-time tokens
10
Number of simulations (MCTS)
Figure 5. Chess Elo improves with more test-time compute. Left: External search results, varying the number of simulations / MAV model calls. Right: Internal search results, varying the breadth (b) and depth (d) of the minimax search performed in single model call. The a-ixis shows the number of tokens in the prompttresponse
5.4. Internal Search Results
address namely, the ability to acquire or generate large quantities of game play data, as well as the availability of reliable solvers or game engines that can be used to annotate this data in order create an appropriate training curriculum for the model.
For our internal search experiments, we vary the depth and breadth parameters of the minimax search, up to breadth 4 and depth 2. We map these different configurations into token counts by computing the average length of the prompt + response per configuration in our training data. Figure 5 (right) shows the performance of MAV-IS as the function of token counts. We can see that playing strength, measured by external Elo?, increases with the search budget.
Another important limitation of our MAV models is that they have been trained exclusively on game data, and therefore do not possess the ability to communicate verbally using natural language. However, there should be no fundamental obstacles in achieving the same ability in potentially larger models that may also incorporate natural language data, as we train the exact same architecture and tokenizer used in classical text-based LLMs.
We also analyzed if the MAV-IS search produces the tree of the requested shape whenever possible, considering the available number of legal moves at each node. MAV-I constructed accurately shaped tree 99.6% of the time on sample 5980 positions taken from existing games.
It remains an open question how to design good value functions for general conversational task, and how to incorporate these value functions or other highly specialized knowledge in training such that the model can draw upon them flexibly at inference time, in a wide variety of conversational contexts.
For an example of how internal search can improve playing strength, see Figure 4. In this example, the initial, MAV section, of the response predicts d6 as the best move. However, as the internal search continues, the model is able to find better move W xg6 after exploring the top-3 lines one step further. This points to the model's ability self- correct, which is an important capability of LLMs that can reason (Kumar et al., 2024).
7. Conclusions
This paper demonstrates the capacity of LLMs to learn strong value functions and act as a world model across mul- tiple perfect information games. This enables their use in MCTS, where we observe significant performance gains of approximately +300 Elo points even with fairly limited search budget. Going further, we find that training on search traces enables the model to learn an effective search proce- dure that can be executed via a single model call. This adds to the rapidly growing body of literature highlighting the promise of planning and reasoning with LLMss
6. Discussions and Limitations
Despite promising results in the domain of perfect infor- mation board games indicating the potential of external and internal planning with LLMs, our initial study makes number of assumptions that future work may need to
'For the internal search experiments, we stopped games once either side had reached a decisive, 1200+ centipawn advantage. This was done since the internal search training data did not in- clude quickest wins, which would sometimes result in the model aimlessly moving pieces around in winning positions.
8

---

Mastering Board Games by External and Internal Planning with Language Models
Acknowledgements
Besta, M., Blach, N., Kubicek, A., Gerstenberger, R., Pod- stawski, M., Gianinazzi, L.., Gajda, J., Lehmann, T. Niewiadomski, H., Nyczyk, P., and Hoefler, T. Graph of thoughts: Solving elaborate problems with large language models. In AAAI, pp. 17682-17690. AAAI Press, 2024.
We would like to thank Alexis Jacq, Yoram Bachrach, and Roma Patel for their contributions early on in the project, and GM Dogdan-Daniee Deac, GM Dharshan Kumaran, and Luka Rimanié for playing test games and providing feed- back on the MAV model. We are grateful to Aliaksei Sev- eryn, David Silver, Jessica Hamrick, Gabriel Dulac-Arolo Been Kim, Simon Osindero, Matthew Lai, and Demis Hass- abis for their support and advising on the project.
Borazjanizadeh, N. and Piantadosi, S. T. Reliable rea- soning beyond natural language, 2024. URL https:
/ //arxiv. otg///ivorrreeee abs/ 22007 2407.11373.
Bronstein, M. M., Bruna, J., Cohen, T., and Veličković, P. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104.13478, 2021.
Impact Statement
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners. Advances in neural information processing systems, 33: 1877-1901, 2020.
References
Top chess engine championship. tcec-chese com/.
URL. https://
Burns, C.. Izmailov, P., Kirchner, J. H., Baker, B., Gao, L., Aschenbrenner, L.,, Chen, Y., Ecoffet, A., Joglekar, M., Leike, J., et al. Weak-to-strong generalization: Eliciting strong capabilities with weak supervision. arXiv preprint 2rXi::23/2.0995 2023.
Torres and his remarkable automatic devices - would substitute machinery for the human mind. Scientific Amer- ican Supplement, 80(2079):296, November 1915.
Chang, Y., Wang, X., Wang, J., Wu, Y., Yang, L., Zhu, K., Chen, H., Yi, X., Wang, C., Wang, Y., al. A survey on evaluation of large language models. ACM Transactions Intelligent Systems and Technology, 15(3):1-45, 2024.
Acher, M. Debunking the chessboard: Con- fronting gpts against chess engines to estimate elo ratings and assess legal move abilities, 2023. URL https: http://boo..attieucchchceheee com/ o
Chaslot, G.-B., Winands, M., van den Herik, H., Uiterwijk, J., and Bouzy, B. Progressive strategies for monte carlo search. New Mathematics and Natural Computation, 4(3):343-35 2009.
Agarwal, R., Singh, A., Zhang. L. M., Bohnet, B., Chan, S., Anand, A., Abbas, Z., Nova, A., Co-Reyes, J. D., Chu, E., et al. Many-shot in-context learning. arXiv preprint arXiv:2404.1100 2024.
Chaslot, G. M. B., Winands, M. H., and van Den Herik, J. Parallel Monte-Carlo tree search. In Computers and Games: 6th International Conference, CG 2008, Beijing, China, September 29- October 1, 2008. Proceedings 6, pp. 60-71. Springer, 2008
Aksitov, R., Miryoosefi, S., Li. Z., Li, D., Babayan, S., Kop- parapu, K., Fisher, Z., Guo, R., Prakash, S., Srinivasan, P., Zaheer, M., Yu, F., and Kumar, S. Rest meets react: Self-
improvement for multi-step reasoming Ilm agent, 2023. https:/ //pps:///rree //axiivvv. www.wiiwwrg//..............ooote /2cs/223112 0003.
Chen, C., Wang, X., Lin, T.-E., Lv, A., Wu, Y., Gao, X., Wen, J.-R., Yan, R., and Li, Y. Masked thought: Simply masking partial reasoning steps can improve mathemati- cal reasoning learning of language models. arXiv preprint arXiv:2403.02. 1781 2024a.
Anonymous. Implicit search via discrete diffusion: A study on chess. In Submitted to The Thirteenth In- ternational Conference on Learning Representations, 2024. URL htttps://operreet 1d=A9y3LFX4ds. under review.
net. forum?
Chen, L., Tong, P., Jin, Z., Sun, Y., Ye, J., and Xiong, H. Plan-on-graph: Self-correcting adaptive planning of large language model on knowledge graphs, 2024b. URL https: /at:://azzz /aa//aiiivv./////////aaa////aavv org. wwtp:/wwwwwgga//////..eaa http//bss//211/.. 23875.
Bang, Y., Cahyawijaya, S., Lee, N., Dai, W., Su, D., Wilie, B., Lovenia, H., Ji, Z., Yu, T., Chung, W., Do, Q V., Xu, Y., and Fung, P. A multitask, multilingual, multimodal evaluation of chatgpt on reasoning, hallucination, and in- teractivity, 2023. URL https: //axxiv.. orgg abs/ 2302. 04023.
Chen, Z., Deng. Y., Yuan, H., Ji, K., and Gu, Q. Self-play fine- munint converts weak language models to strong lan- guage models, 2024c. URL https: //////aaa //arxiivvor. abs/2401. 01335.
9

---

Mastering Board Games by External and Internal Planning with Language Models
Chen, Z.,, White, M., Mooney, R., Payani, A., Su, Y., and Sun, H. When is tree search useful for IIm planning? it depends on the discriminator, 2024d. URL https: // //arxiv. org/ abs /202..242... 10890.
Feng, G., Zhang, B., Gu, Y., Ye, H., He, D., and Wang, L, Towards revealing the mystery behind chain of thought: theoretical perspective. Advances in Neural Information Processing Systems, 36, 2024a.
Chia, Y. K., Han, V. Y. Ghosal, D., Bing, L., and Poria, Puzzlevqa: Diagnosing multimodal reasoning challenges of language models with abstract visual patterns, 2024. URL hww.s:tpp/////c..tmm araiiiiiiv....... orgg abs / 2403. 13315.
Feng, X., Luo. Y., Wang, Z., Tang, H., Yang. M., Shao, K., Mguni, D., Du, Y., and Wang, J. Chessgpt: Bridg- ing policy learning and language modeling. 2023. URL https: //wpivaarxvvvv/vvv org/ 2206 09200.
Costarelli, A., Allen, M., Hauksson, R., Sodunke, G., Hari- haran, S., Cheng, C., Li, W., and Yadav, A. Gamebench: Evaluating strategic reasoning abilities of LLM agents. arXiv preprint arXiv:2406. 06611,, 2024.
Feng, X.,
Wan, Z., Wen, M., McAleer, S. M., Wen, Y., Zhang, W., and Wang. Alphazero-like tree-search can guide large language model decoding and training, 2024b. URL https: / wwwai. abs 2309.17172
Cui, W., Bi, K., Guo, J., and Cheng, More: Multi-modal retrieval augmented generative commonsense reasoning. arXiv preprint ar arXiv:2402. 2024.
Gan, E., Zhao, Y., Cheng, L., Mao, Y., Goyal, A., Kawaguchi, K., Kan, M.-Y, and Shieh, M. Reasoning ro- bustness of Iims to adversarial typographical emors, 2024. URL https::/p///......t. a x www.wii.rrrr..oooooeooooo.oooeee www.//rggbbo.o..... abs / 241 05345.
Czech, J., Blüml, J., Kersting, K., and Steingrimsson, H. Representation matters for mastering chess: Improved feature representation in alphazero outperforms switching to transformers. arXiv preprint arXiv:2304. 14918, 2024.
Gandhi, K., Sadigh, D., and Goodman, N. Strate- gic reasoning with language models. arXiv preprint arXiv:2305.19165. 2023.
Dagan, G., Keller, F., and Lascarides, A. Dynamic planning with a I1m, 2023, URL hittps://arxx org/ abs/ 2308. 06391.
Gandhi, K., Fränken, J.-P., Gerstenberg. T., and Goodman, N. Understanding social reasoning in language models with language models. Advances in Neural Information Processing Systems, 36, 2024a.
Ding, R., Zhang, C.. Wang, L., Xu, Y., Ma. M., Zhang, W., Qin, S., Rajmohan, S., Lin, Q., and Zhang, D. Every- thing of thoughts: Defying the law penrose triangle for thought generation. arXiv preprint arX1v:2311.04254, 2023.
Gandhi, K., Lee, D., Grand, G., Liu, M., Cheng, W., Sharma, A., and Goodman, N. D. Stream of search (SoS); Learn- ing to search language, 2024b.
Gao, C. and Pawlewicz, J. neurobenzene: An improved benzene project for playing and solving hex with the help deep neural networks. URL aattps://githir com/ cqaao/ neurobenzene.
Duan, J., Zhang, R., Diffenderfer, J., Kailkhura, B., Sun, L., Stengel-Eskin, E., Bansal, M., Chen, T., and Xu, K. Gtbench: Uncovering the strategic reasoning limita- tions of Ilms via game-theoretic evaluations, 2024. URL https: / arxiv. org/ abs / 2402. 12348.
Gao, T., Fisch, A., and Chen, D. Making pre-trained lan- guage models better few-shot learners. arXiv preprint arXiv:2012.15723, 2020.
Elo, A. E. The proposed uscf rating system, its development, theory, and applications. Chess life, 22(8):242 247, 1967.
Gemini Team, Anil, R., Borgeaud, S., Wu, Y., Alayrac, J.- B., Yu, J., Soricut, R., Schalkwyk, J., Dai, A. M., Hauth, A., et al. Gemini: A family of highly capable multi- modal models, 2024. URL abs/2312.00 11805.
Ensmenger, N. Is chess the drosophila of artificial intelli- gence? a social history of an algorithm. Social studies of science, 42(1):5-30, 2012.
Fang, M., Deng, S., Zhang, Y., Shi, Z., Chen, L., Pech- enizkiy, M., and Wang, J. Large language models are neurosymbolic reasoners. In AAAI, pp. 17985-17993. AAAI Press, 2024.
Giadikiaroglou, P., Lymperaiou, M., Filandrianos, G., and Stamou, G. Puzzle solving using reasoning of large lan- guage models: A survey, 2024. URL https: /tte:///axxi.. /arxiv.
org abs/ 2402.22.. 11291.
Farebrother, J., Orbay, J., Vuong, Q., Taiga, A. A., Chebotar, Y., Xiao, T., Irpan, A., Levine, S., Castro, P. S., Faust, A., Kumar, A., and Agarwal, R. Stop regressing: Train- ing value functions via classification for scalable deep rl. 2024. URL https: / arxiv. orgo abs abs/2403. 03950.
Gramopadhye, O., Nachane, S. S. Chanda, P., Ramakrish- nan, G., Jadhav, K. S., Nandwani, Y., Raghu, D., and Joshi, S. Few shot chain-of tf-thuugttt driven reasoning to prompt Ilms for open ended medical question answering. arXiv preprint arXiv:2403. 200.:2090000 2024.
10

---

Mastering Board Games by External and Internal Planning with Language Models
Gu, J., Li, C., Liang. Y., Shi, Z., Song, Z.,, and Zhou, T. Fourier circuits in neural networks: Unlocking the potential of large language models in mathemati- cal reasoning and modular arithmetic. arXiv preprint arXiv:2402.09469, 2024.
game agents, 2024b. URL https://arxiv.org abs/2404. 02039.
Hu, S., Huang, T., and Liu, L. Pokellmon: human- parity agent for pokemon battles with large language models, 2024c. URL https:/ /ppps://arxivv httpi/iiiiio.a//..aaa.///. /abs/ 2402. 0.02.011110 01118.
Guo, K., Nan, B., Zhou, Y., Guo, T., Guo. Z., Surve, M., Liang, Z.., Chawla, N. V., Wiest, O., and Zhang, X. Can LLMs solve molecule puzzles? a multimodal benchmark for molecular structure elucidation. In The Thirty-eight Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2024. URL https: // //openreiiew net/ forum? iddtdddllmm 1m..bmm.
Huang, J., Chen, X., Mishra, S., Zheng, H. S., Yu, A. W., Song, X., and Zhou, D. Large language models can- not self-correct reasoning yet, 2024. URL https: //arxiv. wttp://..rr/abb//11.00000
Jenner, E., Kapur, S., Georgiev, V., Allen, C., Emmons, S., and Russell, S. Evidence of learned look-ahead in
Hadi, M. U., Qureshi, R., Shah, A., Irfan, M., Zafar, A., Shaikh, M. B., Akhtar, N., Wu, J., Mirjalili, S., et al. A survey on large language models: Applications, challenges, limitations, and practical usage. Authorea Preprints, 2023.
chess-playing neural network, 2024. URL https: / //aaxivv..v///////a/.aa/eaaa //taaii..rggaa//////./. www.oogg///a...... /4066 0087700777
Ji, D., Zhu, L.,, Gao, S., Xu, P., Lu, H., Ye, J., and Zhao, F. Tree-of tree-of-tabbe: Unleashing the power of Ilms for enhanced large-scale table understanding. 2024. URL https: // //arxiv.. org/ /ttgab///////eeeee/e///g/e/eaaa/ 22t//241.1100 08516.
Hamade, K., Mcllroy-Your R., Sen, S., Kleinherg, J., and Anderson, A. Designing skill-compatible ai: Method- ologies and frameworks in chess, 2024. URL https: //a //rxiiv. www.iiiorgg/...eeee.......ooooee abwaabas24444 2405. 05066.
Jiang, J., Chen, Z., Min, Y., Chen, J., Cheng, X., Wang, J., Tang, Y., Sun, H., Deng, J., Zhao, W. X., Liu, Z., Yan, D., Xie, J., Wang, Z., and Wen, J.-R. Technical report: Enhancing Ilm reasoning with reward-guided tree search, 2024. URL https:/: /ttps////avvv....//a .ovvvorgg.. /abs/ 1111.11694,
Hao, S., Gu, Y., Ma. H., Hong, J., Wang, Z., Wang. Z. and Hu, Z. Reasoning with language model is planning with world model. arXiv preprint arXiv:2305.14992. 2023.
Jin, Z., Chen, Y., Leeb, F., Gresele, L., Kamal, O., Lyu, Z.. Blin, K., Gonzalez Adauto. F., Kleiman -einner, M., Sachan, M., et al. Cladder: A benchmark to assess causal reasoning capabilities of language models. Advances in Neural Information Processing Systems, 36. 2024.
Haresh, S., Dijkman, D., Bhattacharyya, A., and Memisevic, R. Clevrskills: Compositional language and visual reason- ing in robotics. In The Thirty-eight Conference on Neu- ral Information Processing Systems Datasets and Bench- marks Track, 2024. URI. https: ropenreviee net/ / coooummicce 65026.
Kahneman, D. Thinking, Fast and Slow. Farrar, Straus and Giroux, 2011.
Horton, J. Large language models as simulated economic agents: What can learn from homo silicus? Technical report, National Bureau of Economic Research, 2023.
Kil, J., Mai, Z.,, Lee, J., Chowdhury, A., Wang, Z., Cheng, K., Wang. L., Liu, Y., and Chao, W.-L. MLLM- compbench: A comparative reasoning benchmark for multimodal LLMs. In The Thirty-eight Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2024. URL https:// openreview, net. forum? Fi
Hosseini, A., Yuan, X., Malkin, N., Courville, A., Sordoni, A., and Agarwal, R. V-star: Training verifiers for self- taught reasoners. arXiv preprint arXiv:2402.00 06457, 2024.
Hu, M., Zong, L., Wang. H., Zhou, J., Li, J., Gao, Y., Wong, K.-F., Li, Y., and King, I. SeRTS: Self-rewarding tree search for biomedical retrieval-augmenner genera- tion. In Al-Onaizan, Y., Bansal, M., and Chen, Y.-N. (eds.), Findings of the Association for Computational Lin- guistics: EMNLP 2024, pp. 1321-1335. Miami, Florida, USA, November 2024a. Association for Computational Linguisties. URL httph::t::/// http:///aaaaatttttaaaeee .org/ 2024.8 f
Koh, J. Y., McAleer, S., Fried, D., and Salakhutdinov, Tree search for language model agents, 2024. URL https:/ / /awx/vivvvv///////v////aa////aav org/ abs 2200 01476.
Kojima, T., Gu, S., Reid, M., Matsuo, Y., and Iwasawa, Y. Large language models are zero-shot reasoners. Ad- vances in neural information processing systems, 35: 22199-22213, 2022.
Hu, S., Huang, T., Ilhan, F., Tekin, S., Liu, G., Kompella, R., and Liu, L. A survey on large language model-based
Kumar, A., Zhuang, V., Agarwal, R., Su, Y., Co-Reyes, J. D., Singh, A., Baumli, K., Iqbal, S., Bishop, C., Roelofs,

---

Mastering Board Games by External and Internal Planning with Language Models
R., et al. Training language models to self-correct via reinforcement learning. arXiv preprint arXiv:2409.12911 2024.
Lu, P., Peng, B., Cheng, H., Galley, M., Chang, K.-W., Wu, Y. N., Zhu, S.-C., and Gao, J. Chameleon: Plug-and- play compositional reasoning with large language models. Advances in Neural Information Processing Systems, 36, 2024.
Lanctot, M., Lockhart, E., Lespiau, J.-B., Zambaldi, V., Upadhyay, S., Pérolat, J.. Srinivasan, S., Timbers, F., Tuyls, K., Omidshafiei, S., al. Openspiel: frame- work for reinforcement learning in games. arXiv preprint arXiv: 09453, 2019.
Markeeva, I.., McLeish, S., Ibarz, B., Bounsi, W., Ko- zlova, O., Vitvitskyi, A., Blundell, C., Goldstein, T., Schwarzschild, A., and Veličković, P. The clrs-text algo- rithmic reasoning language benchmark. arXiv preprint arXi::2406.04229, 2024.
Laskin, M., Wang, L., Oh, J., Parisotto, E., Spencer, S., Steigerwald, R., Strouse, D., Hansen, S., Filos, A., Brooks, E., Gazeau, M., Sahmi, H., Singh, S., and Mnih, V. In-context reinforcement learning with algorithm distilla- tion, 2022. URL https: / arxiv. org/ abs /2110. 14215.
Markowitz, E., Ramakrishna, A., Dhamala, J., Mchrabi, N., Peris, C., Gupta, R., Chang, K.-.,, and Galstyan, A. Tree-of-traversals: A zero-shot reasoning algorithm for augmenting black-box language models with knowledge graphs, 2024. URL https: htttp://axxxxx http://axxvi.rr../.. abs/ 2407.21355
Lee, J., Yang, F., Tran, T., Hu, Q., Barut, E., Chang, K.- W., and Su, C. Can small language models help large language models reason better?: Am-guided chain-of- thought. arXiv preprint arXiv:2404.0344 2024.
McCarthy, J. Chess as the drosophila of ai. In Computers, chess, and cognition, pp. 227-237. Springer, 1990.
Lehnert, L.., Sukhbaatar, S., Su, D., Zheng, Q., Mevay, P., Rabbat, M., and Tian, Y. Beyond a Better planning with transformers via search dynamics bootstrapping, 2024.
Menon, A. Bridging chess mastery and ai innovation: The making of llm-chesscoach, 2023.
Menon, S., Zemel, R., and Vondrick, C. Whiteboard-of- thought: Thinking step-by-step across modalities, 2024. URL https: httttp:://arxiv.coo wwtp://wwwwww./.a//aaae/ooosse/ hbtp:///bba/aa/aa 14562.
URL htthtt://// htttt::://axxv..ooo wttp://gp/p//.....2oeo. 14083.
Li, J., Le, H., Zhou, Y., Xiong, C., Savarese, S., and Sa- hoo, D. Codetree: Agent-guides tree search for code generation with large language models, 2024a. URL bttts:://rrxte org/ httgg//b////////////g/////// abss/2111 04329.
Minaee, S., Mikolov, T., Nikzad, N., Chenaghlu, M., Socher, R., Amatriain, X., and Gao, J. Large language models: survey. arXiv preprint wwXiv:2402.061990 2024.
Li, N., Gao, C., Li, Y., and Liao, Q. Large language model- empowered agents for simulating macroeconomic activi- ties. arXiv preprint arXiv:2310. 10436, 2023.
Mirsoleimani, S. A., Plaat, A., van den Herik, J., and Vermaseren, An analysis of virtual loss in parallel MCTS. International Conference on Agents and Artificial Intelligence, 2017. URL https: /api. semanticscholare www.oola.rrrrg///oooooooo CorpporrrpsDDS00
Li, Y., Zhou, Q. Luo, Y., Ma, S., Li, Y., Zheng, H.-T., Hu, X., and Yu, P. S. When LLMs meet cunning texts: A fallacy understanding benchmark for large language models. In The Thirty-eighi Conference on Neural In- formation Processing Systems Datasets and Benchmarks Track, 2024b. URL https:///// http::////peeeeieew. / Borum?id=JayeBal
4.
Mitra, C., Huang, B., Darrell, T., and Herzig, R. Composi- tional chain-of-thought prompting for large multimodal models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 14420- 14431, 2024.
Light, J., Cai, M., Chen, W., Wang, G., Chen, X., Cheng, W., Yue, Y., and Hu, Z. Strategist: Learning strategic skills by Ilms via bi-level tree search, 2024. URL https: //arxiv. org/ abs/ 2abs/2460 2408 10635.
Monroe, D. and Leela Chess Zero Team, T. Mastering chess with a transformer model, 2024. URL https: / //arxiv.. hwtp:oorg/aaa /tsp//b/////// abw.///9/990 2409 12272.
Nguyen, M. and Shareghi, E. One step at a time: Language agents are stepwise planners, 2024. URL https:// arxiv. wawvvoorg/bbss 2211. 08432.
Long. Large language model guided tree-of-thought arXiv preprint (xXiv:2305.0829) 2023.
Lu, P. Mishra, S., Xia, T., Qiu, L., Chang, K.-W., Zhu, S.-C., Tafjord, O., Clark, P., and Kalyan, A. Learn to explain: Multimodal reasoning via thought chains for science question answering. Advances in Neural Infor- mation Processing Systems, 35:2507-2521, 2022.
Nori, H., Usuyama, N., King, N., McKinney, S. M., Fer- nandes, X., Zhang, S., and Horvitz, E. From med- prompt to ol: Exploration run-time strategies for medical challenge problems and beyond, 2024. URL 03590.
https: fttpp://arxiv.org///e 2413033990
12

---

Mastering Board Games by External and Internal Planning with Language Models
Paranjape, B., Lundberg, S., Singh, S., Hajishirzi, H., Zettle- moyer, L.,, and Ribeiro, M. T. Art: Automatic multi-step reasoning and tool-use for large language models. arXiv preprint arXiv:2303. 090144 2023.
Ruoss, A., Pardo, F., Chan, H., Li, B., Mnih, V., and Ge- newein, T. LMAct: A benchmark for in-context imitation learning with long multimodal demonstrations, 2024b. URL https::///....... / arxiv. wwtp:/orgggaabaa/aaaeaae 01441.
Parekh, T., Prakash, P., Radovic, A., Shekher, A., and Savenkov, D. Dynamic strategy planning for efficient question answering with large language models, 2024. URL https: /tapctps///rii..../// org/ abs/ 23511.
Saab, K., Tu, T., Weng, W.-H., Tanno, R., Stutz, D., Wul- czyn, E., Zhang, F., Strother, T., Park, C., Vedadi, E., et al. Capabilities of gemini models in medicine. arXiv preprint arXiv:2404. 18416, 2024.
Pfau, J., Merrill, W., and Bowman, S. R. Let's think dot by dot: Hidden computation in transformer language mod- els, 2024. URL https:tt...... arxiv. org www.or////////../../eee 15758.
Saparov, and He, H. Language models are greedy rea- soners: A systematic formal analysis of chain-of-thought, arXiv preprint arXiv:2210.012444 2022.
Schaul, T., Togelius, J., and Schmidhuber, Mea- suring intelligence through games. arXiv preprint arXhv:1109.3314, 2011.
Plaat, A., Wong, A., Verberne, S., Broekens, J., van Stein, N., and Back, T. Reasoning with large language models, survey, arXiv preprint 24v 2024.
Schrittwieser: J., Antonoglou, I., Hubert, T., Simonyan, K., Sifre, L., Schmitt, S., Guez, A., Lockhart, E., Hassabis, D., Graepel, T., Lillicrap, T., and Silver, D. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839):604-6666 2020. doi: 10.1038/ $41586-020-03051-44 URL https: / org/10.
Press, O., Zhang, M., Min, S., Schmidt, L., Smith, N. A., and Lewis, M. Measuring and narrowing the com- positionality gap in language models. arXiv preprint arXiv:22/0.03330, 2022.
Prystawski, B., Li, M., and Goodman, N. Why think step by step? reasoning emerges from the locality of experience. Advances in Neural Information Processing Systems, 36, 2024.
Shao, H. Qian, S., Xiao, H., Song, G., Zong. Z., Wang, L., Liu, Y., and Li, H. Visual cot: Advancing multi-modal language models with comprehensive dataset and bench- mark for chain -f-hhughth reasoning. In The Thirty-eight Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2024a. URL https: / //operrevii eww net/ forum? d=aXe CbMFFJ.
Putta. P., Mills, E., Garg. N., Motwani, S., Finn, C.. Garg, D., and Rafailov, R. Agent q: Advanced reasoning and learning for autonomous ai agents, 2024. URL https: //arxiv. lllaxii.orgg//eooeee......oo abs/ 2abb//400 /208..2488.0 07199.
Rafailov, R., Hejna, J., Park, R., and Finn, C. From r to g": Your language model is secretly f-function, 2024. URL https: //apii/aaaiv..///a org/ abs/ 2404. 12358.
Shao, Z., Gong, Y., Shen, Y., Huang, M., Duan, N., and Chen, W. Synthetic prompting: Generating chain-of- thought demonstrations for large language models. In In- ternational Conference on Machine Learning, pp. 30706- 30775. PMLR, 2023.
Rasal, S. and Hauer, J. Optimal decision making through scenario simulations using large language models, 2024.
URL //axiiiv://///ivv./a/aa org abs/ /aabbs//4407 2407.44400 06866.
Shao, Z., Wang, P., Zhu, Q. Xu, R., Song, J., Zhang, M., Li, Y., Wu, Y., and Guo, D. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03330 2024b.
Rebstock, D., Solinas, C., Sturtevant, N. R., and Buro, M. Transformer based planning in the observation space with applications to trick taking card games, 2024. URL https: /aaxiviiiiv.//a.//aaaa//aaaaavva org/ abs 2404 13150.
Shi, F. Suzgun, M., Freitag, M., Wang, X., Srivats, S., Vosoughi, S., Chung, H. W., Tay, Y., Ruder, S., Zhou, D., et al. Language models are multilingual chain-of-thought reasoners. arXiv preprint arXiv:2210.03057 2022.
Ren, A. Z., Ichter, B., and Majumdar, A. Thinking forward and backward: Effective backward planning with large language models, 2024. URL hwwpt:tt////eee http:://aaxxv.oogg//p abs/ 22412411111 11.110000 01 790.
Shi, W., Hu, Z., Bin, Y., Liu, J., Yang. Y., Ng. S.-K., Bing, L., and Lee, R. K.WW Math-llava: Bootstrapping math- ematical reasoning for multimodal large language mod- els, 2024. URL ht : / /arxiv. www.v.oo.//ooo.o......o.oo.ooo.r hbs//ab//aa 2406. 17294.
Ruoss, A., Delétang, G., Medapati, S., Grau-Moya, J., Wen- liang, L. K., Catt, E., Reid, J., Lewis, C. A., Veness, J., and Genewein, Amortized planning with large-scale transformers: A case study on chess. In NeurlPS, 2024a.
13

---

Mastering Board Games by External and Internal Planning with Language Models
Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, I.., Kumaran, D., Graepel, T., Lillicrap, T., Simonyan, K., and Has- sabis, D. Mastering chess and shogi by self-play with general reinforcement learning algorithm, 2017. URL https::/aaae wttpe/iiioo//oooeooeeee abs///bs//////// 2os/17122 111111111111 01815.
Veličković, P., Perivolaropoulos, C., Barbero, F,, and Pas- canu, R. softmax is not enough (for sharp out-of- distribution). arXiv preprint arXiv:2410.01104, 2024.
Wang. D., Ye, Z., Fang, F., and Li, L. Cooperative strategic planning enhances reasoning capabilities in large lan- guage models, 2024a. URL abs 2/1///11.220000
Singh, A., Co-Reyes, J. D., Agarwal, R., Anand, A., Patil, P. Garcia, X., Liu, J., Harrison, J., Lee, J., Xu, K., Parisi, A., Kumar, A., Alemi, A., Rizkowsky, A., Nova, A., Adlam, B., Bohnet, B.. Elsayed, G., Sedghi, H., Mordatch, I., Simpson, I., Gur, I., Snoek, J., Penning- ton, J., Hron, J., Kenealy, K., Swersky, K., Mahajan, K., Culp. L., Xiao, L., Bileschi, M. L., Constant, N., Novak, R., Liu, R., Warkentin, T., Qian, Y., Bansal, Y., Dyer, E., Neyshabur, B., Sohl-Dickstein, J., and Fiedel, N. Beyond human data: Scaling self-training for problem-solving with language models, 2024, URL https: /ttp:///aaivvv./ org/ abs/ 221.. 06585.
Wang, H., Feng, S., He, T., Tan, Z., Han, X., and Tsvetkov, Y. Can language models solve graph problems in natural language? Advances in Neural Information Processing Systems, 36, 2024b.
Wang. H., Xu, J., Xie, S., Wang, R., Li, Xie, Z., Zhang, B., Xiong, C., and Chen, X. M4u: Evaluating multilin- gual understanding and reasoning for large multimodal models, 2024c. URL http::://aaxxv.oo/ abs/ 2405. 15638.
Stechly, K., Valmeekam, K., and Kambhampati, S. Chain of thoughtlessness? an analysis of cot in planning, 2024.
Wang, K., Pan, J., Shi, W., Lu, Z., Zhan, M., and Li, H. Mea- suring multimodal mathematical reasoning with math- vision dataset. arXiv preprint arXiv:2402. /4804, 2024d.
URL https: /ttp:v/aaavvvv//iia org/ abs/ 2405. 04776.
Tang, X., Wang, X., Zhao, W. X., and Wen, J.-R. Dawn- icl: Strategic planning of problem-solving trajectories for zero-shot in-context learning, 2024a. URL https: //arxiv. org/ abs/ 241 2.215.
Wang, L.,, Xu, W., Lan, Y., Hu, Z., Lan, Y., Lee, R. K.-W,, and Lim, E.-P. Plan-and-solve prompting: Improving zero-shot chain-of ofothhoggt reasoning by large language models. arXiv preprint wrXiv:2335.04099 2023.
Tang, Z., Zhang, X., Wan, B., and Wei, F. Mathscale: Scaling instruction tuning for mathematical reasoning. arXiv preprint arXiv:2403.0288. 2024b.
Wang, X., Wei, J., Schuurmans, D., Le, Q., Chi, E.,, Narang, S. Chowdhery, A., and Zhou, D. Self-consistency im- proves chain of thought reasoning in language models. arXiv preprint arXiv:2203.1117/ 2022.
Tian, Y., Peng, B., Song, L., Jin, L., Yu, D., Mi, H., and Yu, D. Toward self-improvement of Ilms via imagina- tion, searching, and criticizing. 2024. URL https: //arxiv. orgo//gga/oo awaaabss2444 2244 12253.
Wang, Y., Zhao, S., Wang, Z., Huang. H., Fan, M., Zhang, Y., Wang. Z., Wang, H., and Liu, T. Strategic chain-of- thought: Guiding accurate reasoning in llms through strat- egy clicitation, 2024e. URL https: aattps://arxiee http://axxvvv.o/// abs / 0..409..3277
Topsakal, O. and Harper, J. B. Benchmarking large language model (IIm) performance for game playing via tic-tac-toe. Electronics, 1333):1532, 2024.
Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E. Le, Q. V., Zhou, et. -hain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837, 2022.
Tromp, J. The fhourstones benchmark. URL https:/
tromp. github. /o/cc////// fhour html.
Tsai, C. F., Zhou, X., Liu, S. S., Li, J., Yu, M., and Mei, H. Can large language models play text games well? current state-of-the-art and open questions. arXiv preprint arXiv:2304.00 0288.8334..288. 2023a.
Wu, S., Zhu, L., Yang, T., Xu, S., Fu, Q. Wei, Y., and Fu, H. Enhance reasoning for large language models in the game werewolf, 2024a. URL https::///a/ttt.t.ooo abs/2402. 02330.
Tsai, C. F., Zhou, X., Liu, S. S., Li, J., Yu, M., and Mei, H. Can large language models play text games well? current state-of-the-art and open questions, 2023b. URL https: / //tp://aaaivve//aa//aa org/ abs/ 2304 02868.
Wu, X., Shen, Y., Shan, C., Song, K., Wang. S., Zhang, B., Feng. J., Cheng, H., Chen, W., Xiong, Y., and Li, D. Can graph learning improve planning in LLM-based agents? In The Thirty-eighth Annual Conference on Neural In- formation Processing Systems, 2024b. URL https: / //operrevi ew, net forum? ? d=bmos d=bmoS6Ggu4
Turpin, M., Michael, J., Perez, E., and Bowman, S. Lan- guage models don't 't always say what they think: unfaith- ful explanations in chain-of th-tiuh prompting. Advances in Neural Information Processing Systems, 36, 2024.
14

---

Mastering Board Games by External and Internal Planning with Language Models
Wu, Y., Liu, J., Bu, X., Liu, J., Zhou, Z., Zhang, Y., Zhang, C., Bai, Z.,, Chen, H., Ge, T., et al. Conceptmath: A bilin- gual concept-wise benchmark for measuring mathemati- cal reasoning of large language models. arXiv preprint arXiv:2402. 14660, 2024c.
Chen, Y., Zhang, H., Shi, Z.., Wang, B., Guo, Z., and Jia, J. MR-ben: A meta-reasoning benchmark for evaluating system-2 thinking in LLMs. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https::/p//.......... wwwperepeeeeeeeeeeeeeeeeee net/ forum? id=GN2gbx2lni.
Xie, J., Zhang, R., Chen, Z.,, Wan, X., and Li, G. Whodunit- bench: Evaluating large multimodal agents via murder mystery games. In The Thirty-eight Conference on Neu- ral Information Processing Systems Datasets and Bench- marks Track, 2024a. URL httpt::/t///....... http:////eeeeeeeeeeeeeeee net/ fert/form?22 i dddiddd--nn Dn
Zhang, D., Li, J., Huang, X., Zhou, D., Li, Y., and Ouyang, W. Accessing gpt-4 level mathematical olympiad solu- tions via monte carlo tree self-refine with llama-3 8b. arXiv preprint arXiv:2406. 07394, 2024a.
Zhang, E., Zhu, V., Saphra, N., Kleiman, A., Edelman, B. L., Tambe, M., Kakade, S. M., and Malach, E. Transcen- dence: Generative models can outperform the experts that train them, 2024b. URL https: aawiv..ro..o///..e...///...... abs / 2406.
Xie, Y., Goyal, A., Zheng. W., Kan, M.-Y., Lillicrap, T. P., Kawaguchi, K., and Shieh, M. Monte carlo tree search boosts reasoning via iterative preference learning, 2024b. URL https: /tte://aaxxxa aatiiviiiivv///..//...a//aaav.at org/ abs/2405 00451.
Xiong, S., Payani, A., Kompella, R., and Fekri, F. Large language models can learn temporal reasoning. arXiv preprint (tti::2001.0685:: 2024.
Zhang. H., Da, J., Lee, D., Robinson, V., Wu, C., Song, W., Zhao, T., Raja, P., Slack. D., Lyu, Q., et al. A careful ex- amination of large language model performance on grade school arithmetic. arXiv preprint arXiv:2405.003: 003320 2024c.
Yang, C., Wang, X., Jiang, J., Zhang, Q., and Huang, X. Evaluating world models with Ilm for decision making, 2024a. URL 2411.08794
org/ abs/
Zhang, Y., Mao, S., Ge, T., Wang, X., de Wynter, A., Xia, Y., Wu, W., Song, T., Lan, M., and Wei, F. Llm as a master- mind: survey of strategic reasoning with large language models. arXiv preprini urXiv:2404.01222
Yang, L., Yu, Z., Zhang, T., Cao, S., Xu, M., Zhang, W., Gonzalez, J. E., and Cui, B. Buffer of thoughts: Thought- augmented reasoning with large language models, 2024b. URL https: /atxiv..vvvv.////////e////aaaa org/ abs/ 20bs/2400 240624066.00 04271.
2024d.
Zhang, Y., Yuan, Y., and Yao, A. C.-C, On the diagram of thought, 2024e. URL https: /ttp:::///..a.a/////////// org/abs/////aaaaoooo/o/ao
Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K., and Cao, Y. React: Synergizing reasoning and acting in language models. arXiv preprint 1rXiv:2210.03629, 2022.
Zhang, Z., Zhang, A., Li, M., and Smola, A. Auto- matic chain of thought prompting in large language mod- cls. 2022. URL https: //axxiv. org/ abs/ 2210. 03493.
Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T., Cao, Y., and Narasimhan, K. Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36, 2024.
Zhang, Z., Zhang, A., Li, M., Zhao, H., Karypis, G., and Smola, A. Multimodal chain-of chain-of-thought reasoning in lan- guage models. arXiv preprint arXiv:2302.009233 2023.
Ye, X. and Durrett, G.
The unreliability of explanations in few-shot prompting for textual reasoning. Advances in neural information processing systems, 35:30378-30392. 2022.
Zhao, Z., Lee, W. S., and Hsu, D. Large language models as commonsense knowledge for large-scale task planning, Advances in Neural Information Processing Systems, 36, 2024.
Zelikman, E., Wu, Y., Mu, J., and Goodman, N. D. Star: Bootstrapping reasoning with reasoning, 2022, URL https: /ttp:///aavv..///a///a org/ abss//bs//ao /as/22203 14465.
Zhou, A., Yan, K., Shlapentokh-Rothman, M., Wang, H., and Wang, Y.-X. Language agent tree search unifies reasoning acting and planning in language models, 2024. URL https: / arwaiivvoooo org/ /abs/ / /211 2.10..0000000 04406.
Zelikman, E., Harik, G., Shao, Y., Jayasiri, V., Haber, N., and Goodman, N. Quiet-star: Language models can teach themselves to think before speaking, 2024. URL https: / arxii.iiivv//aaa org/ abs/ 0bs/2203 2203. 09629.
Zhou, D., Schärli, N., Hou, L., Wei, J., Scales, N., Wang, X., Schuurmans, D., Cui, C., Bousquet, O., Le, Q. et al. Least-to-most prompting enables complex reasoning in large language models. arXiv preprint arXiv:2205.10625 2022.
Zeng, Z., Liu, Y., Wan, Y., Li, J., Chen, P., Dai, J., Yao, Y., Xu, R., Qi, Z., Zhao, W., Shen, I.,, Lu, J., Tan, H.,
15

---

Mastering Board Games by External and Internal Planning with Language Models
Ziems, C., Held, W. Shaikh, O., Chen, J., Zhang, Z., and Yang, D. Can large language models transform computa- tional social science? Computational Linguistics, 50(1): 237-291, 2024.
16

---

Mastering Board Games by External and Internal Planning with Language Models
A. External MCTS
A.I. Additional Plots and Results
Batch size, le
1. Run simulations
2. Queue ovaluations
3. Wait/process results
01
MAV(s, a)
02
(181,0)) (86, as)
Evaluate asynchronously!
Figure 7. Dynamic virtual counts for Yimax
8 and Vésin 2. Virtual counts from separate simulations are added, as the case in +44 node with two children (+4 = (+2) (+2)).
Figure 6, overview of Asyuc MCTS.
Figure 8. Async MCTS and Dynamie Virtual Counts building blocks.
1700
1650
1600
Internal Elo
1550
1500
1450
MAV-MCTS (mean scoring)
1400
MAV-MCTS (max scoring)
1350
100
250
500
1000
2000
Number of simulations
Figure Performance scoring methods MCTS among a tournaments between MCTS agents, various levels of Stockfish, and basic MCTS. The y-axis shows the internal Elo of cach agent with basic MCTS set to 0 internal Elo.
A.2. Performance Considerations and Async MCTS
Since modern large transformer models can take orders of magnitude longer for a single inference than an optimized deep convolutional network (such as the ones used MuZero (Schrittwieser et al., 2020)), keeping the elapsed time for an MCTS search to a reasonable level can challenge. The inference time of a single model call dominates the time take for
17

---

Mastering Board Games by External and Internal Planning with Language Models
Number of Simulations, .M
Average Elapsed Time per Search (seconds)
100
39.82
250
114.12
500
187.10
1000
378.32
2000
729.23
Table 3. Average elapsed time taken per search by Asyne MCTS.
search, so we aim to keep the total calls low. Since the prior and value for a new node are both obtained for the MAV, there is at most one model call per simulation of MCTS. In the low simulation count regime, reusing the search trees is simple optimization that reduces the number of server calls by 5-10% in our experiments.
Despite this lower number of inference calls, it can still be costly make many MAV calls. Hence, we run an asynchronous version of MCTS that is conceptually very similar Algorithm 1, but with the main loop changed. An overview is shown in Figure 6.
Parallel MCTS implementations usually rely on virtual losses (Mirsoleimani et al., 2017; Chaslot et al., 2008) to avoid multiple threads choosing the same simulation paths down due to deterministic action choices. Our Async MCTS introduces three new parameters:
Batch size b. The number of simulations, each leading to an evaluation (MAV call), that are done asynchronously at any given time.
Timeout to. The amount time wait for evaluations. After the timeout expires, any evaluations that have not returned are discarded.
Virtual Count Value nh.. The "virtual" value to temporarily add to a visit count (ss, a) during the simulation to discourage all simulations in batch from choosing the same path.
In Async MCTS, simulations are instead performed in batches. First, b downward passes are performed serially to queue b evaluations. The b evaluations are performed in parallel and the MAV outputs are returned asynchronously.
The evaluations are then processed one-by-one as they return. For each queued evaluation that was successful (i.e., did not time out), its values are then backpropagated up the tree (serially). The state-action pairs that are visited before the queuing of evaluations are assigned temporary virtual counts: their visit counts are temporary set to N a) N(s, a) + ne- The visit counts and virtual counts are then subtracted upon the upward pass, i.e., (s, N(s, a) n
Note that, since the simulations and processing of evaluations (backpropagation) are both done serially, there is no need for complex concurrency handling primitives such as mutexes or semaphores. In practice, the implementation is based on Python's 's concur futures module and re-uses most of the serial MCTS subroutines, changing only the main loop.
The average amount of time taken per search is shown in Table
A.3. Hyper-Parameter Tuning and Values
using a combination of manual and head-to-head comparisons. We found that setting T = 0.1, 5, and ε = 0.05 worked best for the prior (Equation 1).
For our eXternal-MCTS agents, we tune
For Asyne MCTS we used batch size 16. We found that lower batch sizes were always preferred in terms of performance. We used timeout of 60 seconds, and (only baseline) static virtual loss parameter n. = 10. In head-to-head comparisons, we found that tuned dynamic virtual count would generally outperform static virtual counts. We use the robust child strategy for final move selection (Chaslot et al., 2009) (choosing the action with the highest number of visits), using the total reward as a tie-breaker.
We used dynamic virtual count values Rmmin = 2 in all cases, and mmax varying with the number of simulations: (M, mmxx) {(100, 8). (250, 8). (500, 8), (1000, 16), (2000, 32)}.
18

---

Mastering Board Games by External and Internal Planning with Language Models
A.4. External MCTS: Algorithm Details
In this section, we describe the terminology and pseudo-code for external MCTS.
Notation:
E 10, denotes the active player; e.g., in chess, 0 for white, 1 for black
M: number of MCTS simulations
Sy string description of state step e.g., FEN in chess
dg an action at step I.
T( 0(-1)
(deterministic) transition function
at = ( a; simplicity of notation
) list of legal actions at step i; note that at is state dependent, but we omit dependency for the
No: root node; stores internal objects
an active player No E {0
string description of the initial state (s) 8o
- a list of legal actions No(aa) af
(se, ae): state-action value from the perspective of player in state st given action at
(se, a+) (st, all legal moves a
(st, (t), Q ar L(oc))): state-action value from the perspective of player in state 8, for
P(s,, = P(ac(ss): prior probability of action in state St
P(st. a = (P(s,, .i).....,PP( at ((*))); a prior distribution, i.c., a distribution over all legal moves at in state st
Ng. a node at step > 0; stores internal objects
an active player (t) = - Ni-
a string description of state Nz(s) E {st 1( NONE)
a list of legal actions .Na(a²) E {a,, NONE} in state 8:
a cumulative value ()(V 2 from child's perspective = Mi(i)
visit count count.N. NN:(N a)) ((t-11, 1)) given the parent state 8t-1 and action d:-1 a prior probability MM a)) P(s a=-1) 2 0 given the parent state st-1 and action a;-1
MAV: a model that supports multi-action value interface
-aff Q()) a) = MAV(se): a state evaluator; returns a list of legal moves af and associated state-action values Q (5) (5o, a for the state 8p in the root node No; notice that the state evaluator is only necessary for the root node
(8t, at Q at) = (AV(s--1,4-1)) a state-action evaluator; for a given state-action parent tuple (st-1, 0z-1) returns the child state s, = T(s:-1, a list of child's legal actions af and the associated state-action values ( (st, at) from child's perspective i == -V(
B. External Engines and Game Data
In this section, we describe the details on the data generation for each game, while Table 4 reports training data statistics.
19

---

Mastering Board Games by External and Internal Planning with Language Models
Algorithm 2 EXPAND(N(-1,
1: Input: Parent node -i-1. prior P
2: Output: NONE
3: for a;-1 E (M-11(a*)) do
4: Create an empty child node No
5: Connect parent node Ni-1 and child node No with edge (N--1, a1-1)
6:
Initialize child node:
7:
Ni(1) + - -
8:
Ni(s) - NONE
9:
Ni(a²) <- NONE
10:
N((V(((()) + 0
$ (s), at a
M((((s. +
13:
(((((s,)) a)
14: end for
15: return
Algorithm 3 SIMULATION(Ni k)
1: Input: Parent node Ni-1, multi-action value model MAV, top values
2: Output: NONE
3: 8r-1 + -N--((s)
4: a;-1 + SELLEC(A(-))
5: NM. < DOOE-TTO-CHILDNNNLLL....
6: if (T()s) is NONE then
7: (s,,at' Q (19
a.)) = MAV (AA(ss;1,, a1-1) from child's perspective = =Ne(1)
P(s at; (()), 3(0,, k) + Equation (1)
8:
9:
EXPAND(N,, P)
10: Ni(s) t St
Ni(a") + a.
Q'= max Eat (10
13:
BACKPROPAGIATH(M., Q")
14: else
15: SIMULATION(N, MAV)
16: end if
17: return
Stockfish For chess and Chess960 we used the open source engine Stockfish 16 (Source Code Avalible on Github) for both annotations and as opponents in our internal Elo caleulations. We compiled all Stockfish builds from source, using clang++, with the following compile flags -03 DIS_64BBIT -DUSF_PTHRES
dth=128 for all builds. We ran Stockfish over a wide array hardware using two different configurations, for older hardware we added -DUSE_POPCNT -DUSE_SSSES -DUSE_SSE41 march= -msse4 2 and for newer hardware added -DUSE_AVX2 -DUSE_PEXT -march=haseelll These builds usually give between 350k-700k nodes per second for single threaded runs of stock fi fish -- bench 4096 1 130000 faullt nodes.
-mprefer-vetton
Ext-BoN (Ruoss al., 2024a) showed that small (270M-parameter) transformer can play Blitz chess on Lichess an Elo of 2895 against humans (i.e., Grandmaster level). They created large-scale dataset of 10 million chess games with legal move and value annotations (15 billion data points) provided by Stockfish 16, the sate-of-the-arr chess engine. They then trained Transformers via supervised learning to predict action-values, i.c., no explicit search, and showed that their models achieve highly non-trivial generalization (e.g., solving challenging chess puzzles). They thus showed that remarkably good approximation Stockfish's 's search-based algorithm can be distilled into large-scale transformers via supervised learning, but that perfect distillation is still beyond reach.
20

---

Mastering Board Games by External and Internal Planning with Language Models
Algorithm 4 SELECT(N(-1)
1: Input: Parent node N
2: Output: Action a" determined by PUCT
3: Access child nodes values from parent's perspective and compute PUCT; if tied select randomly
4: 1i)
5: NN-
6: s' Ni(s)
7: at = Nat)
8: (s)) = Eoear (N((Vss a))
(x(
(N(a) [+N,aN(e..]]
9: A + arg aea
N.(((( 'pact" (G(,ss)))
10: if ||a > then
11: a" + RAAN(A"))
12: else
+ A
14: end if
15: return a²
Algorithm 5 BACKPROPAGATEE(N, Q)
1: Input: Child node N₁, state-action value Q
2: Output: NONE
3: while MG # No do
4: (G(V(((s))
N((VV(( 5: S= N=N)-1ss), a a= Ni
6:
(s(((s,a)) - a1)
7: MG + MOVE-TO-PAAREN((M)
8: end while
9: return
Algorithm 6 MOVE-TO-CIILLDN--1..eaa
1: Input: Parent node NV-1, parent action d;-1
2: Output: Child node N
3: Move from a parent node Nr-1 child node Mr via the edge (N ac-1)
4: return N₁
Algorithm SOOVE-TOOPARENTCLE
1: Input: Child node Nr
2: Output: Parent node N
3: Move from a child node N₁ to a parent node Ni-1
4: return N
Chess/Chess960 Game Training Data Chess positions were drawn from two sources: Lichess and TCEC. TCEC data consisted of all 34,291 standard chess games played in seasons 1-25, from which 4,204,025 unique positions were extracted. Lichess standard rated chess games were drawn from the months October 2014, March 2017, and January 2020 for a total of 58,705,532 games. All 19,758,457 Chess960 games played on Lichess from August 2013 June 2024 were included. All positions annotated with Stockfish 16 for duration of second, with the exception of those drawn from TCEC and Lichess October 2014 games, where 15 seconds of analysis time was used.
Hex Training Data 12,279,64 6,45 Hex games were generated by self-play with neurobenzene (Gao Pawlewicz), run with search time set to 10 seconds. In 10% of positions, a random move was chosen instead to encourage exploration of an otherwise narrow state space distribution.
21

---

Mastering Board Games by External and Internal Planning with Language Models
Algorithm 8 FINALMOVESSELECTIONNN.)
1: Input: Root node No
2: Output: Best final action a' given search statistics
3: Determine most visited child; if tied find maximum estimated value
4: + Nu(ss
5: a= +No(aa*)
6: A" <- arg aax (s)
7: if |A*|
then
8: Access child nodes values from root's perspective and find maximum estimated value
9: i (1)
10:
+ Ni(s)
(s()
11: a" + arg aE (N((e)))))
12: else
13: a" f- A
14: end if
return a*
Table Multi-action-value (MAV) model training data statistics.
Game
Positions
Action values
Chess
3.1B
54.3B
Chess960
1.2B
20.9B
Connect Four
21.8M
110.5M
Hex
125.6M
537.0M
Connect Four Training Data 2,458,293 Connect Four games were generated using an e-greedy strategy with e = 0.4. Greedy actions were chosen uniformly among all moves that yielded the best attainable minimax value, computed using the Fhourstones solver (Tromp).
C. Games League
We conduct planning and reasoning experiments in games, similar GameBench (Costarelli al., 2024) and GTBench (Duan et al., 2024). Games present an opportunity to develop and test approaches in controllable and safe environment, with ground truth that is readily verifiable through existing game models. We use OpenSpiel (Lanctot et al., 2019) as the game engine to drive our evaluations.
Decision Docisinn-making with language agents inseparably fuses a prompting strategy. the language model, and the response interpretation. The language model essentially interfaces with a second modality - the game, for which prompting encodes the state observation as language input, and response interpretation maps from language output back to action. The language model performs the response computation in language space. Any given triplet can be evaluated specific states, or by playing against another triplet against benchmark bots (e.g., Random, search or reinforcement learning based agents) that operate directly on the game representation.
We evaluate agents offline, through fixed datasets of states, and online, in pairwise matches against reference opponents. Metrics such as action-choice quantiles and action-valus regret that we compute for each dataset across agents are directly comparable, and exhibit different skill dimensions (tasks), such as doing well in opening, mid-game or endgame positions. In contrast, online matches directly measure relative playing strength as wins/draws/losses, and may traverse different distributions of states for each match-up of opponents. While the eventual objective is increase playing strength across wide range of opponents, the offline evaluation on datasets helps characterise each policy.
A tournament of multiple opponents results in square agent-vs-agent matrices indicating the number of wins and draws (losses inferable from transposed of wins) for each pair. Elo (Elo, 1967) finds the best mingle-dimension rating for each contender, such that their mutual win probabilities are best explained by ratio of their exponentiated rating. This implies a ranking, i.e., an ordinal preference over each of the contenders. We report average winrates (treating draws as half wins) for
22

---

Mastering Board Games by External and Internal Planning with Language Models
matches, and Elo for tournaments.
D. MAV Generalization
During the opening and endgame, human players often rely on memorized theory, while middlegame requires more calculation and intuition. In Figure 10, we observe that 10% of the positions played by MAV in evaluation appear in its training data, while between moves 20 and 50, virtually no position has been seen by MAV during training. These results show that in order to avoid losing games during middlegame, MAV is required generalize.
Finally, show example of MAV's generalization capabilities into position which does not appear in the training data. In the position shown in Figure 11, MAV has found creative move, g5, which is the best move according to Stockfish, The move allows the White knight on 13 to capture the pawn but results in long-term advantage for Black.
100
Test positions scen during training (%)
80
60
40
20
mn
0
0
10
20
30
40
50
60
70
Fullmove number
Figure 10. Percentage of chess positions encountered during evaluation that also appear in the MAV training data. Between moves 20 and 50, almost the encountered positions are unseen, requiring the model to generalize.
2
3
MM
7
h
f
a
Figure 11. Example position where MAV plays creative pawn sacrifice, g5 (best move according to Stockfish), to gain long-term advantage.
23

---

Mastering Board Games by External and Internal Planning with Language Models
outtr--Distribttion test set positions We programmatically generate out-of-distribution (OOD) positions by randomly sampling the number and type of pieces the board while ensuring compliance with several rules such as: kings cannot be in check simultaneously, the position is not checkmate. Examples of OOD positions are shown in Figure 12. Notice that some positions are not reachable via legal sequence of moves from the initial chess position, which showcases that MAV generalizes outside of the human games it was trained on by achieving near 100% accuracy as reported in Table 2.
8
8
7
7
6
6
5
5
4
3
3
2
3
2
8
1
a
b
C
8
9
b
C
9
8
8
7
7
6
6
5
5
4
4
3
3
2
2
b
d
b
d
h
Figure 12, A sample from oul-of-distribution set to test the legal move rate and state tracking accuracy of MAV. The squares next to the diagrams indicate active players.
E. Related Work
Planning and reasoning with language models both an open challenge and an active area of research. Given how widely relevant planning as a capability to support decision making in complex, dynamic, and open-ended domains (Rasal & Hauer, 2024), there is, perhaps unsurprisingly, correspondingly wide variety of planning approaches that have been explored to date, mapping onto these unmet needs. The remainder of this section first outlines general reasoning benchmarks, and then goes into game benchmarks in particular. Next, we outline adjacent works of in-context reasoning, which shares with internal search that plans are expanded by the language model itself, and reasoning as search, which sketches a broader scope around approaches similar to external search. Finally, we give pointers to specific works as chess, which takes a prominent role our evaluation.
24

---

Mastering Board Games by External and Internal Planning with Language Models
Benchmarking reasoning Reasoning tasks can be divided into tasks of common sense reasoning (Zhao et al., 2024; Cui al., 2024), structured reasoning (Wang et al., 2024b), mathematical reasoning (Shao et al., 2024b; Wu et al., 2024c; Chen et al., 2024a; Gu et al., 2024; Wang et al., 2024d; Zhang et al., 2024e; Tang et al., 2024b), algorithmic reasoning (Markeeva et al., 2024), symbolic reasoning (Fang et al., 2024), causal reasoning (Jin et al., 2024), temporal reasoning (Xiong et al., 2024), meta-reasoning (Zeng et al., 2024) and strategic reasoning (Zhang et al., 2024d). Multimodal reasoning may span any subset of these categories, with the added complexity of incorporating cross-modal tasks (Chia et al., 2024; Kil et al., 2024; Xie et al., 2024a; Haresh et al., 2024; Shao et al., 2024a; Shi et al., 2024). There are also multilingual benchmarks (Bang et al., 2023; Wang et al., 2024c), aimed at evaluating model reasoning across languages. Large language models can approach these reasoning tasks directly, with help of external tools (Paranjape al., 2023; Lu et al., 2024) planners and solvers (Dagan et al., 2023; Borazjanizadeh & Piantadosi, 2024), and their performance can be evaluated in typical scenarios or puzzles (Giadikiaroglou et al., 2024; Li et al., 2024b), which tend to be more complex and more These evaluations can either be general or more domain-specific (Nori et al., 2024; Guo et al., 2024). There have also been efforts aimed at evaluating the utility of language models as world models, from the perspective of decision making and planning ( (Yang et al., 2024a).
Reasoning in games Strategic reasoning (Gandhi et al., 2023), which naturally arises in game play, is particularly challenging due to dynamic environment and the uncertainty in predicting the actions of the adversary. It is goal-oriented, interactive, adaptive, and requires a level of predictive ability. Outside of games, this type of reasoning may be valuable in economic (Horton, 2023; Li et al., 2023) and social (Gandhi et al., 2024a; Ziems et al., 2024) applications. The focus in this paper is primarily on strategic planning in games, which have been suggested as a an important set of benchmarks for developing and evaluating strategic reasoning (Tsai et al., 2023a; Duan et al., 2024; Costarelli et al., 2024) in language models, not unlike their historical role in the development of Al previously (McCarthy, 1990; Schaul et al., 2011; Ensmenger, 2012), and sequential decision making in particular. Three particular game benchmarks that have been concurrently developed with this paper are GameBench (Costarelli et al., 2024), GTBench (Duan et al., 2024), and LMAct (Ruoss et al., 2024b). All three adopt the same agentification of language models for games: an agent comprises a prompting strategy that generates a prompt from a game state, an LLM that generates the response, and an interpretation of the textual response as a game action. The resulting agent can be evaluated by playing matches in specific games, like tic-tac-toe, either against benchmark RL agents or other language model agents. This makes it possible draw conclusions on strategic reasoning abilities from the pairwise winrates rankings derived from Elo-rating the tournament results. Our specific evaluation is delineated in the experimental section of this paper.
Reasoning in-context has been demonstrated that large language models encode a certain level of intrinsic reasoning ability in the natural language space, especially when prompted to do so (Plaat et al., 2024), which can be solicited by chain-of-thought (CoT) techniques (Kojima et al., 2022; Wei et al., 2022; Shi al., 2022; Zhang al., 2023; Wang et al., 2024e), least-to-most prompting (Zhou et al., 2022), plan-and-solve prompting (Wang et al., 2023), self-ask structured prompting (Press et al., 2022), multi-step problem decomposition and plan execution (Nguyen & Shareghi, 2024), few-shot prompting (Brown et al., 2020; Gao et al., 2020; Gramopadhye et al., 2024), and many-shot prompting (Agarwal et al., 2024), among others. Yet, CoT methods are not always reliable, may express inconsistent reasoning steps or traces that do not actually correspond to how the decisions are reached (Ye & Durrett, 2022: Turpin et al., 2024), may not be robust to typographical errors (Gan et al., 2024), and may not be the best approach for planning in more complex domains, though it has recently been shown that they can in principle handle e.g., dynamic programming tasks (Feng al., 2024a). Without world model capable of tracking state transitions, it is hard to evaluate the long-term consequences of earlier decisions (Hao et al., 2023). These emerging capabilities are heavily influenced by the data itself, as intermediate reasoming steps are only helpful in case of locally structured data, consisting of local clusters of variables with strong mutual influence (Prystawski et al., 2024). CoT rationales can be optimised through task--riented feedback (Lee et al., 2024). Informative thought templates can be distilled from and reused across a number of different tasks, and compiled in a buffer of thoughts (Yang et al., 2024b). Diversity in CoT generations matters, and generating a larger number of diverse reasoning chains can lead to better performance (Zhang al., 2022). Reasoning traces can be interleaved with actions, as in ReAct (Yao et al., 2022). Self-consistency techniques present another avenue for further improving model performance (Wang et al., 2022). To be useful, CoT prompts may need to be specific to their problem class (Stechly et al., 2024). Synthetic data generation can be used to improve the quality and the coverage of demonstrations (Shao et al., 2023). CoT has also been considered in the multimodal context (Lu et al., 2022; Mitra et al., 2024) and whiteboard-or thothoo was recently shown to be helpful, in encouraging reasoning across modalities (Menon et al., 2024). Language models are capable of improving their performance on some types of problems merely by the extra computation granted by the additional tokens, even when those are filter
25

---

Mastering Board Games by External and Internal Planning with Language Models
tokens rather than structured interpretable CoT (Pfau al., 2024). It is possible to consider instead generating internal thoughts, rationales at the token level for predicting future tokens, demonstrated by the Quiet-STAR method (Zelikman et al., 2024). This method belongs to a class of approaches that utilise self-improvement self-play for boosting the planning and reasoning ability in language models, which has become a widely used approach (Zelikman et al., 2022; Singh et al., 2024; Hosseini et al., 2024; Aksitov et al., 2023; Chen et al., 2024c; Tian et al., 2024; Saab et al., 2024). Self-improvement approaches often rely on the intrinsic ability for self-correction in LLMs, yet self-correcting reasoning without explicit external feedback remains difficult (Huang et al., 2024). Given that CoT reasoning is ultimately greedy and may have problems when there are many options worth exploring (Saparov & He. 2022), this was a motivation for exploring alternative, more structured search methods. Dynamic prompt-conditionas strategy selection may help identify the best strategic approach to each particular problem (Parekh et al., 2024). Multi-agent approaches can be used to further develop this particular point, decoupling strategic reasoning and more specific step-wise planning (Wang et al., 2024a). Planning can also be done over associated knowledge graphs (Chen et al., 2024b), and graph learning may help with the overall planning capabilities in the more general case (Wu et al., 2024b). Finally, some problems may lend themselves more naturally to backward planning, potentially necessitating a custom approach (Ren et al., 2024).
Reasoning as search Testing LLMs on especially sequential decision-making problems requires agentification, with a variety of proposed approaches to use LLMs as or within game agents (Tsai et al., 2023b; Hu et al., 2024b; Wu et al., 2024a; Hu et al., 2024c). MCTS- based planning, and self-play, have been also been explored in this context (Rebstock et al., 2024; Putta et al., 2024; Light et al., 2024). Rather than relying on individual reasoning chains, it is possible to instead construct a tree of thoughts (Long, 2023; Yao et al., 2024) graph of thoughts (Besta et al., 2024), or a diagram of thoughts (Zhang et al., 2024e). There has also been recent interest in utilizing MCTS with LLMS for complex reasoning tasks (Zhang et al., 2024a). The everything-of soahiinng-f-thuuuue thouuhth (XoT) (Ding al., 2023) approach utilizes MCTS for incorporating external domain knowledge into thoughts, as does effectively reason over facts encoded in knowledge graphs. Tree search has also proved valuable in completing realistic web tasks (Koh et al., 2024), as well as code generation (Li et al., 2024a), mathematical reasoning (Jiang et al., 2024), and tabular data handling (Ji et al., 2024). While most approaches rely on the prompted LLM itself acting as a value function, therefore bounding the utility of search by the quality of that value function approximation (Chen et al., 2024d), and searching at low depths, it is also possible to use tree search with a learned value function in guiding LLM decoding, as was demonstrated in TS-LLM (Feng et al., 2024b). Language Agent Tree Seatch (LATS) (Zhou et al., 2024) incorporates MCTS along with self-reflection and memory, achieving strong performance on programming tasks. MCTS has also been used to improve LLM reasoning ability through iterative preference optimization (Xie et al., 2024b). When applied in the language generation space, MCTS can be seen as a likelihood-base search on the direct preference optimization (DPO) policy (Rafailov et al., 2024). MCTS can also be used to strategically plan over the the problem-solving trajectories for zero-shot in- co-textext learning (Tang et al., 2024a). Self-Rewarding Tree Search based on MCTS has been used for improving domain-specift strieval-augmentte generation (Hu et al., 2024a). In terms of other search strategies, Searchformer has recently been proposed (Lehnert et al., 2024), a Transformer model that was trained to mimic the dynamics of the A algorithm, showing good performance on Sokoban puzzles and in maze navigation. Algorithm distillation has recently been proposed as a method for distilling reinforcement learning algorithms into neural networks, facilitating in in-context reinforcement learning with language models (Laskin et al., 2022).
(Markowitz et al., 2024), enabling language models to
Reasoning in chess As our paper explores the application of planning with language models chess, which has been a separate topic of interest, here we also briefly review the current state of art and the approaches and evaluations relevant to chess in particular. Chess- GPT (Feng et al., 2023) was custom model, integrating chess playing and language ability, that was shown to offer notable improvements in board state tracking and playing strength over a number of LLM baselines. More recently, it was shown to be possible to train Transformer models to Grandmaster- strength in chess (Ruoss et al., 2024a), without search, looking just a single move ahead. There have been recent advances involving diffusion models as well (Anonymous, 2024). By training specialized Transformer models for chess, it has been shown that the models may demonstrate transcendence (Zhang et al., 2024b), at least lower playing strengths where the resulting model may outperform any of the human players from the training set, as the model leams policy that effectively averages out some of the mistakes human players make. This is in line with the findings showing that weak-to-strong supervision is possible (Burns et al., 2023). It is also possible to develop skill- seill-compatbble models (Hamade et al., 2024), as skill compatibility is ultimately distinct from playing strength. There is also an interest in developing models that can act as chess coaches (Menon, 2023). There is evidence that chess-playing Transformers can learn and internalize look-ahead in relation to future optimal moves (Jenner et al., 2024). Hybrid convolutional transformer networks have been identified as a
26

---

Mastering Board Games by External and Internal Planning with Language Models
promising avenue, yielding performance improvements (Czech al., 2024). An in-depth analysis of chess playing strength of the most prominent language models (Acher, 2023) had identified 11n-3.5-turbo-instree the strongest model the time, capable of completing longer games and winning against non-trivial Stockfish difficulty levels, yet still failing to finish non-negligible percentage of games due to illegal moves.
27

---

Mastering Board Games by External and Internal Planning with Language Models
F. Featured Games
F.1 Chess
8
We start games from the opening book described in Table 5. symbol indicates the last move loaded from the open- ing book after which the agents continue the game. Once the game is finished, the agents reverse the colors and play the game with the same opening position. A square next to the diagrams represents the side to play. All games, except for Game () and Game 1, use Stockfish with 2 seconds of thinking time per move. Further details can be found in Section "External Engines and Game Data". We use MAV- MCTS to represent the external search MAV with mean scoring, MAV-MCTS max scoring is self-explanatory, and MAV-IS represents the internal search MAV.
7
6
5
4
3
2
1
Game O
b
e 9
A win against human player Long-term piece activity
Bxdl MAV is not afraid to enter the endgame with
opposite-colored bishops. 37. Kxdl e4 38. Be2 Bxf2 39, a4 bxa4 40. Bxa6 a3 41. Bc4 Be3 42. b5 Rd2+ 43. Kel Rb2 44. b6 Bxb6 45. Kdl Kc5 46. Kel Be3 47. Kdl f4 48. Kel f3 49. Kd1 Kd4 50. Bf7 Kc3 51. Ba2 Rxa2 52. Rxf3
Date: 2024-07-24
White: Luka Rimanié, 1990 FIDE Elo Black: MAV max scoring
Result: 0-1
ex13 53. Kel Ral# 0-1
Online PGN: https:/fiihess.org/lliifjj
I. e4 e6 2. d4 d5 3. Ne3 dxe4 4. Nxe4 N16 5. Bg5 Be7
Game 1
6. Bxf6 gxf6 7. g4
The first win against Stockfish Unelear long-term attack
Date: 2024-05-31
White: MAV-MCTS, development version
Black: Unoptimized Stockfish (50K-90K nps)
Result: 1-0
6
Online PGN: httts://lichees.or//gNNWii
1. d4 f5 2. Bg5 g6 $ e3 Bg7 4. Qd2 h6 5. Bh4 c5 6. f4
Qb6
8
4
8
2
3 600
8
7
6
a
b
C e g h
5
7...h5 MAV sacrifices a pawn for the long-term piece activity, 8. gxh5 f5 9. Ng3 c5 10. NB3 Ne6 11. c3 cxd4 12. Nxd4 Nxd4 13. Qxd4 Qxd4 MAV exchanges queens, but the bishop pair the open board and rooks' activity secure the advantage for Black. 14. cxd4 Bd7 15. 0-0-0 Bc6 16. Rgl Rc8 17. Kbl f4 18. Ne2 Be4+ 19. Kal Bf3 20. Rb1 Rd8 21. Nxf4 Rxd4 22. Bb5+ Kf8 23. Ne2 Rd2 24. Rbel Rxh5 MAV regains the sacrificed pawn with interest after 17 moves; despite the even material, White losing. 25, Rc8+ Rd8 26. Rxd8+ Bxd8 27. Ne3 Rxh2 28. Rfl Bb6 29. Nd1 Ke7 30. a3 f5 31. Kb1 Kf6 32. Kc2 a6 33.
4
3
2
8
8
8
1
b
d
f
g h
7. Nc3 prelude to a pawn sacrifice. cxd4 8, exd4 Bxd4 MAV-MCTS sacrifices central pawn and likely loses castling rights for compensation that is unclear to
Bc4 Bd4 34. b4 b5 35. Bd3 e5 36. Kd2
28

---

Mastering Board Games by External and Internal Planning with Language Models
human eye. 9. Nf3 Be3 10. Qd3 Ne6 11. Nd5 Qxb2 12.
Qxe3
8
7
6
7
5
4
5
3
2 8
8
A
A
8
8
1
e g
17. g6 A nail in the coffin Black is lost despite being two rooks up. Qal 18. Bxe7+ Kg7 19. Bd6 cxd5 20. Qe8 Be6 21. Qxe6 (game terminated by early termination). MAV-MCTS's playing style resembles games of players such as GM Mikhail Tal and IM Rashid Nezhmetdinov who sacrificed material for unclear long-term attacks. Note that the game played with limited resources during the development phase, which affected the evaluation of some moves. 1-0
a
C e g
h
1xa..Qxal+ MAV-MCTS proceeds with sacrificing an exchange with check. 13. Kf2 K18
7
Game 2 Restricting opponent's activity
Date: 2024-11-12
White: MAV-MCTS(M 2000) max scoring
Black: Stockfish-L20
2
8
8
Result: 1-0
Online PGN: http::///cchess.org//ssTTTT/
1. c5 2. 14 exf4 3. NI3 g5 4. Ne3 Ne6 5, g3 g4 6. Nh4 13
7. d4 Bb4 d5 Qe7
9. Be3 Ne5 10. Nf5 Bxc3+ 11.
a
C
g h
bxe3 Qa3
14. Bb5 MAV-MCTS sacrifices the rook! Qxhl 15. Bxc6
g5 16. fxg5 dxc6
8
7
6
5
8
4
3
3
2
8
8
500
1
a
6
0
29

---

Mastering Board Games by External and Internal Planning with Language Models
12. d6 MAV-MCTS sacrificed the second pawn to paralyze Black's queenside. White will further rapidly develop its pieces by attacking the exposed Black's queen. Qxc3+ 13. K12 Nf6 14. Bd3 cxd6 15. Bd4 Qc6
8
7
6
5
7
4
3
8
5
2
8
4
1
200
000
b
d
e g
A
2
29. Qxh6 MAV-MCTS correctly sacrifices an exchange
to ruin Black's 's kingside. Bxfl 30. Kxfl c6 31. Rel Rac8
32. Bg6 Qg7 33. Qxg7+ Kxg7 34, Bxe8 Rxe8 35, e6 Kf6
a
C e 9 h
36. c7 c4 37. b3 cxb3 38. axb3 Rxe7 39. Rxe7 Kxe7 40.
16. a4 At the first glance, this move aims to stop b5 and queenside development, but the move also has a much deeper idea. Rg8 17. Ra3 Now the real idea behind 16.a4 becomes apparent; MAV-MCTS wants activate its rook via c3! Rg5 18. Qd2 Rxf5 A knight paralyzes the entire Black's 's position, so Black desperately sacrifices the rook for some activity. 19. exf5 Ne4+ 20. Bxe4 Qxe4 21. Rel Qxf5 22. Rd3 f6 23. Bb2 Kd8 24. Rxd6 b6 25. Bxe5 fxe5 26. Rd5 Qf6 27. Rexe5 Kc7 28. Re3 h6 29. Rc3+
Kel Kd6 41. g3 c5 42. h4 gxh4 43. gxh4 Kd7 44. h5 Ke8
45. Kdl K18
8
7
6
Kb8 30. a5 Qc7 31. Q14+ d6 32. Re3 Qc7 33. Rxd6 Kb7 34.
5
Qe4+ Kb8 35. Re6 Bd7 36. Rxc7 Kxe7 37. Qxa8 bxa5 38.
4
Qxa7+ Kc6 39. Re3+ Kd6 40. Rd3+ Kc6 41. Qxd7+ Kb6
42. Rd6+ Kc5 43. Re6+ Kb4 44. Qb7+ Ka3 45. Qb3# 1 0
3
2
A
2
Game 3
Precise pawn endgame
1
Date: 2024-11-12
b
f
9 h
White: MAV-MCTSMM 2000)- max scoring
Black: Stockfish-L118
46. f4 MAV-MCTS plays the only winning move in a seemingly simple pawn endgame. The idea is to timely set up the 15-h5 pawn formation. Kg7 47. 15 Kg8 48. Kc2 Kh7 49. f6 Kh6 50. Kb1 Kh7 51. Kc2 Kh6 52. Kd3 Kh7
Result: 1-0
Online PGN: https://iiches.org/Aoaes Y
1. c4 Nc6 2. d4 d5 3. Nc3 Nf6 4. c5 Nd7 t 5. Nce2 e6 6.
c3 f6 7. Nf4 Qe7 8. exf6 Nxf6 9. Be2 Qd7 10. Nf3 Bd6
53. Ke3 Kh8 54. Kf4 Kg8 55. Kf5 d4 56. exd4 Kh7 57. f7
11. O-0 O-O 12. Nd3 Ne4 13. Nfe5 Bxe5 14. Nxe5 Nxe5
Kg7 58. Ke6 c4 59. Ke7 Kh6 60. f8=Q+ Kh7 61. Kf6 cxb3
15. dxe5 a5 16. Be3 b6 17. Qc2 Bb7 18. Bd3 h6 19. Radl
62. Qg7# 1-0
Qe8 20. f3 Ne5 21. Bh7+ Kh8 22. Bg6 Qe7 23. Qd2 Kg8 24. Bbl Bа6 25. Qc2 g5 26. Bxc5 bxc5 27. Qgó+ Qg7 28.
Game 4 Building a fortress
Qxe6+ Q17
Date: 2024-11-12
White: Stockfish-Li8
Black: MAV-MCTS(M = 2000) max scoring Result: 1/2- 1/2
30

---

Mastering Board Games by External and Internal Planning with Language Models
Online PGN: https::/fichees.ogggARRssss
Black: Stockfish-L118
1. d4 Nf6 2. Bg5 Ne4 3. Bf4 c5 4. f3 Qa5+ 5. c3 Nf6 6. d5
Result: 1 1 0
Qb6 7. e4 E Qxb2 8. Nd2 Qxe3 9. Bc7 g6 10. Rcl Qe3+
Online PGN: httpss//lichees.or//llaaaa
11. Ne2 d6 12. Rb1 Nid7 13. f4
1. e4 e6 2. d4 d5 3. e5 c5 4. c3 Ne7 5. Nf3 Necó S 6. Bd3
Be7 7. O-Q Nd7 8. Re1 f6 9. exf6 Nxf6 10. dxc5 a5 11. c4
O-O 12. Nc3 dxc4 13. Bxc4 Qxdl 14. Rxd1 Bxc5 15. Na4
8
Ba7 16. Be3 Nd5 17. Bxa7 Nxa7 18. Ne5 Ne6 19. Ng5
Re8 20. Racl Nb6 21. Bb5 a4 22. a3 Ra5 23. Bxc6 bxc6
24. Nge4 h6 25. Rd6 Rb5 26. Rd2 Kh7 27. Nd6 Rd8 28.
6
Nce4 Rd5 29. Rxc6 Rxd2 30. Nxd2 Na8 31. N6c4 Bb7 32.
Rxe6 Rd4 33. f3 Bd5
5
8
3
8
3
7
8
8
8
6
1
5
a
b
C
0
9 h
4
N3...Na6 Prelude to queen sacrifice. 14. Rb3 Qxb3
MAV-MCTS sacrifices queen hoping its position is
3
A
solid enough to hold back White's pieces activity. 15.
2
8
axb3 Nxe7 16. Qal Rg8 17. h4 Bg7 18. Ne3 b6 19. h5 Bb7
20. hxg6 hxg6 21. Rh7 Bd4 22. Qc1 1 a6 23. No4 N16 24.
1
Rh3 Bxc3+ 25, Rxc3 Nxe4 26. Re3 f5 27. Nxb6 Nxd5 28.
Nxa8 Nxe3 29, Qxe3 Bxa8 30. g4 Rh8 31. gxf5 gxf5 32.
a
b d f
g
b4 cxb4 33. Qb6 Kd7 34. Qd4 Re8 35. Bxa6 Rcl+ 36.
34. Rd6 After dominating the key squares by masterful maneuvers, MAV-MCTS correctly evaluates that entering a rook versus minor pieces endgame is decisive.
Ke2 Ne5 37. Bb5+ Bc6 38. Qxb4 Ral 39. Bc4 Ra4 40.
Qc3 Kc7 41. Kd1 Kb6 42. Qel e6 43. Qb2+ Kc7 44. Qc3
Bd7 45. Kel Ne4 46. Qc1 Ra5 47. Bfl+ Bc6 48. Be2 Nc5
Rxc4 35. Nxc4 Bxc4 36. Rc6 Bd5 37. Ra6 Nc7 38. Rxa4 Kg8 39. Ra7 Ne6 40. b4 Kf8 41. b5 Ke8 42. b6 Nd8 43. Rxg7 Nf7 44. a4 Kd7 45. a5 Kc6 46. Rg6+ Kb7 47. h4 h5
49. Qc3 Ra4 50. Qg3 Ral+ 51. Bd1 Kb6 52. Qc3 Rb1 53.
Qd4 Kc7 54. Qg7+ Kb6 55. Qe7 Ba4 56. Qxd6+ Be6 57.
Qd8+ Kb7 58. Q18 Nd7 59. Qa3 Kb6 60. Qd3 Rel 61. Kd2
48. R16 Bc4 49. RIS Nd8 50. Rxh5 Bf7 51. Rh8 Nc6 52.
Re5 62. Qb3+ Kc7 63. Be2 Bd5 MAV-MCTS builds
Rh7 Ne5 53. f4 Nd7 54. Rxf7 Kc6 55. Rxd7 Kxd7 56. a6
fortress. 64. Qb4 Bhl 65. Ba6 Bc6 66 Ke2 Kd8 67. Be4
Kd6 57. b7 Kc7 58. h5 Kd6 59. b8=Q+ Ke6 60. a7 Kd5 61.
Bd5 68. Bа6 Be6 69. Kd2 Bh1 70. Ke3 Bd5 71. Bb5 Rc7
a8=Q+ Kc5 62. Qa4 Kd5 63. Qe5# 1 1-0 0
72. Ba4 Ra7 73. Qd4 RC7 74. Qh8+ Kc7 75. K12 Kd6
76. Qg7 Bh1 77. Bb5 Be6 78. Qd4+ Ke7 79. Qb4+ Kd8
Game 6 Stunning piece sacrifice
80. Be4 Bd5 81. Bd3 Ke8 82. Ke3 Rb7 83, Qd4 Be4 84.
Qh8+ Ke7 85. Bc4 RC7 86. Qg7+ Kd6 87. Bb5 Bc6 88.
Date: 2024-11-14
Be4 Bd5 89. Ba6 Be4 90. Qal Rc5 91. K12 Bd5 92. Be2
White: MAV-MCTS(M 100)
Bc6 93. Kg3 Rd5 94. Qa3+ Rc5 95. Bfl Kc7 96. Be2 Bd5
Black: Stockfish-L18
97. Kh4 Kc8 98. Qb2 Kc7 99. Kg3 Be4 100. Bf3 Bd5 101.
Result: 1/2 - 1/2
Bd1 Re4 102. Bh5 Bc6 103. Qg7 Rel 104. Qe7 Rc3+ 105.
Online PGN: https://ficeess.or//TTgggss
K12 Rc2+ 106. Kgl (threefold repetition). MAV-MCTS proves its decision to sacrifice a queen on move 14 was correct. 1/2 1/2
1. c4 c5 2. Nf3 d6 3. d4 cxd4 4. Nxd4 Ni6 5. Ne3 a6 6.
Be3 e6 7. f3 Be7 8. Qd2 b5 9. g4 Ntd7 & 10. O-0-0 Ne5
11. g5 b4 12. Na4 O-0 13. f4 Ned7 14. Qxb4 Nc5 15. h4
Bd7
Game 5 Masterful middlegame maneuvering
Date: 2024-11-12
White: MAV-MCTS(M = 2000)- max scoring
31

---

Mastering Board Games by External and Internal Planning with Language Models
8
7
7
6
2
5
5
8
4
3
3
8
8
2
1
a C e g h
b
e
g
16. Nxe6 MAV-MCTS sacrifices knight on a square
Stunning end to an exciting game. 1/2 - 1/2
defended by three pieces. Nxe6 17. f5 d5 It is still unclear what MAV-MCTS gained for a sacrificed piece.
Game 7
18. Qb3 Bxa4 19. Qxa4 Bc5 20. Kbl Bxe3 21. fxe6 d4 22. exf7+ Kh8 23. e5 Rxf7 24. Bg2 Raa7 25. Rhel Bf2 26. e6
Exquisit active defense
Date: 2024-11-14
RIS 27. Re2 Re7 28. Rfl Q18 29, Qb4 Nd7 30. Bh3 d3 31.
White: Stockfish-L19
exd3 Bc5 32. Rxf5 Bxb4
Black: MAV-MCTS(M 250)
Result: 0-1
Online PGN: httpp://fichess.or/yyyaarr
8
1. e4 c5 2. Ne3 Ne6 3. Nf3 g6 4. d4 cxd4 5. Nxd4 Bg7
6. Be3 d6 7. h3 NI6 8. g4 O-O 9, g5 Ne8 10. h4 Nc7 11. 13. h5 fxe4 14. Qd2 d5 15. O-0-0 d4 16. hxg6 This is start of an attack where cost of mistake is an immediate loss. dxc3 17. Qxc3 Qc8 18.
f4 e5 12. Nde2 f5
6
8
Qb3+ Be6 19, Qxb7 Nd5 20. Bc5 Rb8 21. gxh7+ Kh8
4
8
8
2
8
7
6
a
e
h
5
33. exd7 It was likely better to grab the queen, but the position remain unclear. Qd8 34. Ríe5 Rxe5 35. Rxe5
4
Be7 36. d4 h6 37. g6 a5 38. Rel Kg8 39. d5 Qb6 40. h5 Kf8 41. a3 a4 42. Rel Qa5 43. d6 Bd8 44. Rc8 Qel+ 45. Ka2 Qe6+ 46. Kal Qf6 47. Bg4 Qg5 48. Bf5 Qf6 49. Be6 Qfl+ 50. Ka2 Qal+ 51, Kxal (stalemate).
3
2
8
1
b
g
22. Qxg7+ White sacrifices a queen as the last resource.
Kxg7 23. Bx18+ Qx18
32

---

Mastering Board Games by External and Internal Planning with Language Models
8
7
7
6
5
5
4
8
3
3
3
3
7
2
609
D00
1
a
C
e
g h
b
e g
24. h8=R White finds an opportunity to underpromote
15. Qxf5 MAV-MCTS grabs a pawn without fearing numerous discovered attacks. Nd5 16. Qe2 Nxc3 17. Qxc3 e4 18. Ng5 Already on move 15, MAV-MCTS needed to assess the exchange sacrifice correctly. Bf6 19. Qa3 Bxal 20. Qxal Nf6 21. Ba3 Rg8 22. Bb2 h6 23. Bxf6
to a rook! Qxh8 25. Rxh8 Rxh8 26. 15 Ne3 27. fxe6 Nxdl
28. Kxdl Rhl After the dust has settled, MAV-MCTS
has a decisive advantage. 29. Ng3 Rg1 30. NB5+ Kg6
31. e7 Kf7 32. g6+ Ke8 33. Kel Nd4 34. Ne3 Kxe7 35.
c3 N13+ 36. Ke2 Rxg6 37. N K16 38. Ne3 Kg5 39, K12
hxg5 24, Bxg5 Bg4 25. Rel Qh5 26. h4 Bxe2 27. Bxe4
Rd6 40. Be2 Nh4 41. b4 Rd2 42. a4 NF5 43. Nxf5 Kxf5
Bxc4 28. Qd4 Bb3 29. Bxc6 Rab8 30. Kh2 Qg6 31. Bd7
44. Ke3 Re2 45. c4 Ra2 46. c5 Rxa4 47. b5 Ra3+ 48, Kd2
Rgf8 32. Re5 Qc2 33. Be3 QdI 34. Rg5 Qxd4 35. Bxd4
e3+ 49. Kc2 Ra2+ 50. Kd3 Kf4 51. c6 Rd2+ 52. Kc3 Rd8
53. Kb4 Kg3 54. Kas KP2 55. Bc4 Rd4 56. b6 Rxc4 57.
bxa7 c2 58. a cl=Q+ 59. Kb6 Qb4+ 60. Ka7 Qa5+
8
61. Kb7 Rb4+ 62. Kc8 Qxa8+ 63. Kd7 Qg8 64. Ke7 Qb8
7
65. Kf6 e4 66. c7 Qg8 67. Kf5 Q17+ 68. Kg5 Qd7 69.
c Qxc8 70. Khs Rbl 71. Kh4 Rg 72. Khs Qh8## 0
6
Game 8
5
The strength of bishop pair
4
Date: 2024-11-14
White: MAV-MCTSMM 500)
3
Black: Stockfish-L18
2
Result: 1-0
Online PGN:
1
1. d4 f5 2. g3 Ni6 3. Bg2 e6 4. NI3 Be7 5. c4 6-0 0-0
d6 7. Nc3 Qe8 t 8. b4 Kh8 9. Qc2 Nbd7 10. a4 c6 11. a5
a
b
d
e
f
9
e5 12. b5 a6 13. bxc6 bxc6 14. dxe5 dxe5
A bishop pair dominates the board even in the endgame. R17 36. Bí5 Kg8 37. Bb6 Rf6 38. g4 Rfxb6 39, axb6
Rxb6 40. Bd3 Bd1 41. Bc4+ Kf8 42. Kg3 Rf6 43. Bd5 a5
44. Rh5 Ra6 45. Rh8+ Ke7 46. h5 Rd6 47. Be4 Rd8 48.
Rh7 K16 49. f4 Rg8 50. g5+ Ke6 51. h6 gxh6 52. Rxh6+
Kc7 53. Ra6 a4 54. g6 Be2 55. Rxa4 K16 56. Rb4 Rxg6+
57. Bxg6 Kxg6 58. Rb1 Bc4 59. Rb4 Be6 60. Rb1 Kf6
61. Rb4 Bc8 62. Rb1 K15 63. Rb8 Bd7 64. Rb7 Ba4 65.
Re7 Kg6 66. Re2 KI5 67. Ra2 Bb3 68. Ra7 Be6 69. Rb7
Be4 70. Rg7 Be6 71. Rb7 Bc4 72. Rd7 Kg6 73. K13 Ki5
74. Rg7 Bd3 75. Rh7 Be4+ 76. Ke3 Bc6 77. Rh3 Be8 78.
Rh7 Bg6 79. Re7 Kf6 80. Rc7 Be8 81. Re4 Bb5 82. Re8
Bd7 83. Ra8 Bh3 84, Ra2 KI5 85, K13 Kf6 86. Ra8 Ke6
33

---

Mastering Board Games by External and Internal Planning with Language Models
87. Re8 K16 88. Re4 Kf5 89. Kf2 Ke6 90. Re2 Bf5 91.
Rc7 Kd6 92. Rb7 Kd5 93. Kg2 Kc5 94, Rf7 Bd3 95. Kf3
Kc6 96. Kg4 Be2+ 97. Kh4 Bfl 98. f5 Bb5 99, Re7 Bc4
8
100. Kg5 Bg8 101. Kg6 Kc5 102. Kg7 Bb3 103. Rd7 Kc6
7
104. Ra7 Kd5 105. Ra6 Ke4 106. Rb6 Bd5 107. Rd6 Ke5
108. Rxd5+ Kxd5 109. Kh6 Ke4 110. Kg5 Kd5 111. f6
6
Ke6 112. Kg6 Kd6 113. f7 Ke7 114. Kg7 Kd7 115. f8=Q
Kc7 116. Qc7+ Kb6 117. Kg6 Kb5 118. Qa3 Ke4 119. K17
5
8
Kd4 120. Qel Ke4 121. Qg5 Kd4 122. Qb5 Kc3 123. Kf6
4
Kd2 124. Qi1 Ke3 125. K15 Kd4 126. Qe1 Kd5 127. Qh6
Kc4 128. Qb6 Kd5 129. Qh6 Kc5 130. Qa6 Kb4 131. Qa2
3
Kc3 132. Ke4 Kb4 133. Kf3 Kb5 134, Qa7 Kc6 135. Ke4
Kb5 136. Qa3 Kb6 137. Kd5 Kb7 138. Qa5 Kb8 139. Kc6
2
8
Ke8 140. Qc7# Note that MAV-MCTS was inefficient in delivering forced mates because of a very low simulation budget. 1
1
a
b
d
e g
N2. 13, a4 axb5 14. Nxb5 Ni6 15. Bc4 Bxf5 16. O-0 Na6 17. 14 e4 Despite being pawn down, MAV-MCTS has a compact pawn structure without any weaknesses that offer an active piece play. 18. Re1 Nb4 19. Ra3 Nd3 20. Re3 Nb4 21. Re2 Kh8 22. Nf1 Bg4 23. Rae3 Qe8 24. Qb3
Game 9 Material quality over quantity
Date: 2024-11-14
White: Stockfish-L119
Black: MAV-MCTS(M = 500)
Result: 1/2-1/2 1/2
Online PGN: https:/liihess.or//Maaaa
1. d4 Nf6 2. c4 c5 3. d5 e5 4. Ne3 d6 5. e4 Be7 6. Nf3
8
Nbd7 7. g3 0-0 8. Bg2
7
6
5
7
4
3
5
8
2
4
8
1
a
b
C
d
e
f
g
2
A
8
24... For two moves in row MAV-MCTS estimates that the bishop is stronger piece than the rook and declines to win an exchange. 25. Rel Rfb8 26. Bd2
a
C e
g h
Nbxd5 27. Rxe4 Bf8 28. R4e2 Nb6 29. Bf7 Qh3 30. Be6
b5..b5 MAV-MCTS plays a pawn sacrifice similar to Benko gambit. 9. cxb5 a6 10. Bfl Ne8 11. Nd2 f5 MAV-MCTS proceeds with shattering White's pawn structure. 12. exi5
Nxa4 31. Bxg4 Qxg4 32, QE7 Qg6 33. Qxg6 hxg6 34. Nc7
Ra7 35. Ne6 Nxb2 36. Be3 Nc4 37. Bxf6 gxf6 38. Rel
d5 39. Rd1 Rd7 40. Re2 Nb6 41. Rb1 Bd6 42. Rcb2 Re8
43. Rxb6 Rxc6 44. K12 c4 45. Rc6 Rc7 46. Rbb6 Rxc6
47. Rxc6 Kg7 48. K13 K17 49. Ne3 Bb8 50. Rc8 Rb6 51.
Nxd5 Rb3+ 52. Kc4 f5+ 53. Kd4 c3 54. Kc4 Rb7 55. Nxe3
Ba7 56. Nd5 Bgl 57. h3 Bh2 58. g4 fxg4 59. Rh8 Kg7 60.
Rh4 g3 61. Rg4 Rb2 62. Kc3 RI2 63. Ne3 RI3 64. Kd2 g2
65. Nxg2 Rxh3 66. Kel Bxf4 67. Kf2 g5 68. Nh4 Rxh4 69.
Rxh4 gxh4 70. Kel h3 71. K12 Bh2 72. KF3 Bd6 73. Kf2
Bh2 74. Kf3 Bd6 75. Kf2 Bh2 (threefold repetition). This
34

---

Mastering Board Games by External and Internal Planning with Language Models
well known draw because the queening square is the opposite color of the bishop. 1/2 1/2
8
Game 10 Exemplary advantage conversion
7
Date: 2024-11-14
6
White: MAV-MCTS(M 2000)
5
Black: Stocktish-L19
Result: 1-0
4
Online PGN: https::/lichess.or//HL.O.
1. d4 d5 2. c4 c6 3. NI3 Nf6 4. c3 e6 5. Ne3 a6 6. c5
3
Nbd7 7. b4 a5 S 8. b5 g6 9. Be2 Bg7 10. O-0 h5
11.
2
8
Rb1 O-O 12. Na4 Qe7 13. Ne5 Nxe5 14. dxe5 Ng4 15.
Nb6 Rb8 16. f4 Bd7 17. Bxg4 hxg4 18. Qxg4 cxb5 19. 1
Nxd7 Qxd7 20. Bb2 b6 21. cxb6 Rxb6 The material is equal, but MAV-MCTS has much more active bishop and hpper-hands for a kingside attack with the minimal resources. 22. h4 Rc6 23. h5 b4 24. Rf3 Rfc8 25. hxg6 fxg6 26. Qxg6 Q 27. Qg5 Q 28. Qxf5 exf5 29. Rg3 Kh7 The conversion is not easy because MAV-MCTS's rooks are seemingly deprived of any activity.
b
g
The endgame looks scary for White because of the advanced Black's pawns, but MAV-MCTS correctly evaluates that Black's king is too weak. 34. Rg5 Rd2 35. e6 Rdxd4 36. exd4 b3 37. g4 Rc3+ 38. Ke2 Kf8 39.
e7+ Kxe7 40. Rxg7+ Kf6 41. Rb7 fxg4 42. Rh5 Rc4 43. Rxb3 Rxd4 44. Rb6+ K17 45, Rh7+ Kg8 46. Rd7 Re4+
47. Kd3 Rxf4 48. Ra7 Rf8 49. Rg6+ Kh8 50. Kd4 a4 51.
8
Rh6+ Kg8 52. Rg6+ Kh8 53. Kc5 d4 54. Rh6+ Kg8 55,
Rg6+ Kh8 56. Ke6 Rf4 57. Rf6 Rf1 58. Rxf1 Kg8 59. Ke5
g3 60. Rg1 d3 61. Rxg3+ Kh8 62. Kf5 d2 63. Ra8+ Kh7
64. Ra7+ Kh8 65. Rd7 dI=B 66. Rxdl Kh7 67. Rh1# 1-0
6
Game 11 Controlling key squares
Date: 2024-11-12
White: MAV-MCTS(M = 2000) max scoring
8
Black: Stockfish-L.18
Result: 1-0
Online PGN: https://iichss.oo//2277/
1. e4 c5 2. NE3 d6 3. d4 cxd4 4. Nxd4 Ni6 5. Nc3 g6 6.
a
b C
h
Be3 Bg7 f3 O-O 8. Qd2 Ne6 9. 0-0-O d5 10. Qel e5
30. Kf2 MAV-MCTS finds beautiful maneuver which activates all its pieces at the cost of pawn. Rc2+ 31. Kf3 R8c4 32. Rhl+ Kg8 33, Bd4 Rxa2
11. Nxc6 bxc6 12. exd5 Nxd5 13. Bc4 Be6 14. Kbl Rb8
15. Ne4 Qe7 16. Bc5 Rid8 17. g4 a5 18. a4 h6 19. Bb3
Kh8
35

---

Mastering Board Games by External and Internal Planning with Language Models
Game 12 Exploiting opponent's aggressive play
8
Date: 2024-11-14
White: MAV-MCTS(M = 2000)
7
Black: Stockfish-L.17
Result: 1-0
Online PGN:
5
1. e4 c5 2. N13 Nc6 Bb5 a6 4. Ba4 Nf6 5. O-0 Be7 6. Re1 b5 7. Bb3 O-0 8. a4 b4 a5 d5 E 10. exd5 e4 11. dxc6 Black sacrifices knight and relies on aggressive piece play with a possible kingside attack. Bd6 12. d4 MAV-MCTS decides to immediately activate its pieces by returning the sacrificed knight. exf3 13. Qxf3 h6 14. h3 Rb8 15. Nd2 Rb5 16. No4 Re8 17. Rxe8+ Qxe8
8
8
3
2
1
a C e g h
8
20. Ba3 MAV-MCTS vacates c5 square for a knight and estimates that the control over a3-18 diagonal is much more important than the control over gl-a7 diagonal. Additionally, it protects b2 square from any possible attack along the b line. Nf4 21. Bxe6 Nxe6 22. h4 Rxdl+
7
6
5
23. Qxdl c5 24. Qd6 Qb7 25. Qd3 Qc6 26. g5 h5 27. Qc4
Qd7 28. Ka2 Rd8 29. Rf1 Qc8 30. Rf2 Rd4 31. Qb5 Qd8
4
32. Qe6 Rdl 33. Bxc5 Nxc5 34. Qxc5 Kh7 35. Re2 Rd5
36. Qe6 Rd7 37. Re3 Rc7 38. Qb6 Qd7 39. Qb5 Qh3 40.
3
c4 Qxh4 41. c5 Qf4 42. Rd3 h4 43. Qxa5 Rc8 44. Qa6 Rc7
2
3
45. Qb6 Re8 46. Qb7 RI8 47. c6 h3 48. c7 h2 49. Rd8
h 50. c Rxd8 51. Qxd8
1
a b d
e
f
g
h
8
18. Bxh6 MAV-MCTS enters a scary tactical sequence.
w
Rí5 19. Nxd6 cxd6 20. Qg3 Nh5 21. Qe3 Qxc6 22. g4 RI3 23. d5 Rxe3 24. dxc6 Rxh3 25. Bg5 Nf6 26. Bxf6 gxf6 27. Ra4 MAV-MCTS finishes the resulting winning endgame with a nice rook lift. Kf8 28. Rxb4 Rh8 29,
6
5
Rb8 Ke7 30. Bd5 Rg8 31. f3 Rg5 32. c4 Kd8 33. b4
Re5 34. Kf2 Kc7 35. Ra8 f5 36. f4 Rxd5 37. cxd5
4
8
Kd8 38. g5 Ke7 39. Rxc8 f6 40. Ke3 fxg5 41. fxg5
3
A
Kf7 42. Kf4 Ke7 43. Rg8 Kf7 44. Re8 Kg7 45. Kxf5
Kh7 46. c7 Kg7 47. Rb8 K17 48. c8=Q Ke7 49. Qb7# 1-0
Game 13 Well executed caveman attack
1
a
b
c
d
e
h
Date: 2024-11-14
51...Qh3 A long maneuvering phase of the game results in four queens endgame! MAV-MCTS is completely winning because of very weak Black's king. 52. Qbb8 Qe6+ 53. b3 f5 54. gxf6 Bxf6 55. Qb7+ Be7 56. Qbxe7+ Qxe7 57. Qxe7+ Kh8 58. Qf6+ Kg8 59. Qxf4 exf4 60. a5 g5 61. a6 Kg7 62. a7 K17 63. a8=Q g4 64. Qd5+ Ke7 65.
White: MAV-MCTS(M 100)
Black: Stockfish-L119
Result: 1-0
Online PGN: https://ficeees.org/ggDiGGG
1. e4 g6 2. d4 Bg7 3. Ne3 d6 4. Be3 a6 5. Qd2 b5 6. h4
h6 7. h5 b4 8. Nd5 c6 9. Nxb4 g5 10. Ne2 a5 11. Nd3 Ni6
Qd6+ K17 66. Qf6+ Ke8 67. Nc5 gxf3 68. Qg7 12 69. Qd7+
12. f3 Qc7 13. Ng3 c5 14. c3 a4 15. Be2 0-0
K18 70. Ne6+ Kg8 71. Qg7# 1-0
36

---

Mastering Board Games by External and Internal Planning with Language Models
inefficient in delivering forced mates because of the extremely low simulation budget. 1-0
Game 14 King in the center
7
Date: 2024-11-21
White: MAV-IS(b 4,
5
Black: Stockfish-L15
Result: 1/2 1/2
Online PGN: https://iichess.or////gk/e
3
e4 c6 2. d4 d5 3. Nd2 N16 4. c5 Níd7 5. Bd3 c5 6. c3 b5
8
A
S 7. Ne2 Ba6 8. a3 Nc6 9. Nf3 cxd4 10. cxd4 Qc8 11. b4
Bb7 12. O-O a5 13. bxa5 Rxa5 14. Ng5 Be7 15. Bd2 Rxa3
16. Rxa3 Bxa3 17. Nf4 MAV-IS starts sequence that sacrifices two central pawns. Nxd4 18. Qh5 Nxe5
a
C
e
g
h
16. Bxg5 MAV-MCTS sacrifices bishop for devastat-
ing attack. hxg5 17. h6 Bh8 18. Qxg5+ Kh7 19. NE5 Nh5 20. Rxh5 f6
8
7
6
5
7
4
3
5
8
3
2
1
3
8
8
8
a b d e
9
19. Ngxe6 MAV-IS sacrifices knight to keep Black's king in the center. Nxe6 20. Bxb5+ Be6 21. Nxe6 Bxb5 22. Rel Bd6 23. Nxg7+ Kd7 24. Rxe5 Bxe5 25. Qxe5 MAV-IS correctly estimated that the vulnerable Black's king and dark squares are worth the sacrificed exchange. Qc5
a
C e
g h
21. Qg7+ A stunning queen sacrifice the cherry on top. Bxg7 22. hxg7+ Kg8 23. Rh8+ KF7 24. Rxf8+ Ke6
25. Nxc5+ Qxc5 26. g8=Q+ Kd7 27. Rd8+ Kc7 28. Rxc8+
Kb6 29. dxc5+ Kb7 30. Bb5 Ra6 31. 0-0-0 Ka7 32. g3 a3
33. Nxe7 d5 34. b3 d4 35. f4 Re6 36. Re8 d3 37. Qh8 f5
38. Bxd3 RI6 39. Be4 Re6 40. g4 Rxe4 41. Rhl Rxc4 42.
Ne8+ Kb7 43. Qg7+ Nd7 44. bxc4 Kc6 45. Kbl Kxc5 46.
Kel Nb8 47. Qd4+ Kc6 48. RI8 Nd7 49. c5 Nxf8 50. Rel
Nd7 51. Re2 Kc7 52. g5 Kxc8 53. Qh8+ Kc7 54. g6 Nb8
55. Rel Na6 56. Re7+ Kc6 57. Qa8+ Kb5 58. g7 Nb8 59.
o4+ Kxc4 60. Rel Kb5 61. g8=Q Kxc5 62. Rg Na6 63.
Kd1 Kb5 64. Rh1 Ne7 65. Rh5 Nxa8 66. Qd5+ Kb6 67.
Qc4 Kb7 68. Qd5+ Kc8 69. RxI5 Nb6 70. Qc5+ Kb7 71.
Qe2 Nd5 72. Rxd5 Kb8 73. Re5 Kb7 74. Qf2 Kc7 75. Kc2
Kb8 76. f5 Kb7 77. Qe3 Kc7 78. Qgl Kd8 79. Qe3 Kc7 80.
f6 Kc6 81. Kd2 Kb7 82. Kc2 Kaб 83. Qgl Kb7 84. f7 Kc7
85. Kd3 Kd8 86. Qfl KC7 87. 18=Q Kb7 88. Kd2 Kc7 89.
Qe2 Kc6 90. Qe7 Kb6 91. Q65#t Note that MAV-MCTS
37

---

Mastering Board Games by External and Internal Planning with Language Models
1xx..Nxf5 To avoid a passive defense, MAV-IS sacrifices piece for two central pawns. 12. exf5 Bxf5 13. Bd3 e4 14. Bfl d4 15. Nd5
7
8
7
5
6
5
3
4
3
a C e g h
2
8
3
2
3
26. h3 MAV-IS plays quite prophylactic move which resolves a potential back rank issues before proceeding with the attack. Ra8 27. Bf4 Bd3 28. Nh5 Rc8 29, Be3 d4
1
b
d
e
f
9 h
30. Nf6+ Kc6 31. Bxd4 Qd6 32. Qe3 Kb7 33. Be5 Qe6
15...0-0-0 MAV-IS pushes backwards the only White's active piece, while all other pieces are still stuck at their original squares. 16. NF4 Qd6 17. Be2 Qc5 18. O-O d3+ 19. Khl dxe2 20. Qxe2 h5 21. c4 Bg4 22. Qel Rd1 23, Be3 Rxel 24. Bxc5 Rxal 25. Rxal h4 26. Re1 Bf5 27. Kg1
34. Qd4 Rc4 35. Qb2+ Ka6 36. Qa3+ Kb6 37. Qb3+ Kc5
38. Qb8 Rcl+ 39. Kh2 Rc2 40. Ng4 Bf5 41. Ne3 Rx12 42.
Qa7+ Kb5 43. Qb7+ Kc5 44. Qa7+ Kb4 45. Qb7+ Ka4 46.
Qa7+ Kb4 47. Qb7+ Kc5 48. Qa7+ (threefold repetition).
1/2 12-11 1/2
h3 28. b3 hxg2 29. Rdl Bh3 30. Rd5 16 31. Nxh3 Rxh3 32,
Bd6 Rd3 33. Kxg2 Rxd5 34. cxd5 Nd4 35, Kf2 Ní5 36.
Bb4 Kd7 37. Ba3 Kc7 38. Bc5 Kd7 39, a4 Kc7 40. Bb4
Game 15 Dominating the center
Kd7 41. Bf8 g6 42. 64 Ne7 43. Bxe7 Kxe7 44. a5 Kd6
45. Kel Kxd5 46. Ke2 Kd4 47, b5 axb5 48. K12 (game
Date: 2024-11-21
terminated by early termination). 0-1
White: Stockfish-L10
Black: MAV-IS(6 =)
Game 16
Result: 0 0-1
Online PGN: https:/ltchess.rr/SSRRRNN
The power of zwischenzug
e4 c5 2. NI3 Ne6 3. d4 cxd4 4. Nxd4 e5 5. Nb5 a6 6.
Date: 2024-11-21
Nd6+ Bxd6 7. Qxd6 Qf6 8. QdI Qg6 9. Ne3 Nge7 10.
White: MAV-IS(b 4, d 2)
f4 d5 11. f5
Black: Stockfish-L10
Result: 1/2-1/2
Online PGN:
1. e4 e5 2. f4 exf4 3. Nf3 d6 4. d4 g5 5. g3 g4 6. Nh4 f3
7. Ne3 S Nf6 Bg5 Be7 Qd2 Ne6 10. O-O-O h6 11.
Bxh6 Nxd4
6
4
A
2
3
3
8
600
a
b
0
38

---

Mastering Board Games by External and Internal Planning with Language Models
Game 17
Execution is stronger than threat
Date: 2024-12-01
White: MAV-MCTS(M = 2000)
7
Black: Stockfish-1.20
Result: 1/2- 1/2
Online PGN:
5
1. c4 g6 2. d4 Bg7 3. Nc3 d6 4. f4 Nc6 E 5. Be3 c6 6. Nf3 a6 7. Bd3 b5 8. a4 b4 9. Ne2 Nf6 10. 0-0 a5 11. f5
MAV-MCTS does not hesitate to start an immediate pawn break. exf5 12. exf5 O-0 13. Bg5 Ne7 14. Ng3 Ba6
3
15. Bxa6 Rxa6 16. Qd3 Ra8 17. Nd2 Ned5 18. c3 bxc3
3
19. bxc3 Qd7 20. Nde4 Nxe4 21. Nxe4 Rfe8 22. h4 Rab8
23. Rf2 Qc6 24. Qf3 Qd7 25. Qd3 h6 26. Bd2 c5 27, Rafl
cxd4 28. fxg6 fxg6
a
C e g h
12. Bg7 Instead of an immediate recapture, MAV-IS complicates the game by playing an in-between move. Rg8 13. Qxd4 Rxg7 14, e5 Nh5 15. Bc4 K18 16. Kbl d5
8
7
17. Nxd5 c6 18. Nxe7 Qxd4 19. Rxd4 Kxe7 20. Rel b5
6
5
8
A
4
3
8
6
2
1
4
b d
e f h
29. Nf6+ MAV-MCTS does take time for the prepara- tory moves, but jumps with knight to square that is defended twice to open the diagonals and lines around Black's 's king, Nxf6 30. Rxf6 Re6 31. Qxgó Rxf6 32. Rxf6 Qe7 33. Rf3 Qe8 34. Qg4 Kh8 35. Rg3 Be5 36. Bf4 dxc3
2
8
a
b c
e
9 h
37. Bxe5+ Qxe5 38. Qg6 Qd4+ 39, Khl Qxh4+ 40. Rh3 Qel+ 41. Kh2 Qe5+ 42. Kgl Qel+ 43. Kh2 Qe5+ 44,
21. e6 Instead of retreating the attacked piece, MAV-IS
plays strong in-hetween move that sacrifices a piece and leads to a dynamic equality. bxc4 22. Nf5+ Kf6 23. Nxg7 Nxg7 24. Rxg4 Bxe6 25. Rf4+ Kg5 26. Rxf3 f5 27.
Kgl Qel+ 45, Kh2 (threefold repetition). Perpetual check
saves Black from getting mated. 1/2 1/2
b3 Rh8 28. Rf2 Rh3 29. bxc4 a5 30. Re5 a4 31. Rc5 Bd7
32. Ra5 Be6 33. Rxa4 Ne8 34. Re2 Rh6 35. c5 Ng7 36.
Game 18
Ra7 K16 37. Ra8 Bc4 38. RI8+ Kg6 39, RI2 Rh7 40, a4
The dragon bishop
Ne6 41. R8xf5 Ra7 42. Rf6+ Kg7 43. h4 Bd5 44. h5 Nxc5
Date: 2024-12-01
45. Rg6+ Kh7 46. Rff6 Be4 47. Rg5 Bd5 48. Rgg6 Be4 49.
White: Stockfish-I.19
Rg5 Bd5 50. Re5 Rb7+ 51. Kel Nxa4 52. g4 Nb6 53. g5
Black: MAV-MCTS( 2000)
Ra7 54. Kdl Nc4 55. Re8 kg7 56. h6+ Kh7 57. Kel Rb7
Result: 1/2-1// 1/2
58. Kf2 Rd7 59. Ke2 Na3 60. K12 Nxc2 61. Re5 Bg8 62.
Online PGN:
Kg3 Nb4 63. Re8 Bf7 64. Rb8 c5 65. RC8 Re7 66. Rxc5
1. e4 c5 2. Nf3 d6 3. d4 cxd4 4. Nxd4 Nf6 5. Ne3 g6 6.
Nd3 67. Rec6 Re3+ 68. Kh4 Ne5 69. RC7 Kg8 70. Rc8+
Be3 Bg7 7. f3 O-O 8. Qd2 Nc6 9. Bc4 Qa5 10. 0-0-0 Bd7
Kh7 71. Rc7 Kg8 72. Re8+ Kh7 73. Rc7 1/2 1/2
S 11. Kb1 Rfc8 12. Nb3 Qd8 13. Be2 Ne5 14. h4 a5 15.
Nd4 a4 16. g4 a3 17. 63 Qa5 18. Neb5 Qxd2 19. Bxd2 Ne6
20. Bel Nxd4 21. Nxd4 Re3 22, Rhel h5 23. g5 Ne8 This
39

---

Mastering Board Games by External and Internal Planning with Language Models
seemingly unimportant knight will play pivotal role in what is to come.
26...Nee7 27. b4 White makes a "luft" to escape a pin from the dark-squared bishop. Ne6 The knight enters the game with great effect! 28. Kb3 Ra8 29, Nxe6
8
8
7
6
6
5
4
A
8
4
3
3
2
8
1
a
b
C
d
e
h
24. Bxa3 Prelude to a very unusual tactic. Rxa3
b
e 9
29.. This zwischenschach is the only move which secures sufficient compensation for the exchange because it pushes the king towards the center of the board. 30. Kc4 fxe6 31, Rel Rc8+ 32. Kd3 Bc3 33. Rfl Bxb4 34. c3 Ba5 35. Bdl Bb5+ The light-squared bishop takes over the role of a pinner. 36. c4
8
6
B
8
8
8
7
8
3
6
5
4
8
3
a
b
C
e
h
8
25. Kb2 lone king "forking" two rooks. Rxa2+ 26.
3
Kxc3
2
1
8
a b d e
9
36...d5 MAV-MCTS is pinning White from every angle!
6
37. Bb3 Ba6 38. f4 Kg7 39, exd5 exd5 40. Kd4 Rds 41. c5 White returns the exchange to release the tension and enter a balanced endgame. Bxf1 42. Rxfl e6 43. Ral b6 44. Kd3 Rc8 45. cxb6 Bxb6 46. Ra6 Rb8 47. Kd2 Bf2 48. Be2 Kf7 49, Ke2 Rb2 50. Kxf2 Rxc2+ 51. Kg3 Ke7 52.
4
8
KF3 Rel 53, Kg2 d4 54. Ra4 Rdl 55. KF3 Rh1 56. Rxd4
Rxh4 57. Ke3 e5 58. Re4 Rh3+ 59. Kd2 Rf3 60. Rxe5+
2
Kf8 61. Re6 Kf7 62. Rf6+ Kg7 63. Kel h4 64. Ke2 Rg3
65. Re6 h3 66. Kf2 Rg4 67. Re7+ Kg8 68. Ra7 h2 69.
Ra8+ Kg7 70. Ra7+ Kg8 71. Ral Kf7 72. Rel Rh4 73.
a
b
C
d
8
h
Rh1 Rh3 74, Kf1 Ke6 75. Kg2 Re3 76. f5+ Kxf5 77. Ral
40

---

Mastering Board Games by External and Internal Planning with Language Models
Re8 78. Kh1 Re7 79. Ra5+ Re5 80. Ral Re8 81. Kxh2
Re7 82. Ra4 Re4 83. Ra3 Kg4 84. Ral Re3 85, Rg1+ Kf4
86. Rb1 Re2+ 87. Khl Re3 88. Rel Kg3 89. Kg Rb3 90.
8
Kh1 Kh3 91. Kg1 Rb4 92. Kf2 Rf4+ 93. Kel Rf5 94. Rc2
7
Rxg5 95. Kf1 Rg4 96. Re2 g5 97. Re6 Kh2 98. Rh6+ Kg3
99. Rb6 Re4 100. Rb3+ Kh2 101. Rb2+ Khl 102. K12
6
Kh2 103. Kfl+ Khl 104, Kf2 Kh2 105. Kf1+ (threefold
repetition). peaceful outcome wild game. 1/2 1/2
5
4
Game 19 Taming the dragon bishop
3
Date: 2024-12-01
2
8
8
8
8
White: MAV-MCTS(M- = 20000
Black: Stockfish-L.19
1
Result: 1-0
Online PGN: httpss/lichessor///eRRR2222
b
e g
1. e4 c5 2. Nf3 d6 3. d4 cxd4 4. Nxd4 Nf6 5. Nc3 g6 6.
33. Rh3 Another beautiful move by MAV-MCTS. Notice that a symmetric move Rf1 is the only alternative which
Be3 Bg7 7. f3 O-O 8. Qd2 Ne6 9. Bc4 Qa5 10. 0-0-0 Bd7 E 11. Bb3 MAV-MCTS chooses the different approach to the Sicilian Dragon than Stockfish in Game 18. Ne5 12. Bh6 MAV-MCTS immediately exchanges the favorite piece of every Dragon player. Bxh6 13, Qxh6 Rac8 14. Nd5 Nxd5 15. exd5 Qc5 16. a3 a5 17. h4 f6 18.
secures the advantage. Kh8 34. Rel Qf4 35. Bbl Bxh3
36. Qxh3 Qg4 37. Qh1 f5 38. Rg1 Qxf3 39. Qxf3 Rxgl
40. Qh5 Re1 41. Qh4 Re2 42. Bd3 Re5 43. Bxb5 Rf6
44. Qf4 Re4 45, QB3 Rg4 46. Ka2 h5 47. Qe2 RI7 48.
Be8 Rfg7 49. Qe6 f4 50. Bf7 Kh7 51. Qf5+ R4g6 52.
Rhel a4 19. Ba2 b5 20. Qd2 Rfc8 21. h5 gxh5 22. Rhl RI8
Qxh5+ Rh6 53. Q15+ Kh8 54. Qc8+ Kh7 55. Q15+ Kh8
23. Rxh5 Rf7 24. Kb1 Nc4 25. Qel Rg7 26. g4 Ne5 27.
56. Qxf4 Rf6 57. Qh4+ Rh7 58. Bh5 Kg7 59. Qg4+ Kh8
Rh2 Rf8 28. Kal Nc4 29, Rh5 Ne5 30. c3 Nxf3 31. Nxf3
60. Qxa4 Kg8 61. Qe8+ Rf8 62. Qg6+ Kh8 63. a4 Rg8 64.
Bxg4
QES Rh6 65, a5 R16 66. Qh3 Kg7 67. Qc3 Kf8 68. a6 c5
69. a7 Ke7 70. Qb6 RABS 71. Qc7+ Kf6 72. Qxd6+ Kf5
73. Qe6+ KF4 74. d6 Kg5 75, Bf7 Ra8 76. Qxe5+ Kh4
77. Qh2+ Kg4 78. Qg2+ Kh4 79. Qh2+ Kg5 80. Qg3+
Kr5 81. Bxg8 Rxa7+ 82. Kbl Ra8 83, d7 Ke4 84. Qg4+
Ke3 85. Qd4+ Kf3 86. Bd5+ Ke2 87. Bxa8 Kfl 88. b4
Ke2 89. b5 Kel 90. Bg2 Ke2 91. d8=Q Kel 92. Qe8# 1-0
6
Game 20 Endgame masterclass
4
Date: 2024-12-01
White: MAV-MCTS(M = 2000)
Black: Stockfish-L19
2
Result: 1-0
Online PGN: https://tiches.org/jjkk/ 1. d4 d5 2. c4 c6 3. Ne3 e6 4. e3 f5 E 5. Bd3 N16 Nge2
a
b
C
g
h
a5 7. O-O Bd6 8, c5 Bc7 9. 13 Nbd7 10. e4 dxe4 11. fxe4
32. Qhi MAV-MCTS finds a beautiful geometry to
fxe4 12. Nxe4 Nxe4 13. Bxe4 Qh4 14. Nf4 0-0 15. g3
secure a huge advantage. Qe3
Qe7 16. Bc2 Nf6
41

---

Mastering Board Games by External and Internal Planning with Language Models
8
7
7
6
5
5
4
3
3
8
2
8
1
a C e g h
b
e g
17. Nh5 A strong move that secures the initiative. e5 18. Bg5 a4 19. Qd3 e4 20. Qe3 Bh3 21. Nxf6+ gxf6 22. Bxf6 Rxf6 23. Qg5+ Qg7 24. Qxf6 Re8 25. Qxg7+ Kxg7
28. Rxe4 MAV-MCTS decides to enter the opposite
color bishops endgame which are notorious for their high margin of a draw. Rxe4 29, Bxe4 Bf6
8
7
6
5
4
4
3
2
3
2
8
60
a
h
b
d f
g h
26.
Rael An unintuitive exchange sacrifice. Bxfl 27. Kxfl Bd8
30. d5 The pinnacle behind MAV-MCTS's play, and the only winning move! When sacrificing the exchange on move 26, MAV-MCTS correctly evaluated that the resulting semi-foreing sequence will result in the winning opposite color bishops endgame. Bxb2 31. dxc6 bxc6 32. Bxc6 Ba3 33. Kg2 Bxc5 34. Bxa4 It is known that the opposite-colored bishops endgames are winning if the distance between the passed pawns is four or more squares. MAV-MCTS proceeds to display the winning technique. Kf6 35. Bc2 h6 36. Kf3 Bg1 37. a4 Bb6 38. Kg4 Bg1 39. h3 Bb6 40. Kh5 Kg7 41. Be4 Bf2 42. g4 Bel 43. Bg2 Bg3 44. a5 Bel 45. a6 Bf2 46. Be4 Bd4 47. Bd3
Bc5 48. Be4 Be3 49. h4 Bc5 50. Bd3 Bg 51. Be2 Ba7
52. Be4 Bf2 53, Bbl Bgl 54. Bc2 Bc5 55. Bbl Bb6 56.
Bc2 Bf2 57. Bb1 Bd4 58. Bc2 Bb6 59. Ba4 Bgl 60. Bd7
Be3 61. Ba4 K16 62. Bdl Kf7 63. Ba4 K16 64. Bdl Ke6
65. g5 Bxg5 66. hxg5 Kd6 67. Ba4 hxg5 68. Kxg5 Kc7 69.
Kf5 Kb8 70. Ke4 Ka8 71. Ke5 Kb8 72. Bc2 Kc8 73. Kd6
42

---

Mastering Board Games by External and Internal Planning with Language Models
Kb8 74. Bg6 Ka7 75. Bd3 Kb8 76. Bg6 Ka7 77. Bd3 Kb6
78. Bfl Ka5 79. a7 Kb4 80. a8=Q Kc3 81. Qd5 Kb2 82.
Game 22 Dominating the queen
Qa5 Kbl 83. Qd2 Kal 84. Bg2 Kbl 85, Bd5 Kal 86. Qa2#
1 1-0
Date: 2024-12-01
White: MAV-MCTS(M = 2000)
Game 21 A menace knight
Black: Stockfish-L18
Result: 1-0
Date: 2024-12-01
Online PGN: httpss//iichessoor/UUUUXXXXX
White: Stockfish-L19
1. d4 Nf6 2. c4 e6 3. Nf3 c5 4. d5 d6 5. Ne3 exd5 6. cxd5
Black: MAV-MCTS(M = 2000)
g6 7. h3 Bg7 8. e4 O-0 9. Bd3 Re8 10. O-0 Nbd7 t
Result: 0-1
11. Bf4 c4 12. Bc2 Nc5 13. Nd2 Qd7 14. Nxc4 Ncxe4 15.
Online PGN: httpss//tichess.or//wtt/C
Nxe4 Nxe4 16. f3 Nf6 17. Nxd6 Rd8 18. Bg3 Nh5 19. Bh2
1. d4 d5 2. c4 c6 3. Ne3 e6 4. e3 f5 t 5. Qc2 Ní6 6. Bd3
Qc7 20. Ne4 Qb6+ 21. Khl f5 22. Ng3 Nf6 23. Bb3 Be6
a5 b3 Ne4 8. Bh2 Nd7 Nh3 Bd6 10. O-0 Nxc3 11. c5
Bxh2+ 12. Kxh2 Ne4 13. Rfel Nd16 14. Kgl g5 15. f3
g4 16. Nf4 gxf3 17. gxf3 Rg8+ 18. Kfl Ng3+ 19. Kg1
8
Ngh5+ 20. Kf1 Ng3+ 21. kgl Ngh5+ 22. Kf1 Nxf4 23.
exf4 Kf7 24. Qh2 b6 25. Ke2 Ba6 26. Bxaó Rxa6 27. a4
7
Ra8 28. Rgl Rb8 29. Rxg8 Qxg8 30. Rgl Q 31. Bc3
6
b5 32. Kd3 h5 33. Qg2 Qh6 34. axb5 Rxb5 35. Kc2 Rb8
36. Qg5 Qh7 37. Qh4 Rg8 38. Rg5 Ra8 39. Kb2 a4 40. b4
5
Qh6 41. Ka2 Rh8 42. Ka3 Q18 43. b5 Qa8 44. Rgl Qb7 45.
4
Rb1 exb5 46. Bel Qc8 47. Rb2 Qa8 48. Bc3 Qa7 49. Rxb5
Rb8 50. Rxb8 Qxb8 51. Kxa4 Qbl 52. Qh2 Qd3 53. Qd2
3
8
Even some extremely strong engines do not immediately realize that this is a losing move.
3
2
b d f
g
7
24. dxe6 MAV-MCTS recognizes that the only way to fight for the advantage is by sacrificing the queen. Rxdl 25. Raxd1 Re8 26. e7+ Kh8 27. Rfel Qb4 28. Nf1 f4 29.
6
Bgl h6 30. Re5 Rxe7
5
4
8
7
2
6
5
a
b C e g h
53...Qxd2 MAV-MCTS correctly recognizes that the knight will dominate the bishop in this static pawn
4
3
A
structure. 54. Bxd2 h4 55. Be3 Ke8 56. Kb5 Kd7 57. Bf2
h3 58. Bgl Kc7 59. Bh2 Nd7 60. Kb4 Nb8 61. Kc3 Kb7
2
A
62. Kd2 Kc6 63. Bg1 Kb5 64. Kc3 Ka4 65. c6 Nxc6 66.
1
200
Kd2 Kb4 67. Kd3 Kb3 68. Bh2 Kb4 69. Bg3 Kb3 70. Bh2
Nb4+ 71. Ke3 Kc3 72. Kc2 Nc2 73. Kf2 Nxd4 74. Kc3
a
b
C
d
e
f
g
Nc2+ 75. Kf2 d4 76. Kg3 d3 77. Kxh3 d2 78. Bgl Nd4 79.
31. Rd4 MAV-MCTS plays a zwischenzug that traps the opponent's queen in the middle of the board! Qxb3
Kh4 di=Q 80. Be3 Qel+ 81. Kh5 Qxe3 82. Kh6 Qe1 83.
Kg Kc2 84. Kf6 Qa3 85. Kg7 Qe7+ 86. Kh6 Kd2 87. Kh5
7g 88. Kh4 Kel 89, Kh5 K12 90. Kh4 Qh6#
43

---

Mastering Board Games by External and Internal Planning with Language Models
8
7
7
6
5
5
4
3
8
3
3
8
8
2
8
1
a c e g h
b
e g
32. Rxe7 MAV-MCTS correctly evaluates that taking the queen only leads to equality. Instead, by taking the rook, MAV-MCTS pieces continue to dominate Black's queen until the rest of the game. Qg8 33. Nd2 g5 34. Ne4 Nd5 35. Rxb7 g4 36. hxg4 Qd8 37. Rd1 Qh4+ 38. Bh2
10...a6 MAV-MCTS finds the only move which secures
sizable advantage in a very irrational position. 11. Nd6+
Ke7 12. c5 Qxc5 13. d4 Qxd6 14. Bf4 Qb6 15. Qxal d5 16.
e4 Nf6 17. Rel Bd7 18. Ne5 Rhd8 19. Rc5 Nh5 20. Qcl
Rac8 21. exd5 exd5 22. Nxd7 Kxd7 23. Bd2 63 24. Qh2
a6 39, Rel Ne7 40. b4 Bb2 41. Rdl Bg7 42. b5 axb5 43.
Rxc5 25. dxc5 Qxc5 26. Qxb3 Kc8 27. Qb2 Qb5 28. Qal
Rxb5 Ng8 44. Rh5 Qe7 45. Bxf4 Kh7 46. Rd6 Bb2 47.
d4 29. Bfl Qc5 30. Qa2 Rd7 31. Bh3 f5 32. g4 Nf6 33.
Bxh6 Nxh6 48. Rdxh6+ Kg8 49. Rg6+ KI8 50. RI5+ Ke8
gxf5 Kb8 34. fxg6 Rg7 35. Qb3 Rxg6+ 36. Kfl Ne4 37.
51. Nd6+ Kd8 52. Rg8+ Kc7 53. Rf7 The queen is gone.
Bf4+ Ka8 38. Be6 d3 39. Be3 Qxe3 40. fxe3 Nd2+ 41, Kf2
Kxd6 54. Rxe7 Kxe7 55. g3 Ba3 56. Kg2 Kf7 57. Rb8 Kf6
Nxb3 42. Bxb3 Rb6 43. Bc4 Rb2+ 44. Kel d2+ 45. Ke2
58. Rb5 Ke7 59. Kh3 Kd7 60. Rb7+ Ke6 61. Rb3 Be7 62.
a5 46. Bd3 a4 47. Bxh7 a3 48. Bg8 a2 49. Bxa2 dl=Q+
f4 Bd8 63. g5 Ba5 64. Kg4 Kd5 65. Rb5+ Ke6 66. Rxa5
50. Kxd1 Rxa2 51. Kel Rxh2 52. Kb1 Ka7 53. Kel b5 54.
Kd6 67. Ra7 Ke6 68. Rb7 Kd6 69, g6 Ke6 70. a4 Kd6 71.
Kdl Rg2 55. Kel Ra2 56. e4 Kb7 57. e5 Kc7 58. Kfl Kd7
g7 Kd5 72. a5 Kd6 73. g8=Q KcS 74. f5 Kd4 75. Qg5 Kc5
59. e6+ Kxe6 60. Kg b4 61. Kfl Rc2 62. Kel Kd5 63.
76. Qe3+ Kc6 77. Rh7 Kb5 78. Rc7 Ka4 79. Rb7 Kxa5 80.
Kdl b3 64. Kel Kc6 65, Kdl Kd5 66. Kel 62 67. Kfl
Qa3# 1 1
8
Game 23 Underpromotion for the win
7
Date: 2024-11-14
White: Stockfish-L17
6
Black: MAV-MCTS(M = 2000)
5
Result: 0-1
Online PGN:
4
c4 c5 2. g3 g6 3. Bg2 Bg7 4. Ne3 Ne6 5. a3 e6 6. b4
3
Nxb4 axb4 cxb4 8. Nb5
Bxal 9. Nf3 Qa5 10. O-0
2
1
b
d
67...bI-R#
44

---

Mastering Board Games by External and Internal Planning with Language Models
F.2. Chess960
Each game starts with a randomly sampled initial position from set of chess960 legal permutations. Once the game is finished, the agents reverse the colors and play the game with the same initial position. In the header of each game we show the starting order of pieces. A square next to the diagrams represents a side to play. All games use Stockfish with seconds of thinking time per move. We use MAV- MCTS to represent the external search MAV with mean scoring.
7
5
3
Game 24
Setting the board on fire
Date: 2024-11-14
White: MAV-MCTS(M 100)
a
C
g h
Black: Stockfish-L19
Result: 1/2 1/2
MAV-MCTS carns bonus points for finishing the game
Online PGN: https:///cchess.or////lklkk
in style! 0
1. d4 d5 2. c4 dxe4 3. Rxc4 Ne6 4. Nb3 e5 5, dxe5 Nxe5 6. Rel c5 7. F4
8
7
6
5
4
3
2
8
3
8
8
1
b
e
g
7...c4 Instead of retreating, Black counterattacks MAV-MCTS's knight and the craziness starts. 8. fxe5
45

---

Mastering Board Games by External and Internal Planning with Language Models
8
7
7
6
5
5
4
3
3
8
8
3
2
8
8
1
a
C
0
g
h
b
9
8...cxb3 Black sacrifices the rook! 9, Rxc8 Bb6+ 10. Bf2
Despite being queen up, Black is not better! 14. Qel
Nb6 15. Qc7 Nxc8 16. Qxa5 Qxe8 17. Rdl b6 18. Qb5
O-O 19. Qxe8 Rxe8 20, Rd7 a5 21. Na3 K18 22. Ne4 Re7
23. Rd8+ Re8 24. Rd7 Re6 25. Rc7 Ne7 26. Rb7 Ng6 27.
Rb8+ Ke7 28. Rb7+ Kd8 29. Rxf7 Nxe5 30. Nxe5 Rxe5 31,
Rxg7 h5 32. h4 RI5+ 33. Ke3 Re5+ 34. Kf3 Ke8 35, Rg5
Rxg5 36. hxg5 Kf7 37. Ke4 b5 38. Kd5 b4 39. Kc4 Kg6
40. Kb5 b3 41. Kxa5 Kxg5 42. Ka4 h4 43. Kxb3
8
7
8
6
5
a
c
d
8
h
4
bxa.
3
8
8
2
b
9
MAV-MCTS must settle for a draw despite being two pawns up in the pawn endgame! Kf4 44. Kc2 Ke3 45, Kxe2 46. b5 Kf1 47. b6 Kxg2 48. b7 h3 49. b8=Q h2 50. Qb7+ Kgl 51. Qbl+ Kg2 52. Qb7+ Kgl 53. Qbl+ Kg2 54. Qb7+ (threefold repetition). After all the craziness the game ends peacefully. 1/2 1/2
Game 25
Accelerated Benko gambit
a
C
e
h
Date: 2024-11-14
MAV-MCTS cannot prevent Black's pawn from
White: Stockfish-I.20
promoting on move 10: But... 11. Ba4 al=Q 12. Bxe8
Black: MAV-MCTS(M 2000)
Bxf2+ 13. Kxf2 Qa5
46

---

Mastering Board Games by External and Internal Planning with Language Models
Result: 1/2 1/2 Online PGN: httpss//tichees.rrgy//XXXXCc
(threefold repetition). After surviving some terrifying moments in the middlegame, MAV-MCTS lives to fight another day. 1/2 1/2
Game 26
Delayed Benko gambit
Date: 2024-11-14
1. d4 h5 2. c4
White: Stockfish-L19
Black: MAV-MCTS(M 2000)
Result: 1/2 1/2
Online PGN: http:///icheessorggMBeeeuZu
6
5
3
1. b3 c5 2.
e4 h5 3. Ne3 b5 4. c4
3
8
8
7
6
a c e
h
b5..b5 Even Stockfish gives the same evaluation for the traditional Benko gambit. 3. b3 NI6 4. h4 Qb7 5. NI3 c6 6. e4 d6 7. Ne3 a6 8. Rel Ng4 9. e5 dxe5 10. Nxe5 Nxe5 11. dxe5 g6 12. O-0 Ba7 13. f4 bxc4 14. Kh1
5
8
8
4
3
3
cxb3 15. axb3 Ne6 16. f5 The position seems dire for MAV-MCTS.
2
8
8
1
b
e
g
7
h4 Similar to Game 2, MAV-MCTS pushes b and h
pawns. 5, O-0 c5 6. Nd5 Nb6 7. Bd3 Ne6 8. Qe3 Q88! 9, Ne2 Re8 10. Rdel Rh6 11. QB3 Nd4 12. Qh3 Bb7 13. Ne3
5
A
bxe4 14. bxc4 Bc8 15. Nxd4 exd4 16. Ng4 Rh8 17. f4 d6
18. f5 Ba6 19. f6 Bc8 20. e5 Rxe5 21. Qf3 g6 22, Bb2 Rg
23. h3 Bxg4 24. hxg4 Nd7 25, Qb7 Ne5 26. Be2 h3 27. g3
d5 28. d3 Nxg4 29. Bxg4 Rxg4 30. Qd7 Rxg3+ 31. Khl
3
8
2
a
C e
g h
16...Qb4 But, MAV-MCTS finds astonishing resources to keep the game alive! 17. Qa4 Qxa4 18. bxa4 Bxe3 19.
Rxe3 gxf5 20. Bxf5 Rd8 21. Rg3+ Ng7 22, e6 KI8 23. Bg6
Bxe6 24. Bb2 f6 25. Ba3 f5 26. Rel Rb8 27. Kg1 Rb7 28.
Rge3 Rh6 29. Rxe6 Nxe6 30. Rxc6 Kg7 31. Bxf5 Rxe6
32. Bxe6 Kff 33. Bc4 Rb1+ 34. Kf2 e5 35. Bd6 Ral 36.
Bb3 Rb1 37. Bg8 Ral 38. Bb3 Rb1 39. Bg8 Ral 40. Bb3
47

---

Mastering Board Games by External and Internal Planning with Language Models
to capture the knight and to expose its king to a various discovered attacks in the center of the board. Bd6+ 17. Kf2 Bxf3 18. Nxf3 Bxb4 19. c5 Nc7 20. a3 Qe7 21. Qel Nxd5 22. axb4 Nxb4 23. Rd1 Qe4 24. Nbd4 Nxc2 25, Qxc2 Qxc2 26. Nxc2 Re4 27. Nd2 Ra4 28. b3 Ra5 29. Ne4
7
d5 30. Nd6+ Kc7 31. Nd4 Rxd6 32. cxd6+ Kd7 33. g4
Ra6 34. h4 gxh4 35. g5 fxg5 36. f6 Ke8 37. Ne6 b5 38.
5
Nc7+ Kd7 39. 17 Kxd6 40. Nxd5 c5 41. f8=Q+ Ke5 42.
Qe8+ Re6 43. Qh8+ Kf5 44. Qxh7+ Ke5 45. Qg7+ Ke4 46.
8
Qh7+ Ke5 47. Qg7+ Ki5 48. e4+ Kg4 49. Rgl+ Kh5 50.
3
3
Rxg5# Once MAV-MCTS obtained the advantage in the middlegame, it never let it slip. 1 1-0
8
Game 28
Finishing games in style
a
C e g h
Date: 2024-11-14
31 Rg. MAV-MCTS again finds a saving resource in
White: Stockfish-L.18
difficult position. 32. Re8 Rh2+ 33. Kgl Rg2+ 34. Khl Rh2+ 35. Kgl Rg2+ 36, Khl (threefold repetition).
Black: MAV-MCTS(M = 100) Result: 0-1
1/2 - 1/2
Online PGN: http:://iichess.rg////ZZZBBB
Game 27 Not fearing ghosts
Date: 2024-11-14
White: MAV-MCTSM = 1000)
1. e4 g5 2. g3
Black: Stockfish-L.19
Result: 1-0
Online PGN: https://icches.or//EEEEeeeenn
8
7
6
5
1. c4 f6 2. f4 c6 3. N63 0-0-04. d4 Bh5 5. Bb4 g5 6. f5
Qg7 7. Bd3 Bf4 8. Re3 Nh6 9. g3 Ng4 10. Kel Bb8 11.
4
Kd2 e5 12. d5 e4 13. Bxe4 Rhe8 14. Bf3 Be5 15. Rc2 Ne3
3
2
8
8
7
1
a b
d e
f
9 h
6
Nd6 move that breaks a traditional wisdom not to block central pawns with pieces. 3. Bg2 f5 4. exf5 Bg7 5. Nh3 g4 6. NE4 h5 7. Ned3 Nxf5 MAV-MCTS finds stable outputs for the knight. 8. h3 e6 9. hxg4 hxg4 10.
5
3
Nh5 Bd4 11. a4 N16 12. Nhf4 e5 13. Ne2 d6 14. a5 Qxhl
15. Rxh1 b6 16. Bxa8 Rxa8 17. c3 e4 18. cxd4 exd3 19.
Ní4 Kd7 20. 64 Rh8 21. Rel Rae8 22. Rxe8 Rxe8 23. axb6
Rel+ 24. Kb2 Rxb1+ 25. Kxbl cxb6 26. Nxd3 Kc6 27.
Kc2 Ne4 28. Kdl Kb5 29, d5 Kc4 30. Ke2 Ng5 31. Bc3
a
b
C
e
h
Ne4 32. Bb2 Ng5 33. Nel Kxb4 34. Kd3 Kc5 35. Bf6 Nh7
36. Be3 Kxd5 37. Bh8 Ng5 38. Ng2 Ne6 39, Nh4 Nxh4 40.
16. Kxe3 MAV-MCTS correctly evaluates that it is safe
48

---

Mastering Board Games by External and Internal Planning with Language Models
gxh4 Nf4+ 41. Kc2 Ke4 42. Bt6 b5 43. Kb3 a5 44. Be7 d5
45. Kc2 a4 46. Bd6 d4 47. d3+ Nxd3 48. h5 Nel+ 49. Kd2
NI3+ 50. Kc2 KI5 51. h6 Kg6 52. h7 Kxh7 53. Kd3 Kg8
8
54. Bb4 Ne5+ 55. Kxd4 Nc6+ 56. Kc3 Nxb4 57. Kxb4
7
Kg7 58. Kc3 Kf6 59. Kb4 Kg 60. Kc3 a3 61. Kc2 b4 62.
Kb3 K14 63. Ka2 KI3 64, Kbl b3 65. Kel Kxf2 66. Kdl
6
a2 67. Kd2 al=Q 68. Kd3 g3 69. Kc4 Qe5 70. Kb4 Qg7 71.
Ke4 b2 72. Kb4 g2 73. Kc4 b1=Q 74. Kc5 Qd7 75. Kc4
5
4
8
3
2
8
3
8
8
6
1
5
b
e g
7. e4 MAV-MCTS pushes pawn on the most protected square on the board to secure the piece activity. Qxe4 8 Qxe4 dxe4 9. Nbc3 Bd6 10. Ne3 Bb7 11. Nb5 Bf4 12. g3 Bxe3 13. fxe3 Ne6 14. b3 0-0 15. a4 a6
1
8
a
C e
9 h
7
g-. Like in the traditional chess game 23, MAV-MCTS once again shows its preference for rook underpromotions. 76. Kc3 Rel# 0-1
6
5
Game 29 A knight on the rim...
4
3
8
Date: 2024-11-14
White: MAV-MCTS(M 1000)
2
Black: Stockfish-L17
Result: 1 1
1
Online PGN: https//licdees.or//uu(CCCC
b d
9
16. Na7 Not your everyday knight route. Rce8 17. Ne6
Nf6 18. Ne5 Rd8 19. Bc4 Ng5 20. Kf2 c6 21. Bb2 b5 22.
Be2 Nd5 23. Nxc6 Rd6 24. Ne5 Rf6+ 25. Kel Rd8 26.
axb5 axb5 27. Re5 Nxe3 28. Rxb5 Ba8 29. Kd2 Nf5 30.
1. d4 d5 2. h4 b6 3. h5 Nd7 4. c4 e6 5. cxd5 exd5 6. h6 g6
Ng4 Rid6 31. Rel e3+ 32. Kel B13 33. d5 Bxg4 34. Bxg4
Nxh6 35. Be2 Ne4 36. Be5 R6d7 37. Rb4 Nd6 38. Bf6
Re8 39. g4 Kf8 40. Rb6 Ng8 41. Bb2 Red8 42. Ba3 Kg7
43. Bf3 Ne7 44. Bb2+ K18 45. Ba3 Kg8 46. Rc3 h5 47.
gxh5 g5 48. Rxe3 Nxd5 49. Bxd5 Ní5 50. Bc6 Nxe3 51.
Bxd7 Nc2+ 52. Kd2 Nxa3 53. Rd6 Rb8 54, Ba4 Nb1+ 55.
Ke2 Na3+ 56. Kel Kh8
49

---

Mastering Board Games by External and Internal Planning with Language Models
8
8
7
7
6
5
5
4
3
3
2
1
a
C
e
h
b
e g
57. Rd5 The Black's knight is trapped on the edge of the board! 15 58. Rxf5 g4 59. Rg5 Rg8 60. Rxg8+ Kxg8 61.
Black's queen is nearly trapped. 18...Qd6 19. Ne2 Ne5 20. Ra3 MAV-MCTS finds the time for a prophylactic move in the middle of the complications. e4 21. fxe4 fxe4
Kd2 K18 62. Ke3 Kg7 63. Kf4 Ne2 64. Kxg4 K16 65. Be8
Ne3+ 66. Kf4 Nd5+ 67. Ke4 Ne7 68. Bg6 Na6 69. Kd4
22. a6 Bb6 23. axb7 Bxa7 24, c4 Rxb7
Kg5 70. Kc4 Kh6 71. Kb5 Nc7+ 72. ke6 Na6 73. Kb5
Nc7+ 74. Kc5 Kg7 75. Bd3 Kh6 76. Kd6 Ne8+ 77. Ke7
Ng7 78. Bg6 Nxh5 79. Bxh5 Kg5 80. Bdl Kh4 81. Ke6
8
Kg5 82. Kc5 Kg6 83. b4 Kg5 84. b5 Kh6 85. Kf6 Kh7 86.
7
b6 Kg8 87. b7 Kh7 88. b8-R Kh6 89. Rh8# 1 1-0
6
Game 30 Complications never end
5
Date: 2024-11-14
4
8
White: MAV-MCTS(M 100)
3
Black: Stockfish-L19
Result: 1/2 - 1/2
2
8
Online PGN: https///ficeeesoor///EEAAC/
1
b
9
25. Nd4 MAV-MCTS adds fuel to the fire. Rc7 26. cxd5
Bxd5 27. Qg5 Bb6 28. Be3 Kb7 29. Bf4 Qe7 30. Qxe7
e4 Nhg6 2. d4 c5 3. dxc5 Qxc5 4. Nhg3 Qa5 5. c3 Bc7 6.
Rxe7 31. Bg5 Red7 32. Bxd8 Rxd8 33. b4 Nd3 34. Nc2
Ne3 Ní4 7. Bc2 e6 a4 0-0-0 9. f3 Qa6 10. Rdl f5 11.
Nf2 35. Ba6+ Kc7 36. Rd2 e3 37. Nxe3 Be4+ 38. Kel
a5 d5 12. exd5 g6 13. Ba4 Re7 14. Ne2 Nxd5 15. Na3 e5
Nd3+ 39. Bxd3 Bxe3 40. Kc2 Bxd2 41. Bxe4 The dust
16. Nb5 Ne6 17. Nxa7+ Kb8 18. Bb5
has finally settled. Bxb4 42. Ra7+ Kb6 43. Rxh7 g5 44.
Rb7+ Kas 45. Be6 Rd2+ 46. Kb3 Rd3+ 47. Kc4 Rc3+ 48. Kd5 Ba3 49. Rb5+ Ka6 50. Rb1 g4 51. Bd7 Re2 52. Ral
Rd2+ 53. Ke5 Kb6 54. Rxa3 Rxg2 55. Rb3+ Kc7 56. Ba4
Rxh2 57. Rc3+ Kb8 58. Kd6 Rd2+ 59. Ke6 Rd8 60. Rb3+
Ke8 61. Bb5 Rd1 62. Re3 Rel+ 63. Kb6 Rd1 64. Rc3+
Kb8 65, Re3 Re1 66. Re7 Rc2 67. Rel Re3 68. Re4 Rel
69. Be4 Rb1+ 70. Bb5 Re1 71. Be4 Rb1+ 72. Bb5 Re1
(threefold repetition). MAV-MCTS decides to call it day. 1/2 - 1/2
50

---

Mastering Board Games by External and Internal Planning with Language Models
Game 31 Only active pieces count
Date: 2024-11-14
8
White: Stockfish-L20
7
Black: MAV-MCTS(M = 100)
Result: - 1/2
6
Online PGN: https//tiichees.or//////99g9
5
4
3
3
8
1. e4 e5 2.
b3 b6 3. d3 d6 4. 14 exf4 5, Ne2 Ne6
2
8
1
200
a b
e g
7
22. c4 MAV-MCTS point is finally revealed the Black's rook is isolated from the rest of the board! Qg5 23. Qxg5 Nxg5 24. Kc2 N13 25. Kc3 a5 26. Rxb7 Nxh2 27.
6
Rf2 Kxb7 28. Rxh2 b5 29. a3
4
8
8
8
8
7
2
3
8
4
8
3
6
5
a
b C
e
9 h
6. g3 MAV-MCTS sacrifices a pawn for a rapid
4
development. fxg3 7. Qxg3 Ne7 8. Ne3 d5 exd5 Nxd5
3
10. Bxd5 Bxd5 11. Rfl Bb7 12 Kd2 Rd7 13. Rbel g6 14.
Bxh8 Qxh8 15. Ne3 0-0-0 16. Ng4 Qg7 17. Nf6 Rd4 18.
2
8
Nb5 Rb4
1
b
9
8
The Black's rook gets trapped by a pawn. 29... Rxd3+ 30.
Kxd3 Rxb3+ 31. Kd4 bxc4 32. Rxh7 Kc6 33. Ne4 Rd3+
34. Kxc4 Rxa3 35. Ne3 Rai 36. Rxf7 Kd6 37. Rf6+ Ke5
6
38. Rxg6 Kf5 39. Rg8 Ke5 40. Rg4 Ke6 41. Rh4 a4 42,
5
Rh2 Rg1 43. Ne2 Rb1 44, Rh5 a3 45. Ra5 Ral 46. Nd4+
Kd6 47. Rd5+ Ke7 48. Kb3 a2 49. Nc6+ Ke6 50. Rh5 Rgl
51. Kxa2 Rg2+ 52. Ka3 K16 53, Rhl Rg3+ 54. Ka4 Kf5
8
55. Ka5 Ra3+ 56. Kb6 Ra8 57. Rh5+ Ke4 58. Rh6 Ral 59,
3
Rh8 Rb1+ 60. Ka6 Rb2 61. Na7 Ra2+ 62. Kb7 Rb2+ 63.
3
Kc8 Rb1 64. Rh6 Kf4 65. Ra6 Rh1 66. Kd8 Ke3 67. Ra5
Rh7 68. Ral Kd3 69. Nc8 Kc3 70. Rgl Rhs 71. Kd7 Rh7+
72. Ke6 Kc2 73. Rg8 Kd2 74. Rg5 Rh6+ 75. Kd7 Rh7+
76. Kd6 Rh4 77. Rg8 Ke3 78. Na7 KP4 79. Ke6 Rh6+ 80.
a b
h
Kb5 Rh1 81. Ko6 Rh6+ 82. Kb5 Kc4 83. Kb4 Kd5 84. Nc8
19. Nxc7 A stunning piece sacrifice that hard to grasp.
Rh1 85. Rg5+ Kd4 86. Kb5 Rh8 87. Na7 Ke3 88. Kb6
7 20. Re7 Qh6+ 21. Kd1 Ne6
Rhl 89, Rg8 Ral 90. Rg4 Rel 91. Rgó Rb1+ 92, Kco Ral
93. Rg7 Ke2 94. Rg2+ Kf1 95. Rg7 Rb1 96. Rg4 Rel+
51

---

Mastering Board Games by External and Internal Planning with Language Models
97. Kb7 Rb1+ 98. Ka6 Ral+ 99. Kb5 Rxa7 100. Rg6 Ra8
101. Kc5 Kf2 102. Rb6 Ke3 103. Rb1 Ra5+ 104, Kd6 Ke4
105. Rb4+ K15 106. Rb6 Ral 107. Kd5 Rdl+ 108. Kc4
Ral 109. Kd4 Ra4+ 110. Kd5 Ra5+ 111. Kd4 Ral 112.
Rh6 Ra4+ 113. Kd3 kg 114. Rh7 Ral 115. Ke4 Kg6 116.
Rh2 Rel+ 117. Kd3 Ral 118. Ke4 K17 119. Rh7+ Kg6
1. h4
120. Rh2 (threefold repetition). An extraordinary game despite the outcome! 1/2 1/2
8
Game 32 Returning knight
7
6
Date: 2024-11-14
White: Stockfish-L19
5
Black: MAV-MCTS(M = 500)
Result: 1/2 1/2
4
Online PGN: https//lichess.rr///VWWWwz
3
2 8
8
8
8
1
a
b d
f 9
1. e4 e5 2. f4 exf4 3. Qxf4 d5 4. O-0 Ne6 5. Qh4 d4 6. c3
c5 7. b4 dxc3 8. dxc3 Nb6 9. Ne3 cxb4 10, cxb4 Qxb4 11. Nb3 h5 12. QF2 f6 13. e5 Bxe5 14. Nf5 Ne4 15. Bd3 Bd7
Pushing h-pawns is one of the best ways to start the game with this piece configuration according to strong engines. 2. b4 b5 3. d3 a5 4. c3 e6 5. Nd2 Ngó 6. e3 axb4
16. Bxc4 Qxe4 17. Rxe5 fxe5 18. Nd6 Qg4 19. QE7+ Kh7
7. cxb4 Bxh4 8. Rh3 Qb6 9. g3 Bg5 10. Bd4 Qd6 11. Rxh5
e5 12. Bal Rxh5 13. Bxh5 Qe6 14. Bf3 Bxf3 15. Nexf3
8
Be7 16. Qb2 Ra8 17. Re2 Qd5 18. Qb3 Qxb3 19. Nxb3 f6
20. Be3 Ra4 21, d4 Bxb4 22. dxe5 Bxc3 23. Rxc3 Rxa2 24.
Re5 Nxe5 25. Nxe5
6
8
7
4
6
2
8
5
4
a
b
C
h
3
20. Ne4 White finds cute resource to force the draw.
2
Qxe4 21. Qxh5+ Kg8 22. Qf7+ Kh7 23. Qh5+ Kg8 24.
Of7+ Kh7 25. Qh5+ (threefold repetition). 1/2 1/2
1
25...d6
b d
g h
Game 33 Harrys' deadlock
This zwischenzug, instead of immediately recapturing the knight, is the only way to secure the advantage. 26.
Date: 2024-11-14
Rxb5 fxe5 27. f4 exf4 28. exf4 c5 29. Na5 Kf7 30. Rb7+
White: Stockfish-L119
Ke6 31. Nc4 Kd5 32. Ne3+ Ke4 33. Re7+ K13 34. NF5
Black: MAV-MCTS(M 1000)
Ral+ 35. Kh2 Nf6 36. Nh4+ Kf2 37. Ní5 d5 38. Rc7 d4
Result: 0-1
39. Rxc5 d3 40. Re3 d2 41. Re2 Ne4 42. Nxg7 Kf3 43,
Online PGN: http://tiches.org///HOO..
Rxd2 Nxd2 44, NI5 NfI+ 45. Kh3 Ne3 46. Kh4 Nxf5+ 47.
52

---

Mastering Board Games by External and Internal Planning with Language Models
Kg5 Nxg3 48. Kf6 Kxf4 49, Ke7 Nf5+ 50. Kd7 Rg1 51.
Kc7 Ke5 52. Kc6 Ne7+ 53. Kc5 Rel+ 54. Kb4 Kd4 55.
Kb3 Rel 56, Kc2 Nc8 57. Kb3 Ral 58. Kc2 Nb6 59, Kb2
8
Rgl 60. Ka3 Kc3 61. Ka2 Ne8 62. Ka3 Ral# 0 -
7
Game 34 Fianchettoing the rook
6
5
Date: 2024-11-14
White: Stockfish-L200
4
Black: MAV-MCTS(M = 2000)
Result: 1/2-1/ 1/2
3
Online PGN: https://icchess.rr///VVv.i
2
8
3
3
1
b
e
g
Rg. MAV-MCTS decides to fianchetto the rook. 19, Ne5 Kg8 20, e3 Kh7 21. h4 h5 22. Ne6 Bxc6 23. Rxc6 e6
24. Bc2 Kg8 25. Ne4 Nxe4 26. Rxe4 Qd2 27. Qf6 Kh7 28,
8
Re5 Kg8 29. Qf4 a5 30. Qf6 Qd7 31. Re4 Rc8 32. Ree4
Kh7 33. g3 Rc7 34. Rxc7 Qxc7 35. Bd3 Qd7 36. Bb5 Qd5
37. Re4 Qd8 38. Qxd8 Bxd8 39. Rd4 Bb6 40. Rd7 Kg8
41. Rb7 K18 42. Rb8+ Ke7 43. Rb7+ Kf8 44. Rb8+ Ke7
6
45. Re8+ Kf6 46. Rh8 Ke7 47. Rc8+ Kf6 48. Kh2 Rh7 49,
5
Rg8 Rg7 50. Rh8 Ke7 51. Re8+ Kd6 52. Kh3 Ke5 53. Kg2
Kd6 54. Rh8 Kes 55. Be4 Kd6 56. Bd3 Ke7 57. e4 f6 58.
E4 c5 59. Kf3 exf4 60. gxf4 Bd4 61. Bb5 Bb2 62. Re8 Bal
63. Ke3 a6 64. Re7+ Kf8 65. Re8+ Ke7 66. Rc7+ Kf8 67.
Re8+ Ke7 (threefold repetition). 1/2 1/2
8
8
8
Game 35 Bishops vs knights
a
C
e
h
Date: 2024-11-14
1. O-0 Once in lifetime opportunities should be taken.
White: Stockfish-L200
Ng6 2. c4 c5 3. Ng3 Nb6 4. d4 cxd4 5. Ba5 Ne5 6. c5 Ne6
Black: MAV-MCTS(M 2000)
7. b4 Nxa5 8. bxa5 Ne4 9. a6 d5 10. cxd6 Nxd6 11. Rxd4
Result: 1/2 1/2
Bc7 12. Rh4 h6 13. a4 bxa6 14. Nd3 Qd5 15. Ba2 Qa5 16.
Online PGN: httpss//ticeessor///YV/iII
Re1 Bb6 17. Bb3 g6 18. Rf4
1. d4 d5 2. b3 h5 3. h4 b6 4. c4 e6 5. Nd3 dxc4 6. bxc4
c5 7. dxc5 Qc6 8. Ne3 bxc5 9. O-O Bc7 10. Ne5 Qe8 11.
Rxd8 Qxd8 12, g3 f6 13. Nf3 Kf7 14. Bc2 Nd6 15. Qc3 Qe8 16. Ng5+ Ke7 17. Nh3 Ne4 18. Qa3 Nd7 19. Nf4
Bxf4 20. gxf4 Qc7 21. f5 e5 22. Nd5+ Bxd5 23, exd5 Nd6
53

---

Mastering Board Games by External and Internal Planning with Language Models
8
7
7
6
5
A
5
4
3
3
A
8
2
1
a
C
e
g h
b
e 9
Bishop pair against two knights imbalance guarantees complex middlegame. 24. Kh2 Rg8 25, e4 g5 26. fxg6 Rxg6 27. Qh3 Kd8 28. Bd1 Rg7 29, Qe3 Qa5 30. a3 Rg8 31. Rel
5x...Nxf2 MAV-MCTS correctly decides to sacrifice knight to steer the game towards a theoretically drawn endgame. 58. Bxf2 Kd6 59. Ka5 Kc7 60. Ka6 Kb8 61.
Be3 e4 62. Bf4+ Ka8 63. a4 c3 64. Bxe3 Kb8 65. Kb6 Ka8 66. Bc5 Kb8 67. a5 Ka8 68. Bf2 Kb8 69. Ka6 Ka8 70.
Kb6 Kb8 71. Ka6 Ka8 72. Bd4 Kb8 73, Bgl Ka8 74. Kb6
Kb8 75. Be3 Ka8 76. a6 Kb8 77. Bel Ka8 78. Ba3 Kb8 79,
Bc5 Ka8 80. Ke6 Kb8 81. Bg1 Ka8 82. Bc5 Kb8 83. a7+
7
Ka8 84. Kd5 Kb7 85. Ke5 Ka8 86. Kf6 Kb7 87. Bf2 Ka8
88. Ke5 Kb7 89. Kd6 Ka8 90. Bgl Kb7 91. Bb6 Ka8 92.
Ke6 Kb7 93. Kf5 Ka8 94. Kg4 Kb7 95. Bc5 Ka8 96. Kf3
5
3
Kb7 97. Bb6 Ka8 98. Kf4 Kb7 99, Be3 Ka8 100. Ke5 Kb7
101. Kd6 Ka8 102. Ke6 Kb7 103. Kd5 Ka8 104. Ke5 Kb7
105. Bf2 Ka8 106. Kff6 Kb7 107. Bd4 Ka8 108. Bf2 Kb7
109. Be3 Ka8 110. B12 (threefold repetition). This draw
because the queening square is the opposite color of the bishop. 1/2 1/2
Game 36 The last resource
a
C e
9 h
31...f5 MAV-MCTS breaks the rule of thumb that the side with knights should keep the position closed because open positions favour a bishop pair. 32. Bxh5 Nxe4 33. Bf3 Nd2 34. Bd1 Ne4 35. Rgl Rxgl 36. Kxgl
Date: 2024-11-14
White: Stockfish-L17
Black: MAV-MCTS(M = 100)
Result: 1/2 - 1/2
37. B13 Qxd5 38. h5 Qd6 39, Kg2 Q16 40. Bxe4 fxe4 41.
Online PGN: http:///tchess..r//MMMMs222
Be3 Qh4 42. h6 Ke7 43. Qh3 Qxh3+ 44. Kxh3 Kf6 45, h7
Kg7 46. Kg4 Kxh7 47. Kff Kg8 48. Kxe4 Kf7 49. Kd5
Ke7 50. Bb4+ KF7 51. Kxc4 Ke6 52. Kb5 Kd5 53. Bd2
Ní6 54. Be3 Ne4 55. Bxa7 Nc3+ 56. Kb4 Ne4 57. Be3
1. a4 a5 Like in Game 10, pushing the flank pawns on the first move seems to be the preferred choice when rooks
the a/h files with kings on the adjacent b/g files. 2. e4 e5 3. Ne3 Ne6 4. g3 g6 5. f4 exf4 6. gxf4 Nxf4
7. Bg3 Ne6 8. Nc4 Ra6 9. Bf3 Ne7 10. e5 Nc6 11. Ne2 f5
12. d4 Ng5 13. d5 Nb4 14. Bg2 h5 15. Ne3 h4 16. Bf4 h3
17. BEI NE7 18. Ra3 g5 19. Bg3 E4 20. Bf2 5xe5 21. Nxe5
54

---

Mastering Board Games by External and Internal Planning with Language Models
Qxe5 22. Bxa6 bxa6 23. Rb3 c5 24, dxc6 Bf7 25. cxd7
Rc7 26. Na2 Bxb3 27. Nxb4 axb4 28. cxh3 Bf6 29. d8=Q+
Bxd8 30. Rel Q15+ 31. Kal
8
7
6
5
4
8
3
3
8
2
1
9
Mll
The drawing mechanism is mesmerizing. 41. Bc7+ Rxc7
42. Qb6+ Kxb6 43. a5+ Ka7 (stalemate).
a C
h
It is hard to believe that this position in equal despite White effectively being two pawns down and and all the pieces stuck at the first two rows. Rc. 32. Bd4 33. Re8 Qd7 34. Rxd8+ Qxd8
8
7
6
5
4
3
8
2
8
g
The final position speaks for itself!
1/2 1/2
a
C
h
It is even harder to understand the equality in this position. 35. Be5+ Ka7 36. Qxf3 Rel+ 37. Ka2 Qdl 38. Qf2+ Kb7 39. Qf7+ Kb6 40. Qf6+ Ka5
55

---

Mastering Board Games by External and Internal Planning with Language Models
G. Opening Book
In each match-up between two agents, a specific opening is used, and agents swap seats to ensure each agent plays each opening both black and as white. The openings are listed in Table
Table 5: Table of the opening book used for chess. Openings collected from various TCEC (Top Chess Engine Championship) seasons. The scores were computed with Stockfish 16 with 1.5B nodes per position. The scores are all from white's perspective (so negative values mean black is better) and were computed via: centipawns
100
Opening
PEN
Score
QGD
mww.hhhhwssspppppppppppppppppprp KQkg
0.47
Sicilian
htw.h//ww.gggggggo.ee//eeeeeesep KQkg
0.67
King's 8 Indian
rl by Irk http://wwwnn///////aa///////aaaa
w KQ 19
0.62
KGA
KQkq
-0,28
Catalan opening
KQliq
0.71
French
rlhggh htt.://www...ooo.oo..ee/ae/a//an
KQkq
0.63
Nimzo-Indian
0.57
Robatsch (modern) defence
mbak pel http://wwww..pa..o//p////o////aa
KQkq
0.52
Budapest
e 2bgk2ppp
KQkg 6.6
0.36
Ruy Lopez
th http://hhwwggggg///////////////a
w--
0.63
English
mbqgb 1e http://p...ggg.....h.//////////p
KQkq -05
0.59
Sicilian defence
KQkq
0.67
QGD
KQkq-10 00
0.62
Pire defence
httphh//pppppoooi/sh///////////p IBOKBNR
KQkg 05
0.63
Dutch
rbg ek httpa////ag//////g/////////////p OKKNNR KQkq
0.82
Caro-Kann
KQkq
0.82
King's Indian
XPP.://PPPPPPPPPPPOONONOIO b KQ
0.24
French
rl httphh/hhhhoooooon/////////////m rlblkh
w KQkq
0.77
Trompovsky attack
(Ruth,
w kq
0.55
Opovcensky opening)
KGA
hww.hp/wwgggggggeeeii//geeggeeen KQkq
-0.52
QGD
htwpa//wwwwggggggg.....2/2022262 KQkq-04
0.73
Sicilian
r162kk1 hr22ac//heegpggg//o///////////10 b-
0.25
English
22gk2r/pb heg.a//..ggggggaa....aaaaaaaeaea
hww.eh/cw..ggggg//////////////ee kq-
0.33
Scandinavian defence
m2kb wwt.:/gwwinnggioo./////////////m KQkq-
KQkq-00 KQQq--
0.71
Benoni defence
m
0.70
Giuoco Pianissimo
w -99
0.55
Slav Slav
KQkq
0.81
Pire defence
mbgkb
KQkq-00 -05
0.74
King's is Indian
httpk//wwwpgg.//o////////////app KQ-08
0.55
Sicilian
pttpa///waa////////////////////m b-
0.05
Queen's pawn
KQkq
0.43
French
rabg Sigglklee htwp://wwwgggg....oo//oo///////s
K
0.33
Queen's Indian
ml http://wwwwppp/////////////////p
0.57
KGA
KOkg
-0.42
Bird
rnbqk htgp://ws.sgggggaae/e/////////rr
KQkq
0.52
Robatsch defence
mbggk htw.://wwwwhhhh////////a///////r
KQkq 0.5
0.69
Benko gambit
mbqkk I http:///ggggggggg..oo/////////pp
KQkq 0
0.55
Ruy Lopez
rhg
0.53
Benoni
rbqqelk k http://wwwpa///a/aaaaaa/aaaaa/am
2
0.62
Sicilian
mb http://hhhhhgg.oo//////////////a I w kq
0.84
QGD Slav
wtw. IBQK2R w KQkq
0.00
Caro-Kann
KQkg
0.63
King's 's Indian
mb2rk http://hhhhpphoooo.....//a/a//pp
0.13
0.51
Scandinavian
rub htt.hh/wwwggggnrrrr////////ssssp
KQkk
0.81
Dutch, 2.Bg5 variation
wwb.bbobuppeeog2ggg/gg////////20 JOKBNR KQkq
0.70
French
KQy-
0.14
English
sbbgkb
IQIIKIE IBIII
0.58
KGA
KQkq 17
0.55
Old Benoni defence
mbgkht http://wwwoppoooo//////////////0
KQkq
0.39
Sicilian
rlblk202g htt.a//ww....o////////////////nn
1.21
King's Indian
mbq rrk htt.:///.aggggg...//////////e//m
0.57
Sicilian
Inblrik http://wwwwpppppa/////////////// rbbq 2 Xtw. KQ&q
w--
0.53
Dutch, 2.Bg5 variation
0.41
KGA
KQkq
-0.26
Benoni defence
mubghh
KQkk -
0.78
French
ribl hhtps///ghhagggggggg///g/////pps I
0.37
English
c3k2r/ /3/2e//bgnbppp//// bwwpbpggbbbppgppppppbe
0.37
Robatsch defence
rl hnppppl
CAAPPP/RRBBBBNNN BNR
KQkq 10kq-115
0.95
56

---

Mastering Board Games by External and Internal Planning with Language Models
King's Indian
rlbq wttp:///wwwpplllopp////////////p
1.14
Sicilian
12gkbiripp r httpe///wwhhhggggo/oo/////////aa
KQkq
0.36
QGD
KB/K2R w KQkq 488
0.38
Ruy Lopez
12rrlk http:///pppppppp////////////////
BORIIK w--
0.85
Queen's is Indian
migh http:///wpppppppppppp//////////p
0.53
Scandinavian defence
|/g. KQkq-
mhggkllepppp
0.77
Kevitz-Trappe Trajkz-Trajkovich defence
wtwp://wwwpppp/////////////////1 KQkq
0,50
Evans gambit
rlblk
-0.07
King's Indian
KQQ33
0.60
Sicilian
rur3k1/1
0.75
English opening
el
w--69
0.47
French
htw.h//w....ggg...g..////////000 KKQ- KQ-59
1.13
King's Indian
ri
KQkq
0.80
two knights defence
KQkg 006
KQkq
0.69
Queen's Indian accelerated
KQkq
0.51
Caro-Kann
0.52
King's Indian
mby
KQQ
0.51
Sicilian
18
-0.43
Dutch
ri httpgp/www/pppp///////////////// w KQ
0.53
Robatsch (modern) defence
rubg incpp otg.apa......g..oo....sssssssrrr KQQq-
0.91
Benoni
htwp
r bire 3ptp::kk//ppppppp1p11pppm..m wwg.a//wwgggpppp//2////////11110 KQQq
0.87
Danish gambit
-0.49
Trompovsky attack
wttp
KQkq
0.57
Opovcensky opening)
French
2.8
0.32
King's Indian
mbq http://pwpppoooooo//////////p/pa
IQRRIRR 07
0.33
Sicilian
rib2rk
http:///ppppppooo//////////////1 (BIRPP/PPPP/KRRRRRRRRRRR w-
0.65
QGD semi-Slav
mhgghllepppp2
1RR2QKRR KQkq
0.16
Vienna gambit
hwtph//wwgg/mmmmm////////////ppp BBOKENR KQkq
rbbokbarrlpop
-0.53
Benko gambit
mi
DOO IBOKBNR KQkq
0.80
Pirc
http://wwww..........//////////p PPPRI IKBNR KQkq
0.49
QGD semi-Slav
KQkq
0.27
Ruy Lopez
KQkq-
0.58
King's 's Indian
mbql1kk
KQ-07
0.77
Sicilian
w-
0.75
Dutch
r1bq http:pppppppppppplp
Modern defence
mbqg http://www....p////////////////m KQkq
0.60
Benoni defence
mbglrkk/1pps http:///twg..gggg///////////////
KQ-0
0.62
KGA
rbb http://wwwp.pppppp////////////ap KNR 34
-0.62
Queen's pawn game, Chigorin
rlbgghooopppp wwtphh/wwww.g....oos///////////m
KQkq
0.54
variation
French
rubq hmtp::/ppphhgqgueeepppp///////pp KQkq
0.17
King's Indian
1by hww.h//pwaalpp////0/pp///////222
-011
0.50
Sicilian
el http://wwppp/////pp////////////p KQky
0.93
King's Indian
r00.0//ppppaaggggg//e//es/222222 w
0.57
Sicilian
wtw.aaawwaagggggggooe//////eeeee 30
0.72
Dutch
wwwpwh/wwwggoooooooaaaaaeaeeeeee KQ
mbbgkb
0.68
KGA
KQkq-06
-0.66
Benoni
rabqk prg.apaeee...oooooooooooooaaonar
KQkq 009
0.70
French
KQkq
0.46
Rohatsch defence
hak nn wwtp://wwwpbpppp///ppppp///////p BQK
KQkq -
0.87
King's Indian
r1b2rk httpap/t..a/uppppp/////////////p
0.51
Sicilian
rl
KQkq
0.50
QGD semi-Slav
Xtw.:///......oooa/////////////0 b-
r1b2rk1/pp h
0.36
Ruy Lopez
ell rliggk2r httpa//wwwgggppppp///////////s/p
0.30
Queen's Indian
-Q-0
0.94
Scandinavian
KQkq
0.58
QGD
tikk htw.:///wwhpgy/////////////////1
0.50
Vienna game
N2k X22.0//wwwoooloolooooo/o/o//o//0
KQ KQ-0
0.72
King's Indian
rbbq wtw.p//www..........///o////a/ar
3
0.67
Sicilian
rbbok lnn' wwwpo:/wo....ooo/a////////////em
KQkq-47
0.80
English opening
rlbq 1/1 http://wwwpppcccc//////////////p
INR
0.23
French
1rkl/ pn http:kkkJJJjiiiopoooo/o////////p
BIR w-
0.76
Neo- Gruenfeln defence
riliig 1/ppp
0.42
Two knights defence
el blggh htw.ap/ww............aaaaaaaaaar
KQQg
0.17
English opening
muhgkhunn umg.ghaww.hgggggggggg////////epe BOKKENR KQkq 03
0.49
Caro-Kane Kano
rabqkb httpp:ppppppppgpgg..a.ggaaaaaaaa ott.upu................////////e
KBNR KQkg
0.63
King's Indian
ribglrk httphh/cwwgppppooooo///////////a
0.42
Sicilian
BOKK
KQkg -08
0.64
Dutch defence
rubq
w
0.57
Robatsch (modern) defence
mbb b http:///ppppgggo///////////////p
KQkg
0.39
Old Benoni defence
KQkg 1Qkg-22
0.67
Ruy Lopez
r2q hanp:h/wwhggggg///m//2////////ep
IKI -5-5%
0.57
Trompovsky attack (Ruth,
KQkg
0.00
Opovcensky opening)
French
rlb Ibb hgg http:///w.pppppppaa///////////// KQkg
0.74
57

---

Mastering Board Games by External and Internal Planning with Language Models
King's Indian
rlbq Irk http://wwwwpph////////////////ap
BQK2R KQ -47
0.76
Sicilian
rib rl http://wwwwogoooooo////////////p I w KQkq
kq-
-0.05
QGD
0.54
Giuoco Pianissimo
r
0.45
Benko gambit
milkb Jolp httpp//pwwwpp/////p/////////opon KQkq
0.56
Pire defence
mhggk httpp//wwwwpppp.///p////a//aaapp
1
0.73
Old Indian
m wtwp::/wwww..........//////aaaaa
KQkq-
0.89
Ruy Lopez
Irk http://wwwoooooaa///////////////
w--
0.64
King's Indian
rbb qeek 1/1 htgps//ww....gggg//gee/////////a
KQ-5
0.21
Sicilian
m mlgk2r/11 wttpp//pppppp///////////////////
KQkq 11
0.43
Dutch
rlbglekl http:p/pww...ggggggg/22////////0
w-
0.87
Robatsch defence
KQkg-
0.69
Queen's 's pawn game
mbbgbb hrpp
http:///wwwp........///////////0 KQkq
0.46
KGA
-0.78
QGD
w-
-0.32
French
wttp://wpwp.p....//.....//////t/ KQkq
0.32
King's i Indian
mbq
0.61
Sicilian
0.89
QGD semi-Slav
K 0
0.11
Sicilian
KQkq -
1.39
King's s Indian
ribylrk
PPPRIQIRII
0.85
Vienna game
http:///ww/////////////////////a w KQkg 08
0,58
Dutch defence
w
0.78
French
KQkq-
1.07
Benoni
KQkq
0.59
Robatsch (modern) defence
rbbgkbarr
KQkq
0.65
Budapess defence
KQkq
0.78
Sicilian defence
rlbikh http:///ppppppp///////////////// IIIRI KQkq
0.43
King's s Indian
1rlg pttppp/pwggggggggog.m//////////n KEIR w
0.66
Ruy Lopez
m hwwphp/pwwgggggggp.////////////p RQK2R w KQkq 06
r htgphh/wwpsspoooc//////a/a//////
0.63
QGD Slav
KQkq
0
L.00
Owen defence
KQkq
0.86
Queen's 's Indian
wttpp//wwww.gpppp./////////////e rabgkb (ttbgkkbl/22pppppgg
KQkq 05
0.91
Sicilian
www.saaappppppp///////////////es KQUu 01
0.15
King's 's Indian
ribinkk
0.87
Sicilian
7
0.84
English opening
el (arkkb///bbld mwg.heaeessnnnggg0002/00000000pa KQkiq 004
htgp://pwpggg0222222222222222220 KQkg 1
0,56
French
KQKq 2
0.54
Semi-Benoni ('blockadc varia-
1.43
tion')
Scandinavian
wttpp//ww.//ppii...../////////ap KQkq 06
mbikkttr/lpp
0.97
Benko gambit
http://wwwgggpooooooomm////sssse KQkq
0.57
Caro-Kana
mi hwg.gh/ww.oogpplllggggg////////s
w KQkq 07
0.00
King's Indian
mb2rk httppp/wwwaaaaaaa//////////////a
http:///pwggggggp//////////////a KQ
-0.30
Sicilian
rub heolkb////ppppppp http://wwwwwpgoooa////////////pr KQkq-
-47
0.58
Dutch defence, Blackburne vari-
0.53
ation
Pirc defence
r hatphpppppppggipl//////////////p
KQKq-06 066
0.74
Benoni defence
mbg http://ppwg.....//../pp////////p ribq Ub hunggpowwkkknnkk////s////r/rrrpp KQ-49
KQ-07
0.61
two knights defence
0.64
Trompovsky attack (Ruth,
mb mblkhh hwwp://wwh.aageee/////////pappap KQkq 2
0.32
Opoveensky opening)
Reti
httpe//w.aaaaaaaaaaoeee/e////sap b-
-0.23
King's 's Indian
ryblk http://ppppppglaaa///////a/////a KQkq -24
0.62
Sicilian
KQkq
-0.41
QGD Slav
mbbgkb
http://pgggpppp//ccppppp/////nna BQKBIR KQKq-06
0.00
KP
el hwgp:h/wwppggggcc...s/////eeeees
KQkq
KQkq-12
0.48
Benoni
rbbqk22fpp http://wwwp.hhp//p//////ppp////p IBQK KQkq
0.70
Pire defence
mbbgk2r/pppp hwtp://///pppppp///////////////p
httpp//pwwpppp.o..///////////a/a 3KBNR KQKq-35
0.46
QGD
IR KQkq -07
0.84
Ruy Lopez
12grbk 1/1
mb2rk http:p/g.l/pppiilll/////////pppp
PPI/BBOR /RRR/KK w
0.39
Sicilian defence
1.00
Dutch
1ppp)
IROKBIR KQkq
0.69
King's 's Indian
rubgkhar/pp hta.kk/nn/pppppppppp///p..pppppp
KQkq 0.3
0.84
Nimzo-Indian
mil Ink http:p/pwggggggg..e////////////s BROK INR KQ
0.49
two knights defence
ri htpphp/pppppppppppp
http://pggggppga22222/2/222/2/20 w KQkq -
1.21
Queen's pawn game, Chigorin
2kr http://wwwwp....../////p///////a
066
0.85
variation
French
www.hh/www..pp..././////////eeer KQkg 004
1.00
King's 's Indian
rbb http://gggggggga..o.///////////p -
0.52
Sicilian
r1bqIrk1/ lnk hwkkk//wwwwggonoo//////////////x
-
0.78
Sicilian
el rlbq tbgggitt/ppppp.pppppi//n//// mblkk httpk//wwpggog//o//////////////e KQQq--OKKOOOOOOO
0.38
King's 's Indian
KQ-19
0.89
French
w KQkq 08
1.45
QGD
KQky
0.69
58

---

Mastering Board Games by External and Internal Planning with Language Models
KGA
KQkq
-0.73
Dutch defence
0.71
Robatsch (modern) defence
http://wwwppppyoo//////////////p IBIKINE KQkq CQkq-06
-0.07
Budapest
miggb
w KQkq-
1.17
Sicilian
r lb http://wwwg.gg.pgo/////////////a
0.99
King's s Indian
ribi
0.99
Ruy Lapez
e hwwpep/ppoyyoo////////////////10
RQkq Qa-- 1
0.71
Queen's Indian
m2khi
211
0.96
Caro-Kann
KQkq-
0.68
Blackmar gambit
KQkq 006
-0.33
Pirc
lrk hxg.ghgg.h...ippgp2222aa///7/111 KQkq
rub hrt.ap/ppppppppiaaaa///222221221
0.93
Benoni defence
KQ 10Q
0.74
Sicilian
rl lnk hpppl htwp://wwww.....oooo///////////a
1.17
King's Indian
3Q-3
0.83
French
rl 2bgkkr2ppbpppp/ http:////w....//////////////////
KQkq-0
1.16
Trompovsky attack
KQkq
0.87
Opovcensky opening)
Scotch
ri http://wwhhpppooo/////////////// KQkq
0.97
Nimzo-Indian
wwwpa//wpp.....e/////////////eea el
0.53
Robatsch defence
KQkq
0.79
QGD semi-Slav
KQ KQQ-0
0.36
Dunst (Sleipner, Heinrichsen)
KQkq
-0.60
opening
Sicilian
htwpw//www......///////////////n KQkq-
0.92
King's Indian
b 112
0.74
Philidor
http:///..ppppoooo/////////////m KQkq
1.08
Dutch, 2.Bg5 variation
mbig Inrippp
KQkq-
0.67
KP
r2gkhon/ppp http://wwwggg//aa/a/////////////
KQkq
1.41
Czech Benoni defence
http://wwww............/a////.ar IR KQkg
1.26
French
tbbgkblr/ppp mhg
w KQkk
1.05
Bogo-Indian defence, Gruenfeld
KQ
0.34
variation
Sicilian
wttpp//wwwppppeaee////////////pr KQKq
L.19
King's s Indian
rl bi lrk httpa//wwwppppp//o/////////////a
KQ-0
0.46
Latvian counter-gambit
wwtpp//wwppgggaaaaaa/////////a/p KQkq -13
1.28
QGD Slav
KQkg 100kg05
1.17
Scandinavian defence
KQkq-16
1.33
English
ribi http://wwwpp.....//////////////a 1P IP/R4BIR
-0.13
Robatsch defence
mbbgk Inr/ httpk///wnpahaaaoooo/////o/////n BOOEII
KQkg 006
0.95
King's Indian
KQ-09
0.77
Sicilian
http://apwwmmhhhhhp////////////p KQkq
mb
0.68
QGD
r1b1k1 www.://wwgggg/22254222222///2220 KQkg 2.8
KQ
0.93
KGA
KQkg
1.08
Benoni
r1bqr wtt.ep/.w..poaaaaaa////////////0
0.89
French
rbb biblktin hwtp://pwpp4sspggg//////////22pp
KQkq
1.33
Dutch
rub otg.ggggggggggg////////////////e
w -
0.94
Petrov
rbq http://wwhhllplpo//////////////p
KQ
-0.47
Sicilian
rlbggh wttp:///w..gggggggo/o///o//////2
-
0.86
Sicilian
mbbgkh www.://///////ppppp/p/////xxxxxx http::/whhhggggg.ca///////////pp
KQkg
0.32
King's s Indian
rlbq Ink httpg//hhggggggg//////////////// BIIPPPPPPPIIIIIIIIIII PQIRKI w
0.73
French
KQkg
1.16
QGD Slav
Slav
hgg.://w.hhgaaa/a/////////////aa BBO.R IBQK2R b KQkq
-0.29
KGA
wwwpppppppeeeeeees///////////p/p /
KQkk 14
-0.68
Dutch, 2.Bg5 variation
KQkg 0.5
1.15
Robatsch defence
KQkq
0.87
Gruenfeld defence
Irk
K
1.02
Ruy Lopez
whw.ge//pppppppp///////////e/eep KQkq -02
0.25
Queen's Indian
mi 2r/p http::/wwwggggooooo///////aaa/ea
0.97
Scandinavian defence
mbgkbnnr'pp wwg.w//wwwpppppo//./..e//eeeeeep KQkq
0.66
Blumenfeld counter-gamth gambit ac-
KQkq -06
0.58
cepted
Pirc defence
mby Irk htpppp/wwwppppi.p//s/s/.....sstp w KQ-36
0.62
Benoni
1rb2rk 1/2qpl httph//w....aaaaga///////////aap KQkq 007
I hmtp://ppeeggogoogoppp///ssssppp
0.72
Sicilian
0.88
King's 's Indian
rl lrk http://gpi.ppppp//ppoo////////ga mww.kkagggggssssseeeeeueeeessspp KQKq -
w
0.85
French
0.49
Trompovsky
attack
(Ruth,
rub htt.://www......ro////o//aaaa/aa
KQkg
-0,29
Opovcensky opening)
Ruy Lopez
kg
0.89
Nimzo-Ined Indian
mbq lbk 1bkll/pp http://p/ppgggooo//n//a////////p B KQ
0.49
Robatsch (modern) defence
KQkq
0.69
Queen's Indian accelerated
mi gkh migphh//peggggnmir/rrr////////pp PP/R IBOKENR KQkq- 05
0.91
Bird
KQkg
0.66
Sicilian
el wtg.hh/pppppgggggpg/////s/eeeenm BOOKB KQkq
1.20
King's Indian
0.10
0.92
59

---

Mastering Board Games by External and Internal Planning with Language Models
KGD
mb mblkhar/pgpp w
KQkq-
1.08
Dutch defence
rlbgkb blbgkb-rrpppe wttp://pwwpppp.///////////////ta KQkq-25
0.77
Alekhine's defence
m http://pwhhgppp////////////////p
2.7
0.91
Czech Benoni defence
miqkk Ip rubqkb http:///wwwppoaaaaaaoaaaaaaapaaa s KQkg c6
1.27
French
KQkq
1.27
Benko gambit
lgkh http:///www//ii/a/////////////pa
0.92
Sicilian
rlbikb ribikblegpssgee hrgpppygwwg.ggoooooooo//ooo/naan
KQQka KQKq
1.28
King's s Indian
r rbgll http:://wwppppgooppp///////////p
KQ-37
0.83
Four knights
rl wtw.ap/wwwg....../a//////s//a/aa
KQ
-0.54
QGD Slav
r bbgkbl Xttpa///w/....../o/////////////a
KQkq
0.84
Caro-Kame Mano-Kann
4--4
0.78
English
1.12
Robatsch defence
mboki
KQkq-- KQkq-05
0.95
King's s Indian
Ink
KQ
KQ-0
0.72
Sicilian
w
0.81
QGD
KQkq
0.83
Ruy Lopez.
0.92
Benoni defence
KQkq 26
1.27
French
mb1k
http://wwww.ppp.ppa///////////ap w KQkq 1.5
1.01
Dutch
mhgkk wttp:h/ww.pp....///////////////a KQkq
Nlbk Ib httpg//b..opooooooo.o.aag//////0
0.84
Vienna
KQ-011
0.89
King's Indian
w--2
0.82
Sicilian
KQ
0.66
Latvian
pww. KQkq-
mbgkkbu
0.00
Nimzo-Indiar Indian
1.21
Robatsch (modern) defence
httpp//www..........//////////aa KQkg -04
0.35
Robatsch (modern) defence
KQkq Lokkg-05
0.56
Ruy Lopez
0.00
Dutch, 2.Bg5 variation
KQkq 02
0.59
Budapest
http://wwpppp......a//////////pm K 0.
I
0.64
Sicilian
www.g//wwwp.uuupoo/////////////m KQk
-0.48
King's s Indian
0.59
QGD semi-Slav
12gk2rfpbin
KQkg
0.48
French
mabkk http://www.ggg......///////////p
KQkq
0.44
King's Indian
KQkq
0.60
Trompovsky attack
(Ruth,
rab kbb wttpap/iih.aigggggg...2200000010
KQkq-
0.69
Opoveensky opening)
Queen's 's pawn
m 4k hwwpppppppp/llpppp.eeee. http:///ww..pm////////////////// KQkq -
0.92
Bird
miigk 2p hwtpgp/pww.neeel/ll//aa////////m KQkg 0.5
0.42
Sicilian
KQkg
0.75
Robatsch (modern) defence
b
KQkq
0.67
Dutch defence
KQkg 0.3
0.81
Ruy Lopez
r1b1k2:224
w
0.90
Caro-Kann
wwppep/ppppoo//rrrrrrr/r//p/pppp KQkq
0.71
King's Indian
rmbgIrk111pppppppll
KQ)
0.82
QGD semi-Slat
r3kb Qttph//wwppppplggggg//////////10
0.33
Queen's Indian
milghlllp22p
KQkq
0.75
QGD
r3k http:///..p/p//////////////////r
Kkq 0
0.76
Benoni
KQkq
1.04
Queen's 's Indian accelerated
IROKBNR KQkq 00
0.79
Benoni
KQkq
0.84
Owen defence
mag.gp/.....ppoooo///////////ppm KQkq
mbggknnn'p
0.97
Robatsch (modern) defence
KQkq Qkq--0
0.85
Philidor
12
w
French
KQkq
1.02
QGD Slav
KQkq 377
0.75
Old Indian
ri
0.85
Sicilian
0.77
French
http://///////////////////////// KQkq 0
1.10
Dutch defence
htg.ggggggggghgggggg///////////m 0
0.83
Sicilian
rlr3k
0.76
Scandinavian
rbb mbbkkbl http://wwww..mgo.//////////////0 KQkq
L.11
King's s Indian
r1b2rk http://ww...oooooo/////////////p
1.05
Sicilian
KQkq
1.19
Sicilian
Irk htt.://.w.....g..o../..///////em
10.12
0.72
Ruy Lopez
22qphh
1.08
Sicilian
0
1.13
Old Benoni defence
http://ww.pg.g...././//////////e KQkq
1.39
Sicilian
1.04
Benoni defence
rlby htw.://w................///oeooe
KQQ
L.09
QGD semi-Sie Semi-Slav
http:://ww.ppooohhh///////////// BBIRKKI k 00
0.69
Czech Benoni defence
wwtphh/www..ooooooom///////p///m IBOKANR KQkq
1.16
French
Sicilian
m 2nbpk220pp
r2q r2qltl
IBIR
KQkq 07
0.85
0.88
English
httphh//wngg.//oooooo/////////1p BROK KQkq
0.86
Sicilian
mbggh
KQky 06
0.48
60

---

Mastering Board Games by External and Internal Planning with Language Models
St. George defence
mibgkbod23pp
hwtpa//wwwpppooooe.//////eppopop KQkq
0.74
Dutch, 2.Bg5 variation
mbgkb httpppppooooee/////////////epee1 XPP
KQkg
1llg-22. 24
0.81
Rohatsch (modern) defence
httpp//pwwggggg///////////////// P/R BBOK IR
R
KQkq
0.60
English opening
rbbqkborllpp httppp/pwwkkkkaaa22a//////////e1
KQkq
1.09
French
mbughl 2/ httpp///ww////////////////////// IBOKINR KQkg
07
0.95
Sicilian
migiti pwwpgppppppnniii/a/aa/////////na P/REA//PPPPPPPP 2/R2QK2R KQ-1
10
0.88
French
rubgkh labgkblrlppp http://wwwwggpp..//////////////p BEOUEE w KQkg
244
0.78
Scandinavian (centre counter)
mhh http://wwwpppp///////////////ppp
KQki 0
0.84
defence
Robatsch defence
KQkq
0.82
French
rlbg httppppppaaagaapop/aaaa//////220 KQkq 17
0.71
QGA
rlbgkb 2tg.
KQKq
0.75
Old Indian
mn hakkar//ppp hwg.://pg/ppppp///////////////pp
KQkq 0
0.91
Sicilian
rib te/kkb///leee httpp///wwwpppppp//////////////p
KQkq
0.85
QGD Slav
mi might http://wwww..pp..........///./aa
KQkq
0.89
English
k-
0.79
King's 's Indian defence
rihgghh h httppp/pwwp.poogo.//.../////////
w KQkq
1.10
Queen's pawn, Mason
rlb htwp:///www.oooo///////////////o
KQkq
0.05
Steinitz counter-gambit
Sicilian
httpa//wppppppapass////////////r KQkq
0.86
Robatsch (modern) defence
mbgg www.apaggggggggggiisss//ss/seser KQkq 0
1.20
Caro-Kana
KQkq 666
0.00
French
rlbgkbarrp hwt.ao/wwwppppgog.////////////ep w KQkq
L.11
KP
rliggh http://wwwnnnnaaaasge//////ppppp
KQkq-
1.21
Sicilian
mb 122o http://pp.ppggggppppooo////////p
KQkq
1.03
King's s Indian
r2q trk http:///wwpggpipaaaaaa////////pp
KQ-29
0.99
Dutch
mb http::/kppp..b//..m/./////meaae
0.86
Robatsch (modern) defence
KQkq
1.07
King's Indian
IOQRRII w w-
-19
1.01
Neo-Gruenfeld defence
lrk http::/pppppppppp/p
0.81
Vienna
0.94
French
KQkq
0.76
Ruy Lopez
el ba lek 1/2g httpp//pppp/pppeeha/////////////
w
1.11
Trompovsky attack
(Ruth,
el http:///||aggg/2222222///////030
KQkq
-0.67
Opovcensky opening)
KGA
bubgkklli/pppp I http://wwwpppppo///////////////s K
http://wwwgg......aaaaa/aaaasprs KQkq 0.6
-0.99
English
-1.27
Sicilian
rlhq irk 1/ http://www......aaa///////////pp w KQ-0
1.06
English opening
w KQkq
0.77
King's Indian
rlbu2k hpppon/
1.10
French
rbblk http://wwwg.///////////////////m KQkg- 005
0.94
King's Indian
ell bylkk htbpl:kkkggg/ppb///2mzg/p// http::/wwwh..oooppo////////////a
w
0.96
QGD
rbbgkb hhwph///ppppppoo///////////////0 KQkq -
1.07
French
KQkq
1.06
Ruy Lopez
bg http://wwwppppp/c//c///////////p
0.92
Queen's 's pawn game
el httpppppwwgpppeoo.e/////////eses
w KQ-39
1.21
Petrov
mbgili lb mmbgkbli/pg http://ppppppppooo//////////////
0
-0.73
English opening
KQkq
1.13
Sicilian
mb Ikh h pappp httpp////ppppppp//////////////// B KQkk
1.16
French
rigq h2tphh/nwpppppppppppppp////////p PROZPERK BIRB 11
-1.07
Robatsch (modern) defence
2p/2 1 http:////tttttooo/////////////pp http:pppwwm/////a/////////////pp
0.95
Queen's 's pawn
KQkq 26
1.09
Owen delence
m I http://wwwwpoooo.o//////////pppp w KQkq
KQkq 26
0.85
King's 's Indian defence
rubgkb I
0.84
Pire
http://wwwgg..g...oo///////ooapa KQkq
0.96
Scandinavian (centre counter)
mi http://ppphggghhhp/////////01010
KQkq-00
0.87
defence
Dutch, Korchnoi attack
hwwp:h/whjggggooo///////rrrrrrra KQKq
1.13
QGD
rib otl.koogguiigplllloo//////////ep w KQkg 2
0.95
King's Indian
w
0.97
Sicilian, Szen, hedgehog varia-
0.68
tion
King's Indian
bylk
1.12
Benoni
rik http://wwhhhhhhoaa///////////ppe KQ
0.81
Queen's Indian
1.00
French
mbbjkh btapkkklllppppppppppppp http://wwwg....aaa//////////ppap KQkg
0.81
French
bibb bi http:://hhphopoppopooooao/o////0 http:p//niiiiiiaaaa////////////p
KQKq 0
0.82
Caro-Kann
w 68
0.81
King's i Indian
rab2rk hppp httpk//pwp...aa......//../////ta
KQ-39
L.15
Ruy Lopez.
KQkq
0.81
Dutch
rlbg http:p/pphhhSS55.ppp22222/////11
B22K w--0
0.92
King's 's Indian
mby rk httpg//hhhnnnnccmm/////////////p IBOKBNR w KQ-
0.73
Polish defence
KQkq
1.19
Ruy Lopez
0.62
King's 's Indian
w--09
1.09
61

---

Mastering Board Games by External and Internal Planning with Language Models
Modern defence
BQKBNR KQkkq
0.76
Nimzo-Indin
www.ap/ww...ooooooooo//////spopp BIKNNR KQ- KQ-07
0.92
Old Benoni defence
hwwpp//wwwggggggg////////a/a///0 BQRBN b KQkq-00
0.71
Old Indian
mq lbb http://wwwwg..oaaaa////a//////// BB KBB KQkq-06
1.07
Ruy Lopez
0.85
Sicilian
IR KQkq-00
1.15
Nimzo-Indian
in htt.g//ttpppgggggggg///ppppeeee
httppp/www...ggaaap///////////// B
KQkq -07
0.89
French
r3k http://wwwg.o/////////////////// KBNR KQkq
1.00
King's Indian
KQ-29
0.81
Sicilian
KQkq
1.14
Nimzo-Indial
r1
KQkq
0.71
King's Indian
KQ-
1.13
French
mbgg Ik
KQ-38
0.79
Budapest
hwtp://wwwwg....aa222//////////a KQkq-
1.06
Benoni
hww.://www...ggoo//////////////m BBOK2R KQ-3
1.02
Caro-Kann
http:////....oooooo////////////n KQkq
0.91
Alekhine's defence
KQiq- 25
0.92
Vienna
KQ 1.34-45.
-0.89
Sicilian
r2g
0.78
Sicilian
wtw.p//ww...agggg//////////////n KQ-39
1.06
Benoni defence
0.93
QGD Slav
ratpe///ssppp//0/////////////110 Kkq 44
1.02
Nimzo-Indial
2t/p2ttpp2p1
KQkq -06
Sicilian
KQkq
0.92
QGD
mugkkbur/pp- hwg.kk/www..ppppp/////////////21
KQkq-
0.89
King's Indian
rlb lnk http://ppbppppp/p//////////////0
anlpp http://wwwwgggg.///////////////p PPIROKIIR KQ-09
0.93
Sicilian
1.07
Pire
robq Irk lpppl http://wwwwpccc.o///////s/////pp
066
0.77
King's Indian
raby Ink hwtp://wwwgggp//////////2222//20 BOKINR KQ 89
-1.05
KGA
wwwph//wwwpppppp///////////////m KQkq
-0.55
Trompovsky attack (Ruth,
KQkq
0.82
Opoveensky opening)
Sicilian
rnbg)
0.94
King's Indian
Irbgr http:///wwppppaaao//o/////////// KQ-79
0.82
St. George (Baker) defence
mi gkkne' http:h/wwwppppoo.///sa//a//////p KQkq -3
0.85
KP
r wtwpb//pppoggo22//////r////ppppp KQkq
-0.62
Dutch
KQkq-27
1.07
Trompovsky attack
(Ruth,
KQkq-0a
0.74
Opovcensky opening)
French
rob lkhrr/pppp http://wwwwwpp/p//////////////// /ttp://wwwwat./////////////////a
KQkq
0.95
King's Indian
mbqlik Irk http::/pppppppp/pppppppppp
KQ-07
0.77
Modern defence
KQkq
1.07
Sicilian
ra rabgkhur
KQkg
0.76
Sicilian
0
0.92
Queen's pawn game
22gkb http://pwppggg/////////////////p
KQkq
0.83
Queen's Indian accelerated
KQkqq
0.99
Sicilian
el htt.ph/wwpppiplloggg/////2/////0
KQkg 12R
0.71
King's Indian
KQkg
0.92
Caro-Kann
KQkq
-0.90
QGA
r2gkb Irlppp http:///aaaaa/a////////////////a
KQkq
0.99
Philidor's defence
KQkkq
0.90
Caro-Kann
KQkg 0.
1.03
Pirc defence
Tlghh htgphh/...pppggsss.o/mm///s/ssap
KQkg
0.88
French
ell
KQkq 00
0.84
Trompovsky attack (Ruth,
rbb lbb httpb//.ppp..gggo.////////////ap
KQkq 06
0.99
Opovcensky opening)
French
mubgk hwgp://wwagggg........//aaaaxaaa
w K-kq 0
1.04
Robatsch (modern) defence
ribqk2er mtgp:///rpppooooooaaaaa//////ee0
0.96
King's Indian
mbg wtt. IBQ KQ-08
-0.82
Ruy Lopez.
http:///waapppppoo///aaaaaaaa//a I IBQRNKI w--5
1.00
Vienna game, Max de-
bbg orgp
INR w KQkq
0.95
fence
English
rl
IR w KQkq 17
1.05
Alekhine's defence
KQkk
0.88
King's 's Indian
0
1.01
Caro-Kann
kq-18
1.05
French
miw.hh/hhhuuuuggggoooo///////sss KQkq 37
1.05
Sicilian
KQkg
1.06
Sicilian
ri ribgkbir/pp) mb lbb htwp:////////ooo////////////////
KQkq -
1.12
Blumenfeld counter-gan gambi,,
KQkg 2.6
0.91
Dus-Chi mns-Chotimursky variation
Two knights defence
ri hww.w//wrrreiiiioooao///////aaap rlg htwp://hwwh.inngggg.../////////a http:///wwppppp..//////////////a XPP.://NNEESPPPPPPPPPPOPPEEE
KQkq 1 -2:gg-210
0.89
Czech Benoni defence
KQ-
0.97
King's Indian defence, 3.Nc3
1.22
Centre game
hhgg2hhhppppphhh22gg/////p....p PPPPP PPP/R 1KBNR w KQkq -47
0.93
62

---

Mastering Board Games by External and Internal Planning with Language Models
Sicilian
12gkb r/ inl http://wwwppppppppp////////////p
0.98
KGA
mwgpup/wwggggpss/spppppppppaappe KBNR KQkq
-1.06
King's s Indian
KQ-19
1.05
Pirc
mbqltk http/ppppppppppppp
IR KQ-07
1.17
English opening
mbqkkl hww.ah/wwpppg.gggng/h///////eeee IBOKII KQkq-20
1.00
Dutch defence
KQkq 1
0.92
French
BQKBNR KQkq-O*
1.00
Sicilian
r rlgghhl wttp://wwwpppppp///////////////m
KQkq
0.88
King's Indian
by Ikk httpgh/wwgggggggg//////////////p
KQ-18
1.13
Budapest
rIb htwpph/wwg.yrrr2250000/222222/1.
KQ
0.91
Blackmar gambit
migkk http:///spppppp.oo.//////////aaa
KQ
-0.78
r1bgkb wtgph///wwpooooooo////////////sp
w KQkq
0.75
King's Indian
migl ptt.g:/k//ppplppppppppppppp mtgpxx/wwgggggg///////////22/222 QBPPP//3K2
1.22
Ruy Lopez
r1b2rk http://whgggggg.g.......///o//// PP IP IBQRIKI w--
1.00
Scandinavian (centre counter)
m2kk
IBQK2R KQkq 0
0.98
defence
King's 's Indian defence
w KQkq 16
1.00
French
mng
rlbqk htgppp/wwwh.h2gghhh..sspppp/2ppp w KQkq
1.15
Giuoco Piano
0
0.95
Queen's 's Indian
KQkq 3.6
0.97
King's s Indian
w
0.96
French
KQkq-
1.06
Sicilian
rlbqkbir/pp htw.p//.gggggggg///////////////p BOKKR KQ
1.05
Sicilian
mb kb l http://ppppppppp.oooo//////////1 BQK2R KQkq-
1.03
Czech Benoni defence
ribqtrkl/1 Lrk1/1 wtt. httpa///w.cppppppgoo////////////
r3rlk http://wpwp..ooogoooo//////////s B w
1.29
Ruy Lopez.
BBQ
1.01
Dutch
0--08
0.93
QGA, Smyslov variation
rlhg Irk http::/www.gppcccaaaaooc///////p IBOIIP w-- ---58
0.90
English
22lrk 1/2pm httppplnpppppppppmmmppmmmmm
https//wwnnngggggg/o///////////0 PAPP/RKS KQ-
0.95
Pirc defence
KQLy
0.99
King's Indian
rlb Irk http://pwwhpphhhhh.h///////////1
0.90
French
w KQkg
0.96
Sicilian
htg.aa/wwgpppggpggoo///////////1 KQkq-25
0.89
Sicilian
el
211
0.88
Queen's 's pawn
KQkq- 055
-0.8
KGA
KQkq
Benoni defence
mbi
BQRRIR KQkq
1.06
Gruenfeld defence
hwt.k//pwwppppppo//////////////p BBOKBN
KQkq
1.10
Sicilian
rlblkb wwi.kbliipppppp//l/oooo
http:///wwwgggggg/////////////// BOOKIRR w KQkq 08
0.97
Caro-Kann
ligh
http://wwwwgiiicooooooccaaaaaaaa BQOBIR KQkg 3.
1.15
King's is Indian
KQ KQ-08
0.78
Dutch, 2.Bg5 variation
rnhgkboolpp httpkkonnpppppppp2222p222p
KQki -04
1.02
Sicilian
w KQkq 336
1.03
Benko's opening
KQkq
1.14
Ruy Lopez
r1by 1ttk///bpp/ppp
0.92
King's is Indian
rlbgolk hppp http://wgggggiii///////////////0
w--
0.99
Gruenfeld
wttp KQkg
ribik magpgl/.wppppggggggo/g///s///ses
rbbgkblrrpppppppn
1.22
Giuoco Piano
KQkq
1.03
QGD semi-Slav
KQkq
0.79
Bogo-Indian defence
rihq Ink pppp httpkk/wwwnnn///////////////////
KQ
1.27
Queen's Indian
1.03
King's i Indian
mb2rk 1nb2rk//pp3pbel http://www.iiiiiaaaa/p////p/aaap
1.16
Vienna
1rbulrk http://wwggggpp////////////////a
hil h
-0.57
Ruy Lopez
L.05
QGA
r1h2rk Upp I
0.88
English opening
KQkq 07
1.06
French
KQky 166
1.00
Sicilian
r1b2rk
w KQ-6
1.08
French
htw.://ww................/.ppppm KBBR -Q
1.02
Philidor's defence
ml hww.://wwwwppppo...//////////pep
KQkq-14
1.23
Scandinavian (centre counter)
htg.kh/www.ppppooc/..//////apapa w KQkq 0.4
rl
0.89
defence
Sicilian
KQkq
0.89
Sicilian
rbbi k
KQkq
1.09
French
0.85
QGD semi-Slav
KQky 08
0.96
Ruy Lopez
www.:///wwo.........p////////aap w
0.97
Ponziani
wtw.hp/wwgggggggi...o..oooeeoeee KQKq
rlb
-0.75
Old Indian defence
det.tnpwwnnggonn/2222222///////s KQkq -
0.95
Sicilian
0.86
QGD semi-Slav
wtw.w///wwwoooooo2222222224/4000 KQkq
rib
1.10
Scandinavian (centre http::/ihiiciioooo////////////00
KQkq-36
1.18
defence
QGD
http://wwwiiioooo//////////aaaaa 12
1.03
KGA
mahhahhwgpgggccchhoa/////sshssee 12XP 36
-0.76
QGD
-0.99
63

---

Mastering Board Games by External and Internal Planning with Language Models
Robatsch (modern) defence
kq-
0.99
King's Indian
r1b2rk wwwp://ppp..e2222ee///////X/P/PP rl rig
1.20
King's Indian
KQ-08
1.12
Nimzo-Indian
w KQkg-
1.17
Ruy Lopez
http://wwwppppooo/////////////pp IBORIIII
1.02
Ruy Lopez.
0.84
QGD
ribik =
w
1.19
QGD
tnk httpk//www..oooo../////////////a QBR
w--8
1.10
Sicilian, Szen "'anti-Taimmnov')
KQUi -
-0.90
variation
King's Indian
r1 lg http://wwwwggggoooo////////////p KQ-37
0.98
Pirc
rabq httpp//pwwppppual//////////////p KQ-07
1.06
Dutch-Indian, Alckhine varia-
m I lik http:///hghhhhg///////////////// w
1.14
tion
Old Indian
r1 http://whhhhggg.aa/////////////r
1.09
Sicilian
rl lnk http://wwwaaaaaaa/////////////ta
-1.06
Ruy Lopez
23k22/ /ppp
1.17
Queen's s Indian
hwwph//gggggggggg.aa//////////pp KQkq-00
1.16
King's Indian
rlblgrk
4
King's Indian
robylik
1.11
Czech Benoni defence
b--09
0.98
English
KQkg 18
1.13
Benoni
1.11
QGA
httpppppwwwaaaai///////////////0 38
In
1.04
Sicilian
http0//wwggggggooo/////////////0 KQkq 5
1.05
French
KQy 0
1.05
Queen's pawn game
hagp://mmaaunnnga/aa///////////m KQkq-17
0.91
Caro-Kana
r1b2rk /btt://poog///ooo222///////////2
1112
1.10
64


Reviews:
[{"review_id": "SYAoNEJjS9", "reviewer": "Reviewer_wDBQ", "summary": "The paper introduces a specialized Multi-Action Value (MAV) 2B model trained exclusively on game data from Chess, Chess960, Connect Four, and Hex. MAV is designed to predict legal moves, track game states, identify the top-k actions, and determine the resulting board state after executing the optimal action. The authors convincingly demonstrate that the MAV model generalizes effectively to previously unseen board configurations.\n\nAdditionally, the paper explores two distinct planning methodologies applied to MAV:\n\n1) External Search: The authors implement an external loop utilizing Monte Carlo Tree Search (MCTS), significantly enhancing MAV's performance. This integration achieves results competitive with current state-of-the-art chess engines.\n\n2) Internal Search: The internal search approach leverages distillation from search trees. This technique also shows a consistent and smooth performance improvement as the number of test-time tokens increases.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to carefully review our paper and for the positive feedback!\n\n1. Regarding training cost, we used more than an order of magnitude more tokens to train the model on MAV data compared to the tokens used for fine-tuning the MAV model on internal search traces. We will clarify this in the text. Regarding inference, the main computational trade-off is that external search can be easily parallelized, whereas internal search is sequential. However, internal search could be optimized via techniques such as speculative decoding.\n2. To estimate the external Elo of our agents, we use a 1D linear interpolation (specifically scypi.interpolate.interp1d) to map from internal Elo to external Elo given the known [CCLR Blitz Elos](https://github.com/official-stockfish/Stockfish/commit/a08b8d4) of the common instances of Stockfish in both pools.\n3. Our preliminary results suggest that limiting MAV to predict only the best move at inference time doesn’t significantly affect its strength. However, training the model to evaluate multiple moves seems to be critical for strength in light of the results from [Ruoss et al. 2024](https://proceedings.neurips.cc/paper_files/paper/2024/file/78f0db30c39c850de728c769f42fc903-Paper-Conference.pdf) and for being able to use the model for external and internal search.\n4. Regarding fine-tuning an LLM (already pre-trained on other tasks) on board game data to enhance its overall reasoning capabilities: This is a very interesting question and sounds like a plausible hypothesis. However, the volume of data required to make the MAV models play at a really high level likely exceeds the volumes traditionally used in fine-tuning stages by a fair margin. So, if the goal is to retain strong playing strength in such models, this would impose some additional restrictions. Nevertheless, recent evidence from other studies, e.g., [Muennighoff et al. 2025, s1: Simple test-time scaling](https://arxiv.org/abs/2501.19393), indicates that it may be possible to unlock the reasoning capabilities from pre-training by a fairly small amount of data, opening up new possibilities. Whether it is possible to do this in this case (by e.g. pre-training on some subset of games and then generalizing to a broader set through a smaller number of examples, or broader capabilities beyond board games) is an interesting question that would hopefully be explored in more depth in future work.", "claims_and_evidence": "The claims are largely supported by clear quantitative results.", "methods_and_evaluation_criteria": "Methods:\nThe paper proposed three approaches to enhance LLM planning capabilities and \n\nEvaluation: \nFor Table 1: It would be beneficial for the authors to clarify the distinction between Internal Elo and External Elo. The current description suggests that External Elo is aligned with human performance, while a brief note that Internal Elo reflects performance among agents would enhance clarity.  \nIt would also be interesting to examine the external Elo ratings for games beyond chess to assess how training primarily on one game generalizes to others.", "theoretical_claims": "The discussion is mostly empirical, and while there is a theoretical underpinning (such as mapping centipawn evaluations to win probabilities), no rigorous proofs were provided or checked.", "experimental_designs_or_analyses": "The experimental design is clear, effectively demonstrating the improvements contributed by each component and providing thorough comparisons with the existing engine. Additionally, it includes a detailed error analysis covering precision, recall, legality, and gameplay aspects", "relation_to_broader_scientific_literature": "The paper builds upon and extends recent work on:\n\n1) MCTS and AlphaZero/MuZero paradigms for game playing.\n2) Internal planning methods such as Chain-of-Thought and Tree-of-Thought approaches.", "essential_references_not_discussed": "The authors have clearly listed related works and the corresponding contributions.", "other_strengths_and_weaknesses": "Strengths:\n- Innovative Framework: The paper offers a novel exploration by integrating external and internal search strategies within a single model framework.\n- Advanced planning: It convincingly demonstrates how LLMs can be enhanced to plan and reason through complex, sequential decision-making tasks.\n- Comprehensive Evaluation: The experimental evaluation is thorough, clearly showcasing the impact of each contribution.\n\n\nMinor Weakness:\n- the MAV model appears to lack essential language capabilities. It would be beneficial to see if the LLM could provide textual reasoning for its solutions or incorporate additional communication functionalities typical of large language models.\n- Providing detailed information on the training costs for pretraining the MAV model and executing the internal search distillation process would offer valuable insights into the resource requirements of this approach, particularly when compared to other methods that enhance reasoning and planning.", "other_comments_or_suggestions": "line 363: and terminal states,. -> remove the extra comma", "questions_for_authors": "1) Could you elaborate on the computational trade-offs between external and internal search methods, specifically regarding training cost and inference latency?\n\n2) How do you calibrate Internal Elo ratings relative to External Elo ratings, given that the latter are anchored to the CCLR Blitz ratings?\n\n3) How would the MAV model’s performance be affected if it were limited to predicting only the best move? Would it still function effectively as a chess world model? If not, which aspects of its chess world modeling capabilities would be compromised, and to what extent?\n\n4) Do you believe that fine-tuning a language model (already pre-trained on other tasks) on chess or other board game data could enhance its overall reasoning capabilities?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6wPjzITn79", "reviewer": "Reviewer_a6GX", "summary": "This paper enhances LLM planning capabilities in board games through two approaches: external search (model-guided MCTS without game engines) and internal search (in-context linearized search trees). Using a pre-trained Multi-Action-Value (MAV) model for Chess, Chess960, Connect Four, and Hex, both approaches significantly improve playing strength, with external search achieving Grandmaster-level chess performance using human-comparable search budgets.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to carefully review our paper and for the positive feedback!\n\n> The internal search performance remains inferior to external search\n\nWe evaluated internal search only up to breadth=4, depth=2, resulting in a search budget of 21 nodes, whereas external search was evaluated using a search budget of 100 to 2000 nodes. Moreover, the underlying search algorithms are different (minimax and MCTS, respectively). Therefore, the performance gains are not directly comparable. The main bottleneck for scaling up internal search to larger search budgets is scaling up the context length and the inference latency increase that this would entail. Nevertheless, even while being more challenging to scale up to large search budgets, we believe that our results provide interesting insights into the internal search capabilities of LLMs.\n\n1. The current advantages of external search are that (i) it is (depending on the exact search method and its implementation) potentially more easily parallelizable, whereas the internal search constructs the tree sequentially, and requires some extra tokens to capture the tree structure and the decisions pertaining to its expansion, (ii) the number of FLOPS required for internal search grows quadratically with the number of positions evaluated due to the quadratic cost of attention in transformer models, whereas it grows linearly for external search. Yet, this strength may also (contextually) be a weakness given that running the external search requires numerous LLM calls, whereas the invocation of internal search requires a single call, which may be advantageous when/if bottlenecked by the query volume, and potential delays in query completion.\n2. We haven’t explored hybrid approaches yet, but that is a really interesting suggestion! A hybrid approach may be able to benefit from a degree of parallelism that is possible to achieve through the external controller, and yet expand sub-trees (rather than single moves) in different branches via internal search when that is potentially useful. It is an open question how best to combine the two, though hybrid approaches (of a slightly different nature) have been successfully utilized in chess engines previously, when it comes to different ways in which neural networks can be incorporated, given that certain positions may require either deep tactical calculations (big trees) or intricate strategic play (shallow trees, but harder/higher quality policies and evaluation).\n3. Since the performance of the MAV model is capped by the performance of the game engine used to train it, the current approach depends on the ability to obtain or generate high-quality game-play data for the model to train on. There are many games where this is possible/easy to achieve. For other games, one can use techniques such as self-play as was done in AlphaZero.\n4. For chess and chess960, the models are somewhat susceptible to drawing a winning game via the 50-move rule or 3-fold repetition. Enforcing these rules requires storing history (or additional variables), which MAV doesn’t do. This happens in particular with the internal search model, which wasn’t trained to predict the quickest win, while in the external search, it can be enforced. Speaking more broadly, these rules are imposed by the external governing bodies (such as international or national chess federations), and under some regulations, 75-move and 5-fold repetition are used. Given this ambiguity, it might be difficult for models trained in a supervised fashion to recognize the pattern even if history was enabled. Additionally, the MAV model is more likely to misevaluate a move, since it does not perform search.\n5. There is a straightforward (but nontrivial) way to extend these methods to imperfect information games using Information-State Monte Carlo Tree Search ([IS-MCTS, Cowling et al. 2012](https://eprints.whiterose.ac.uk/75048/1/CowlingPowleyWhitehouse2012.pdf)). The value functions would be with respect to ground states (where all the information is revealed), and MAV would be trained in the same way as chess. The model would need to be augmented with an additional generative output that could sample a ground state given the current observation (excluding the hidden information), encoding a distribution that is learnable from data. The search would then start by first sampling possible world states from the generator, and run simulations as is currently done, starting from each one, but then aggregate statistics over information states, similar to the application of IS-MCTS with generative networks in [Li et al. 2023](https://arxiv.org/abs/2302.00797).", "claims_and_evidence": "The performance claims are well-supported by comprehensive empirical evidence showing increasing Elo ratings with larger search budgets. Tournament results against Stockfish at various strengths provide credible evidence for the Grandmaster-level performance claim, with appropriate calibration between internal and external Elo ratings.", "methods_and_evaluation_criteria": "The methodology is appropriate and comprehensive.", "theoretical_claims": "The paper doesn't make substantial theoretical claims requiring formal proofs.", "experimental_designs_or_analyses": "The tournament methodology using random pairings is sound with sufficient sample sizes. Analysis of model capabilities on both in-distribution and out-of-distribution positions demonstrates robustness. The experiments show a clear relationship between computational resources and performance.", "relation_to_broader_scientific_literature": "See above.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n\nThe paper presents a unified approach that integrates world modeling, policy, and value prediction in a single model, streamlining what previously required separate components. Its implementation of state tracking without external game engines enables self-contained operation, representing a significant advancement in model independence. The methodology demonstrates successful generalization across multiple diverse board games, suggesting broad applicability of the core techniques. The achievement of Grandmaster-level chess performance with human-comparable search budgets marks an important milestone in LLM reasoning capabilities. The innovative linearization technique for search trees enables effective in-context planning, creating a pathway for self-contained reasoning in language models.\n\nWeakness:\n\nThe internal search performance remains inferior to external search, indicating room for further refinement. What's the bottleneck here?\n\nMeanwhile, the paper provides insufficient analysis of computational efficiency between the approaches, making it difficult to assess practical trade-offs for real-world applications.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. How does the computational efficiency of internal vs. external search compare? At what point (if any) does internal search become more efficient?\n\n2. Have you explored hybrid approaches combining both search methods?\n\n3. How dependent is the approach on high-quality annotated game data? Do you have some intuitive explanations?\n\n4. What are the primary failure modes of each approach?\n\n5. A side question is that what modifications would be needed to extend this to imperfect information games?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4vmUQqvLYP", "reviewer": "Reviewer_2VtU", "summary": "- This paper focuses on game playing for board games with LLMs\n\t- it compares external search, where model acts as a proposal function for a symbolic search algorithm, with internal search, where the model is trained on search trajectories to perform search itself\n- The paper claims three contributions\n\t- Multi action-value model, which can be used to score action-value pairs\n\t- External search, where the MAV is used with MCTS to guide search\n\t- Internal search, where the search procedure is used to generate trajectories that are then used to train a model to directly do search itself.\n- Models are evaluated across different board games, including Chess, variants of chess, Connect Four, and Hex)\n- MAV is trained on text representations of the game whih include the game being played and the input state/legal output space \n\t- MAV models are trained from scratch on a custom text representation\n- MAV is integrated into an MCTS solver for external search\n\t- MAV is used to predict state transitions and actions during the rollout phase\n\n- MAV is also trained with additional search information in the prompt on search traces from symbolics solvers to internalize search\n- MAV models are compared agaisnt numerous chess-playing baselines, achieving competitive ELO. \n\t- MAV-MCTS consistently performs better than MAV alone, and larger models perform better.\n\t- External MCTS improves with more simulations\n\t- The internal search MAV improves with increased search budget, scaling w.r.t. number of tokens.\n\n## update after rebuttal\nThe rebuttal has addressed my remaining questions, and I will maintain my score of 5.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to carefully review our paper and for the positive feedback!\n\nWe have not tried self-consistency since we currently use greedy decoding, which we found to improve the strength of the MAV models compared to sampling. However, sampling multiple outputs from the internal search model and using self-consistency is a very promising idea for further improving the model strength! One piece of evidence that this approach would work is the performance of MAV with mean scoring, which outperforms MAV with greedy decoding, and can be viewed as a form of weighted voting.", "claims_and_evidence": "- The claims are generally supported by results:\n\t- MAV models combined with symbolic search perform better than a variety of baselines across multiple games \n\t- MAV can be trained to internalize search", "methods_and_evaluation_criteria": "- The method is described clearly and Fig 1 is helpful in showing the input/output format. \n- The evaluation criteria seem robust and the method is evaluated on multiple games.No theoretical claims made.", "theoretical_claims": "No theoretical claims made.", "experimental_designs_or_analyses": "The experimental designs are sensible and the token scaling analysis supports the results well.", "relation_to_broader_scientific_literature": "The paper is positioned well w.r.t. prior work on learning to search/game playing. The related work section is in the appendix but I think this decision makes sense as it is quite extensive.", "essential_references_not_discussed": "Paper covers essential references", "other_strengths_and_weaknesses": "- Strengths:\n\t- By including the state representation and action in the output space, MAV can act not only as a kind of Q value function but also as a world model and policy. \n\n- Weaknesses:\n\t- It's not clear what the relative gains for Connect Four and Hex are, since there are no baselines there. \n\t- MAV training requires access to a large amount of training data; it's not clear how it would generalize to real-world domains where there is no simulator/game engine. This is mentioned in the limitations. \n\t- Values are discretized; it would be nice to see how sensitive the method is to the number of bins here.\n\t- The MCTS rollout requires a parser that can verify/parse illegal actions, which reduces hallucination. It's also not clear here how one would implement this outside of a game environment with manually-defined rules.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "The current method outputs a state, top-5 actions etc. as a kind of CoT output. One of the big benefits of CoT is the ability to average/marginalize across reasoning paths, e.g. with self-consistency. Have you explored something like self-consistency on the best action prediction -- is this the same as just running more simulations?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces a new method, called MAV, which uses LLMs to play board games. The authors propose two methods, an external search, which uses LLM as a policy and value function within MCTS, and an internal search, where the LLM search itself. The results show that the proposed method, especially the external search, achieves significant improvements.

All reviewers unanimously recommend acceptance. The method is novel, and empirical results are strong. Compared to previous game-specific algorithms, the proposed method achieves high performance within a lower computational budget, bringing a significant impact in combining game-specific approaches with LLM. One weakness is that the experiments are limited to board games, so it remains unclear whether this method can be generalized to other games (like video games) or other applications. Nevertheless, the overall strengths of the paper outweigh its weaknesses, I therefore recommend acceptance.
Decision: Accept (spotlight poster)