Research map / Large language models / Agents, code and math
GameTraversalBenchmark: Evaluating Planning Abilities Of Large Language Models Through Traversing 2D Game Maps
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces GameTraversalBenchmark (GTB), a set of 150 LLM-generated 2D grid game maps on which LLMs must generate action sequences to traverse ordered objectives, scored by a composite GTBS metric; evaluates many LLMs and preliminarily o1.
Problem
Whether LLMs can plan by traversing 2D grid-based game maps represented as character strings, a setting rarely seen in training data, and how current LLMs compare on such planning.
Approach
A benchmark of 150 Word2World-generated 2D maps where LLMs output action sequences per objective; a composite reward score (GTBS) combines path length, generation errors, and distance to objective, with A* optimal paths as reference.
Key results
- GPT-4-Turbo achieves the highest zero-shot GTBS of 44.97%, and 52.07% one-shot.
- o1 scores 67.84% GTBS in a single preliminary run, above GPT-4-Turbo but below 70.
- Random-RP baseline scores 3.04 GTBS, showing the task requires planning beyond random sequence length guessing.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add one extra attempt per objective when the exact coordinate was not reached (ablation) | GPT-4-Turbo · GTB | GTBS: 44.97 ± 0.22 -> 52.07 ± 0.25 | Helped |
| add one extra attempt per objective when the exact coordinate was not reached (ablation) | LLaMa-3-70B · GTB | GTBS: 11.39 ± 1.36 -> 15.17 ± 1.53 | Helped |
| add one extra attempt per objective when the exact coordinate was not reached (ablation) | Gemma-7B · GTB | GTBS: 15.65 ± 0.21 -> 13.63 ± 0.31 | Hurt |
Surprising findings
- Several LLMs (all except the top four) score below a Random-FP baseline that uses the correct path length with random actions.
- Smaller LLMs tend to produce shorter paths but fail to produce correct actions.
Limitations
- Maps are static and the benchmark only tests pathfinding, one dimension of planning.
- Action space limited to four discrete actions.
- A single static prompt is used for all LLMs, which may disadvantage smaller models.
Experimental setup
Datasets: GameTraversalBenchmark maps extracted from Word2World
Benchmarks: GameTraversalBenchmark (GTB)
Metrics: GTBS MGE MPL MAT Top-0 accuracy Top-1 accuracy Top-5 accuracy
Baselines: Random-FP Random-RP Claude-3-Opus Claude-3-Sonnet Claude-3-Haiku GPT-4-o GPT-3.5-Turbo Mixtral-8x7B
Builds on: Word2World A* search PlanBench
Closest papers by meaning
- Mastering Board Games by External and Internal Planning with Language Models (ICML 2025 · similarity 0.89)
- On the self-verification limitations of large language models on reasoning and planning tasks (ICLR 2025 · similarity 0.88)
- Large Language Models Play StarCraft II:Benchmarks and A Chain of Summarization Approach (NeurIPS 2024 · similarity 0.88)
- GameArena: Evaluating LLM Reasoning through Live Computer Games (ICLR 2025 · similarity 0.88)
- GTBench: Uncovering the Strategic Reasoning Capabilities of LLMs via Game-Theoretic Evaluations (NeurIPS 2024 · similarity 0.88)
- Monte Carlo Planning with Large Language Model for Text-Based Game Agents (ICLR 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.