PaperlayerView exact revision on arXiv

Source-linked AI summary

Cooperation on the Fly: Exploring Language Agents for Ad Hoc Teamwork in the Avalon Game

Zijing Shi, Meng Fang, Shunfeng Zheng, Shilong Deng, Ling Chen, Yali Du

arXiv:2312.17515v1cs.CL

TL;DR

The paper studies ad hoc teamwork for LLM agents operating in natural-language environments without established coordination protocols. It introduces AvalonPlay and CodeAct, which combines memory retrieval with code-driven reasoning to infer teammate roles. Experiments report effective collaboration, while also identifying hallucinations and a lack of human-player experience as limitations.

  • Problem

    LLM collaboration in complex, natural-language settings without established coordination protocols requires agents to infer teammates’ roles from limited and potentially misleading information.

    Source: §1 · p. 1

  • Method

    The paper introduces AvalonPlay and CodeAct, using memory retrieval and code-driven reasoning to help agents infer new teammates’ roles in multi-round ad hoc teamwork.

    Source: §1 · p. 1, §2 · p. 2, §3.1 · p. 4

  • Results

    CodeAgent achieves the best performance across three metrics against Chain of Thought and ReAct, including a team selection accuracy of 0.830.

    Source: §4.4 · p. 6

  • Takeaways & Limitations

    LLM agents show potential for ad hoc team collaboration, while communication hallucinations and early memory forgetting remain important challenges.

    Source: §1 · pp. 1–2, §4.5 · p. 7

    The study does not incorporate experience pools from human players, limiting comparison with human performance.

    Source: §7 · p. 8

Abstract

from arXiv · show

Multi-agent collaboration with Large Language Models (LLMs) demonstrates proficiency in basic tasks, yet its efficiency in more complex scenarios remains unexplored. In gaming environments, these agents often face situations without established coordination protocols, requiring them to make intelligent inferences about teammates from limited data. This problem motivates the area of ad hoc teamwork, in which an agent may potentially cooperate with a variety of teammates to achieve a shared goal. Our study focuses on the ad hoc teamwork problem where the agent operates in an environment driven by natural language. Our findings reveal the potential of LLM agents in team collaboration, highlighting issues related to hallucinations in communication. To address this issue, we develop CodeAct, a general agent that equips LLM with enhanced memory and code-driven reasoning, enabling the repurposing of partial information for rapid adaptation to new teammates.

1 Introduction

The study frames ad hoc teamwork as natural-language cooperation without stable protocols, where agents must infer teammates’ roles from limited and potentially misleading information. It introduces AvalonPlay and CodeAct to evaluate and improve this capability through memory retrieval and code-driven reasoning.

1 Introduction

  • Ad hoc teamwork requires agents to adapt to teammates and shared goals without pre-established strategies, while inferring roles from limited information and potentially misleading communication.These conditions distinguish the setting from fully cooperative tasks with explicit coordination protocols.Source: §1 · p. 1
  • AvalonPlay evaluates LLM agents in a multi-round, hidden-role game where learners select teammates and adapt strategies without prior coordination protocols.The benchmark uses The Resistance: Avalon to simulate natural-language ad hoc teamwork.Source: §1 · p. 1
  • The study observes that LLM agents may hallucinate, forget early information, and provide inaccurate or misleading responses during collaboration.These issues can include inconsistencies between prompts, reasoning, and generated actions.Source: §1 · p. 1
  • CodeAct addresses these issues with memory retrieval, code-driven reasoning about potential teammate roles, and action-oriented use of interaction knowledge.The approach is designed as a general agent rather than a task-specific coordination protocol.Source: §1 · pp. 1–2
  • The paper explores LLM agents’ ad hoc teamwork capabilities and reports comprehensive AvalonPlay experiments demonstrating the proposed agent’s effectiveness.The experiments compare backend models, natural-language communication, and prompting strategies.Source: §1 · p. 2

2 The AvalonPlay Benchmark

AvalonPlay is a language-based, multi-agent benchmark for ad hoc teamwork in which agents with hidden roles must adapt their team strategies across multiple quest rounds. It specifies role-dependent information, a staged game pipeline, and structured observations delivered by a non-interactive moderator.

2 The AvalonPlay Benchmark

  • AvalonPlay evaluates ad hoc teamwork through multi-round, language-based gameplay with limited knowledge of other agents’ roles.Each round selects a leader who must infer teammates’ roles and intentions while dynamically adapting strategy.Source: §2 · p. 2

2.1 Teammate Role

  • The benchmark uses seven players assigned to six roles across just and evil factions, with the just side disadvantaged by more limited role information.Merlin recognizes factions, Percival sees Merlin-or-Morgana ambiguity, Loyal Servants have no special knowledge, and evil roles recognize teammates.Source: §2.1 · p. 2

2.2 Pipeline

  • Each game has five rounds combining leader assignment, team selection, discussion and voting, and quest execution.Team sizes are n1 = 2, n2 = 3, n3 = 3, n4 = 4, n5 = 4; teams require a majority vote and may be forced after five failed approvals.Source: §2.2 · pp. 2–3
  • Quest success depends on evil-member votes: sabotage occurs when Qi ≥1 in rounds 1–3 or Qi ≥2 in rounds 4–5.Just-side members approve quests while evil-side members oppose them.Source: §2.2 · p. 3
  • The benchmark includes an assassination phase, but the study evaluates teamwork rather than assassination accuracy.The Assassin identifies Merlin after all rounds, and this feature is retained for prospective future research.Source: §2.2 · p. 3

2.3 Observation Understanding

  • Agents receive structured observations containing global rules and role information plus real-time game history and action descriptions.A moderator supplies action descriptions and records gameplay events without interacting with the LLMs.Source: §2.3 · pp. 3–4

3 Methodology

CodeAct addresses teammate-role reasoning in ad hoc teamwork with memory retrieval, code-driven reasoning and action, and interpreter-based self-debugging. The method combines historical information with executable programs so leaders can reason about teammates and revise failed code.

3.1 Overview

  • CodeAct transforms complex teammate-role reasoning into flexible code structures rather than task-specific prompts or demonstrations.Its three stages are memory retrieval, code-driven reasoning with action, and interpreter execution with self-debugging.Source: §3.1 · p. 4

3.2 Memory Retrieval

  • The memory system combines key information and recent messages globally, while leader-specific retrieval supplies factual private and public evidence from earlier interactions.Retrieved examples include role-derived uncertainty and failed historical quests used during current team selection.Source: §3.2 · p. 4

3.3 Code-driven Reasoning with Action

  • During team selection, CodeAct processes current private and public information through a zero-shot program that generates intermediate reasoning and actions.The approach uses Python code-like reasoning and is intended to be applicable to other programming languages.Source: §3.3 · pp. 4–5
  • Code-driven reasoning combines semantic intermediate steps with formal code structure and computational tools for inference.This design is intended to make reasoning both expressive and computationally reliable.Source: §3.3 · p. 5

3.4 Code Execution with Self-Debug

  • The agent executes generated programs in a Python_REPL and uses successful outputs to inform decisions.A reflection mechanism lets the leader refine programs before interpreter execution.Source: §3.4 · p. 5
  • When execution fails, CodeAct revises the code using the encountered issue and previous outputs, providing self-debugging during decision-making.The revision loop is part of the code execution stage rather than a separate coordination protocol.Source: §3.4 · p. 5

4 Experiments

The experiments evaluate LLM agents for ad hoc teamwork in AvalonPlay across backend models, communication settings, prompting strategies, and failure patterns. GPT-4 performs best overall, while communication alone does not significantly improve performance and hallucinations remain a challenge.

4.1 Baselines

  • Experiments compare GPT-3.5, GPT-4, and LLaMA 2 agents on both good and evil sides, with and without communication, and using Chain of Thought, ReAct, or CodeAct.The evaluation uses AvalonPlay’s multi-round collaborative tasks and compares agents under several backend and reasoning configurations.Source: §4.1 · p. 5, §4 · p. 5

4.2 Metrics

  • The benchmark measures game win rate by quest, total quest win rate, and team selection accuracy for successful quests.Game Win counts games where the good side completes three of five quests; Quest Win counts successful quests; Team Acc measures successful leader selections.Source: §4.2 · pp. 5–6

4.3 Implementation Details

  • The evaluation uses temperature 0.7 for text generation, temperature 0 for code generation, a global-memory retrieval window of k=15, and randomized role assignments.Random role assignment is used to avoid bias from player turn order.Source: §4.3 · p. 6

4.4 Main Results

  • GPT-4 agents achieve the strongest game and overall quest win rates, with later-round quest success indicating better learning and adaptation than GPT-3.5 and LLaMA agents.The authors therefore use GPT-4 in subsequent experiments.Source: §4.4 · p. 6, Figure 5 · p. 6, Figure 6 · p. 6
  • Communication does not significantly improve GPT-4 self-play performance, possibly because agents can already reason from quest outcomes observed in previous rounds.The result suggests that communication quality and factual verification matter more than adding a communication channel alone.Source: §4.4 · p. 6, Table 2 · p. 7, §4.5 · p. 7
  • CodeAct achieves the best performance across the three metrics, including a team selection accuracy of 0.830, compared with Chain of Thought and ReAct.The comparison targets leader team selection under different prompting strategies.Source: §4.1 · p. 5, §4.4 · p. 6, Table 3 · p. 7

4.5 Quantitative Analysis

  • Multi-turn gameplay exposes memory forgetting: agents often prioritize recent-round information and fail to integrate important early-game observations into later decisions.The analysis identifies this as a recurring issue in cooperative tasks involving communication.Source: §4.5 · p. 7, Table 1 · p. 7
  • Hallucinations include response inconsistencies and counterfactual content, such as incorrect team sizes, votes that diverge from reasoning, and contradictions of established game facts.These problems are less pronounced for GPT-4 but remain possible across all evaluated models.Source: §4.5 · p. 7

5 Related Work

Related work spans LLM agents, multi-agent interaction, and ad hoc teamwork. The paper distinguishes its focus on dynamic, natural-language AHT with LLM-powered agents from prior work using preset protocols, constrained settings, or behavior models trained from data.

LLMs and Agents

  • LLM-agent research extends planning and reasoning through prompting methods such as ReAct, Chain of Thought, and Tree of Thought, alongside memory, reflection, and tool use.This work places AvalonPlay agents within that broader expansion of LLM capabilities.Source: §5 · p. 8

Multi-agent Interaction

  • Multi-agent LLM research assigns distinct roles or uses sandbox environments to study collaboration, debate, complex projects, deception, and leadership.These studies examine both task-performance improvements and emergent behaviors in interacting agents.Source: §5 · p. 8

Ad Hoc Teamwork

  • Ad hoc teamwork seeks cooperation with novel agents and has progressed from preset action rules toward probabilistic, deep-learning, and reinforcement-learning approaches.Prior work also considers communication when teammates follow shared protocols.Source: §5 · p. 8
  • This paper differs by studying LLM-powered ad hoc teamwork in dynamic environments driven by natural-language communication rather than limited multi-agent settings or fixed coordination protocols.It explores how to improve agent performance under those language-based conditions.Source: §5 · p. 8

6 Conclusion and Future Work

The study investigates LLM agents’ ad hoc teamwork capabilities in AvalonPlay and proposes CodeAct to address early memory forgetting and hallucination generation. CodeAct combines factual memory retrieval, code-driven reasoning, action execution, and self-debugging.

6 Conclusion and Future Work

  • CodeAct combines factual memory retrieval, code-driven reasoning with action, and interpreter-based self-debugging to improve cooperation with new teammate roles.The agent retrieves factual information from prior interactions, reasons about potential teammate roles, executes generated code, and self-debugs.Source: §6 · p. 8
  • AvalonPlay exposes LLM agents to ad hoc teamwork with limited role knowledge, requiring leaders to adapt team strategies dynamically across rounds.Source: §6 · p. 8
  • The study identifies early memory forgetting and hallucination generation as challenges arising alongside LLM agents’ reasoning abilities.Source: §6 · p. 8
  • Future work should enable agents to decide autonomously when to communicate, reduce hallucinations, and develop fact-evaluation and verification systems for practical use.The current benchmark uses moderator-guided communication, and the paper identifies factual verification as a promising direction.Source: §6 · p. 8

7 Limitations

The study does not incorporate experience pools from human players, leaving the use of human experience and comparison with human performance for future work.

7 Limitations

  • The study does not incorporate experience pools from human players, limiting current comparison with human performance.Future research will develop robust strategies for leveraging human-player experience.Source: §7 · p. 8

A Global Prompt for Agents

The global prompt supplies AvalonPlay agents with the game rules and role assignments needed for benchmark gameplay. Figure 7 presents the game rules, while Table 4 presents role assignments across agent roles.

A Global Prompt for Agents

  • The global prompt provides the game rules and role assignments used by LLM agents in AvalonPlay.Source: A Global Prompt for Agents · p. 11
  • Figure 7 displays the specific game rule prompt shared by all LLM agents in the AvalonPlay benchmark.Source: Figure 7
  • Table 4 shows role assignments for LLM agents in various AvalonPlay roles.Source: Table 4 · p. 11

B An Example of Code-driven Reasoning Generation

This appendix provides a complete GPT-4 example of code-driven reasoning with action generation. Figure 8 illustrates the example.

B An Example of Code-driven Reasoning Generation

Related papers

Loading 2312.17515v1…