PaperlayerView exact revision on arXiv

Source-linked AI summary

AvalonBench: Evaluating LLMs Playing the Game of Avalon

Jonathan Light, Min Cai, Sheng Shen, Ziniu Hu

arXiv:2310.05036v3cs.AIcs.CL

TL;DR

Avalon tests agents on deduction, coordination, persuasion, and deception, making it a testbed for studying language understanding and reasoning. AVALONBENCH provides a game environment, rule-based baselines, and ReAct-style LLM agents; evaluations find that LLMs struggle to formulate and execute simple strategies. In good-role play, the best model's win rate was 22.2%, compared with 38.2%.

  • Problem

    Avalon requires agents to reason about identities while coordinating and communicating under pressure to deceive, making it a testbed for studying language understanding and reasoning.

    Source: §1 · p. 2

  • Method

    AVALONBENCH combines a Resistance Avalon game environment, deterministic rule-based baseline bots, and ReAct-style LLM agents with phase-specific tutorials and prompts.

    Source: §1 · p. 3

  • Results

    LLMs could deduce identities from discussion but struggled to formulate and execute simple strategies; in good-role play, the best model's win rate was 22.2%, compared with 38.2%.

    Source: §1 · p. 3, §7 · p. 11

  • Takeaways & Limitations

    AVALONBENCH can serve as a testbed for developing LLM agents with better decision-making and communication skills.

    Source: §7 · p. 11

    For comparison with naive strategies, the base implementation feeds LLMs mission information after each quest but not the publicly visible voting history.

    Source: §3.2 · p. 6

Abstract

from arXiv · show

In this paper, we explore the potential of Large Language Models (LLMs) Agents in playing the strategic social deduction game, Resistance Avalon. Players in Avalon are challenged not only to make informed decisions based on dynamically evolving game phases, but also to engage in discussions where they must deceive, deduce, and negotiate with other players. These characteristics make Avalon a compelling test-bed to study the decision-making and language-processing capabilities of LLM Agents. To facilitate research in this line, we introduce AvalonBench - a comprehensive game environment tailored for evaluating multi-agent LLM Agents. This benchmark incorporates: (1) a game environment for Avalon, (2) rule-based bots as baseline opponents, and (3) ReAct-style LLM agents with tailored prompts for each role. Notably, our evaluations based on AvalonBench highlight a clear capability gap. For instance, models like ChatGPT playing good-role got a win rate of 22.2% against rule-based bots playing evil, while good-role bot achieves 38.2% win rate in the same setting. We envision AvalonBench could be a good test-bed for developing more advanced LLMs (with self-playing) and agent frameworks that can effectively model the layered complexities of such game environments.

1 Introduction

Avalon combines hidden identities and asymmetric information with discussion that requires deduction, coordination, persuasion, and deception. AVALONBENCH evaluates multi-agent LLMs in this setting, and the authors report a substantial gap between LLMs and baseline bots.

1 Introduction

  • Avalon challenges agents to infer motives from votes and dialogue, coordinate and persuade teammates, and conceal identities; most good players lack the identity information evil players share.The game also proceeds through team selection, voting, and mission phases.Source: §1 · p. 2
  • AVALONBENCH combines a Resistance Avalon environment, deterministic rule-based baseline bots, and ReAct-style LLM agents with phase-specific tutorials and prompts.The environment records player actions and advances the game.Source: §1 · p. 3
  • Good-role win rate was 22.2% for the best model, compared with 38.2%; evil-role win rate was 66.7%, compared with 61.8%.The authors report these comparisons from evaluations against naive baselines.Source: §1 · p. 3
  • Current LLM agents still lack the deduction, persuasion, negotiation, and deception capabilities needed to play Avalon well, and can fail against simple baseline players.The authors identify integrating decision-making techniques with LLMs as a direction for further exploration.Source: §1 · p. 3

2 Pipeline of Avalon

Avalon cycles through role-dependent decisions in team selection, voting, and quests, with public discussion supporting deduction, negotiation, and team approval. After three successful missions, an assassination attempt can still give evil the win if Merlin is targeted.

2 Pipeline of Avalon

  • The game alternates among team selection, voting, and quest phases until an end condition, with discussion also occurring between phases.Figure 3 depicts game states and transitions, marking decision phases with round boxes and the acting role in brackets.Source: §2 · p. 3, Figure 3 · p. 4

2.1 Roles

  • The four roles differ in their hidden information and powers: Merlin and Assassin know player sides, while the Assassin can target a player at game end.Servants know no identities, and Minions know sides but not specific roles; Merlin must conceal his identity while discreetly guiding good players.Source: §2.1 · p. 3

2.2 Actions for each Phase

  • Leaders propose teams of mission-specific size; players vote publicly, and a strict majority advances the team unless four consecutive proposals were rejected.Selected players vote anonymously to pass or fail; revealed failure counts determine mission outcomes, and three failed missions give evil the win.Source: §2.2 · p. 4

2.3 Discussion

  • Public discussion centers on mission observations, suspected identities, and plans; leaders seek advice and support, while persuasive accusations need justification.Players infer identities from actions such as team proposals, votes, and mission outcomes, then negotiate over proposed teams.Source: §2.3 · pp. 4–5

2.4 Game Ending and Assassination

  • Three successful missions trigger an assassination phase in which evil wins if the Assassin targets Merlin; otherwise good wins.The Assassin may discuss with other players before choosing a target.Source: §2.4 · p. 5

3 Implementation of LLM Agent

The implementation uses ReAct-style LLM prompts to generate game actions, dialogue, and history summaries. It separates action parsing from generation and recursively summarizes game history, while limiting post-quest input to mission information for baseline comparison.

3 Implementation of LLM Agent

  • The LLM agent generates actions, dialogue, and game-history summaries, with prompts organized into four functional categories.The implementation uses a Reason-then-Action approach with zero-shot Chain-of-Thought prompting for decisions.Source: §3 · p. 5, §3.1 · p. 5

3.1 Actions

  • For actions, the LLM receives rules, role information, a game summary, current-round discussion, and an action request; a separate LLM parses its response into engine-readable actions.The separate parser achieved 100% action-format success in pilot experiments, while vanilla ReAct could not guarantee consistent formatting.Source: §3.1 · pp. 5–6

3.2 Summary

  • Recursive history summaries combine the previous summary, current discussion minutes, and mission outcome to manage game histories that can reach thousands of dialogue words.The baseline comparison implementation feeds LLMs only mission information after each quest, not voting history.Source: §3.2 · p. 6

3.3 Discussion

  • Discussion proceeds in a predefined order, with each player speaking once per round and the leader speaking twice; the resulting transcript informs decisions and summaries.Each LLM is prompted to speak a rule-limited number of sentences, and the discussion context before player i’s turn is indexed by t.Source: §3.3 · p. 6

4 Baseline Strategies

The baseline agents use deterministic, role-specific strategies and generally ignore dialogue and voting history. The Naive Servant tracks possible role assignments and uses mission outcomes to update beliefs and rank teams.

Baseline assumptions

  • Naive baselines use mission failures rather than dialogue or voting history, and assume other players behave similarly; an LLM may generate their dialogue while decisions remain detached from language.The agents act optimally under those assumptions.Source: §4 · p. 6

Naive Servant

  • The Naive Servant maintains possible good/evil assignments with probabilities, rules out assignments incompatible with observed failures, and prefers teams by probability of containing no evil players.When a mission has no failures, it also favors subsets or supersets of the last successful team.Source: §4 · pp. 6–7

Naive Minion and Naive Assassin

  • Naive Minions approve teams containing evil players, propose teams including themselves, and sabotage missions unless an Assassin teammate is present; Naive Assassins always fail missions they join.The Naive Assassin chooses a random good player to target without using voting patterns.Source: §4 · p. 7

Naive Merlin

  • The Naive Merlin proposes and approves only teams without evil players, making its voting pattern detectable to non-naive Assassins.The paper says future upgraded Merlin baselines may add voting randomness to obscure that pattern.Source: §4 · p. 7

5 Evaluating LLMs Against Baseline Bots

The evaluation benchmarks GPT-3.5 and Llama2 against naive agents in Assassin and Servant settings. LLM performance was poor in several conditions, although discussion was associated with more Merlin assassinations by LLM Assassins.

5.1 Experimental Setup

  • The experiments compared GPT-3.5 and Llama2 with naive strategies in baseline, Assassin, and Servant settings, with discussion enabled or disabled.In the Assassin and Servant settings, the LLM had access to mission outcomes but not voting outcomes; discussion-capable naive agents used a detached LLM for dialogue.Source: §5.1 · p. 8

5.2 Benchmark Metrics

  • The metrics included EVIL mission wins, Merlin assassination rates and accuracy, GOOD win rates, and Servants’ average deduction accuracy.Deduction accuracy compares Servants’ beliefs about player sides with the true sides.Source: §5.2 · pp. 8–9

5.3 Results and Analysis

  • With discussion, LLM Assassins increased the probability of assassinating Merlin, while LLM Servants still performed poorly; without discussion, LLMs performed very poorly against naive strategies.The authors suspect discussion may reveal identity information, while high Servant deduction scores suggest difficulty turning deductions into better decisions.Source: Table 2 · p. 8, Table 3 · p. 8, §5.3 · pp. 9–10

6 Exploring Multi-LLMs Self-Play

In 60 GPT-3.5-turbo self-play games using ReAct with zero-shot CoT, EVIL dominated; case studies showed both strategic behavior and serious mistakes.

Result of Multi-LLM

  • EVIL won 83.3% of the 60 discussion games, versus GOOD's 16.7%.EVIL won 48.3% by sabotaging missions and 35% by assassinating Merlin after three missions passed.Source: §6 · p. 10

Case Studies

  • An Assassin proposed joining two good players to disguise his identity and make them suspect one another after sabotage.Merlin agreed while concealing his identity, using “seems” to signal concern discreetly.Source: §6 · p. 11
  • Another example showed an evil player wrongly targeting a good player and revealing his own identity, while good players rejected the team.The authors say these cases show basic game understanding alongside irrational mistakes.Source: §6 · p. 11

7 Conclusion

The conclusion reports that LLMs can infer identities from discussion but struggle to formulate and execute simple strategies, including avoiding identity leaks. The appendix lists prompts for game setup, actions, discussion, parsing, and other tasks.

7 Conclusion

  • AvalonBench evaluates LLM agents; the conclusion reports identity deduction from discussion alongside strategic failures and frequent evil-identity leaks.The authors propose it as a test-bed for improving decision-making and communication skills.Source: §7 · p. 11

A.1 System Prompt

A.2 Action Prompt

A.4 Parse Prompt

B.1 Examples of Summary

The supplied examples include a recap of quest progress and a player’s belief about another player’s identity.

B.1 Examples of Summary

B.2 Examples of Discussion

The subsection labels three tables as examples of discussion.

B.2 Examples of Discussion

B.3 Example of Voting

Table 28 is identified as an example of voting.

B.3 Example of Voting

C Common Human Strategies

The section sketches human play as meta-dependent and describes tactical and rhetorical techniques players use in Avalon.

C Common Human Strategies

  • Human strategies vary with opponents and role, and include sleeper-agent play, trusted partnerships, and Merlin’s all-evil team tactic.Source: C Common Human Strategies · p. 28
  • Consistency, patience, and agitation are presented as role-sensitive tactics: good players may reject teams to gather information, while evil players may favor quick approval.Source: C Common Human Strategies · p. 28
  • Players can use voting behavior as evidence because they must sometimes vote according to their preferences to achieve desired outcomes.Source: C Common Human Strategies · p. 28
  • Merlin and evil players are advised to conceal their information, while servants may act knowledgeable to mislead evil players about Merlin’s identity.Source: C Common Human Strategies · p. 28
  • Suggested rhetoric includes logical argument, emotional appeals, what-about-ism, and information overload; the text says evil players will not be persuaded in good faith.Source: C Common Human Strategies · p. 28
  • The section closes by emphasizing that every player matters and a side can be only as strong as its weakest link.Source: C Common Human Strategies · p. 28
Loading 2310.05036v3…