Strategist: Self-improvement of LLM Decision Making via Bi-Level Tree Search
Authors: Jonathan Light
Min Cai
Weiqin Chen
Guanzhi Wang
Xiusi Chen
Wei Cheng
Yisong Yue
Ziniu Hu
Venue: ICLR 2025 Poster (2025)
Keywords: LLMs
games
search
self-improvement
self-play
RL
agent
multi-agent
planning
decision-making
Monte Carlo Tree Search
hierarchical learning
strategy optimization
reinforcement learning
game AI
strategic reasoning
population-based training
adversarial learning
policy refinement
social deduction games
partially observable environments
heuristic learning
evolutionary strategies.
Primary area: foundation or frontier models, including LLMs
TL;DR: We introduce STRATEGIST, a bi-level framework that enables LLMs to self-improve decision-making in multi-agent games by iteratively refining high-level strategies through self-play and optimizing execution with Monte Carlo Tree Search (MCTS).

Abstract: Traditional reinforcement learning and planning require a lot of data and training to develop effective strategies. On the other hand, large language models (LLMs) can generalize well and perform tasks without prior training but struggle with complex planning and decision-making. We introduce **STRATEGIST**, a new approach that combines the strengths of both methods. It uses LLMs to generate and update high-level strategies in text form, while a Monte Carlo Tree Search (MCTS) algorithm refines and executes them. STRATEGIST is a general framework that optimizes strategies through self-play simulations without requiring any training data. We test STRATEGIST in competitive, multi-turn games with partial information, such as **Game of Pure Strategy (GOPS)** and **The Resistance: Avalon**, a multi-agent hidden-identity discussion game. Our results show that STRATEGIST-based agents outperform traditional reinforcement learning models, other LLM-based methods, and existing LLM agents while achieving performance levels comparable to human players.

Published as a conference paper at ICLR 2025
STRATEGIST: SELF-IMPROVEMENT OF LLM DECISION MAKING VIA BI-LEVEL TREE SEARCH
Jonathan Light' Min Cai Weiqin Chen' Guanzhi Wang Wei Cheng' Yisong Yue Ziniu Hu
Xiusi Chen?
Rensselaer Polytechnic Institute, Shenzhen University, University of California, Los Angeles, *NEC laboratories America, Caliioomia Institute of Technology
ht https: //t::/11mmm strategist. github.io
ABSTRACT
Traditional reinforcement learning and planning typically requires vast amounts data and training to develop effective policies. In contrast, large language mod- els (LLMs) exhibit strong generalization and zero-shot capabilities, but struggle with tasks that require detailed planning and decision-man makinng in complex action spaces. We introduce STRATEGIST, novel approach that integrates the strengths both methods. Our approach leverages LLMs to search and update high-level strategies (as text), which then refined and executed by low-level Monte Carlo Tree Search (MCTS). STRATEGIST is generalizable framework to optimize the strategy through population- baseid self-play simulations without the need for any training data. We demonstrate the effectiveness of STRATEGIST in learning optimal strategies for competitive, multi-tum games with partial information, including Game of Pure Strategy (GOPS) and multi-agent, hidden-identity discussion games like The Resistance: Avalon. Our results show that agents equipped with STRATE- GIST outperform those trained with traditional RL methods, other LLM-based skill acquisition techniques, pre-existing LLM agents across both game environments and achieves comparable performance against human players.
INTRODUCTION
Recent studies have shown the potential of Large Language Models (LLMs) for learning skills and improving bocisionnmmakin in interactive environments Wang et al. (2022; 2023a; 2024); Xi et al. (2023); Zhao et al. (2024); Liu et al. (2023). However, adversarial, multi-agent envi- ronments present significant challenge. LLMs must reason about opponent actions, plan ahead strategically, and navigate vast policy space Kambhampati et al. (2024); Valmeekam et al. (2023); Kambhampati (2024). This complex- ity hinders the LLM's ability to identify, under- stand, and translate optimal policies into effec- tive actions. Simply generating decision rules by querying the LLM proves inefficient and im- practical in such settings. This raises two critical questions: (1) How can LLMs effectively learn complex policies in adversarial multi-agent en- vironments? (2) What is the best approach to improve these policies?
Agent
High level strategy abstraction
Environment feedbock
Real environment
Blokggg
8
Idee A
Uee
OR
iLM-veed strategy
Population based self-play
Low level policy
VS
Refined policy
Figure 1: Overview of STRATEGIST. We use an LLM to generate and improve high-level strategy abstractions using environment feedback, then re- fine strategy into policy using tree search or CoT.
This paper introduces STRATEGIST, a novel framework that leverages LLMs to develop high- level strategies, represented as interpretable text, which are then refined and translated into executable policies using low-level executor (Figure 1). Our approach combines LLM self-immprvemment with a hierarchical search process, operating on both level strategy space and low-level action space.

---

Published as a conference paper at ICLR 2025
At the high level, STRATEGIST constructs strategy tree through evolutionary process, iteratively testing and improving strategies via LLM-guided revisions based on self-play feedback. This process fosters the emergence of robust, adaptable strategies. To further enhance strategy improvement, maintain a queue of "improvement ideas" sampled via a bandit algorithm to guide L.MM revisions. At the low level, employ fine-grained tree search techniques (e.g., MCTS) guided by the high-level strategy to refine the agent's 's policy. We can run the policy against itself through self-play in the multi- agent strategic game, and use win-rate as final outcome reward. The reward can be backpropagated to help update the strategy. This bi-level approach effectively integrates the generalization capabilitiess of LLMs with the precise planning of MCTS. Both levels are updated through simulated self-play, eliminating the need for extensive training data.
We demonstrate the effectiveness of STRATEGIST in two challenging games: the Game of Pure Strategy (GOPS) and Resistance: Avalon (Ross, 1971; Light et al., 2023), chosen for their strategic complexity and differing levels of natural language interaction. Our results show that STR ATEGIST outperforms existing LLM-based self-improvement methods and traditional RL approaches, achieving superior performance within the same computational and data budget. Furthermore, we highlight the successful integration of feedback across the different levels of our framework, demonstrating the synergistic interplay between high-level strategy improvement and low-level policy refinement. Moreover, STRATEGIST matches human performance in Avalon while employing more sophisticated mixed strategy and strategic randomization to deceive others and conceal its identity.
To summarize, our main contributions are:
We propose STRATEGIST, a general non- -an-paraeetric bilevel skill-learnigg framework that uses LLMs to learn high-level strategy abstractions, refined into low-level policies by a modular executor. These abstractions can define strategic profiles for all players in the game.
We introduce modular improvement method for high-level strategies using population- based self-play without training data, demonstrating superior performance over existing LLM- --adedded skill learning methods.
We apply STRATEGIST to GOPS and Avalon, demonstrating its effectiveness in learning policies for both dialogue and non-dialogue actions, achieving higher win rates than both existing agents and human players. Examples of learned strategies are provided in H.3 and I.3.
2
METHODOLOGY
2.1 DECISION MAKING SETTING AND GAMES
The general goal in our decision-making setting is to learn a good policy function in a sequential decision-making setting (generally formulated as partially observable Markov decision game (POMDG)). Our strategy-learninn framework is generalizable to any decision making setting.
Problem definition. Given state space S and action space A, policy function & in policy space &b is a mapping o : S - AA where we allow & to output probability distribution over the actions AA. An environment = A, T, R, A, (.) defines the state space S, the action space A, set of actors N. transition function T: S x A - S, reward function R S x A + R WM that specifies intermediate rewards for each actor, an action function A S + N, P(AA) that specifies which actor may take what legal actions some state where P is power set, and é.. the policy function for the environment actor. Note that transitions are deterministic in our notation, and stochastic transitions are handled by the environment actor e E N instead, so we cover stochastic, deterministic, multi-agent, and single agent cases. For a partial information setting, we also have a space of information sets I and function H: : x N + I that maps from hidden states and actors to hidden information sets. Hence, é I + A.A is function from information sets to action distributions instead. A strategic profile c = [o>]|NN] describes the policies for every player E N,
Let f Σ + & be the function that maps strategies to policies. A high-level strategy E Σ helps parameterize policies so that we can search over the lower dimension Σ space instead of $. Let + $_, denote the space of possible opponent policies, where -i are the indices of players other than i. Then our goal is to find the optimal strategy of that approximates finding the optimal policy given the policies of the other agents Φ_ i.c.
argmax 9
E T=((oo)))1))
Σ R((s,a) ~ argmax E (s,a)er
Σ (((s (s,a)rr
2

---

Published as a conference paper at ICLR 2025
where (so, au, ...) is the simulated trajectory according to the strategic profile (øi, Φ-1) and the transition function T, with a, ~ ((ar(st) and $1+1 = (s,, az). Thus, a key part of these settings involves learning the probable strategic profile of other players, usually by assuming that they play optimally like in a Nash equilibrium (Perolat et al., 2022).
The state space, action space, and actor space are different depending the setting. In non-stochastic, single agent settings such as question answering (Yang et al., 2018; Wang et al., 2022; Shridhar et al., 2020; Thome al., 2018), . =00.. In stochastic single agent settings such as web browsing (Yao et al., 2022a; Deng et al., 2024; Zhou et al., 2023), NN {e, 0} where we add an environment agent e. We specifically focus on adversarial. multi-agent stochastic game (N fe, 0, 1..))) settings where the other agents are actively working against each other. In non-dialogue-bee GOPS (see B for rules) for example, S consists of the cards played so far, /V {e, 1} for players and 2 respectively, and A consists of the cards you can play. In dialogue-based games such as Avalon (see for rules), A consists of both the discrete actions (moves) such as voting, and language actions which consist of text. Similarly, S consists of both the historical moves and historical dialogue record, and W = {e, 0, }... depending on the number of players involved, with [ 2
card games such as
2.2 ABSTRACTING HIGH LEVEL STRATEGIES AS PROCESSES
key part of our framework abstracts key features of the policy Φ, representing them as a high-level strategy which is more suitable for LLM-driven improvement. a is then executed and refined by low-level executor, often during inference, resulting in the execution policy do.
feedback from environment + LLM- Improver + a + Executor(c) + do
Abstraction offers two key benefits: (1) High-level strategies provide more abstract, compressed, and intuitive representation of the problem, which the LLM better understands, enabling its generalization and reasoning capabilities. (2) Searching over high-level strategies is more efficient than low-level policy exploration, as it simplifies the search space by focusing on core principles rather than fine details. This approach guides the search toward promising areas more quickly, leveraging domain knowledge, patterns, or heuristics that generalize across scenarios.
For non-dialogue actions, while the action spaces A and state spaces S are typically discrete and finite, the number of possible functions mapping state to action is vast. Most LLM-agents query the L.M directly with state information to decide the next action in decision-making environments (Yao et al., 2023; Shinn et al., 2024; Zhao et al., 2024). However, this is costly because the LLM must be queried for every move, and in Avalon, each player makes at least 20 moves. This becomes even more expensive when incorporating look-ahead search, which requires querying the LLM for future actions and states. Traditionally, space by parameterizing the policy and optimizing these parameters, reducing the search space.
reinforcement learning addresses the large policy
We abstract and "parameterize" the policy é as value heuristic (VH) a == : S + RMM that estimates the expected cumulative returns for each player at given state, typically the expected probability of winning for each player. Using a value heuristic simplifies reasoning, as it's casier to describe how good a state is than to specify the optimal action. This makes intuitive for the LLM to reason about winning probabilities. Additionally, we represent the value heuristic as Python code, allowing the LLM to easily process and modify the logic for computing the value for each state.
Example LLM Generated Value Heuristic Function
def evaluate wwaaluteesttteeeeee (eate(etate):
Calcullainng the pacentiaal scorea for each player
playez_0 0 potenttnil scoze sunfetateepll Stwpsteepppyye_____ (anan))
playez L www.ectetlllaaaecc score sum(state sumsstate.player_ Lann))
calculating the potentiaa final acores for each player
player 0 Lacoe acove player soore player Lal_sotall_oore playe= Linallii___aaa_a scoze p playez 1 pecentiell_coe soore
Storing the intemediate values used to caleulate the scores Intermeiiata va les
"player_0 potettii ial score' player_ palpoentiall pal
potential
recurn player_scores, Interedistt values
At the low-level, we execute the strategy (value function) by selecting the action that leads to
the best state: (b))s) argmax Q(s,a) argmax Ri(s, a) + (x()')ss' as) Since
3

---

Published as a conference paper at ICLR 2025
we learn the value for each actor, value function into a strategic profile Φ. Since value heuristics can be inaccurate, we can refine the policy using search such as MCTS to look ahead through multiple action-state sequences. resulting in a better policy (Grill et al., 2020; Silver et al., 2017; Schrittwieser et al., 2020). MCTS also generates additional feedback by comparing the updated value estimate from MCTS with the initial value heuristic. The estimated win-rate from search provides a shaped reward signal, which is more informative than the simple win/lose outcome reward. We focus on key states with the largest discrepancy between the MCTS estimate and the episode outcome for self-improvemenn feedback. More details on our MCTS implementation are in Appendix F.
compute the best action for each actor i, refining the
Dialogue generation poses a unique challenge for self- improvemeen Both the action space A, representing possible word sequences for each discussion round, and the state space S, representing prior input dialogues, are enormous. As result, the number of possible dialogue generation policies vast, making traditional parameter training approaches difficult to optimize. To address this, we develop a high-level strategy guide that the agent processes before speaking. This guide formalizes a chain-of- -fthughht process to analyze the situation before generating dialogue (Wei et al., 2022b). It is implemented as a question-and and-answer worksheet, where the agent answers all questions in the guide before using it as a prompt for dialogue generation.
Example (fully generated) Chain of Thought Dialogue Strategy Guide
Q1: Who are the players you suspect are the Evil side and why?
A1: I suspect Player 2 and Player 4 are the Evil side. Player 2's suggestion for the team consisting of themselves and Player seems too convenient, as would allow Evil easily fail the quest. Player 4's agreement with Player 1 and Player 2's proposed team without offering any alternative suggestions raises suspicion.
Q2: Draft subtle statement that casts doubt on these players without directly accusing them. A2: "I can't help but wonder some players are pushing for certain team compositions to benefit themselves rather than considering what is truly best for the success of our Quest."
Generated dialogue: "I have observed patterns in the voting that suggest certain players may be working together to push specific team compositions. This raises suspicion and calls into question their true intentions. We must not allow ourselves to be swayed by potentially deccitful tactics."
2.3
MODULAR SEARCH FOR HIGH-LEVEL STRATEGY IMPROVEMENT
High-level strategy improvement
Reflection and ideo generation
Strategy Library
Strotogy improvement step lines
Key states simulated trajectory
coach. Previously you Implament this limprovement idea) into the strllery best as you
Sample stategy and ideo
State: Plyaes hune wis firmnsss hiivey is fox and theo the Jockas lilory
Sample strotegy feedbock
Mau
Ide2
Action The stuclet rod (pecarzted didogee!
Stolagy
Ststegy 8
LLM
Outcernn Good
was
Intermediate valums: mnsiett thought
Search estimatts 32% wivore Good
idee
Idea
Beeeeem Shrngg
Example strategy
chould occure player
Stotegy AA
Shotegy
la the lase you andarto team fhat leader nugportdd
Translate to natural longunge
Idea Queue
player you
You coach. Previously
Inpreeement
[arategy]] which produced these [ittemediate values) ot this [siate]. Search suggests that the valu of (stmt) is (search astincte), while this is the (Rnel outcomee. What conclssion can you draw, what ways
this
Improvement idea B:
Fagure out wil player mott supporting
Update score
poahon frs
Evaluator
Seore: 2.2-0 -0 31
Number of Impleseentations:
Idwas Score priors
VS
improve
feedbock
Adapfive Been/Bnndt
Salfplay simulations MCTS
LLM
Sampling Policy
Figure 2: Overview of our high-level strategy improvement method:
The process alternates between two steps steps-idea idea generation and strategy improvement. For more details see Figure 11.
4

---

Published as a conference paper at ICLR 2025
Our framework alternates between two steps: idea generation and strategy improvement, as shown in Figure 2 and detailed in App. D. Each cycle refines strategies stored in a tree structure based on feedback from self-play simulations and generates new improvement ideas stored in priority queue.
2.3.1 IDEA GENERATION
In the idea generation step, a strategy a and its feedback trajectory Ta are selected from the strategy tree using an adaptive selection policy (c.g., UCB or BFS). Feedback consists of trajectories from previous self-play simulations, including visited states, actions taken, estimated win rates, final outcomes, and intermediate values. To avoid processing lengthy trajectories, we select key states that best capture discrepancies between the strategy's 's value heuristic and search-based estimates.
These key states are translated into natural language and used to prompt the LLM for new improvement ideas. The ideas are added to the idea queue with prior score estimating their potential effectiveness: strategy, strategy feedback)
Idea-queue LLM- iell-idea--ie iereeee-iiieettorSaaaaaeee
2.3.2 STRATEGY IMPROVEMENT
In the strategy improvement step, we sample a strategy a from the strategy tree and an idea from the queue, using method that balances exploration and exploitation (c.g., UCB). The LLM refines a using d, generating a new strategy One- This new strategy is evaluated via self-play simulations, which produce win rates [[o] and trajectory feedback T(o].
During simulations, players conduct MCTS tree searches to estimate win rates at different states, providing additional feedback. The strategy tree is updated with the new strategy and its performance:
strategy-11 aibrrryrrr.rrr + LLM-revi ser (Sampled idea, sampled prior strategy) The improvement score of the idea d is updated based on how much it improved a.
2.3.3 SEARCH MODULARIZATION
key feature of our framework is the use of an idea queue to modularize the search process. By refining strategies incrementally rather than globally, we avoid confounding factors and ensure interpretability of changes. The queue also tracks successful improvements that are generalizable across strategies, enabling transfer and reuse of ideas. Improvements are often additive (e.g., penalties or adjustments) and enhance performance when applied to similar strategies (Table 2).
We use UCB sampling to balance exploration of new ideas and exploitation of proven ones:
I Niota)
UCB((dea) = Zidea + eV
Nitea
where Z is the empirical average improvement score, Neoual is the total number of ideas implemented, and Nidea is the number of implementations of the specific idea.
To simplify the improvement process, we optimize dialogue generation and gameplay moves sepa- rately in Avalon before integrating them into unified agent (Appendix E). This modular approach mirrors strategies used in related domains, such as Diplomacy (FAIR).
2.4 POPULATION BASED SELF-PLAY SIMULATION
Recent works focus on using either another LLM for critique-based feedback (Madaan al., 2024; Shinn et al., 2024), real environment interactions (Nottingham et al., 2024), or a combination of both (Wang et al., 2023a) during the LLMMimprovement process. Our method improves on this by simulating opponents using the learned high-level strategy, enabling higher-quality feedback. Since our high-level strategies can be refined into policy for any player, we can easily pit different strategies against each other by refining them into specific policies for different players. Specifically, we use population based self-play, where we conduct round-robin games among the top ten strategies generated and use the average performance the strategy score for each strategy (Xu al., 2023b). During round-robin games, strategies are given the same level of low-level refinement to ensure faireess. This evolutionary approach makes the final improved strategy more robust to different opponent policies, since it will have survived multiple round-robin tournaments. We demonstrate the effectiveness of this method in section 3.5.
5

---

Published as a conference paper at ICLR 2025
3 EXPERIMENTS
We evaluate the effectiveness of our bi-level framework through four key experiments: demonstrating STRATEGIST's competitiveness with human players, its superiority over RL-based deep learning methods, its advantage over LLM-based agents, and the effectiveness of our LLM-imen I.M-improvement method compared other techniques. Our approach tested on two games with distinct challenges. Game of Pure Strategy (GOPS) is two-player, zero-sum card game requiring strategic decisions under partial information and simultancous moves (see B) (Ross, 1971; Lanctot et al., 2009). The Resistance: Avalon is mullti-agent (5+ players), team-based game combining language. deception, and deduction (see A) (Light et al., 2023). These games highlight STRATE STRATEGIST's versatility in handling strategic and social complexities.
Voting action distribution
% Correct vote Correct
Approve
Reject
Incorrect
Human
52.7%
37.05
71.0%
Strategist
6.55
35
122%
As Merlin
As Servant
As Evil
As Merlin
As Servant
Figure Action analysis of STRATEGIST and humans when playing against each other in Avalon. STRATEGIST conducts more strategic randomization than humans, making its identity harder deduce based on actions.
3.1 HUMAN EVALUATIONS
Persuasiveness
We conducted human experiments in the six- player Avalon setting, using the following char- acter roles: Merlin, 3 Servants of Arthur, As- sassin, and Minion of Mordred. Ten partici- pants were recruited and randomly assigned to one of the roles, playing against five STRATE- GIST agents. In total, 30 games were collected and analyzed. As presented in Table 1, STRATE- GIST achieved win rate comparable to human players. After each session, participants com- pleted survey evaluating the performance of StrateGIsT across seven key metries. while an experimenter independently assessed human performance. The survey results are visualized in Figure 4, revealing that STRATEGIST outper- formed humans in concealment and adaptability human playstyles, but lagged behind in rea- soning, deduction, and cooperation.
Merlin Conceala billy
Adaptabillty
1
Cooperation
Rcasoning
Evil Concealability
Evil Dete ction
Human
Stratagist
Figure 4: Human vs STRATEGIST performance metrics Avalon. We ask humans to evaluate the performance of STRATEGIST and human players in ad-hoc human-Al games. STRATEGIST performs better than humans at concealment, but worse at reasoning and cooperation.
Additionally, we conducted action analysis to compare the behavior of STRATEGIST and human players, shown Figure 3. Specifically, we examined the distribution of approval votes pivotal action in Avalon. The data revealed that human players exhibited distinct voting patterns based on their roles, facilitating the deduction of their identities. In contrast, STRATEGIST demonstrated strategic randomization, producing more uniform action distributions across roles and thereby making its identity harder to infer. More details on human evaluations can be found in Appendix O.

---

Published as a conference paper at ICLR 2025
Table Comparison of different self-improvement methods. The improvement process was run with the same number of strategies generated for each method (40 for GOPS, 24 for Avalon) on the same seed functions, all with GPT3.5. We collect 9 functions from each process and play them against each other (a total of 5 x 9 = 40 different agents), reporting the average number of points you win over your opponents for GOPS and the average winrate for Avalon. For the dialogue guide, we show the improvement over the baseline seed function, which has score 0.875 É (-2, 2,, a rating from opponents which we describe in G.
Self-Improvement Methodology
Line search
Greedy search (Ma et al., 2023)
Best First Search (BFS) (Yao al., 2024)
BFS with thought
STRATEGIST
(Madaan al..
2024; Shinn et al., 2024)
GOPS Value Heuristic
-0.47 10.74
-0.54 +0.45
0.092 0..67
-0.4::10.375
1.5 +0.99
Avalon Value Hcuristic
0.54 #0.11
0.47 #0.11
0.50 +0.085
0.55 4:0065
0,59 =0.11
Mcrlin Dialogue Guide
0.37 0.19
0.62 + 0.13
0.49 0.063
0.37 0.06
0.88 00.063
Assassin Dialogue Guide
1.83 0.25
1.81 + 0.063
1.82 0.063
0.093
1.98 +0.042
We further analyzed the proportion of correct votes, defined as rejecting teams with at least one Evil player approving teams with only Good players. This metric indicates a player's s ability to infer Good and Evil identities, a skill particularly crucial for the Merlin role. As shown in Figure 3, STRATEGIST employed in- creased randomization as Merlin, minimizing information leakage through voting patterns. Conversely, human players displayed highly role-specific correctness trends. These findings align with survey feedback, corroborating that STRATEGIST excels in concealment strategies compared to human counterparts.
Strategist Playstyle
Human Playstyle
20.00
30.0%
40.0%
20.0%
20.0%
Logical
Deceptive
Aggressive
Cautious
Figure 5: Description of STRATEGIST play-style compared human players, as evaluated by hu- man participants. STRATEGIST is described as being more logical and cautious.
3.2 DIFFERENT LLM IMPROVEMENT METHODS
We demonstrate the effectiveness of our strat- egy improvement method by benchmarking it
Table 1: Results of STRATEGIST Human.
against four other skill-improvement methods. Line search (Madaan et al., 2024) always re- flects and improves upon the latest improved strategy. Greedy search (Ma et al., 2023) se- lects the best strategy from the last generation of improved strategies to improve upon each im-
Metric
Human
STRATEGIST
Win Rate
0.367
0.333
Standard Error
0.089
0.061
provement cycle. Best first search (Yao et al., 2024) improves upon the & best strategies generated in any iteration of each improvement cycle. Best first search with thought enhances BFS by prompting the LLM to reflect, think, and propose ideas how to improve the previous strategy before improving the strategy itself (Yao et al., 2022b). ATRGIITIS is our method that uses an additional idea queue Q and an idea generation step to guide the improvement process. Comparing BFS with thought and STRATEGIST helps demonstrate the value of having a modularized reflection and idea proposition process that separate from strategy generation. More details can be found in Appendix N.
Our results, presented in Table 2, use the same feedback method (simulation play) while varying the improvement methods, with constant number of new strategies generated across all methods. Figure 12 (right) shows the gameplay scores of these strategies on GOPS. Even when controlling for the number of output tokens generated by the LLM, our method outperforms the others, as demonstrated in Figure 18. We attribute this to (1) the idea queue, which helps test incremental improvements and guide the search process, and (2) our strategy and idea selection policy, which more efficiently explores the strategy space and escapes local maxima (Figure 12 left).
population self-
3.3 INTERACTION BETWEEN LOW-LEVEL REFINEMENT AND HIGH LEVEL STRATEGY SEARCH
7

---

Published as a conference paper at ICLR 2025
We demonstrate that both high-level strategy improvement and low-level refine- ment processes scale effectively with in- creased budgets by showing how differ- high-level strategies performance with varying MCTS search budgets. A higher search budget allows for more nodes be looked ahead before taking actions, resulting in more refined policy. As shown in Figure 6, strategies improved with more iterations using STGITT ex- hibit both higher performance and greater performance gains with increased refine- ment. Policy refinement also scales excep- tionally well.
Scaling greph Strategist
Scaling graph Strategist
Int Wi
1.8
cot-itaration VIi 20th tenatin
-3.
-1.0
Pont -1.
1.2
-5.5
-6.0
20 40
60
80
100 120 140 180 Budget
20
40
60
80 300
120 140 160 Budget
Figure 6: Performance of high level strategies on vary the level of low-level MCTS finement (MCTS search budget). Left: Scaling curve for initial unimproved LLM-generated value-heuristic. Right: Scaling curve for improved value-heuristic us- ing STRATEGIST after 20 and 40 iterations (steps) of eeff-improvement respectively. STRATEGIST improved value heuristics scale better with increased low-level refinement.
GOPS
3.4 LLM-MMPROVEMENT
Vs. REINFORCEMENT
LEARNING (RL) BASED METHODS
We demonstrate the effectiveness of method compared to traditional RL-based approaches for learning good policy. Specifically, we show that our method learns value heuristic function more effi- ciently than deep RI., used in AlphaGo, MuZero (Silver et al., 2017; Schrittwieser al., 2020), and DeepRole (Serrino et al., 2019). While AlphaGo uses MCTS (Koc- sis & Szepesvári, 2006) with deep value network, DeepRole combines counterfac- tual regret minimization with deep value network (Moravčík et al., 2017; Zinkevich et al., 2007). We adapt both algorithms to our setting.
0.40
Bonttii Difference
1.0
0.30
2.25
0.0
0:15
0.10
Strataprt
Alphazio
Stratngist
Desoitlle
Stratepi
Alplaco
Stranagist
Despitoie
Figure 7: Performance of different training methods against the baseline in Avalon and GOPS.
Although deep RI. approximate the true value function with enough data, training, and large network, we ensure a fair comparison by (1) limiting both RI methods and our approach to the same number of simulated episodes, and (2) capping the number of training steps after each batch of episode trajectory data. While both RL methods and STRATEGIST use the same number of self-play episodes, STRATEGIST only trains on a small subset of transition steps, whereas RL methods train on the entire dataset. Our results, shown in Table 3 and Figure 7, demonstrate that STRATEGIST consistently outperforms both AlphaGo and DeepRole, More details on our RL implementation and the effects of increased sample size can be found in Appendix L, where we observe performance improvements with additional samples.
Table 3: Comparison of reinforcement learning our method. We run each process 10 times, taking the best strategy generated by each run and playing them against each other for 1024 games. Average win-rates, total number of self-play episodes, and training transition steps across best. generated strategies are shown here.
Setting
Metric
VS Alpha-go
VS DeepRole
Alpha-go
STRATEGIST
DeepRole
STRATEGIST
Point difference Self-play eps.
-0.39 + 0.22
0.33 + 0.38
-0.56 + 0.18
1.14 + 0.09
GOPS
320 episodes
320 episodes
320 episodes
320 episodes
Trans. steps
3,840 steps
100 steps
3. 840 steps
100 steps
Winrate
0.30 0.03
0.38 0.04 160 episodes
0.33 0.04
0.44 0.02
Avalon
Self-play eps.
160 episodes
160 episodes
160 episodes
Trans. steps
24, 000 steps
60 steps
24, 000 steps
60 steps
8

---

Published as a conference paper at ICLR 2025
3.5 FEEDBACK QUALITY AND REWARD SIGNAL
We benchmark our feedback method (population based self-play) against (1) an LLM-critic (Madaan et al., 2024) and (2) trajectory feedback from fixed opponent policy, with results in Table showing superior performance in both GOPS action planning and dialogue generation. This shows the effectiveness of our evolutionary population based play approach, and that of our strategy abstraction that learns strategic profile for all players.
Table 4: Comparison of different methods of collecting feedback. All methods use the same high- level improvement process (STRATEGIST) For GOPS we collect 24 generated functions from each method and play them against each other. For Avalon we evaluate 9 generated guides. We simulated 32 games for GOPS and 4 rounds of discussion for Avalon to collect gameplay feedback during each improvement step, across 10 and 6 improvement rounds for GOPS and Avalon respectively.
Setting/Method
Metric
LLM-critic
Fixed opponent
Population- based Self-play
Point difference
-0.27 = 1.1
0.089 + 0.86
0.87
115
GOPS
# of opponents
0
4
Winrate
0.37 + 0.063
0.62 0.13
0.88
0.06
Avalon
# of opponents
0
4
3.6 STRATEGIST Vs. LLM AGENTS
We demonstrate that our method also achieves better performance against other LLM-agents. ReAct is a popular L.LM-agent that prompts the LLM to think before taking an action (Yao et al., 2022b). ReCon is LLM-agent for hidden identity games that prompts the LLM recursively contemplate on what opponents are thinking and might do before taking actions (Wang et al., 2023b). We adapt ReCon to our setting by asking the agent to recursively contemplate. Our gameplay results shown in Table 5. This suggests that through STRATEGIST, our LLM-agent is able to learn high-level strategies similar in performance to those of ReCon, such as recursive contemplation.
Table 5: Results of STRATEGIST playing against LLM--ased baselines, i.e., ReAct and ReCon.
VS ReAct
VS ReCon
Metric
ReAct
STRATEGIST
ReCon
STRATEGIST
Winrate
47.5 + 2.5 56 = 14.3
52.5 2.5
38.9 + 5.5
61.1 5.5
#Tokens per round
164.3 + 27.7
245.7 = 21.2
248.2 + 24.1
RELATED WORK
LLMs for Text Agents. Large language models (LLMs) demonstrate emergent capabilities such as zero-shot prompting, reasoning, and extensive world knowledge (Bommasani al., 2021; Brown et al., 2020; Wei et al., 2022a; Yu et al., 2023a). Recent frameworks like ReAct (Yao et al., 2023) and Reflexion (Shinn et al., 2024) have incorporated reasoning, memory, feedback, and tool use to improve Decision-making (Wang et al., 2023a; Huang et al., 2022; Schick et al., 2024). Prompting techniques like Chain-of-Thoon Thought and Tree-of- Thee-hf-Thought are effective for reasoning (Wei et al., 2022b; Yao et al., 2024) but fall short in complex games requiring iterative self-improvemennt. Our method, STRATEGIST, introduces a bi-level tree search combining high-level planning and self-play for feedback-driven strategy refinement.
Skill Learning with LLMs. LLMs have been used to acquire skills by learning textual memories or insights (Shinn et al., 2024; Zhao al., 2024). However, textual approaches struggle with long, quantitative trajectories. We focus on high-level strategies optimized through simulational self plaf, enabling robust skill learning in multi-agent environments. While reward models learned by LLMS

---

Published as a conference paper at ICLR 2025
excel in Bangleageen tasks (Ma et al., 2023; Yu al., 2023b), extend these ideas to multi-agent settings by introducing methods for feedback generation and strategy improvement.
Al in Strategy Games. Advances like AlphaGo and MuZero highlight the synergy of MCTS, deep learning, and self-play (Silver et al., 2017; Schrittwieser et al., 2020). LLMs have also been integrated into dialogue-based games such Diplomacy FAIR) and Texas Hold' em (Zhang al., 2024). Our approach bridges these domains by enabling LLMs to both train value heuristics more efficiently than RL and generate dialogue for social deduction games without human examples. Additionally, our method has potential applications in negotiation tasks (Abdelnabi et al., 2023; Fu et al., 2023).
LLM--geets for discussion games. There has been much recent interest in using LLMs develop agents for discussion-basee games, as these games provide an excellent benchmark for assessing the reasoning. planning, and strategic deception capabilities of LLMs. This includes Werewolf (Bailis et al., 2024; Xu et al., 2023b;a; Wu et al., 2024), another social deduction game, and other negotiation and word games (Fu et al., 2023; Cheng et al., 2024). We give a more detailed comparison of our work to other Al agents in Table 6 and App. P.
EnReaWoil
Cicero
Com Wolf
LARLWolf
SPAG
AlphaGo
ICL-AIF
Agent- Pro
ReCon
DeepRole
Strategist
Metric
Used in Avalon
X
X
X
Parameter-free
x
x
X
X
Uses LM
V
V
x
Self-improve
1
x
X
Tree Search
x
1
x
X
X
X
X
X
Human-annotation free
x
x
/
/
Belief updates
x
x
x
x
x
x
x
Bi-level improvement
x
x
x
x
x
x
x
x
x
x
Table Comparison of Strategist with Related Works. We use an bi-level improvement approach, paired with advanced high-level strategy learning process that is parameter free. Our approach handles beliefs and partial observability and uses low-level policy refinement (tree-search) to further enhance our policy. For details see App. P
CONCLUSION
In conclusion, have introduced STRATEGIST, bi-level framework that facilitates high-level abstract strategy learning with LLMs and generalizable non- parametric self-improvement mecha- nism. This approach enables the model learn and refine skills autonomously. Without relying on task-specific prompts or human- generated policy data, our method demonstrates its ability to learn effective strategies through population- based self self-play, guided solely by the rules of the game.
The performance of STRATEGIST highlights the potential of leveraging LLMs for generating high- level strategic abstractions, while using low-level tree search to iteratively refine the policy. This dual approach not only showcases the power of modular guidance-whether whether through high-level strategy exploration or low-level self-play feedhack-but also underlines the value of integrating these processes for accelcrated and robust skill acquisition in LLMs.
Furthermore, our results suggest broader implications for the development of LLM-driven decision- making agents across range of complex domains. By embedding flexible and adaptive learning mechanisms, our framework paves the way for more autonomous systems capable of mastering tasks with minimal human intervention. This opens new avenues for the application of LLMs in areas such as multi multi-agent agent systems, reinforcement learning, and general AI, where strategic planning and self-improvement are key.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Sahar Abdelnabi, Amr Gomaa, Sarath Sivaprasad, Lea Schönherr, and Mario Fritz. Lim-deliberation: Evaluating Ilms with interactive multi-agent negotiation games, arXiv preprint arXiv:2309.1723: 2023.
Suma Bailis, Jane Friedhoff, and Feiyang Chen. Werewolf arena: A case study in Ilm evaluation via social deduction, arXiv preprint urXiv:2407.139443 2024.
Rishi Bommasani, Drew A. Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S. Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, Erik Brynjolfsson, Shyamal Buch, Dallas Card, Rodrigo Castellon, Niladri Chatterji, Annie Chen, Kathleen Creel, Jared Quincy Davis, Dora Demszky, Chris Donahuc, Moussa Doumbouya, Esin Durmus, Stefano Ermon, John Etchemendy, Kawin Ethayarajh, Li Fei-Fei, Chelsea Finn, Trevor Gale, Lauren Gillespie, Karan Goel, Noah Goodman, Shelby Grossman, Neel Guha, Tatsunori Hashimoto, Peter Henderson, John Hewitt, Daniel E. Ho, Jenny Hong. Kyle Hsu, Jing Huang, Thomas Icard, Saahil Jain, Dan Jurafsky, Pratyusha Kalluri, Siddharth Karamcheti. Geoff Keeling, Fereshte Khani, Omar Khattab, Pang Wei Koh, Mark Krass, Ranjay Krishna, Rohith Kuditipudi, Ananya Kumar, Faisal Ladhak, Mina Lee, Tony Lee, Jure Leskovec, Isabelle Levent, Xiang Lisa Li, Xuechen Li, Tengyu Ma, Ali Malik, Christopher D. Manning, Suvir Mirchandani, Eric Mitchell, Zanele Munyikwa, Suraj Nair, Avanika Narayan, Deepak Narayanan, Ben Newman, Allen Nie, Juan Carlos Niebles, Hamed Nilforoshan, Julian Nyarko, Giray Ogut, Laurel Orr, Isabel Papadimitriou, Joon Sung Park, Chris Piech, Eva Portelance, Christopher Potts, Aditi Raghunathan, Rob Reich, Hongyu Ren, Frieda Rong, Yusuf Roohani, Camilo Ruiz, Jack Ryan, Christopher Ré, Dorsa Sadigh, Shiori Sagawa, Keshav Santhanam, Andy Shih, Krishnan Srinivasan, Alex Tamkin, Rohan Taori, Armin W. Thomas, Florian Tramèr, Rose E. Wang, William Wang, Bohan Wu, Jiajun Wu, Yuhuai Wu, Sang Michael Xie, Michihiro Yasunaga, Jiaxuan You, Matei Zaharia, Michael Zhang, Tianyi Zhang, Xikun Zhang, Yuhui Zhang, Lucia Zheng, Kaitlyn Zhou, and Perey Liang, On the opportunities and risks of foundation models. arXiv preprint arXiv: Arxiv-2108.072555 2021.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanic Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Herbert-Vore Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCan- dlish, Alec Radford, Iya Sutskever, and Dario Amodei. Language models few-shot learners. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeuriPS 2020, December 6-12, 2020, virtual, 2020. URL https: https::/proceeeeeeeeee http:////ooooeocs///cooo. neurips cctppppp//222/000000 / html.
1457c0d6bf 4 1bte44/1eaaaa1111141aa-aa
Pengyu Cheng, Tianhao Hu, Han Xu, Zhisong Zhang, Yong Dai, Lei Han, and Nan Du. Self-playing adversarial language game enhances Ilm reasoning. arXiv preprint arXiv:2404. 10642, 2024.
Xiang Deng, Yu Gu, Boyuan Zheng, Shijie Chen, Sam Stevens, Boshi Wang, Huan Sun, and Yu Su. Mind2web: Towards a generalist agent for the web. Advances in Neural Information Processing Systems, 36, 2024.
Meta Fundamental AI Research Diplomacy Team (FAIR)t, Anton Bakhtin, Noam Brown, Emily Dinan, Gabriele Farina, Colin Flaherty, Daniel Fried, Andrew Goff, Jonathan Gray, Hengyuan Hu, et al. Human-level play in the game of diplomacy by combining language models with strategic reasoning. Science, 37866624):1067-1074 2022.
Yao Fu, Hao Peng, Tushar Khot, and Mirella Lapata. Improving language model negotiation with self-play and in-context learning from ai feedback. arXiv preprint arXiv:2305.10142, 2023.
Grill, Florent Altché, Yunhao Tang, Thomas Hubert, Michal Valko, loannis Antonoglou, and Rémi Munos. Monte-carlo tree search as regularized policy optimization. In International Conference Machine Learning, pp. 3769-3767777 PMLR, 2020.
11

---

Published as a conference paper at ICLR 2025
Wenlong Huang, Fei Xia, Ted Xiao, Harris Chan, Jacky Liang, Pete Florence, Andy Zeng, Jonathan Tompson, Igor Mordatch, Yevgen Chebotar, Pierre Sermanet, Noah Brown, Tomas Jackson, Linda Luu, Sergey Levine, Karol Hausman, and Brian Ichter. Inner monologue: Embodied reasoning through planning with language models. arXiv preprint arXiv: Arxiv-2207.00
2022.
Subbarao Kambhampati. Can large language models reason and plan? Annals of the New York Academy of Sciences, 1534(1):15-18, 2024.
Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Kaya Stechly, Mudit Verma, Siddhant Bhambri, Lucas Saldyt, and Anil Murthy. Lims can't plan, but can help planning in llm-modulo frameworks. arXiv preprint arXiv:2402.01817 2024.
Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning, In European conference on machine learning. pp. 282-293. Springer, 2006.
Marc Lanctot, Kevin Waugh, Martin Zinkevich, and Michael Bowling, Monte carlo sampling for regret minimization in extensive games. Advances in neural information processing systems, 22,
2009.
Jonathan Light, Min Cai, Sheng Shen, and Ziniu Hu. From text to tactie: Evaluating ilms playing the game of avalon. arXiv preprint arXiv:23/0.05036, 2023.
Xiao Liu, Hao Yu, Hanchen Zhang, Yifan Xu, Xuanyu Lei, Hanyu Lai, Yu Gu, Hangliang Ding, Kaiwen Men, Kejuan Yang, et al. Agentbench: Evaluating Ilms as agents. arXiv preprint VrXiv:2308.03688 2023.
Yecheng Jason Ma. William Liang, Guanzhi Wang, De-An Huang, Osbert Bastani, Dinesh Jayaraman, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Eureka: Human-level reward design via coding large language models. arXiv preprint arXiv:2310. 12931, 2023.
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with self-feedback. Advances in Neural Information Processing Systems, 36, 2024.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508-51 2017.
Kolby Nottingham, Bodhisattwa Prasad Majumder, Bhavana Dalvi Mishra, Sameer Singh, Peter Clark, and Roy Fox. Skill set optimization: Reinforcing language model behavior via transferable skills. arXiv preprint arXiv:2402.03344. 2024.
Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T Connor, Neil Burch, Thomas Anthony, et al. Mastering the game of stratego with model-free multiagent reinforcement learning. Science, (78(6623)999-999
2022.
Sheldon M Ross. Goofspiel-thh the game of pure strategy. Journal of Applied Probability, 8(3):
621-625, 1971.
Timo Schick, Jane Dwivedi-YY Yu, Roberto Dessi, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models teach themselves to use tools. Advances in Neural Information Processing Systems, 36, 2024.
Julian Schrittieserr, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with learned model. Nature. 58887839):604-699, 2020.
Jack Serrino, Max Kleiman- Weiner, David Parkes, and Josh Tenenbaum. Finding friend and foe in multi-agent games. Advances in Neural Information Processing Systems, 32, 2019.
Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024.
12

---

Published as a conference paper at ICLR 2025
Mohit Shridhar, Xingdi Yuan, Marc-Alexandre Côté, Yonatan Bisk, Adam Trischler, and Matthew Hausknecht. Alfworld: Aligning text and embodied environments for interactive learning. arXiv preprins arXiv:2010.03766 2020.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676::35-3599 2017.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
James Thorne, Andreas Vlachos, Christos Christodoulopoulls, and Arpit Mittal. Fever: a large-scale dataset for fact extraction and verification. arXiv preprint arXiv: 05355, 2018.
Karthik Valmeekam, Matthew Marquez, Sarath Sreedharan, and Subbarao Kambhampati. On the planning abilities of large language models-a critical investigation. Advances in Neural Information Processing Systems, 36:75993-76005, 2023.
Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Voyager: An open-ended embodied agent with large language models. arXiv preprint ar arXiv:2005.1629, 2023a.
Lei Wang, Chen Ma, Xueyang Feng, Zeyu Zhang, Hao Yang, Jingsen Zhang. Zhiyuan Chen, Jiakai Tang, Xu Chen, Yankai Lin, et al. A survey on large language model based autonomous agents. Frontiers of Computer Science, 18(6):183445 2024.
Ruoyao Wang, Peter Jansen, Marc-Alexandre Côté, and Prithviraj Ammanabrolu. Scienceworld: Is your agent smarter than 5th grader? arXiv preprint arXiv:2203.07540 2022.
Shenzhi Wang, Chang Liu, Zilong Zheng, Siyuan Qi, Shuo Chen, Qisen Yang, Andrew Zhao, Chaofei Wang, Shiji Song, and Gao Huang. Avalon's 's game of thoughts: Battle against deception through recursive contemplation. arXiv preprint arXiv:2310.01320, 2023b.
Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph. Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H. Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang. Jeff Dean, and William Fedus. Emergent abilities of large language models. arXiv preprint arXiv: Arxiv-2206 220.0-2200....,,, 2022a.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoc Lee and Denny Zhou. Chain of thought prompting elicits reasoning in large language models. arXiv preprint arXiv:2201.11903. 2022b.
Wikipedia contributors. Goofspiel - Wikipedia, the free encyclopedia, 2023. URL https: //en. wikipedia org/wr http////ndexx////eeeeeeeeeeeesie http:ppppppaaoooaaaaaaaaaaaaaaaa accessed 22-May-2024J.
[Online;
Shuang Wu, Liwen Zhu, Tao Yang, Shiwei Xu, Qiang Fu, Yang Wei, and Haobo Fu. Enhance reasoning for large language models in the game werewolf. arXiv preprint arXiv:2402.023311 2024.
Zhiheng Xi, Wenxiang Chen, Xin Guo, Wei He, Yiwen Ding, Boyang Hong, Ming Zhang, Junzhe Wang, Senjie Jin, Enyu Zhou, al. The rise and potential of large language model based agents: A survey. arXiv preprint N0XKv:2309008666 2023.
Yuzhuang Xu, Shuo Wang, Peng Li, Fuwen Luo, Xiaolong Wang, Weidong Liu, and Yang Liu. Exploring large language models for communication games: An empirical study on werewolf. arXiv preprint arXiv:2309.044 04658, 2023a.
Zelai Xu, Chao Yu, Fei Fang, Yu Wang, and Yi Wu. Language agents with reinforcement learning for strategic play in the werewolf game. arXiv preprint arXiv:2310. 18940, 2023b.
Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio. William W Cohen, Ruslan Salakhutdinov, and Christopher D Manning. Hotpotqa: A dataset for diverse, explainable multi-hop question answering. arXiv preprint / 1809.09600 2018
13

---

Published as a conference paper at ICLR 2025
Shunyu Yao, Howard Chen, John Yang, and Karthik Narasimhan. Webshop: Towards scalable real-world web interaction with grounded language agents. Advances in Neural Information Processing Systems, 35:20744-20757, 2022a.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models, arXiv preprint arXiv:2210.03629, 2022b.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.03622, 2023.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Deliberate problem solving with large language models. Advances in Neural
Tree of thoughts: Information Processing Systems, 36, 2024.
Jifan Yu, Xiaozhi Wang, Shangqing Tu, Shulin Cao, Daniel Zhang-Li, Xin Lv, Hao Peng, Zijun Yao, Xiaohan Zhang, Hanming Li, al. Kola: Carefully benchmarking world knowledge of large language models. arXiv preprint arXiv:2306.09220 2023a.
Wenhao Yu, Nimrod Gileadi, Chuyuan Fu, Sean Kirmani, Kuang- Huei Lee, Montse Gonzalez Arenas, Hao-Tien Lewis Chiang, Tom Erez, Leonard Hasenclever, Jan Humplik, et al. Language to rewards for robotic skill synthesis. arXiv preprint ar36v: 08647, 2023b.
Wenqi Zhang, Ke Tang, Hai Wu, Mengna Wang, Yongliang Shen, Guiyang Hou, Zeqi Tan, Peng Li, Yueting Zhuang, and Weiming Lu. Agent-pro: Learning to evolve via policy-level reflection and optimization. arXiv preprint arXiv:2402.17574 2024.
Andrew Zhao, Daniel Huang, Quentin Xu, Matthieu Lin, Yong-Jin Liu, and Gao Huang. Expel: Llm agents are experiential learners. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 19632-19642, 2024.
Shuyan Zhou, Frank F Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Tianyue Ou, Yonatan Bisk, Daniel Fried, et al. Weharena: A realistic web environment for building autonomous agents. arXiv preprint arXiv: 13854, 2023.
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. Advances neural information processing systems, 20, 2007.
14

---

Published as a conference paper at ICLR 2025
A
RESISTANCE: AVALON GAME DESCRIPTION
5
5
3
4
Majority
Mojeriy vata you
Selection Phase
Voting Phase
Mission Phase
Team proposed
Figure 8: The three phases per round of Resistance game. Good players are shown in blue, while Evil players in red. In Selection Phase, the team leader (player 5 in this round) proposes team (player and 5, himself). In Voting Phase, all players vote publicly whether to approve this team or not. If the strict majority votes yes, the team is approved and moves on the mission phase. Otherwise, redo the Selection Phase with the next player as leader. If the team goes on the Mission Phase, selected team members (player and 5) anonymously vote to pass or fail the mission. If at least one person (player 1, as he is the evil player) votes fail, the mission fails. Otherwise, it succeeds.
We describe the game in more detail here. There are four phases in the game where players need to make decisions: (1) team selection phase, (2) voting phase, (3) quest phase, and (4) assassination phase. The game alternates between the first three phases until the end condition is reached, which point we move on to the assassination phase. Each phase also contains discussion where players can challenge others, defend themselves, and negotiate. A flowchart of the game presented in Figure 10, and an Avalon Rule Prompt is included in Section A.4.
A.1 ROLES
There are four basic roles Resistance Avalon: Servant Arthur, Minion of Mordred, Merlin, and Assassin. The Servant is basic good character who does not know the identity of any of the other players. The Minion is a base evil character who knows who is good and evil but does not know the specific roles of each player. Merlin is unique good character who knows who is good and evil. The Assassin is a unique evil character who knows who is good and evil, and addition, has the ability to assassinate character at the end of the game. If that character is Merlin, the evil team wins.
Good players will always outnumber evil players. Hence, evil players order to be voted in on teams (and thus sabotage missions). SERVANTS will thus need to sniff out the evil players through their actions and dialogue. MERLIN is usually the only good player with additional information, so they will need to discreetly guide the SERVANTS in the right direction. Servants also need to protect MERLIN, so a common strategy is for SERVANTS to pretend to have hidden information so that evil players will think that they are MERLIN. Evil players will be trying to sniff out MERLIN at the same time, so deduction skills are required for all roles.
pretend be good in
A.2 ACTIONS FOR EACH PIIASE
Depending the phase team selection, voting, quest, and assassination, players may conduct different actions. We detail the specific actions that players can take in each of these phases below.
During the team selection phase, only the current leader has to make choice. Leadership passes around the players sequentially a loop. The action space of team selection for the leader consists of all subsets of the players with size equal to the mission team size. The mission team size is different
15

---

Published as a conference paper at ICLR 2025
leeed you vote yes for team with you me, player
know the first mission with me and player falled, 5 who foiled
think that players 1, great
Hayere went on fulled. Player 3 must be
refuse to be team player fried cheese himselti
truel
3
voied posa on the first
2
Would you happy with me, and player then?
2
consleting
5
Player has been acting very suspidiooly gome, every team
Deduction
Coodination
Deception
Figure 9: Communication Skills required to play Avalon. 1) First, they use logical reasoning to analyze the voting pattern and dialogue of other players and deduce their motives. 2) they must coordinate, communicate, and persuade their teammates follow particular strategy. 3) they must also hide their identity and motives through deception.
Team Selection Phase (Leader)
Tours
si Hoand?
Quest Phase [Team Members)
Ouaex
Convddy Isantiie
Game Start
Switch Leader
Voting Phase (All Players)
Game End
Headeed
Appeceal
Qutonn
Sucoed
Assassination Phase (Assassin)
Marie
winst
Figure 10: Flowchart illustrating the various game states and transition diagram. Round boxes indicate game states (phases) where the player (role highlighted bracket) has to make decisions
for each mission and is determined by the total number of players in the game. For example, in a 5-player game, on mission No.4, the mission team size 3, so any subset of {1, 3, 4, 4,5) with size 3 would be valid action. After the team proposal is determined by the leader, we move on to the voting phase with the selected players.
During the voting phase, every player in the game needs to simultancously vote either APPROVE (1) or REJECT (0). Votes are publicly revealed all players, so players can see what other players voted. If a strict majority votes APPROVE (I), we then move on to the quest phase with the team that was approved. Otherwise, we move back the selection phase. Note that if four teams have been rejected in row, and this is the fifth time a team is proposed (for the same mission), we skip the voting and move directly to the quest phase. This prevents the game from dragging on forever.
During the quest phase, each selecied player the approved team votes anonymously to either PASS (1) or FAIL (0) the mission. The number of votes PASS vs FAIL are then revealed to everybody. the number of FAILS is greater than equal to the number of FAILS required for the mission to fail (usually 1), then this mission is marked as a failure. Otherwise, this mission is marked as a success. Hence, good players usually have incentive fail missions, while evil players will want have enough failures to pass the failure threshold. If three out of five missions fail, evil wins immediately. Otherwise, if three out of five missions succeed, we move on to the assassination phase.
A.3 DISCUSSION
Group discussion occurs between the quest and selection phases, as well as right before the as- sassination phase. Players may not communicate during any other time. All conversations public, and there is no private communication. Typically players may discuss in any format of their choosing long as only one person is speaking at time. Some examples of formats include
16

---

Published as a conference paper at ICLR 2025
natural (spontaneous) seminar style (most common, where there is no fixed order of speaking), or sequentially (where players speak in some predefined order). Interruptions and arguments between two players are very common between human players.
Usually, players will spend this time discussing a couple of key topics, including (I) the observations they made, (2) the guessed identities and sides of players, and (3) the plan for the next mission. The team leader will usually spend this time asking for advice on what team to select and gathering support for that team. Persuasion and adhering the preferences of other players are usually key to getting a team approved. Players can also accuse other players of being evil, though arguments will need be justified in order to be persuasive.
For example, player (player 3) could start off by stating their (1) observations of what happened in the previous mission. One FAIL was observed. so at least one player on the previous team (consisting of players (1,2,3)) is evil. Player 3 then emphasizes that both Players I and 2 voted APPROVE for the previous mission, which ended up a failure. Moreover, the team was proposed by Player 1 in the first place. Player 3 then moves says that, despite the fact that only one FAIL was observed, both Players and are evil since they both voted to APPROVE previously. Player 0 is probably good since they voted to REJECT in the previous mission, and Player 3 is also good since they also voted to REJECT, even though they were on the mission. Player then says what they think the (3) plan should be. Specifically, Player 3 says that they should reject the current team no matter what since Player 2 is the leader and is evil. The leadership will then pass to Player who will choose the team (0, 3, 4), which good players should vote to approve since it does not contain any suspected evil players !
discuss the (2) identities of other players. The player
A.4 GAME ENDING AND ASSASSINATION
In classic RESISTANCE, good team wins immediately if three missions are successful. In RESIS- TANCE AVALON, there is an additional assassination phase if three missions are successful. During the assassination phase, the ASSASSIN player chooses one player to assassinate. If that player is MERLIN, then evil wins. Otherwise good wins.
Before they assassinate a player, the ASSASSIN player and is encouraged to discuss with the other players (mostly their teammates). good players are also welcome to join in on this discussion to mislead the evil players, though it rarely helps. Players can diseuss in format of their choosing, though there is usually a time limit on how long players can discuss before reaching a decision.
At this point, Player reveals that they the assassin and assassinates Player 3, who is indeed MERLIN.
Player 3's intuition and analysis were way too correct he SERVANT
17

---

Published as a conference paper at ICLR 2025
Avalon rules prompt
The game you are interested in is called The Resistance: Avalon. The Resistance: Avalon is the game of hidden identities and social deduction. There are two teams in the game: Good and Evil. Each player has a hidden identity (role) and side.
There are five Quests in the game and five turns, one for each quest. Good players aim to help three Quests succeed, while Evil players aim fail three Quests. Different quests require different numbers players to participate.
At the beginning of the game, each player is assigned role secretly and randomly. Private information then revealed each player. random player is selected the leader for the first round.
Each round, after a round of discussion, the leader will select team of players to participate the Quest. Then, players will vote on whether to approve or reject the team publicly. the team is approved (a strict majority vote to approve), the Quest will be carried out. If the team not approved, the next player becomes the leader and the next round will start. four teams rejected in row, the fifth team will automatically be approved.
If the team is approved, each team member chooses pass fail the Quest anonymously. Usually, if there is at least one failed vote, the Quest fails. Otherwise, the Quest succeeds. In either case, move
the next turn and the next quest.
Below the roles in the game:
Servant of Arthur (Servant): A Good player who does not know who is on the Evil side. The Servant's job is make sure that the three Quests succeed.
Minion of Mordred (Minion): An Evil player who knows who is on the Evil side. Minion's job fail three Quests without being identified by the Good players.
Merlin: A Good player who knows who is on the Evil side. Merlin's 's job is to make sure that the three Quests succeed without revealing themself Evil.
Assassin: An Evil player who knows who on the Evil side. Assassin's job is to assassinate Merlin if the Evil players can identify who Merlin is. If the Assassin successfully assassinates Merlin, the Evil players win the game immediately, even if three quests succeed.
Hence, Evil players usually know who is on the Evil side, but Good players usually do not know who is on the side.
Players may make any claims during the game, at any point the game. Discussion, deception, accusation, persuasion, and logical deduction are all equally important in order for Good prevail Evil to rule the day. Hence, players should rarely reveal their true identity to other players. Players will, can, and should lie to achieve their goals.
18

---

Published as a conference paper at ICLR 2025
B GAME OF PURE STRATEGY (GOPS) GAME DESCRIPTION
Game of Pure Strategy (GOPS) a card game for two or more players with a standard deck of card, which is commonly used an example of multi-stage move game artificial intelligence (Wikipedia contributors (2023)). In our experiments we play 5 or card GOPS. Specifically, the score cards are {1, n and each player starts with hand of cards f1.2, ...m. where the number of cards and rounds. The GOPS rules prompt is included in this section below.
GOPS rules prompt
The game you want to write function for is GOPS (game of pure strategy), also known as Goofspiel. The game has two players. and is played with a deck of score cards. Each player dealt the same hand of cards at the beginning. The goal of the game is to get score higher than your opponent. At the beginning of each round, a score card is randomly drawn without replacement from the score deck. Then each player plays card simultaneously from their hand. The player who plays the higher card wins the round and gets the score card. They add the score of the score card to their total score. If the two cards played are the same, the person who wins the next round will get both score cards. The game continues until all score cards have been played. The player with the highest total score wins the game.
19

---

Published as a conference paper at ICLR 2025
C LIMITATIONS
While our method performs better on average, individual runs can have high variance. Since the performance of agent in multi-agent adversarial game settings is highly dependent on opponents' policies, feedback from these environments tend to be highly noisy, with noise increasing with the number of players. This especially true when learning Avalon heuristics, where the performance depends on the policies of other players, teammates and opponents. We believe that running more game simulations with different opponent policies can help reduce this feedback noise. We also acknowledge the inherent noisiness in LLM generations and how that can impact our results. We tried reduce this noise by (1) using the same seed functions when benchmarking the different L.M improvement methods and (2) collecting generated strategies from multiple runs. We also did not test our method on other non-adversarial environments such as question answering and text-based worlds. However, given the strong performance of our method in adversarial multi-agent settings, believe that similar performance will be observed in single agent, non-adversarial settings.
20

---

Published as a conference paper at ICLR 2025
Strategist
Reflection and
Strology improvement
Strategy Library
Strategy Library
Idea Queue
Altematt
Stotegy
Vee
Mau
steps
Idea
Ieproveced idea
Ststegy
Strregy B
Stower
Stategy
idea
eproeement idea Sooe:
Stotugy 80
Oraweyy AA
Stategy AB
Stokeg
Troadooy leebbod.
Trajectory feedback
Prirrty score
Update strowayy and idea libraries
Stonee:
Adaptive Treo/ Bandit Selection Policy
Joint acfions takern Kayer seid i. Plyer
Spicads outiomes Full vine
Select key decision states
Search wine sctmmates 30% 45% 20%
Internediate voluses G-A, GVA
Key states simulated trajectories
Intermediate valume skudeet crewared
fellows
fartce
GT: Wicc player fhet
Selfplay simulations with MCTS
Actions sholurt
Markin the woo?
(pessilted dhalopoe)
AT: Player
Improved stralegy F
Outcome: Good last beil
G2: Wichh player shoul you try eccase
Soarch extimater 30% worrte
for Guaa
being Ewll
Player alvoady sopaoh ane si shouk
Player lestood
Mario toughh procen querhonaire:
Oi: whek player sppert you Mlanle the west? 02: What player should you arose bakng Evit What cosduaions can yea besed
natural language iption
You cooch. Previously you suggested this (strttggr] which produced these [intemediate vnlumej this [sote]. Swarch linall outcome). What [siche] is (search ssimatel, while this the aanciaiaaa can you drow, and what arw ways we could improve the staatgy?
suggested (erategy) Implament this [improvement idea) strotegy best
that value
LLM
LLM
Korks shought procen pueskoesine
Wilk player clould you by excnse being
Add quarton that oibs which Eel playe sespesh you en Moris
ecceed Flaso qusskios apprapriats lacatioe.
Generated ideas
condlation con you srow based
on Selected strategy
Add questoo that oots whetferyor
Selected idea
douid ocrone crybooly the rouell
Adaptive Tree/Bard ree/Bandit Selection Policy
Altemate between stops
ilea
Score:
idea
Skoreg
Number tries!
Impe ovement ideu C: Score: 0.0
A
Hos
Ieprovement idea A, soone
Number of triess
Ieprovenent Edeo scoe
Idea Queue
Strategy Library
Idea Queue
Figure 11:
Overview of our high-level strategy improvement method: The process alternates between two steps-idea generation and strategy improvement.
D IMPROVEMENT PROCESS IMPLEMENTATION DETAILS
Our method alternates between two main steps: idea generation and strategy implementation, as illustrated Figure 11. These steps are structured around the optimization of strategies stored in hierarchical tree structure T. Below, we detail the key components of our implementation.
D.1 STRATEGY TREE AND IDEA QUEUE
The strategy tree 7' maintains all discovered strategies, their associated feedback (7,), and priority scores (2.), which determine their likelihood being selected for further refinement. Complementing this is the idea queue Q, prisrity-based queue that stores candidate ideas generated during the improvement process. Each idea d'e E Q is initialized with prior score 2n = 0.0 and usage count na = 0.
21

---

Published as a conference paper at ICLR 2025
Algorithm 1: STRATEGIST Pseudocode
Data:
T: strategy storing stralegy s, feedback (Tw), and priority (z.). Q: idea queue, 'seed functions', Nudeax: number of ideas, Natrategies: number strategies, N Navolations! number of evolutions, "Jeedback_ezamplee number of states of give as foedback,
Function solect_strat :T'):
arg softmaxzz // possible implementation where you take oEls
of the best two strategies in the whole tree zandomly (BFS2)
return
Function solect_ided (Q,0):
Abeat sottargmax UCB((za, na) // one possible implementation where you take the best strategy the queue using softmax UCB, za being the empirical g-value and na being the number of tries
return (Ther
Function select_ Setecte_ey_ttttssttte (T>):
Kg f- arg F vs(s)) // one possible way to select key
aE"
states for a that is a value heuristic fo
return Kr
Function generate ideas (Nateas):
0 + seleet_strategy/ (T));
Ko + select_key_statee
(To) Ko is set of key states from the trajectcry feedback To for strategy
Deew idess <- LLM(Generate Nidens new ideas based on string description K,, which includes the output of the strategy, action taken, state description, final outcome of the trajectory, search estimate the state, and any intermediate values used to compute the output of the strategy); for E Dwww ideas do
Store d with prior score z4 0.0 and na O; end
F Function Lmpplement_stratcgggee
(Natrategics):
Enew, D 1J, (1, 1ist new generated strategies, dictionary mapping new generated strategy to the idea that generated it, and di dictionary mapping generated strategie es to their parents for +- 1 to Natrategies do
select_strraeey (T);
select idea (Q,a):
Orew
<- LLL((Iprroeee a using d);
Enww (pw.a
D Dnew d;
[new 0:
end
W, W + SelfplaySSmullatCCeeww U umiquu((Pvaatuss) // simulate games, getting average winrates Woa [o] for each strategy and simulated trajectory feedback T(o]
for a E Emew do Tadd(oo, P(a), D(a)) // add new strategy to tree from parent based on idea
za - W[ // add function score
Zp|ei + "pjel
e apj+)t (W[o) W(P[o]) // update idea score with how much it improved the strategy by
end repeat
generate_ideas (Nuaar);
implement_see saammcnt_ssrrttgiiee (Naanteia)))
until
N Naviiiioo::
return Best strategies in T' according to their scores
D.2 KEY FUNCTIONS
Selecting Strategies (SelectSttraeggy To identify promising strategies for refinement, use a softmax over the priority scores 2, stored in One implementation chooses between the two highest-priority strategies in breadth-first search order.
22

---

Published as a conference paper at ICLR 2025
Selecting Ideas (SelectIdea) Ideas selected from Q using Upper Confidence Bound (UCB) approach. Each idea's 's selection balances its empirical improvement potential (za) with its exploration term R.d, ensuring both promising and underexplored ideas are considered.
Selecting Key States (SelectKeyStatee) Key states Ka for a given strategy o are selected based on a heuristic that emphasizes discrepancies between search-based estimate and the strategy's value function Eig. These states highlight areas where the strategy can be improved.
D.3 IDEA GENERATION
During the idea generation step, the algorithm:
1. Selects strategy a from T using SelectStrategy.
2. Extracts key states Kg from the trajectory feedback To using SelectkesStates.
3. Uses language model (LLM) to propose Nideas new ideas based the string description Kg. This description includes the strategy's actions, state details, trajectory outcomes, search estimates, and intermediate values.
4. Adds the generated ideas to Q with default priority and usage counts.
D.4 STRATEGY IMPLEMENTATION
In the strategy implementation step, the algorithm:
Selects strategy from T and an idea d from Q using Select and SelectIdea.
2. Refines a using d, producing a new strategy dnew
3. Simulates self-play games for onew and related strategies to evaluate performance (win rates W(o)) and collect trajectory feedback (T(a)).
4. Updates the strategy tree T with Onew. linking it to its parent strategy and the idea that inspired
5. Updates the priority scores 2g for strategies and za for ideas based on the observed improve- ments.
D.5 ITERATIVE EVOLUTION
The improvement process repeats for Nevolutions iterations. each iteration, new ideas and strategies generated and evaluated, incrementally building tree of optimized strategies.
D.6 SCALABILITY AND EFFICIENCY
Our method leverages efficient UCB-based selection and hierarchical feedback propagation to scale to large and Q. By iteratively refining strategies through targeted improvements, ensures continuous enhancement while maintaining computational feasibility.
23

---

Published as a conference paper at ICLR 2025
Performance of strategles in strategy tree
Gameplay scores each method
Finsl Score
Score
Generation
Method
Figure 12: Left: Example performance of value heuristics strategy tree for GOPS. Points indicate the final evaluation scores and the generation of improved functions, with lines showing the evolutionary path between functions. Our method successfully escapes local maxima and continues exploring the strategy space. These scores reflect final gameplay results against a fixed set of opponents, differing from the intermediate self-play scores used to guide strategy improvements. Right: Comparison of different improvement methods 6-card GOPS, where 9 functions generated by each method play against one another over 1024 total games.
E AVALON AGENT IMPLEMENTATION DETAILS
describe detail how we implement our model below and as shown in figure 13. Unless otherwise specified, the word 'action' will refer to non-dialogue actions. Note that we do not conduct search over raw dialogue space since that is not very computationally feasible. Instead, we search over intended actions and condition dialogue that.
Specifically, the language component consists of a dialogue analyzer and a dialogue generator, while the moves component consist of the action planner. Whenever the agent needs speak, they first analyze what was said so far in the current discussion round using the dialogue analyzer. The dialogue analyzer, with the help of LLM, updates the internal beliefs of the agent. For example, in Avalon, internal beliefs might include the probability that the agent assigns to each other player of being Evil and of being Merlin. These beliefs are then passed the action planner, which uses them to figure out the best next move, i.e. the action intent. The action intent is then passed to the dialogue generator, which generates dialogue with the help of an LLM. When the agent needs take move, we run through the same process except that the agent takes the action intent as the move and no dialogue generated.
E. DIALOGUE ANALYZER (DISCRIMINATOR)
The dialogue analyzer fana takes as input I information set (partial information) of the current state for the player, d, the discussion so far this round, and b some prior beliefs about the hidden state of the game, and returns b, the updated beliefs, and II, the predicted joint action policy of the all the players (i.c. the action intent) for the next action step t. Recall that simultancous games can be expanded as partial information games, where the simultaneous moves are treated as hidden information. Hence, information set I using the dialogue analyzer.
essentially predicting distribution the hidden states given the
6, A, Sana (I, de b)
In the context of Avalon, I will contain information such as (1) the dialogue this round so far (2) summary of the dialogue from previous rounds (3) mission track record (4) historical record of
actions taken by players in previous rounds, and (5) private information of the player such as who is
Good and Evil. b will contain information (1) the probability of each player being Evil and (2)
24

---

Published as a conference paper at ICLR 2025
Discussion
somioo dillogue
Gene uted dologue
Dialogue Discriminator
Action Planner
Dialogue Generator
b,
[ol, 02, ...!
LLM
LLM
Bes octon
Summary of previous dialogue
Action State
Figure 13: Overview of the LLM-powered agent, including the three main modules that we use to generate dialogue during discussion
the probability of each player being Merlin, both conditioned on the private information contained in I. While a full treatment of the distribution over the hidden state space S we require assigning probabilities each possible combination of Good and Evil players, not just assessing the marginal probability of each player being Good individually, in practice
We implement fana using an LLM, which fed I, d, b (converted to natural language form) as prompts, along with some instruction prompt dana that prompts it to produce b, II, Specifically,
fana (I, de, b) fLLM d I, I,d,b. d)
We show examples of such prompts Appendix J.
E.2 ACTION PLANNER
Given b the belief prior, I1, the predicted joint action policy for all players, and a the representation of the current state, the action generation model fact generates probability distribution possible actions n' for the main player that is the best response II, We do so by using search techniques to look ahead and find the best response.
n' fact (b, I1, I)
More specifically, in our search implementation, at the first layer, we first sample across possible hidden states ~ according to the belief prior. At the second layer (i.e. the first action stage t), we calculate expected q-values for each action a e A that the main player can take if the other players play actions a I1, according to the predicted joint distribution. In subsequent action stages, the search process will assume that other players play according their policy simulated and induced by the value heuristic that not dialogue dependent. We then take the best response action a; max(r" T') as the intended action. Since this is partial information game, expected g- valuees taken across information sets, not states. We describe how our action planner implemented in more detail in Appendix F.
25

---

Published as a conference paper at ICLR 2025
E.3 DIALOGUE GENERATION
The dialogue generator gee takes as input I some representation of the current information set and ay the intended best response action, and outputs dialogue d.
d= f [Ia,])
We will implement fgen using an LLM, which is fed I and a directly as prompts, along with some instruction prompt Øgen that prompts it to produce realistic sounding dialogue that helps achieve its intended action.
For example, perhaps the player wants to approve the next team. Then it should try to generated dialogue that convinces the other players to also approve.
We show examples of such prompts Appendix J.
26

---

Published as a conference paper at ICLR 2025
F
VALUE HEURISTIC IMPLEMENTATION DETAILS
Action planner
First Action
Second Action
Iniaal inference
Backpropagate values
Sampled hidden state
30%
30%
pt
50%
pt
30%
20%
Matropalattaaingg Sompling
3
ph
Beliefs dialogue analyzer
20%
Probobilty sompling computed using UCT
Probability of each player being Good: 50%, 20%,
Infer
Different hidden stotes belong to the some information sot
60%)
Value houristic
Figure 14: Overview of how we utilize the trained value heuristics MCTS tree search to get non-dialogue based policy. While only display the values for single player in the diagram, note that in practice we infer and update the values for all players at the same time. Next states sampled using the PUCT formula described. We sample the internal beliefs of the agent. Metropolis- Hastiiss is used to sample since it may be difficult to calculate the probability density specified by the internal beliefs. Note that values estimated using MCTS are also passed as feedback to the evaluator.
initial hidden state based on
The MCTS search process is depicted in Figure 14, where we simulate a trajectory from the hidden state we are at until we reach some unexpanded state s. The probability of transitioning to state during simulations is computed assuming that each player samples from their optimal actions according to their PUCT (polynomial upper confidence trees) values (and Φ. for the environment actor) (Schrittwieser al., 2020). Since some environments players may only able to observe information sets, when computing the PUCT values we average over all expanded states in that information set. Moreover, the initial hidden state can be sampled according to a prior (or empirical prior) over the states in the information set that the player observed. Then, using value heuristic, we compute the values of each of the next hidden states. We then backpropogate our new values back up the simulated trajectory, updating the intermediate states. After running few MCTS simulations (roll-outs) like the one we described, the planner then outputs the action which leads to the highest value next state. We show our information of times we took action a at state during MCTS rollouts, P(s, a) is the prior prior probability of selecting action from state s, C is the exploration constant, Qemp is the empirical average of MCTS roll-out outcomes, (ss, a) is the prior computed by our value heuristic, a controls how much weight be put on the prior (often a = 1), and л is the distribution across hidden states in the information set given our beliefs B, some parametrization of πв. Since म is often hard to compute, we can Σ, (((.))
PUCT formula below, where N N(s, a) is the number
simply n (s Eve E. ((5(6)) be the empirical roll-out distribution, given that sample initial states F ( 7) according to our beliefs. For example, in Avalon, we can sample the hidden roles according to our beliefs B using Metropolis-Hasttngs for the initial state 8g-
Q(s,a)= N(8,a) Qemp (8, a) ta (s.
(1)
N(s, a) +a
VL, ((
PUCT(L, Σ (B(s|!) sEf
+ C.. P(s,a) 1+ ((,,a)
(2)
27

---

Published as a conference paper at ICLR 2025
G DIALOGUE GUIDE IMPROVEMENT EVALUATION IMPLEMENTATION DETAILS
We provide details our dialogue improvement evaluation process here and shown in figure 15. The improvement method (skill coach) remains the same as we described before.
We first generate synthetic dataset by simulating game of Avalon with initial dialogue and move policies Φb Given the dialogue guide a we want to evaluate, we then sample 'scenarios' from the dataset. A scenario consists of game state, intended action, and private information the simulated trajectory. We create an Avalon agent like the one we described in E for each player in the game, initialized with their corresponding private information. The Avalon agent is then asked generate dialogue using the dialogue guide a.
Using this new generated dialogue, we then simulate the next round of dialogue analysis for each Avalon agent. This produces analysis scores based on how likely they think the player is to be Merlin Amerlin, and how likely they think the player to be Evil ževit, where Smerlin Zevit E [-2,2] For evaluating Merlin, get the average Amerlin scores from the Evil players, Emertin along with the average ževil scores from the Good players Zevil. We then take the minimum of these two as the feedback score probability of being detected by the Evil players, and also minimize the probability of being identified Evil by the Good players.
min(Zeval merlin ). This is because Merlin wants to both minimize the
Skill coach
Strotegy guide
exompla
The current state of the game is (state).
How to play Merlin: 1. Avoid making direct accusations or openly
In this example sitvation
Library of guides
[scenario] the student, student, with your guide, generated the
summary of the previous
discussions is (summaryy)
claiming to be Marlin,
diologue [generated
This round players have said (discussion) so far. Your role is [role] this game and you know that (private information). You like to
Instead, focus on guiding the
dialogue). Here are the
towards making informed decisions without drowing attention
other player's is thoughts on the genarated diologue (analysis). After few game simulations, the average winrate using this dialague was (score).
Sens teclock
2.
(achion intent).
Evaluator
Improved guide
Anolysis
Scenario database
Dialogue generator
Dialogue analyzer
Score
Given current siluation (scenario), dialogue that would help you achieve ochivee your goals, some lips: Jotrategy guide]
Did the probabiity of the player being Merlin
Game simulator
Stole claustion
the dialogue fgenerated dialogue) and situction [scenarioss
Updoted bellef
Sote, dboussoon fastoyy....
are
Sampled scanorio
Generated diologus
each player
LLM
LLM
Figure 15: Overview of our improvement process for learning dialogue generation strategies. This includes how we evaluate the dialogue and how we collect feedback. The skill coach here can be implemented as either our improvement method, STRATEGIST, any of the baseline methods we described.
The dialogue analyzer (discriminator) is described in more detail in Appendix E and the specific generation and analysis prompts shown in Appendix J.
28

---

Published as a conference paper at ICLR 2025
H VALUE HEURISTIC LLM PROMPT AND OUTPUT EXAMPLES
H.1 SYSTEM PROMPTS
System prompt are guidelines for L.M to generate outputs align with the intended goals. In our case, the goal is to generate function that evaluates the value of state in game under low cost.
Value heuristic system prompt
You are function engineer trying write a function that can evaluate the value of state in game. This is known as value heuristic, and will be used in look search algorithms to evaluate the value of unexplored states. Your goal is to develop heuristic that accurate as possible without being too expensive to compute. Hence, you are not allowed to runs simulations the function.
The following example is detailed prompt telling the LLM how format the value heuristics specifically in the GOPS game. The format of input and output are clearly defined in the prompt with illustrations, examples and structures.
29

---

Published as a conference paper at ICLR 2025
GOPS value heuristies function signature
The function (written in python) should be named 'evaluate state' and take in a tuple called 'state' of the game state as input. Specifically, the input tuple will be of length 9, and it should return 2 elements. The first element should be a tuple with floats: the first element being the score you expect player O will get at the end of the game, and the second element being the score you expect player will get at the end of the game. The second element should be dictionary of any important intermediate values that you used to calculate the scores. For example, if you think player 0 will win 12 total points by the end of the game and player will win total points, the function should return (12, 8).
Make sure your output only includes the code of the function itself in plain text such that is executable using exec() in python. Any helper functions should be defined within the scope of the function 'evaluate state'. Include comments your code so that is readable, but everything should be implemented.
The signature of the function should be as follows:
evaluste (staatt)
tuplefsuple(fleat, floatl, diml;
scuze scuze_carde = state(O; python list of the scoze cards (integeral that have been played, in the were played
playez_ O playyd__aadds state[l] a python list of the cards (integere) player has played, in the order they
playes.
player p_pp__py____oo cards state(2) a python Hist the cards (integera) player has played, i'm the order they vere played.
turn state(3] bool, to drow a now score card
is you your apponent' turn to play, false if time
playez_0_scm sccoo state[4] float integes, player 0f
far
scoze Looze score deck scate.6] 6] python set of the soore cards (integers) left in the deck, either same
state[5] # floa: oz integec, playez I's sooze so far
length player_ 2_r_____aanc.
or one less since score card appeazs before
playeze play. May be exply
player_ 0__hndd stabe(?]
python aet of the (intagers) left in player hand, May be
cmpty
player___hamd L_aandd state[8] a python aet of the carda (integers) left in player afa hand. May be
arpty
explanation of what we do next
..*
<intermedi ste_ explanation of what do
value'> etlleeeeedddeeeeeleee.b valuel
sintereed ate_ va loel va lue?? explaration of
player (playor_ Sapprr___sppp exppertod score, glayer____sporteen expoocted (ccora)
Interedieet vaiues d'sintermediste_vve wealiiittteevellbeeeeeeeee valueb> intermediate valuel "dintemediat__valle intermdicte intemmciate_valiee volus? ...)
recurn pleyer_ pcores, intermediate values
retum exactly this format
Where you can use your own names for the intermediate values and the values themselves. Please start with "def evaluate state(state):"
H.2 IDEA GENERATION EXAMPLES
The idea generation prompt included system prompt, game rules, previous guide and feedback reflections. Following those four components, we construct the format and an example of ideas to guide the generation of L.M.
30

---

Published as a conference paper at ICLR 2025
Prompt for idea generation
<Systemm prompt>
<Game rules>
<Previous guide>
<Feedback reflections>
Based on the function, feedback, and conclusions you drew, what are 2 improvements that you can make the function that you think will have the most impact? Be specific and concrete possible, and write them out in the following format:
Thoughts: <your thoughts here>
Idea <your idea here>
Idea 2: <your idea here>
Here's an example of what this might look like for 3 improvement ideas:
Thoughts: I should consider the number of cards left in the deck when evaluating the value of a state.
Idea I: should add a term the value function that penalizes states where there are fewer cards left in the deck.
Idea 2: should add term to the value function that rewards states where the player has more cards in their hand than the opponent.
Idea 3: should add term to the value function that rewards states where the player has more cards in their hand than the opponent and there are fewer cards left in the deck.
Below an instance of Feedback of GOPS game, showing the setup two players, the intermediate values involved in the computation, and the actual scores.
31

---

Published as a conference paper at ICLR 2025
Feedback example
Example 9:
The state you were trying to estimate a value for is:
The current state of the game is as follows:
The score cards that have been revealed are: (2, 4, 3)
The cards that player has played are: (1, 2, 4, 3, 5)
The cards that player has played are: (3, 5, 4)
Player O's score far is: 9
Player I's score far is: 6
The score cards left in the deck are: set()
The cards left in player O's hand are: set(
The cards left player I's hand are: set()
The function you generated returned the following values:
(0: 3, -3)
for the expected end of game scores of the players.
Some intermediate values that you used to calculate the scores were:
(' ('player_0 @_expected__come score":
Learss___eepeeeeeeee_e namic peaaiic_peaatt:::: 0.0, "player hand reward': 0, 'player_1 I_hadd reward': Blajur___ajjusmmeett
9,
6. 'dy-
0.
'player 0 adjustment': O, "player adjustment': 0, 'player 0 strategic sttraeggi__chuustmntt 0. siciiiidddjstmtt 0}
The estimated end of game scores of the players using lookahead search with your function was:
(0: 0.0. 1: 0.0}
The actual scores of the players at the end of the game in the simulation were:
(0: 3.0, 1: -3.0)
Recall that feedback reflection refers to feedback for strategy, which is used generate ideas. For prompting, We specify that game rules, previous guide and feedback examples are generated previously. The following is the prompt for feedback reflections.
32

---

Published as a conference paper at ICLR 2025
Prompt for feedback reflections
<Systemm prompt>
<Game ru rules>
Previously you generated the following function evaluate the value of state in the game.
<Previous guide>
Below is some feedback on how the function you generated performed when we tested it. Note that simulations involve high variance and the actual scores may not match the expected scores exactly. Hence, you should focus on trying to get the scores produced by your function to match those predicted by look-aheat search as closely as possible.
<Feedback examples les>
Based on the feedback given and the function you generated previously, what are some conclusions you can draw from the feedback? Make sure to cite the specific examples in the feedback to justify your analysis.
Below the feedback reflections from the LLM.
Feedback reflections
From the feedback provided, draw several conclusions regarding the performance of the function in evaluating the value of a state in the GOPS game:
Discrepancy in Expected Scores: In several examples (e.g., Example 4, Example 7, Example 8), the expected end-of-game scores returned by the function do not match the scores predicted by look-ahead search closely. This indicates that the function may not be accurately estimating the value of the states the game.
2. Inconsistencies Strategic Adjustments: The function includes a strategic adjustment based the opponent's 's played cards, but in all cases, the strategic adjustments zero. This suggests that the strategic adjustments made in the function may not be capturing the true strategic implications of the opponent's 's moves effectively.
3. Dynamic Penalty Adjustment: The function includes dynamic penalty adjustment based on the remaining high-value score cards in the deck. However, the dynamic penalty adjustments may not accurately reflecting the impact of high-value score cards left in the deck on the game outcome.
4. Limited Hand Size Reward:
The function rewards states where player has more cards in their hand than the opponent. While this reward is included, might not be capturing the full strategic implications of having more cards in hand effectively.
5. Simulation Expected Scores: The actual scores the end of the game in the simulations do not match the expected scores returned by the function precisely. This indicates that the function's evaluation may not be aligning well with the actual game outcomes.
In conclusion, the function may need further refinement in terms of capturing strategic adjustments, dynamic penalties, and hand size rewards improve the accuracy of the state evaluation in the GOPS game. Additionally, considering the discrepancies between the expected and actual scores, further testing and adjustments may be necessary to enhance the function's 's performance in evaluating the value of states accurately.
Also, with the prompts of idea generation, below is the generated ideas by LLM.
33

---

Published as a conference paper at ICLR 2025
Generated new ideas
Thoughts:
The function needs to better capture the strategic implications of the opponent's moves and adjust the expected scores accordingly. Additionally, the dynamic penalty adjustment and hand size rewards could be improved to better reflect their impact on the game outcome.
Idea 1: Enhance the strategic adjustment component of the function by analyzing the opponent's played cards more deeply. This could involve considering patterns in the opponent's 's moves, potential card combinations, and predicting future moves based on past actions.
Idea 2: Revise the dynamic penalty adjustment more accurately reflect the impact of high-value score cards left in the deck. This could involve adjusting the penalty dynamically based on the remaining high-value cards and their likelihood of being drawn in future rounds. This adjustment could help in better assessing the risk associated with certain states in the game.
H.3 STRATEGY IMPLEMENTATION EXAMPLES
During the strategy implementation step, first select a strategy and idea from the libraries using the adaptive selection policy. Then, we prompt the LLM to implement the idea on the strategy. generating new improved strategy.
In this section, we showcase two examples. Each example illustrates strategies before and after enhancements made by the LLM. This comparison highlights the effectiveness of our strategy implementation. The improved parts by LLM are highlighted in yellow.
Below the prompt for strategy implementation.
Prompt for implementation
<System prompt>
<Game rules>
Previously you generated the following function to evaluate the value state the game: <Previous guide>
Here a possible way to improve this function:
<Improvement ideas>
H.3.1 EXAMPLE 1
Below is the GOPS Value Heuristics Function before the strategy improvement.
34

---

Published as a conference paper at ICLR 2025
GOPS Value Heuristies Function (Before)
def evaluste_ (tate(t
tuple[tuple[IToak floatl, dist]:
score_carde statell;
player_ playopp conds atabe[1]
playe:
state[2]
tuuturn state[3]
playez_0_scom state]4]
playez scate[5]
score_deck stste]6]
playez_Q_had state[7]
playe: state(8]
Calculate pocential
each player based the remeining scoze
Slayer_potential__og player_
opponent aponent_potentlal potptttppttttlllppea _acoree player_1_son
1f (enoso deok) >
somaining_accro_cco
if len (piayere 0 cards)) len (elayllyrrraaaee playee cardal) player_ pesser__ttentialleom soore reneining soore_ccoroe cards elif lengplayer played cardss) > (player 0 played cards) sppoeent_potentiee
remeining_roore.coo
player jabaantg player potger_pttnttall.. score oppanent_ www.ppottttll..oooo. __aoooe
recurn (player_pocent score, opponent opponent_potentee patentlal_aoore) ("player_avvantage" player_adventagel
Below is the selected idea to improve the above strategy.
Selected GOPS Value Heuristies Improvement Idea
Update the function calculate the advantage winning future rounds based the potential scores each player could achieve with the remaining score cards and their current scores. This would involve considering the number of cards left in the deck, the players' hands, and the current scores to determine the advantage one player may have over the other in the upcoming rounds.
Below is the GOPS Value Heuristics Function after enhancement by LLM. The improved parts by L.M are highlighted in yellow.
35

---

Published as a conference paper at ICLR 2025
GOPS Value Heuristies Function (After)
def evaluste_sLatee (aate(t
tuple[tuple[[Toal, floskl, dist]:
score_carde statell;
player 0oper___p00 playoop condds atabe[1]
playe:
state[2]
tuuturn state[3]
playez_0_scam state]4]
playez scate[5]
score_deck stste]6]
playez_0 state[7]
playe: state(8]
Calculate posential
each player based the remeining score
and ourzent scores
player ogpenent_pctential www.tppaleettoooooeooooo pcore player_ Lacore + zum (smorre__cckk) /
player score aumiscoree_eess deok))
adventage winning future
potantial score
Ir is_turm:
player player_potentla potenttat ial
aayyr_pottettlal
card in player handd]
#eponent_potentiie pocres
card player hand]
Blayer_advantag wwmpplayer_poeentill..ooo
ppt.pplyerrppttnttllll potentiel scores)
sumlogponent potenttil http:ppprrni.pottreaaae..oooo
elae:
player advantage player, potpor__otttttlll.oom score opponent potentisl__nn poore poore
re:urn peper_pocentallccee opponent (oceantal__scrred aallayer_avvattgee player_adventage
H.3.2 EXAMPLE 2
Below is the Avalon Value Heuristics Function before improvements.
36

---

Published as a conference paper at ICLR 2025
Avalon Value Heuristics Function (Before)
evaluate state
num mim_moocnsffll quests quests
zum authitttrriaal queeeeereil__eeeett_oo_o
questtremmtss)) remuls))
neLralled questss tirthisttoiiaa sueest mun_aucoess cul.euucoessulaaee
num Lum_reraining.om geestss guest
len porttelportsspr per__ausstt (historical gewest____tteollll
nunevil (playera) monggood
mmLov: 1 qneat toom lont (player for player in guast if not is_godd(laaeer)
success prckabiiiy 0.5
1f phase
questa sucees_protabille - 0.9
elif mum fai guests 3:
sucsss_probbbii
0.1
elff phase =
ciccesa_pacbabillit.
8.8.3. mum_coi inuggess_ngommm clae
elif phase - 2:
success_ pacbabbilyyy
if pum_euccessfo quests fan__aileed_queee
elif phase 3:
if "Merlin' in coles and 'Asssssian in zoles: nerlin_index zoles. index insaasin_indes roles. iol (coassiinn) aseassin
team
succesa prohaallpppphliie Iry 0.1
alss:
poccess_ercbbbllig 0.9
expectei_ wwwrrteeeppeeeeecco.eeeeoe player dict
for player in players:
is goodlplayer
expected petpeeeeeeeteeeeeeeeeeeeeeeee
succers probabiiibyyyy
elae:
expected wwnrstaas_prr... por_ppeyerrrplll (ylrrp)
proosse_protenit ity
Intereedaae
"mmm_suuee suseesoful quests' mm muconnsfflll quateaassoofflll.utttt
famm_fiiled quests's faifea quests,
"aun muunrrensiningggueer mm minurenee rew.rreeiiinng quests,
fmmn_evil wnt.vvil_innueerrree questttterrrr : minevil inuggsst_ttomm
expected winrates_ pereeseppee_eeeee parppppeeppppppeee per_playes, Intermedi valuss
Below is the improvement idea pf Avalon Value Heuristies Function.
Avalon Value Heuristics Function Improvement Idea
Incorporate more nuanced success probability calculation based on the roles of the players and the current phase of the game. For example, in phase (team selection), consider the balance of Good and Evil players the quest team and adjust the success probability accordingly. This can help better reflect the strategic considerations during team selection.
The following Avalon Value Heuristics Function after enhancements, highlighted in yellow.
37

---

Published as a conference paper at ICLR 2025
Avalon Value Heuristics Function (After)
def evaluste_statee (eateee diet)
tuplefdicl [lsa;), diet]:
prob_ 0.5
probobt that Good will win
phose select phose
nuLuuccesaful quests qunthistoricall_eessssss reculll))ss
nun_railed quests thistorical qpaetaal_______eeeepe resultt)) num_aucosestul
mm rwm_romanninggggaa.. len www.tciaaassss.r..ccccccco per_giass len/historicol_gga cttpriooo___ss__eeeeeeeee
mineviil len(slyyers) mun_good
nenevil gosses team - len( pplayer for player in queet_teen if not 1s_geod(plaaye])
nun wuw.euuuuuuuuucoooo questa >- 3:
proo good vrletory = 0.9
elif foilfii guests
proo_good, citi__goo__rrrttrrrooooo wilctory 0.1
Interneiate valuel
V'nur_aucceseslll_co quessts www.eeestulgueeeeeeee "nun_iaflled_ee Ludn_saalee_.uessaa'
fai lam_faaledd_uxeeee quests,
"mmm ron__remniingg..om guesttss nom remainn ng guesta)
intermedisto.o walue ['mm__vill questt peoal boomf mim_ovil gonsttest,,___.oooooooooo toam)
elif phase = 1: i team approval phase
pvil htt_arrr1____eeeeee _nn__gest_____oo_ooo qpeet_ttemm_ttt len( [player for player quast_ream (g_goo((payy)r]
prok_goox 0.8 sun_evil guestt -- else 0.2
internedisto walul ['mm_ovil giggeestt boom/ mun_evi 1 ii team)
intermediate
Initialize empty dictionacy avoid error
elif phase 2: quest plase
rmm ann_acccessull quests sunthlatorfoal _qistt queett results)
len thistorical quess:: resull))) nun_aucoessfl
ceoh_good_yycttrr 0.9 if num sam_succassful guest > nm fai alap 0.1
Internediate setmmddiateevaa luet I'nun aunnssoooossttl gueets : mom mum_9uoeesaful queets "nom_ leddl questaa
rum fal lum_fallle__peeste
Intermeistte
Initialize empty dictionsry to avoid the erroz
phase asssasinat phase
merlin_Inde roles, index (' (' assassin index zeles index Assassin')
if assassin_ index in quest teams grod_good beclggooo__rrooooo victory 0.1
elae:
pmob good__oo____ieo victory 0.9
Intermediate ['nerl inn_innnnndd Indew' merlin_'ndey "asssasin_ Indew" assassin_Indewy
interedictta valvee () Instialize empty dimionnzy
preecteiiyinreeee. patperetteeepepppeeereeeeeeeeeee diet
prok victory prol_gooo_vvcctory
for player players:
is goddlpyyley
(playe) grob_ggoo_wietorry
else:
expected poraoeteeeerooroorgrrrrpop
prob_evil_sictor
Intermediata aa ves ves wiintemodlata..aalaa incernedlate, att_valltteaaalaee "intemedlan ate aatplltte_aaaaaal value2' intermed ste_vallua))
vecurn expectedd wi wrateeess_pe patppppeepppppppe playe,, intermedi ateemedllbeewwar valus
38

---

Published as a conference paper at ICLR 2025
H.3.3
EXAMPLE 3
Below is the GOPS Value Heuristics Function before the strategy improvement.
GOPS Value Heuristies Function (Before)
def evaluste__Late(etaa (eate(e
LupletLuple[[oott, floatl, dict]:
score_carde statell
player_
patpee___pllo___oompp conds atate[1]
state(2]
1o_turn state(3]
playez_0_scom state]4]
playez sscyce___ccoze state[5]
score_deck scate]6]
Blaye=_0_hand state[7]
playe: stabe(8]
Calarlate potantials
playez_ 0.pee__tpcteetiie sumiplayer hand) hand)
potenttl_pteettll sumplayyrr__11 hand)
score_ potar_pocentiall... sum aumlscore_dess
Update player poteotiala based on zenaining cards and spore deck playez_ 0 pctential +- sunicard for card in player_ hand if any (card > scoze for score in score score_deck
player_1 potential tu aunleard for card in player_ 1.f any (card score for score in score_deck
Ads half of the goore pocential to the player who has the turm
playe=_0_potentiee i- score_potential. 2
clse:
L t- score_potential.
Count nomber certain wina each player
pertainn wins sunleard max (slayer Land for card In haadd: player_L
nax
player___hadd)
rounds left len(score_dest:
Dynamic adjustment based on: specific cards played player ceettain _id___jusss___ adjus:
player_ Lectain postainnxing wine adj______s_____ -0 for in range (len Slaayeer___laye__crmm if player p_plyyed_______pp cardd cards [1] Llaye__
Blaaye____eeraae wewraainniing _i____iie_______________________ t-
player_ 1-1
playez_ Q wins += player 0 cwntair yor
playes Lpertiiniin +* Lesterr__eetttiiryyrvss...
Add potential sccres from certain vins
rounde leAt Clayes___oertain gighest_acoree sortediscore deck) reotte_leftt)
pettetall i- sumthighess_
if rounda_ledd <a player pertain_vines
highest_noores scrtedlscore (-cound
to (imthighest_sooree)
39

---

Published as a conference paper at ICLR 2025
Calculate expected scores
playe=_Q_egeen wtt.o_ppppcttsssseeee player sccre player Saaree____pptteee potencial
playez Legeete_ expectee__ccoree Alayer_A_ccon
1.steecc.
aum of played cards sun pwuppeyye__.alm playy_pp_____aa cards = suniplayer 0. playye_yyyacaae sumpplayer_ ptwppplaaadaaac pandil
Calariate diffeenn
htm_ppayyr___pppp playyd sum ptt.playy___arr__ieeee ammplayer 1am__laye____ppppeedd playyo__mod
Adjust scores
diffarence
sum played
adjustment factor 0.1 i adjust this factor based on the level of adjustment desired playez eewpeeeeeeeeeeeccoeooooo sun played_ diff adjustzent factor
Blaye=___eppe Leepp_eeeeppepecooeoooo -- sun pardyllyyyladsss_poooop
adjustnent_ Tactor
Dynanic jdjuttent based on uncertaincy the game atace "a
uncertainty. factor = 0.1 rounds_left Adjust this factor based the level of uncertainty desired
player_ 0 [eepeet_eepeeete_______ expectee__scooe score -* player_0_ p_pteetialllll uroertaiityy player_l_potaree
player Lerye_____ppooo wwwppeott_p__oooeeo
uncartaiitt_fartton
Refine uncertainty factor based specific conditiens
lengplayer_) hand)
sesartainty_fccttaae +- 0.5
Lenjplayer__ unoertalitt_ffcctorr =- 0.5
Store Intereedaae values dietionary
Intermediota_yllleee
"player_0_ppteee pootentillttt 1layer___potential
[player ppttetttl Lpotenil
sscoee pesoreppbenttal scora_potentiat.
"player o_eertainniinnss
"player_ _e
"player_0 [eper_t_ooe (oottan wataatnnnnanannnnnnnnaann adjust player_0 [ poortan wine adjust,
"player certtain witii_iis____eeeee
saunpplayed_cm caredd__rrd_doeeee ditt'' pum_playdd_card caadyed__arr__dttee
"uncartainty_fartt"
imoortainty_footrr
recurn (player 0 expeccted player (xppotedd intermdiaate values
Below is the selected idea to improve the above strategy.
Selected GOPS Value Heuristics Improvement Idea
Incorporate term in the value function that takes into account the distribution of score cards left in the deck. Certain score cards may have a higher value or strategic importance, so adjusting the potentials based on the presence of these cards can provide more accurate evaluation of the state.
Below is the GOPS Value Heuristics Function after enhancement by LLM. The improved parts by L.M are highlighted in yellow.
40

---

Published as a conference paper at ICLR 2025
GOPS Value Heuristies Function (After)
def evaluste__tatee (tate(t
tuple[tuple[[Toak, flostl, dist]:
score_carde statell;
player_ playoop conds atabe[1]
playe:
state[2]
tuuturn state[3]
playez_O_scam state]4]
playez scate[5]
scorm_deck state]6]
huaned_ state[7] playe: state([]
Calculate initial potentiials
playe=___potende sum sumbolayer hand)
poyyr___psteetti smmplayrr___eeee. 1anod)
pocentil aumjscore_des...
Update player potentials
remoining
noora dack
playez_0 pctentiial +- sun/card for card in player_Q_hard hand if any (card > scoze for sccre in score
player I pctentiel sum/card for card in player hand if any (card score for socre in score_deck
Add half of the soore pacential to the player who has the tum
+u score_ootentall /
clae:
potential +- score_potential. /
Count mumber
wins each player
playe=_0 Qeretain wins sunleard max (slayer Uhnd for card In player_0_harp player_ Loerta_norr
phayer___hard)
rourds Jeft len (scoreec decc))
Dynamic adjustment based on specific cards played
player_0 "pe____n wins_adjus: player Lcortain cortain winn_adjuce
for in range (len (player playyee___pp____eee__eeeee c
if player_0 O_pla_pp__eeeeee__eeo cards [i] 1 ; player_ Si.prraannniii Mine adjuse +
elif Leayye____payye_ccoo
player played 1-
playe: Q'oertain wins player D Loaytr_ +- player_ Leaatr___oertttrrreeeeeeeo
Adé pocential sccres from certain wins rounds_le2 lest playes___oertate highest__corrs scrtedissore desk) (-roudd__lftt) potentall i- sumthighess_roore
if rounda_left <e player_1 Loerr_l____tttttttee wins:
highest_soores scrieciscore deck)) counde left:] plater_l_potential t= senthiighst_sooree))
Incosporate distr ton of scoze cards left in Ube deck
ipportantsccora (7, 10, 13) Pxamples deffnne important acore camds
player Seayer___pptteee potentiall (mard for card player handnd card important_peet pocre_ccorrrie cords))
player potentiel
card player hand card impertant_accre,
Calculate expected scores
player wwwpeeee____eeeeeee score player 0oore player potenntalll playez I Leppectes_ccoree player Sccore score potential
calaulate the di fferencs the aum of played cords el_player__0 p.played_aard cards sumppaaye wtwpppyyye___ppee___..pp p_playdd__aree sur surpeeayes_ played_aarde sumiplayer playpd cards)
om pan_pladd_drreee_iiee mmmplayer playydd___ooee cords ammpllaeer playod
41

---

Published as a conference paper at ICLR 2025
Adjuet acores based on Lhe difference in the sun of played carde edjustment factor 0.1 adjust this factor based the level of adjustment desired playez eeegeetee score sun_plyys diff adjustment factor
Leaye:__ - parppalyy__arrss..oo ditE adjustneet__actoc
Dynemio juatment based on uncertalncy in the game aLaze uncertainty. factor desired
rounds_left:
factor
level of uncertainty
player_ Socyy=____eppere Leepectei_scoors @layer_O_potezzn uzcertainty factor player wew_peccte_sccoee
Lppterrl_pttettaall umsartaiinny_fatto
uncertainty Sactor
specific conditions
1f Boppayyr____aaaeae -- 1;
uncertainty
0.5
lentplayer Jhand) 1:
uncertainty_facttn += 0.5
Store Interneiate values in diotionary
interodiataaymn
Sllayer_0_potentinne
player_0_potenie potentiail,
[poayer___pttetiaall Letemiil
socoee wawprepppeentttteeeeeee potentialttttt scora_potential,
"player_
wwt.e_eeteetttinnneeeeeee @laysr___cerrtiin
player___oertaiie
"player_ (woor_otttttttooee sa seinnaadjuuttt player [tr______aaaaa meLoertatnnyye wine winn__ddjust
"aun bounpplyydd_caeeee
caaod_aarrdtttoeree ditt'' sum paaded__adddddddttt ff
saaetttiny__aacttrr umeartainty_fore factor
(player_0 Lewpectee__sooe score, player expeetted intermedlato_yaluss
H.3.4 EXAMPLE 4
Below is the GOPS Value Heuristics Function before the strategy improvement.
42

---

Published as a conference paper at ICLR 2025
GOPS Value Heuristies Function (Before)
def evaluste__tatee (eate(t
tuple[tuple[IToak, flostl, dist]:
score_carde statell;
player_ playopp conds atabe[1]
playe:
state[2]
tuuturn state[3]
playez_O_scam state]4]
playez scate[5]
score_deck state]6]
huandd state[7] playe: state([]
Calculate initial potentiials
Blaye=_0_potente sum sumbolayer 01
player_1_potettt
score score_pocential. sumjscore_dest
Add half aoore posential player cumm if is_tur::
jilaye____poteniee
score_potentall
else:
potential i- score_potential.
Gount the number of cartain wing for each player Deeetainn wins aunteard max (p layer____aaa handy for card in player_
(slayer Dand
In player
rounds left len.score_decii)
posential sccres certain if rounds_ c- playec_ Dpertain_
highest__soree sortediscore deck) (-rounde_lefts) Olayer_0_ i- sumltighess_scores
rounda_lede player Lertain winas
highost__noores = sertedlazore peteccllsooo__eal (-rondo left:)
player_]_potettia aumthighest, scoress)
New imprevement: incesporate probubilistic approach based on the zemaining cards player Leepectes__ccoee player score player ppttentall playez 1 Leopectas player pocre player potennial
Dynamic evaluation of opponent's s potential moves opponent potential sumplayer_ @allayer__aann if opponent wertiirrriiiiiiiie wins sunfeard max (olayeer hand) for card In player haadd Lucn else sum leard maxiplayer___ (_ann)) for card in [naner_]__and)
Adjust evaluation based oppenent's pocential plays
rounds_le2 opporent centtin_eertinnnaee
highest_ scorees sortediscore deck) (-foudd_leftt)) if is_tum:
p sunthighestt_eoo scores)
else:
player_ Dasye____poeerr poteentaal suwthighesttssoooo scores)
Store inberodiate values dietoonayy
attemmdiitta.aavvee
"player 0 potential' player (layer_0_pere potential,
L
prcore_potentiil" poteeniit
"player o_teetanneeeaeieeee player_0_ Blayer___certainn.vin
"player Leaatar__cettain certainnvinsf
[aayee___erttiinnn
opporeni__poeeee pal ogpooen._potentiaa
ropporent, _errtooeettttnte wina': opponent_oorie _oertooeeetatnee wina, 'player 0 expgpcceed perocced__ccaee paome playar_0 Barpar___sso expecttd pcone,
"player eetpe_____ppe_e_eee__e_
recurn (pleyer_0 Oxeepected_ player LxsrecteLL internedaate velues
Below is the selected idea improve the above strategy.
43

---

Published as a conference paper at ICLR 2025
Selected GOPS Value Heuristies Improvement Idea
Introduce penalty factor for potential scores that are excessively high, indicating potential overestimation. By capping the potential scores applying scaling factor based on certain thresholds, we can prevent the function from assigning unrealistic values and improve the accuracy of the value heuristic.
Below is the GOPS Value Heuristics Function after enhancement by LLM. The improved parts by LLM are highlighted yellow.
GOPS Value Heuristics Function (After)
evaluate_sie seallsatessaateetlall (eate(eLat)))
Luple[Luple[Iooal, floatl, diet]:
score_cards atabeld
plpyyr___playedd__... cords atabe[1]
state[2]
to state[3]
__score stste]4]
playez scoze scoze state[5]
score_deck state:
playez_ hand state(7] playe:_l_aap stale[8]
Calculate Initial patentials
player_0_pes p_ppeetttlllll @mmplayerr___ana player potentiel pottet___pttentill
sum sumpplayrr__iiee hand))
poneeppotttiillll sumiscore_desse
Add half of the score potential to the player who has the tumn turn:
pottetiall i- potze_oo / 2
else:
player_ scoree
Sount
number cortain wina each player
sunteard max (player_ Landd for card In player_0_handd ayer handd) inn player_ 1hardd
Llayer_ aumloard
courds_lef len
Add potential sccres from certain wins
rounde leAt playes_0_ Corrtain gighest_aoores sortediscore deck) (-ronde_lefttt)
pottetall i- sum sumthighess__cooo
if roanda_lefs <a player werrtlooerrrtttttreeee
highest_noores scrtedlscore (-condd ppttental to (taphiighest_soore))
44

---

Published as a conference paper at ICLR 2025
New imprevement:: incesporate listic approsch based on the remaining cords playez Lexpectes player scccze player_ pottensial Leope:e_eeeeeeeeeeeccoo player_"__con [llaye____otentte
Dynemio evaluation of opporent's 's potential moves opponent potential sumplayer aaaa____rrrraa__ if aepnent_portaiie vins sumfcard max (xlayyer hand) for cord in player_Q_hare if tuutum clae zum (card maxiplayer band)) for card in player Laand)
sumiplayer, 1_handd
Adjust evaluation based appenent'a potential plays rounde esponent_erraann
highest_ aoores sortectscore_ left:] if is_tum:
I sunthighestt_com scores)
else:
player 0 potential auwihighest_ooo scoras)
Introdaco perality factor excesalvely high potent scones
penalty_thresheld 100
Define a thresheld for petential scores to trigger penslty
Factor 0.5 Define factor by which to zeduce potential acores above threshold
1 1toyyr___potsntial tomhehoyt
player_..potential penalay threshold (player pocential penalty chrashold) Factoty_factorr
if __ppr____poooe potential ppttoral
thrssholt
player potential threshodd L penalty_ chreshold)
penalty
Store internedaate values dimionary
Intermdiiata an
"player potenttaal player_0 potential,
"player_ 1 potenttaal 1
"acore_pod" potentiall poore_poLentlee
"player_0_cco w_tpr_ooeertttttiiieeee
glayer___oertaing
plaayer certaintwinss player Certaiiin.
rppporent_ potentfal" enpoorent_ootentfall
opponent Ia
"aegament_ccrttte wwwtainnttnnneeeeee wins opponent_ wing
"player 0
player_0 Dt expecteedddd.... score,
player Leep_peee_edd_oooe 'player poyer_i__xppetee _ew_peeee__ooeeeeeee playor_
recurn Iplayer O_ eoppcctdd_soor ncors, player sxpected_saorre) interedd values
45

---

Published as a conference paper at ICLR 2025
1 DIALOGUE GUIDE LLM PROMPT AND OUTPUT EXAMPLES
This sections shows the system prompts of dialogue guidance on LLM and several examples, including system prompts, idea generation prompts, and strategy implementation examples.
1.1
SYSTEM PROMPTS
Below is the Dialogue guide system prompt.
Dialogue guide system prompt
You are coach trying write section of strategy guide how to play game well.
The specific section of the strategy guide you writing right now is how play the Merlin role effectively during the discussion phase so that they can win the game. Recall that players often use the discussion phase (1) gather information about other players, (2) try to convince other players of their innocence or guilt, and (3) try to persuade other players of particular course of action. The game you are interested in is called The Resistance: Avalon. The Resistance: Avalon is the game of hidden identities and social deduction. There are two teams in the game: Good and Evil. Each player has a hidden identity (role) and side.
Dialogue guide signature follows, specifying the structures and contents dialogues regarding role playing the Merlin.
Dialogue guide signature
Your guide should be in the form of a worksheet that the student can use to build their speech. You should order the worksheet questions in way that makes logical sense, and you should have no more than six questions. Your questions should instruct the reader to write parts of their speech.
The title your section should be "Questions out before speaking as Merlin role". Below is an example of how your worksheet should look like:
1. Questions to fill out before speaking as the Merlin role
2. Q1: Which player seems the most suspicious of you and why?
3. Q2: For the player that seems the most suspicious of you, produce a statement addressing their suspicious.
4. Q3: Which player is the quest leader?
5. Q4: Produce statement addressing the quest leader to convince them to support
your intended course of action/ desired team.
6. Q5: Which player is the most supportive of you?
7. Q6: Produce a statement addressing the supportive player to convince them to support your intended course of action/ desired team.
46

---

Published as a conference paper at ICLR 2025
Example Generated Dialogue Strategy Guide for Assassin
QI: Which player seems to have a deeper understanding the game flow than normal Servants should possess?
2. Q2: Develop non-confromtationall statement to subtly challenge this player. This should cause them to either prove their innocence reveal more clues about their identity.
3. Q3: Who has been the most influential in the team selection and voting process?
4. Q4: Devise a statement to express agreement with this player's viewpoint sub- tly. This should make you less suspicious while enabling you manipulate the discussion.
5. Q5: Which player seems the most supportive of your views and actions in the game?
6. Q6: Craft statement subtly emphasizing your alignment with this supportive player's thoughts. This should increase your chances of being included in quest teams and reduce suspicion around you.
1.2 IDEA GENERATION EXAMPLES
The following the selected dialouge guide speaking as the Merlin role.
Select dialogue guide
Questions fill out before speaking as the Merlin role
1. Who are the players you suspect the Evil side and why?
2. Draft subtle statement that casts doubt on these players without directly accusing them.
3. Who is the current round leader and which players are you considering suggest for the team?
4. Create a subtle suggestion that influences the leader's 's team decision towards your preferred team without revealing your knowledge.
5. What the voting patterns you't 'ee observed and what do these patterns indicate about the players' identities?
6. Analyze the voting patterns and team compositions proposed by each player to identify potential alliances or suspicious behaviors. Craft statement to subtly address these observations without revealing your role.
7. Which player seems the most supportive of Good and how can you align with them during the discussion phase to better ensure success for your team?
feedback example is provided for better understanding of dialogue guidance to teach LLM how to role play Merlin.
47

---

Published as a conference paper at ICLR 2025
Feedback example description
Example 2:
The student using your guide was playing as player O in this example filled out your guide as follows:
1. Q1: Based the statements made far, I suspect Players 2 and 4 are the Evil side. Player 2's suggestion of team consisting of Player and Player 2 seems too convenient, possibly indicating desire control the team composition. Player 4's agreement with Player and Player 2 without offering any alternative team suggestions raises suspicion as well.
2. Q2: "I can't help but wonder if some players are trying steer the team selection process in particular direction. It's important for us to carefully consider all perspectives and not be swayed by potentially self-serving suggestions."
3. Q3: The current round leader is Player I would suggest team consisting of Player (Merlin) and Player I, as this would allow me to closely observe the actions of the other players and potentially guide the team towards success.
4. Q4: "Player 1, believe that team comprised of Player O and Player would provide a strong foundation for success. By working closely together, we can ensure that our mission is carried out effectively."
5. Q5: The voting patterns so far show agreement among Players 1, 2, and 4, indicating a potential alliance or shared goals. Player 3's suggestion of including themselves in the team may also indicate desire to control the outcome of the quest.
6. Q6:
'I've noticed pattern of agreement among certain players in the team selection process. It's important for consider all perspectives and not be swayed by potentially biased suggestions. Let's focus on working together as a team to achieve our common goal."
7. Q7: Player seems the most supportive of Good based on their consistent emphasis on unity and success for the Quests. will align with Player during the discussion phase ensure that our
selected and the quest completed successfully. Then they said the following during the discussion phase:
"Fellow players, as we embark on this quest, it crucial that we approach the team selection process with caution and consideration. have noticed pattern of agreement among certain players, which could potentially indicate a desire to steer the outcome in particular direction. It is important for to carefully consider all perspectives and not be swayed by potentially biased suggestions.
I believe that team comprised of Player 0 and Player 1 would provide a strong foundation for success. By working closely together, we can ensure that our mission is carried out effectively. Player has consistently emphasized unity and success for the Quests, making them trustworthy ally in this endeavor.
Let us focus on working together as a team to achieve our common goal, rather than allowing personal agendas to influence our decisions. Let us approach this quest with unity and determination, ensuring that Good prevails the end. Thank you for your attention."
48

---

Published as a conference paper at ICLR 2025
Below is some feedback from the other players how player 0 performed during the discussion phase, Recall that Good players are trying to access which other players are likely be Good, while Evil players are trying access which Good player is likely to be Merlin.
Player with role Servant had the following thoughts on this discussion round:
Thought:
Player I's speech emphasizes unity and success for the Quests, which aligns with the goals of Good and decreases the probability of Player being Evil. Player 2's statement also focuses unity and careful consideration, indicating commitment to the success of Good and decreasing the probability of Player 2 being Evil. Player 3's response as a Servant of Arthur is focused on the success of the Quests and unity, which aligns with the goals of Good and decreases the probability of Player 3 being Evil. Player 4's speech seems overly enthusiastic and focused unity and cooperation, which could be tactic divert attention from their true identity as an Evil player. This raises suspicion and increases the probability of Player being Evil.
Dictionary: {O: (-1, 'decreased slightly"), 1: (-1, 'decreased slightly"); (0, "stayed the same"), 3: (-2, ddecreased significantly"). 4: (2, 'inrreseed significantly")
Player 4 with role Assassin had the following thoughts on this discussion round:
Thought:
Player seems to suspect the Evil players (Player 3 and Player 4) without any evidence and trying steer the conversation towards them. This aligns with the behavior of Merlin, who knows the identity of the Evil players and is trying to subtly guide the Good players towards the correct decisions. This increases the probability of Player 2 being Merlin. On the other hand, Player 3's speech seems generally clueless and lacks any strategic insight, which decreases the probability of Player being Merlin.
Dictionary: [O: (0, 'stayed the same'), 1: (0, 'stayed the same'). 2: (2, 'increased signifi- cantly"), 3: (-2, 'decreased significantly", 4: (-2, 'decreased significantly')
This is the prompt for feedback reflections.
Prompt for feedback reflections
<System prompt>
<Game rules>
You previously generated the following section of the strategy guide: <Previous guide>
Below is some feedback on how your guide performed when student used it play the
game:
<Feedback examples>
Based on the feedback given and the guide section you generated previously, what are some conclusions you can draw from the feedback? Make sure cite the specific examples in the feedback to justify your analysis.
The following the feedhack reflections generated by LLM.
49

---

Published as a conference paper at ICLR 2025
Generated feedback reflections
In Example 0, Player O effectively followed the guide by suspecting certain players of being on the Evil side, crafting subtle statements cast doubt on them, and aligning with players supportive of Good. This led to Player 0 being perceived positively by other players, with Player 2's probability of being Merlin decreasing significantly due their behavior aligning more with the Evil side.
In Example 1, Player 0 again effectively followed the guide by suspecting players, making subtle statements, aligning with supportive player, and emphasizing unity and success in their speech. This resulted in Player 0 being perceived positively by other players, with Player 4's probability of being Merlin decreasing significantly due to their lack of strategic insight.
In Example 2, Player 0 successfully identified suspicious behavior in other players, made subtle statements, and aligned with a supportive player. This led to Player being perceived positively, with Player 2's probability of being Merlin decreasing significantly due their behavior aligning more with the Evil side.
In Example 3, Player effectively followed the guide by suspecting players, making subtle statements, aligning with a supportive player, and emphasizing unity. This resulted in Player O being perceived positively by other players, with Player 4's probability of being Merlin increasing significantly due to their behavior raising suspicion.
Overall, the guide's emphasis on analyzing player behavior, making subtle state- ments, and aligning with supportive players has proven be successful in helping players navigate the discussion phase effectively as the Merlin role in The Resistance: Avalon.
Players who followed the guide were able strategically assess the situation, cast doubt on potential Evil players, and align with Good players to increase their chances of success.
Below is the Prompt for idea generation regarding this dialogue guides
50

---

Published as a conference paper at ICLR 2025
Prompt for idea generation
<System prompt>
<Game ru rules>
You previously generated the following section of the strategy guide:
<Previous guide>
Here possible way improve your guide: <Feedback reflections>
Based on the worksheet, feedback, and conclusions you drew, what are 2 improvements that you can make to worksheet that you think will have the most impact?
Be as specific and concrete as possible, including what questions to add, edit, remove, and write them out in the following format:
Thoughts: <your thoughts here>
Idea I: <your idea here>
Idea <your idea here>
Here's s an example of what this might look like for 3 improvement ideas:
Thoughts: should tell the reader to address each player individually the guide.
Idea 1: Add a question asking the reader who they think most suspicious of them
and produce statement addressing their suspicions.
Idea 2: Add a question asking the reader to consider which other player is most supportive of them and produce statement addressing their support.
Idea 3: Add a question asking the reader produce statement addressed
Generated new improvement ideas demonstrated below, showing the improvements made by LLM following the prompt for idea generation.
Generated new improvement ideas
Thoughts:
The current worksheet focuses on analyzing player behavior, making subtle statements, and aligning with supportive players, which are all crucial strategies for playing the Merlin role effectively. To enhance the guide further, we can add questions that prompt the player to consider their own actions and statements more explicitly.
Idea 1: Add a question asking the player to reflect on how their proposed team composition would benefit the success of the Quest and provide statement justifying their choices.
Idea Add a question asking the player to assess their level of suspicion towards each player and craft statement addressing how they will interact with those players during the discussion phase.
Idea Add a question asking the player to consider how they can subtly guide the discussion towards a successful Quest.
I.3 STRATEGY IMPLEMENTATION EXAMPLES
Recall the strategy implementation mentioned in the paper before. Here, implement strategy improvements on dialogue guide. The improved dialogue guide is highlighted.
I.3.1 EXAMPLE
Below is the dialogue guide before any improvements happened.
51

---

Published as a conference paper at ICLR 2025
Dialogue guide (previous)
Questions fill out before speaking as the Merlin role
1. Who are the players you suspect the Evil side and why?
2. Draft subtle statement that casts doubt on these players without directly accusing them.
3. Who is the current round leader and which players are you considering to suggest for the team?
4. Create a subtle suggestion that influences the leader's 's team decision towards your preferred team without revealing your knowledge.
5. What the voting patterns you' ve observed and what do these patterns indicate about the players' identities?
6. Analyze the voting patterns and team compositions proposed by each player to identify potential alliances suspicious behaviors. Craft statement to subtly address these observations without revealing your role.
7. Which player seems the most supportive of Good and how can you align with them during the discussion phase to better ensure success for your team?
Below is the improvement idea prompted into LLM.
Improvement idea
Add question asking the player assess their level of suspicion towards each player and craft a statement addressing how they will interact with those players during the discussion phase.
Here, implementation prompty follows to teach LLM how improve the dialogue guide.
Implementation prompt
<5ystem prompt>
<Game rules>
You previously generated the following section of the strategy guide:
<Previous guide>
Here is possible way improve your guide:
< <Improvement idea>
Implement this improvement into the guide section best as you can, but do not change the original guide too much. Make sure to stay within the scope of the guide section, which we reiterate below:
<Guide signature>
Finally, we have a improved dialogue guide, where the changes are highlighted below comparing to the previous guide.
52

---

Published as a conference paper at ICLR 2025
Dialogue guide (improved)
Questions fill out before speaking as the Merlin role
1. Who are the players you suspect the Evil side and why?
2. Draft subtle statement that casts doubt on these players without directly accusing them.
3. Who is the current round leader and which players are you considering to suggest for the team?
4. Create a subtle suggestion that influences the leader's 's team decision towards your preferred team without revealing your knowledge.
5. What the voting patterns you' ve observed and what do these patterns indicate about the players' identities?
6. Analyze the voting patterns and team compositions proposed by each player to identify potential alliances suspicious behaviors. Craft statement to subtly address these observations without revealing your role.
7. Which player seems the most supportive of Good and how can you align with them during the discussion phase to better ensure success for your team?
8. Assess your level of suspicion towards each player and craft statement addressing how you will interact with those players during the discussion.
1.3.2 EXAMPLE 2
Below the dialogue guide before any improvements happened.
Dialogue guide (previous)
Questions to fill out before speaking as the Merlin role
1. Who are the players you suspect are on the Evil side and why?
2. Draft subtle statement that casts doubt on these players without directly accusing them.
3. Who is the current round leader and which players you considering suggest for the team?
4. Create a subtle suggestion that influences the leader's team decision towards your preferred team without revealing your knowledge.
5. What are the voting patterns you' 've observed and what do these patterns indicate about the players' identities?
6. Craft statement to share these observations subtly without giving away your role.
Below is the improvement idea prompted into LLM.
Improvement idea
Add question asking the reader to identify which players they feel most aligned with in terms of strategy and decission-maiigg and how they can subtly align themselves with these players during the discussion phase.
Here, implementation prompt follows to teach L.M how improve the dialogue guide.
53

---

Published as a conference paper at ICLR 2025
Implementation prompt
<System prompt>
<Game rules>
You previously generated the following section of the strategy guide:
<Previous guide>
Here possible way improve your guide:
< <Improve ovemnnt idea>
Implement this improvement into the guide section as best as you can, but do not change the original guide too much. Make sure to stay within the scope of the guide section, which we reiterate below:
<Guide signature>
Finally, have improved dialogue guide, where the changes highlighted below comparing to the previous guide
Dialogue guide (improved)
Questions fill out before speaking the Merlin role
1. Who are the players you suspect the Evil side and why?
2. Draft subtle statement that casts doubt on these players without directly accusing them.
3. Who is the current round leader and which players are you considering to suggest for the team?
4. Create subtle suggestion that influences the leader's 's team decision towards your preferred team without revealing your knowledge.
5. What are the voting patterns you't 'e observed and what do these patterns indicate about the players' identities?
6. Craft a statement to share these observations subtly without giving away your role,
7. Which player seems the most aligned with your strategic decisions and why?
8. Produce a statement to subtly align yourself with the player you feel most aligned with during the discussion phase.
I.3.3 EXAMPLE 3
Below is the dialogue guide before any improvements happened.
54

---

Published as a conference paper at ICLR 2025
Dialogue guide (previous)
Questions fill out before speaking as the Merlin role
Who are the players you suspect are on the Evil side and why?
2. Draft subtle statement that casts doubt on these players without directly accusing them.
3. Who is the current round leader and which players are you considering to suggest for the team?
4. Create subtle suggestion that influences the leader's ' team decision towards your preferred team without revealing your knowledge.
5. What are the voting patterns you've observed and what do these patterns indicate about the players' identities?
6. Craft a statement to share these observations subtly without giving away your role,
7. Which player seems the most aligned with your strategic decisions and why?
8. Produce a statement to subtly align yourself with the player you feel most aligned with during the discussion phase.
Below is the improvement idea prompted into LLM.
Improvement idea
Add question asking the reader to analyze the voting patterns and craft statement subtly highlighting any inconsistencies or suspicious trends in the voting behavior of specific players.
Here, implementation prompt follows to teach LLM how to improve the dialogue guide.
Implementation prompt
<System prompt>
<Game rules>
You previously generated the following section of the strategy guide:
<Previous guide>
Here is possible way improve your guide:
<Improvement idea>
Implement this improvement into the guide section best you can, but do not change the original guide too much. Make sure to stay within the scope of the guide section, which we reiterate below:
<Guide signature>
Finally, we have a improved dialogue guide, where the changes are highlighted below comparing to the previous guide
55

---

Published as a conference paper at ICLR 2025
Dialogue guide (improved)
Questions fill out before speaking as the Merlin role
Who are the players you suspect are on the Evil side and why?
2. Draft subtle statement that casts doubt on these players without directly accusing them.
3. Who is the current round leader and which players are you considering to suggest for the team?
4. Create subtle suggestion that influences the leader's 's team decision towards your preferred team without revealing your knowledge.
5. What are the voting patterns you've 'v observed and what do these patterns indicate about the players' identities?
6. Craft a statement to share these observations subtly without giving away your role,
7. Which player seems the most aligned with your strategic decisions and why?
8. Produce a statement to subtly align yourself with the player you feel most aligned with during the discussion phase.
9. Analyze the voting patterns and craft statement subtly highlighting any inconsis tencies or suspicious trends in the voting behavior of specific players.
56

---

Published as a conference paper at ICLR 2025
J DIALOGUE GENERATION AND ANALYSIS EXAMPLE LLM INPUTS AND OUTPUTS
This sections shows the examples of dialogue generation and analysis, including descriptive prompts, dialogue generation, and dialogue analysis.
J.1 DESCRIPTIVE PROMPTS
Below is the discussion history prompted into LLM for better knowledge of dialogue generation.
Discussion history
Here is summary of previous rounds of discussion far:
Player 1: "Grectings, fellow players. As Servant of Arthur, my primary goal is to
ensure the success of our Quests. am committed to working together with all of you achieve victory for Good. I believe that for this first Quest, team consisting of Player and Player 4 would be strong choice. I hope for your support in approving this team,
confident that we can work effectively together to accomplish our goal. I encourage everyone to share their thoughts and strategies openly. Let's work together assess each other's intentions and make the best decisions for the success of our Quest. Remember, the fate of Camelot rests in our hands, and we must be vigilant against the forces of Evil."
"Greetings, noble companions. I echo Player I's sentiment in working together for the success of our Quests. believe it is essential to carefully consider our team choices ensure victory for Good. suggest that for this first Quest, team consisting of Player and Player 2 would provide strong foundation for success. Together, we can overcome any challenges that come our way. Let us unite in efforts and show unwavering dedication to the cause. I urge all players to carefully evaluate each team proposal and remember that unity is key to thwarting the forces of Evil."
Player 2:
Player 3: "Greetings, noble companions. I echo the sentiments shared by Player and Player 2 regarding our shared goal of ensuring the success of our Quests. Unity and cooperation will be key in our endeavors to protect Camelot from the forces of Evil. As we deliberate on the composition of our team for this first Quest, I would like to offer perspective that considers the balance and strength of our choices. A team comprised Player and Player 3 would bring together a diverse set skills and viewpoints that greatly contribute the team, we can ensure a comprehensive approach to overcoming any challenges that may arise. Let us work together in harmony, leveraging individual strengths for the greater good of Camelot. urge my fellow players to consider this team proposal thoughtfully, I believe it holds great promise for the success of our Quest."
success. By including Player 3 in
Player 4: "Greetings, honorable players. I appreciaae the dedication and commitment displayed by Player 1, Player 2, and Player towards our common goal of ensuring the success of this Quest. Unity and cooperation are indeed vital in our quest to safeguard Camelot. believe that the proposed team of Player and Player presents a strong foundation for success. Their combined skills and perspectives can greatly benefit our mission, and urge players to consider this team thoughtfully for the betterment of our cause. Let us unite our strengths and work together seamlessly overcome any challenges that may arise. By standing united, we can ensure the triumph of Good over the forces of Evil. I urge all players to support the team of Player and Player for the success this Quest."
State description shows LLM which state will be for role playing and dialogue generation.
57

---

Published as a conference paper at ICLR 2025
State deseription
You are Player O, with identity Merlin. You are on the side of Good. The Evil players are Players and 4. Please do not forget your identity throughout the game.
The current state of the game is as follows:
The number of players in the game is:
This the quest number O which requires players and fails to fail
This the O round of discussion
The previous results for the quest were () (True for Success, False for Fail)
The current phase of the game is the team selection phase
The current leader is player You would like the following team to be approved: [o, 1]
J.2 DIALOGUE GENERATION
Below the prompt for filling out worksheet. Filling out this worksheet assists LLM generated better dialogue aligned with the role, Merlin as in the example.
Prompt for filling worksheet
<5ystem prompt>>
<Game rules>
<Discussion history>
<State description>
Given the discussion history, current state, and your intended action, answer the above worksheet to the best of your ability. The answers should be based on the information you have and your own reasoning.
Six questions to fill out before speaking as the Merlin role
Q1: Who are the players you suspect are on the Evil side and why?
Q2: Draft subtle statement that casts doubt on these players without directly accusing them.
Q3: Who is the current round leader and which players are you considering to suggest for the team?
Q4: Create a subtle suggestion that influences the leader's team decision towards your preferred team without revealing your knowledge.
Q5: What are the voting patterns you't ve observed and what do these patterns indicate about the players' identities?
Q6: Craft statement to share these observations subtly without giving away your role.
The worksheet filled out by LLM follows, demonstrating the LLM capability and the effectiveness of prompting.
58

---

Published as a conference paper at ICLR 2025
LLM filled worksheet
Q1: suspect Players 2 and 4 are on the Evil side because they both proposed the same team composition of Player and Player which seems too coordinated and potentially trying exclude other players from the team.
Q2: "I've noticed strong push for the same team composition from certain players, which may raise questions about their motivations and potential alliances within the group."
Q3: The current round leader Player would suggest Player and Player the team, as I believe this composition would provide strong foundation for success and help me subtly guide the decision towards my preferred team.
Q4: "Player 1, have a feeling that selecting Player O and Player for the team could bring a diverse set of skills and viewpoints that may greatly contribute to success. Let's consider all options carefully for the betterment of our cause."
Q5: The voting patterns have shown strong push for the team composition proposed by Players and indicating potential coordination or alignment between these players. Player 3's suggestion of including themselves in the team also raises suspicions of wanting to secure a spot on the quest.
Q6: "I've noticed a pattern in the team composition suggestions and voting behaviors that may reveal certain alliances motivations within the group. It's important for to carefully evaluate all options and consider the implications for the success of our quest."
Below is the prompt for speech generation. Worksheet completion assists LLM to understand the states and role. The following prompt asks LLM assemble responses the questionaire filled above.
Prompt for speech generation
<System prompt>
<Filled out worksheet>
Assemble your responses the questionaire you just answered into a speech that would help you achieve your intent. Note that dialogue will be seen by all players in the game, so you should not reveal your identity.
Your speech:
Finally we have LLM generated speech after the preparations.
LLM generated speech
I've noticed strong push for the same team composition from certain players, which may raise questions about their motivations and potential alliances within the group. The voting patterns have shown strong push for the team composition proposed by Players I and 2, indicating potential coordination or alignment between these players. Player 3's suggestion of including themselves in the team also raises suspicions wanting to secure a spot on the quest. It's important for carefully evaluate all options and consider the implications for the success of our quest. Let's consider all options carefully for the betterment our cause. have feeling that selecting Player 0 and Player for the team could bring diverse set of skills and viewpoints that may greatly contribute to our success. As the current round leader, Player 1, would suggest Player and Player for the team, as believe this composition would provide a strong foundation for success and help me subtly guide the decision towards my preferred team. Thank you for considering my input.
59

---

Published as a conference paper at ICLR 2025
J.3
DIALOGUE ANALYSIS
After dialogue generation, we continue have LLM assume the role of Merlin, and dialogue analysis is conducted.
Below is the prompt for dialogue analysis regarding to the role of Merlin. A thought is included to guide LLM analyze.
Prompt for dialogue analysis: Merlin
<5ystem prompt> <Game rules>
<Discussion history>
<State description>
Based on the discussions this round, for each player in players 0, 1, 3, do you think the probability of the player being Merlin (2) increased significantly (1) increased slightly (0) stayed the same (-1) decreased slightly or (-2) decreased significantly and why? Begin with your reasoning and end with a dictionary of player to your multiple choice answer, i.c. {0: (2, 'increased significantly", ... 4: (0, 'stayed the same')) )) Make sure you include quotes around the dictionary values that are strings.
Here's an example:
Thought:
Player 2 seems to suspect the Evil players (Player 3 and Player 4) without any evidence and trying to steer the conversation towards them. This aligns with the behavior of Merlin, who knows the identity of the Evil players and is trying subtly guide the Good players towards the correct decisions. This increases the probability of Player 2 being Merlin. On the other hand, Player 4's speech seems generally clueless and lacks any strategic insight, which decreases the probability of Player being Merlin.
Dictionary:
(0: (0, 'stayed the same'), 1: (0, 'stayed the same'), ; (2, 'increased significantly') 3: (-2. 'decreased significantly"), 4: (0, "stayed the same"))
Generated dialogue analysis follows. The role Merlin.
LLM generated dialogue analysis: Merlin
Thought:
Player 2 is actively participating in the discussion and proposing team compositions, which is a behavior that could align with the role of Merlin, who knows the Evil players and wants to guide the Good players towards success. This increases the probability of Player 2 being Merlin. Player 4, on the other hand, seems to be going along with the proposed teams without much strategic insight, which decreases the probability of Player 4 being Merlin.
Dictionary:
(0: (0, 'stayed the same'). 1: (0, 'stayed the same'), 2: (2, 'increased significantly's ) 3: (0, "stayed the same'), (-2, "decreased significantly")
Under dialouge analysis, besides focusing specific role, also have LLM target good and evil in the game, which is broader in terms role playing. Below the prompt for dialogue analysis regarding to Good and Evil.
60

---

Published as a conference paper at ICLR 2025
Prompt for dialogue analysis: Good and Evil
<Systemm prompt>
<Game rules>
<Discussion history?
<State description>
Based on the discussions this round, for each player in players 0, 1, 2, 3, 4, do you think the probability of the player being Evil (2) increased significantly (1) increased slightly (0) stayed the same (-1) decreased slightly or (-2) decreased significantly and why? Begin with your reasoning and end with a dictionary of player to your multiple choice answer, i.e. {0: (2, 'increased significantly"), ... 4: (0, 'stayed the same")) )}. Make sure you include quotes around the dictionary values that are strings.
Here's s an example:
Thought: Player 4's speech seems overly enthusiastic and focused on unity and cooperation, which could be tactic divert attention from their true identity raises suspicion and increases the probability of Player 4 being Evil. On the other hand, Player 3's response Servant of Arthur more focused on the success of the Quests and unity. which aligns with the goals of Good and decreases the probability of Player 3 being Evil.
Evil player. This
Dictionary: (0: (0, 'stayed the same'), 1: (0, 'stayed the same'). 2: (2, 'increased signifi- cantly'), 3: (-2, "decreased significantly") ) 4: (0, "stayed the same")]
Below the dialogue analysis generated by LLM on Good and Evil.
LLM generated dialogue analysis: Good and Evil
Thought:
Player I's speech is aligned with the goals of Good and focuses on ensuring the success of the Quests, which decreases the probability of Player 1 being Evil. Player 2's speech also emphasizes unity and cooperation, which is line with the goals of Good and decreases the probability of Player being Evil. Player 3's response suggests including themselves in the team, which may raise suspicions of wanting to secure a spot on the quest, potentially increasing the probability of Player being Evil. Player 4's speech seems overly enthusiastic and focused on unity and cooperation, which could be a tactic to divert attention from their true identity as Evil player, increasing the probability of Player being Evil. Player 0's speech suggests different team composition that may bring di- verse of skills and viewpoints, potentially decreasing the probability of Player being Evil.
Dictionary:
(0: (-1, 'decreased slightly"), ), 1: (-1, 'decreased slightly'), 2: (1, 'increased slightly'). ), 3: (1. 'increased slightly'). 4: (2, 'increased significantly") }
61

---

Published as a conference paper at ICLR 2025
K
OTHER ABLATION STUDIES
K.O.1 BASE LLM MODEL
We show the performance of different base models in Figure 16.
GPT3
2
-8
Category
Game play performance of base LLM models six card GOPS: GPT3.5 and GPT4.0. We see that the two language models perform similarly with our method.
Figure 16:
K.0.2 SEARCH BUDGET
How does the effectiveness of the search+LLM agent scale with regards to the search budget? Does having larger search process help achieve better performance?
Table Average score difference for MCTS (num rollout=32) + LLMFunction (Playerl, top-3 func- tions shown in the table) vs. MCTS (num_rollout=3)) + RandomRollout (Player2, ham_rollout=10) 100 games for each experiment;
Best Func.
2nd Best Fune. Player
3rd Best Func.
budget
Player
Player
Player
Player
Player
16
-0.91
0.91
-0.7
0.7
-0.88
0.88
32
-0.95
0.95
0.44
-0.44
-0.73
0.73
64
-1.14
1.14
1.15
-1.15
0.46
-0.46
128
-1.28
1.28
0.36
-0.36
0.25
-0,25
256
-0.45
0.45
-0.85
0.85
-0.42
0.42
inf
-1.5
1.5
-2.26
2.26
-1.03
1.03
62

---

Published as a conference paper at ICLR 2025
0010
-14
-2.6
Peformance
-0200
-.0
-.0
2.2
-2.4
0.35
13.0
12.5
15.0
17.
200
10.0 Evalution
12.5
15.0
250
Evolution
(a) Avalon
(b) GOPS
Figure/ 17: The training curves of the value heuristic via reinforcement learning in five-player Avalon and five-card GOPS, averaged across five independent runs. The solid lines show the mean and the shaded areas depict the standard deviation.
L DETAILS ON LEARNING THE VALUE HEURISTIC VIA REINFORCEMENT LEARNING
We employ Monte-Carlo based RL approach (Sutton Barto (2018)) to train a value heuristic for both five-player Avalon and five-card GOPS games. To do so, construct MSE loss in each episode for training the value function, i.e.,
N
T
Σ 1=
(v:()) Score'(si))
argmin
where N represents the number of actors, (s),, 1,2, .N denotes the value function for each actor, and T is the time horizon. Notice that s, and Score denote the state time step t and the corresponding cumulative reward for each actor, i.e., ΣT R,(st, (z)) is worth pointing that Score"(s)) (the cumulative reward starting from 82) is the unbiased estimate of the value function V (s:).
For both Avalon and GOPS games, the value function (s:)) is predicted by a neural network. We then train the value function network by minimizing the aforementioned loss function In Avalon, we consider 20 evolutions (epochs) for the training process. At the end of each evolution, 30 batch (episodes) are generated and used train the value function network, i.e., total of 600 episodes for training. In GOPS, we train by 20 evolutions as well while considering 60 batch runs each (1200 episodes total). We evaluate the final performance over 10 episodes both games, The neural network is constructed by multilayer perceptron (MLP) with 2 hidden layers. We select a hidden layer size of 128 128 for Avalon and that of 64 64 for GOPS. Likewise, the chosen learning rates are 5e 4 and 8e 4, respectively. The value function is expected to predict the score for each player the game, e.g., two GOPS and number players for Avalon. All experimental hyper-parameters are summarized in Table 8.
episodes.
Having introduced the set up, one can observe Figure 17 an increased performance of RL-trained value heuristic in both five-player Avalon and five-card GOPS games. This validates the improvement for training value heuristic via reinforcement learning within limited evolutions.
63

---

Published as a conference paper at ICLR 2025
Table 8: Summary of experimental hyper-parameters in RL-training value heuristic
Parameters
Avalon
GOPS
Type of neural network
MLP
MLP
Number of hidden layers
2
Hidden layer size
128* 128
64%64
Learning rate
5e-4
8c-4
Output dimension
# of players
2
Number evolutions
20
20
Number of batch runs
30
60
Number of final batch runs
10
10
M EXPERIMENTAL COMPUTE RESOURCES
All experiments in this work were performed on workstation with an NVIDIA GeForce RTX 3070 GPU, Intel Core 10900 CPU at 2.80 GHz, and Macbook Pro.
64

---

Published as a conference paper at ICLR 2025
N IMPROVEMENT METHOD BASELINES
Line search is a straightforward iterative process that continuously builds upon the most recent improved strategy. In each iteration, a strategy is generated and evaluated based on feedback from the environment. The feedback is then used to enhance the strategy via the LLM, and this cycle is repeated similar the Reflexion framework (Madaan al., 2024). The essence of line search lies in its focus on immediate feedback, where only the latest strategy is considered for improvement, ensuring that progress is always aligned with the most recent understanding of the problem space.
Greedy search takes more competitive approach by selecting the pert-performing strategy from the last generation to serve as the foundation for the next eycle of improvements. During each cycle, the best strategy is used to generate n variations, each an attempt at improvement. These variations are evaluated, and feedback from the environment gathered to determine the best candidate for the subsequent cycle. This method is inspired by the Eureka framework (Ma et al., 2023), where LLMs are leveraged to iteratively refine reward functions in a manner akin to evolutionary algorithms, focusing winner-takes- selection mechanism.
Best-first search generalizes the improvement process by considering the top strategies at each iteration, as opposed to focusing on single best option. This is reminiscent of beam search but with a flexible branching factor that allows for the generation of multiple strategies from each selected candidate. By expanding multiple promising pathways simultaneously, the search can escape local optima and explore broader solution space. This approach is related to the Tree of Thought method (Yao et al., 2024), which similarly employs a branching mechanism explore various strategies in parallel during self-improvement cycles.
Best-first search with thought enhances best-first search by incorporating a reasoning layer into the improvement process. Before generating new strategies, the LLM is prompted to first refine the underlying "thoughts" or decision-making processes that led the generation of the top strategies, including possible improvement ideas, before generating new strategy. This meta-cognitive step draws from the React framework (Yao et al., 2022b), which emphasizes reasoning and actions during strategy development, adding an introspective element that encourages deeper exploration of strategy refinements.
STRATEGIST introduces an additional layer of guidance through the use of an idea queue, Q. In this approach, ideas are generated and stored in Q. providing a reservoir of potential directions for improvement. The LLM uses these ideas steer the strategy enhancement process, enabling more structured exploration. By separating idea generation from strategy improvement, STRATEGIST facilitates more focused and deliberate search, ensuring that each iteration explores both immediate refinements and novel directions.
All methods were with the same computational budget-i.e. each method allowed to generate the same number of improved cnntegies-ensuring a fair comparison across approaches in our experiments.
We display a scaling curve for the various improvement methods in Figure 18.
65

---

Published as a conference paper at ICLR 2025
Computation budget vs performance for different methods
1-
0.5
Score
-1.5
-2-
-2.5
20k
40k
60k
Number of Output Tokens
Method
Thought BFS
Greedy
Our method
Number of output tokens from LLM vs game-play performance of generated value heuristics for 6-card GOPS. Each method was rum 20 times at different token budgets, and the best function generated by each method was benchmarked against a baseline opponent policy.
Figure 18:
O HUMAN EVALUATION DETAILS
We recruited ten experienced graduate students to participate in a study involving a total of forty games of Resistance: Avalon with six players per game. Each human participant was randomly assigned a character, while the remaining five characters were controlled by STRATEGIST agents. The characters used in the games were follows: Merlin, three Servants of Arthur, Minion of Mordred, and Assassin.
Participants completed surveys both before and after the games. In the pre-game survey, participants rated their familiarity and skill level with Resistance: Avalon a scale of to 6. The results, summarized in Figures and 20, indicate that participants were generally familiar with the game's rules and displayed strong skill levels.
How familiar are you with the rules of Resistance: Awalon?
Putorfag
20
Never Teard 2f
Way Aemila
Panskarit Sonel
Figure 19: Familiarity of human participants with Resistance: Avalon.
The study consisted of two experimental setups. Participants played game of Avalon with dialogue against the STRATEGIST agents, which lasted approximately 30-40 minutes. They also played three games of Avalon without dialogue, each lasting about 10 minutes.
66

---

Published as a conference paper at ICLR 2025
How you you Redistanre: Avaion?
60
30
pkyo
Figure 20: Skill Level of human participants in Resistance: Avalon.
After completing the games, participants rated the STRATEGIST agents seven key metrics (Figure 4) using a scale from to 6. Additionally, the experimenter independently evaluated the human participants the same metrics word that best described the STRATEGIST agents from the following options: logical, deceptive, emotional, aggressive, cautious. Similarly, the experimenter selected word describe each human participant's playstyle. The results of these qualitative assessments are summarized Figure 5.
consistency. Participants were also asked select single
67

---

Published as a conference paper at ICLR 2025
P RELATED WORKS DETAILS
In this section, we provide an in-depth discussion of related works that were briefly mentioned the main paper:
ICL-AIL (Fu et al., 2023) includes textual feedback and descriptions of previous self play experiences as few-shot prompts to improve the negotiation abilities of the LLM-agent. The framework iteratively improves negotiation strategies by incorporating Al-generated feedback and historical dialogues.
SPAG (Cheng et al., 2024) employs reinforcement learning to train an LLM-agent for the game Adversarial Taboo. The agent learns reasoning and adversarial strategy improvements through self-play, resulting in enhanced performance across various reasoning benchmarks.
Agent-Pro (Zhang et al., 2024) updates textual memories (prior experiences) and tex- tual beliefs about itself and the environment through reflection it plays Blackjack and Texas Hold' em. The agent's ' policy optimization enhances its decision decision-making making capabilities, outperforming baseline models.
LARLWorf (Xu al., 2023b) integrates reinforcement learning optimize the action distribution suggested by the LLM. This approach addresses the biases the LLM's suggestions and results in superior strategic play in the social deduction game Werewolf.
ComWorf (Xu al., 2023a) creates LLM-agent that reflects past experiences to improve its performance in the game Werewolf. The framework uses retrieval and reflection prior interactions without requiring additional parameter tuning.
EnRea Wolf (Wu et al., 2024) leverages dataset of human games to fine-tune an LLM- agent for the Werewolf game. This fine-tuning improves both reasoning and communication capabilities, allowing the agent to surpass standard LLM performance.
68


Reviews:
[{"review_id": "Y4sKxpmAtz", "reviewer": "Reviewer_XeVt", "summary": "The paper presents STRATEGIST which combines LLM-generated high-level strategies with Monte Carlo Tree Search (MCTS) for refined action execution. STRATEGIST uses population-based self-play to optimize strategies. The paper presents experimental results in two game environments: GOPS and The Resistance: Avalon. The results indicate that STRATEGIST outperforms traditional RL agents and pure LLM-based methods.", "questions": "1. How does the proposed method compare to other RL-LLM approaches? Both conceptually and experimentally?\n\n2. Is STRATEGIST properly randomizing its actions in the actual play of Avalon?\n\n3. Are there any human evaluation results?", "limitations": "", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The idea of using LLM to generate high-level strategy and use MCTS to get low-level strategy is interesting.\n\n2. The proposed method is evaluated in two game environments, one simple and one complex, which is good.", "weaknesses": "1. Lack of Competitive Baselines: The paper compares with methods that do not use LLM at all (like DeepRole) and methods that only uses LLM but no RL. However, the comparisons exclude more recent RL-LLM hybrid methods that would provide a fairer benchmark for STRATEGIST's effectiveness. In fact, in the past two years, there are a number of papers that combines RL with LLM to play complex strategic multi-agent games that involve natural-language based communication. For example, the paper mentioned the Cicero paper by FAIR, but there is no comparison with the method used in the Cicero paper. There are a lot more papers following up the Cicero paper, and can potentially be used for games like Avalon. Here are a few example papers: 1). Exploring large language models for communication games: An empirical study on werewolf. 2). Language agents with reinforcement learning for strategic play in the werewolf game; 3). Enhance reasoning for large language models in the game werewolf; 4). Agent-pro: Learning to evolve via policy-level reflection and optimization. \n\n2. Limited Analysis on Strategic Randomization: Strategic randomization is essential in hidden-role games like Avalon. However, the experiment section does not show how well STRATEGIST presents deceptive behavior in a properly randomized fashion. \n\n3. Absence of Human Evaluation: Despite STRATEGIST's applicability to discussion-based games, there is no reported evaluation of the model's interactions with human players, which would provide insights into its performance in realistic scenarios.\n\n4. Comparison of Bi-Level Structure: Cicero also uses a bi-level structure, although in a different way as this paper proposes: In Cicero, it uses iterative learning methods to choose the intent at the high-level, and uses LLM to generate low-level actions. Cicero's bi-level structures ensures strategic randomization at the high level. In this paper, it is not well explained why this paper's bi-level structure is more effective than Cicero's.\n\n5 (minor). Ambiguity in RL Positioning: The abstract and methodology sections position MCTS as an RL method. However, MCTS is typically classified as a heuristic search within the RL framework and lacks key RL characteristics, such as learning policy updates from experience. So I would suggest the authors carefully choose the wording to avoid confusing the readers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "fW1KfH9fZ5", "reviewer": "Reviewer_GQJM", "summary": "This paper introduces STRATEGIST, which is a framework to optimize the strategy induced by LLMs through population-based self-play simulations without the need for any training data. The effectiveness of STRATEGIST in learning optimal strategies is demonstrated against strong baselines on Game of Pure Strategy (GOPS) and the Resistance: Avalon.", "questions": "- What makes the self-play method in STRATEGIST better than previous self-play methods for LLMs, in terms of improving the LLM-induced strategy? I would expect a clear comparison against previous self-play methods in LLMs both in terms of the methodology (as mentioned in the weakness) and experiment study (For instance, ablation studies comparing STRATEGIST to other LLM self-play methods).", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written and well organised.\n- The description of different components in STRATEGIST is clear.\n- The experimental results are strong and comprehensive.", "weaknesses": "- The differences and advantages of the self-play mechanisms of STRATEGIST in improving the strategy against previous related work on self-play for LLMs is unclear.  It would be helpful to provide a clear comparison (e.g. a table) between the self-play mechanism in STRATEGIST and previous self-play methods for LLMs  (e.g. [1] [2] ...) .\n\n[1] Yao Fu, Hao Peng, Tushar Khot, and Mirella Lapata. Improving language model negotiation with\nself-play and in-context learning from ai feedback. arXiv preprint arXiv:2305.10142, 2023.\n\n\n[2] Cheng, Pengyu, et al. \"Self-playing Adversarial Language Game Enhances LLM Reasoning.\" arXiv preprint arXiv:2404.10642 (2024)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "OnhhL4p261", "reviewer": "Reviewer_u9ZM", "summary": "The paper presents Strategist, a novel framework that leverages Large Language Models (LLMs) for strategic skill acquisition in multi-agent games through a bi-level tree search and self-improvement mechanism. The approach aims to enhance both high-level strategy formulation and low-level execution by utilizing self-play simulations and LLM-based reflections. The framework is evaluated on two games, Game of Pure Strategy (GOPS) and Resistance: Avalon, demonstrating improved performance over baseline methods.", "questions": "Please see Weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Novel approach: the combination of LLMs with a bi-level tree search for strategy improvement is a novel method for enhancing performance in complex multi-agent games. Addressing both high-level strategic planning and low-level execution allows for improvements of agent capabilities.\n2. Good empirical evaluation: The authors conduct various ablation studies and additional experiments comparing their method with established baselines like DeepRole and ReCon, providing a broader context for their contributions.", "weaknesses": "1. Reliability of population-based self-play simulation: the authors use round-robin games between top-ten strategies to evaluate the performance of high-level strategies. Since games like Avalon have high uncertainty and the variance of the simulation result is large, it would require many simulations (like hundreds) to get a reliable evaluation of these strategies. However, these simulations would take a long time for LLM inferences. In addition, LLM usually cannot take so many trajectories as input due to the limited context length. It would be better if the authors could provide results to justify the reliability of population-based self-play simulation results.\n2. Modular improvement Assumptions: the assumption that improvement ideas are universally applicable across different strategies requires further justification. Improvement ideas may interact with specific strategies in unique ways, possibly leading to unintended consequences or limited effectiveness when applied broadly. While the authors argue that improvements are additive and generalizable, empirical evidence demonstrating this across a variety of strategies would strengthen the claim.\n3. Statistical significance and result variability: the reported variances are very large and show significant overlap in many results like Table 1, 2, 3, etc., which implies that the proposed methods might not be delivering substantial enhancements in these test environments. For example, in Table 2, the result of Alpha-go is $-0.39\\pm0.71$, and the result of Strategist is $0.33\\pm1.21$. The variance is too large to determine whether the new method offers improvements over existing baselines.\n4. Suggestions on some related works: the experiments on mainly conducted on the social deduction game named Avalon. A closely related game is Werewolf and there are some recent works like [1,2,3] on building LLM AI agents for these games and could be added to the related work section.\n\n[1] Yuzhuang Xu, et al. \"Exploring large language models for communication games: An empirical study on werewolf.\" arXiv preprint arXiv:2309.04658 (2023).\n\n[2] Zelai Xu, et al. \"Language agents with reinforcement learning for strategic play in the werewolf game.\" arXiv preprint arXiv:2310.18940 (2023).\n\n[3] Bailis, Suma, Jane Friedhoff, and Feiyang Chen. \"Werewolf arena: A case study in llm evaluation via social deduction.\" arXiv preprint arXiv:2407.13943 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "c5gewYvgQz", "reviewer": "Reviewer_MWLe", "summary": "The paper presents STRATEGIST, a framework that combines LLMs with MCTS for learning optimal strategies in competitive multi-agent games. The approach uses LLMs to generate and iteratively improve high-level strategies, which are then refined into executable policies using MCTS. The framework is evaluated on two games: GOPS and Avalon, showing superior performance compared to traditional RL methods and other LLM-based approaches.", "questions": "- What happens when the LLM generates syntactically correct but semantically inconsistent or illogical strategies? How does the framework detect and handle such cases? \n- How does the method prevent the idea queue from becoming dominated by similar or redundant improvement suggestions? \n- What happens when there are multiple valid interpretations of a strategy? How is the most appropriate one selected? \n- Are the proposed method verified to learn general strategies instead of overfitting to specific feedback examples?\n- Could the method combine successful elements from different strategies into new hybrid approaches?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Integration of LLMs with MCTS in a bi-level framework that leverages their complementary strengths.\n- Clear empirical validation through rigorous experiments.\n- The paper is well written and easy to follow", "weaknesses": "See the questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "lHdjD7gMxt", "reviewer": "Reviewer_DMCE", "summary": "This paper proposes a new complicated method named Strategist for using LLMs to generate strategies and ideas for multi-agent games.\n\nIn summary, there are two levels.\n\n- Low-level self-play tree-search provides value for learning and updating skills.\n\n- High-level skill learning module improves skills, both for text-based strategies (in text modality) and for value heuristic functions (in code modality).", "questions": "Please refer to Weaknesses. Especially,\n- Could you report the standard error of the median in addition to the IQR for all results in Table 1? Could you improve the clarity of Figure 4, perhaps by separating the data into multiple plots or using a different visualization method.\n- Could you discuss potential limitations or biases introduced by using textual strategies only for dialogue actions? Have you considered any alternative methods to unify the approach of both types of actions, and if so, why they were not pursued?\n- Could you clarify what metric is being reported in the 'Winrate' column for GOPS in Table 2, as negative values are unexpected for winrates? If this is an error, please provide the correct values.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- The idea to learn skills (strategies) not only for (1) text strategy guide, but also for (2) a value heuristic is inspiring. Utilizing LLMs for generating and improving value functions in code modality seems to be an innovative practice that utilizes their ability to reason and to write code. Moreover, the value functions generated could be used to search for good actions for non-speech phases of the game. To use these generated functions rather than to use LLMs could be cost-efficient and time-efficient.\n- Improvement is shown. Moreover, performance scales with improvement of inference budget.\n- Extensive experiments and details are provided to show the improvement of value functions and text strategies.", "weaknesses": "- Some results measured have no or confusing error analysis. For example, in Table 1, the median scores and IQR of quantities measured are reported, but the error range of the median scores is not reported. I recommend the authors also to report $median\\pm error(median)$, in which the error is introduced because number of experiments is limited. Moreover, I wonder if enough duplicated experiments are carried out to prove that Strategist is better than BFS with Thought w.r.t. Avalon Value Heuristic. Also the presentation in Figure 4 is a bit chaotic.\n\n- From section 2 it seems that the value functions are mainly for non-dialogue actions, and the text-based strategies are mainly for dialogue actions, and the action planner based on MCTS tree search described in Appendix F seems to be searching on the values generated by heuristic value functions. According to Appendix G it seems that the authors do not conduct similar search process on dialogue actions, and speeches are mainly provided through a rather traditional prompt-based approach. Of-course this does make sense given that speech is more related to text and is harder to assign scores, but these different approaches for non-dialogue and dialogue actions give a sense of fragmentation.\n\n- There are typos. For example, in table 2 for GOPS the averaged 'winrate' of AlphaGo and DeepRole is negative (I assume it is a typo here: do the authors mean Heuristic Value or other scores?); in table 4 there are only results for winrate but no assassination rate is reported (though mentioned in table caption).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)