PaperlayerView exact revision on arXiv

Source-linked AI summary

Games Over Observation Spaces in Multi-Agent Capture the Flag

Mae Frost, Michael Amir, Shaunak D. Bopardikar

arXiv:2609.06178v1cs.GT

TL;DR

When optimal policies are impractical, the paper asks how decentralized heuristic teams can shape their behavior in Capture the Flag. It makes defender visibility a strategic choice and uses a Double Oracle approach; experiments report improved defensive outcomes, while noting profile overfitting to policies already considered.

  • Problem

    Finding optimal policies can be infeasible for large teams or graphs, motivating study of how decentralized heuristic teams can shape behavior.

    Source: §1 · p. 2

  • Method

    The paper formulates a zero-sum game between an attacker choosing from a heuristic library and a defense choosing visibility profiles for its fixed policy, solved with Double Oracle and an approximate DRL profile oracle.

    Source: §1 · p. 2, §2.4 · p. 7, §3 · p. 7

  • Results

    The method reduces expected game value from 1 to 0 flag captures in gridworld and from 2 to 0 in a 200-vertex urban environment.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Observation manipulation can elicit improved behavior from a fixed policy and introduce useful heterogeneity without engineering new defense policies.

    Source: §1 · p. 3, §5 · p. 19

    Visibility profiles tend to overfit to attacker policies represented in the sub-game, leaving transfer to policies outside Πa as a key open issue.

    Source: §5 · p. 19

Abstract

from arXiv · show

We consider a multi-agent Capture the Flag (CtF) scenario in a graph-based environment, where a team of attackers seeks to reach designated flag vertices while a defending team attempts to intercept them. In our setting, both teams operate using decentralized heuristic policies. While the attacking team may choose its heuristic from a diverse library of policies, the defense is restricted to playing a single fixed policy. To overcome this limitation, a centralized defense oracle strategically restricts the portion of the graph visible to each of its agents in order to elicit a wider range of emergent behaviors from its fixed policy. We formalize this interaction as a two-player zero-sum game, where the attacker reasons over its library of heuristics and the defense reasons over the combinatorial space of visibility profiles. To solve this intractably large game, we propose a Double Oracle algorithm to find approximate empirical equilibria, and we empirically validate that observation manipulation can improve the defense's performance.

1 Introduction

The paper studies a zero-sum Capture the Flag game with decentralized heuristics, asking how attackers and defenders can shape behavior when optimal policies are impractical. It proposes defense-side observation masking and a Double Oracle method, with experiments showing improved defensive outcomes.

1 Introduction

  • A centralized oracle can restrict each defender’s graph observations, eliciting varied behavior from a fixed policy as an alternative to manually building a large heuristic library.Masking can constrain an agent’s action space, for example steering it toward holding a choke point rather than pursuing a target.Source: §1 · p. 2
  • The method reduces expected game value from 1 to 0 flag captures in gridworld and from 2 to 0 in a 200-vertex urban environment.Both are reported as maximal improvements for the defense against the defined heuristic set.Source: §1 · p. 2
  • The proposed Double Oracle algorithm seeks approximate empirical equilibria, using an exact attacker policy oracle and a DRL-approximated defense profile oracle.The framework is tested in a small gridworld and a larger urban street-map setting.Source: §1 · p. 2
  • Observation manipulation can introduce useful behavioral heterogeneity and support favorable equilibria without engineering new defense policies.The paper presents this as empirical evidence from its defined heuristic settings.Source: §1 · pp. 2–3
  • The work relates its team-based CtF setting to pursuit-evasion and perimeter defense, while distinguishing it from formulations requiring attackers to return to a safe zone.It also connects visibility-profile design to agent-environment co-design [12].Source: §1 · p. 3

2 Problem Formulation

The formulation models graph-based Capture the Flag with decentralized heuristic teams, then gives the defense a strategic choice of visibility profiles while attackers choose from a heuristic library. The resulting zero-sum game evaluates expected flag captures.

2.1 Environment and Agent Formulation

  • The graph-based game uses flag vertices, team starting locations, and fixed team sizes, with attacker starts disjoint from defender starts and flags.The environment is a connected, undirected graph with static flags.Source: §2.1 · pp. 3–4
  • Agents observe the global state and move to adjacent vertices or stay; attackers seek captures, while defenders tag attackers to prevent them.Captures take priority over tags when both would occur simultaneously.Source: §2.1 · p. 4
  • The game ends when a team is eliminated or the time horizon is reached, and the number of possible captures is bounded by attacker-team size.More flags increase the defensive task by adding locations to protect, not the possible payoff.Source: §2.1 · pp. 4–5

2.3 Policy Structure

  • The policy class uses suboptimal, rule-based heuristics that are easier to design and can perform across environments; policies are topologically agnostic and uniformly decentralized.Agents act independently from their observations without shared hidden state or inter-agent communication.Source: §2.3 · p. 5

2.4 Games Over Visibility Profiles

  • With a fixed defense heuristic and an attacker library, the attacker can exploit the static defense, motivating the defense to choose visibility profiles against attacker policies.The profile and attacker policy are selected simultaneously as mixed strategies over their respective spaces.Source: §2.4 · pp. 6–7
  • A visibility profile assigns each defender an induced subgraph, restricting the graph and state information it can use and correspondingly its action space.Profiles are imposed before play, so defenders do not know the true environment.Source: §2.4 · p. 6
  • Each profile subgraph must be connected and include a flag, an attacker starting position, and that defender’s starting vertex.These conditions ensure each restricted subgraph remains a valid CtF environment for the policy.Source: §2.4 · p. 6
  • The game’s minimax objective uses expected flag captures, with attackers maximizing and defenders minimizing the value over heuristic and visibility-profile strategies.The equilibrium strategies are probability distributions over the attacker heuristics and valid visibility profiles.Source: §2.4 · p. 7

3 Methodology

The method uses Double Oracle to search the visibility-profile game through a subgame rather than enumerate the defense’s combinatorial strategy space. An exact attacker oracle and an approximated profile oracle generate responses, so the resulting equilibrium is empirical rather than generally exact.

3 Methodology

  • Double Oracle solves a subgame over generated visibility profiles and attacker policies, avoiding enumeration of the defense’s combinatorial strategy space.The current subgame is solved for equilibrium strategies before each oracle adds a best response.Source: §3 · pp. 7–8

3.1 Attacker Oracle

  • The Attacker Oracle selects an exact best response by searching the finite attacker policy library against the defender’s mixed visibility-profile strategy.Its policy set is much smaller than the space of pure defense profiles.Source: §3.1 · p. 9

3.2 Profile Oracle

  • The Profile Oracle approximates profile selection with a DRL visibility agent that sequentially removes vertices and receives reward after committing a profile.The agent uses an Actor-Critic architecture with a graph neural network, and β on the surrogate reward is annealed from 1 to 0.Source: §3.2 · p. 9, Reward Shaping · p. 10
  • Autoregressive action masking keeps each defender’s subgraph connected and preserves a flag, an attacker start, and that defender’s start.Connectivity masking requires articulation-point computation and may become burdensome on large graphs or teams.Source: Profile Action Masking · pp. 10–11

3.3 On Convergence and Termination

  • Because the DRL Profile Oracle has no formal ε-best-response bound, Algorithm 1 yields an empirical equilibrium rather than generally guaranteeing an exact Nash equilibrium.The standard exact-convergence guarantee applies when both oracles return true best responses.Source: §3.3 · pp. 11–12
  • Algorithm 1 stops when the subgame value changes by less than δ and no new attacker heuristic is added; with accurate U, zero captures also guarantees a true Nash equilibrium.The zero-capture guarantee is conditional on the utility matrix accurately estimating expected game payoffs.Source: §3.3 · p. 12

4 Experiments

Experiments evaluate Algorithm 1 and the approximate Profile Oracle, beginning with a 12-vertex gridworld and extending to randomized trials on 100- and 200-vertex OSM graphs. The section also examines one 200-vertex trial in detail.

4.1 Experimental Setup

  • The first experiment evaluates a 12-vertex gridworld with one defending agent, one attacking agent, and one flag at corner vertices; defender tagging radius is 1 and attacker capture radius is 0.The attacker oracle uses three distinct routing behaviors; defense is locked to one of two preset policies.Source: §4.1 · pp. 12–13

4.2 Implementation Details

  • The Profile Oracle uses a GNN optimized with Masked PPO and retrained from scratch each iteration; utility-matrix values average 20 simulations.The GNN receives a graph representation and the current visibility profile as state inputs.Source: §4.2 · pp. 13–15

4.3 Gridworld Experiment

  • In the gridworld, the first profile neutralizes Evasive Routing but not Shortest Path, leaving the equilibrium at one capture until later iterations introduce mixed strategies.The initial sub-game also yields one capture; the Attacker Oracle adds Shortest Path after the Profile Oracle responds to Evasive Routing.Source: §4.3 · p. 16
  • In the gridworld, the final defense mixes two profiles that mitigate Evasive Routing and Shortest Path, yielding zero captures; Receding Horizon remains suboptimal.The profiles exploit the policy's fail case by hiding the attacker at a critical time-step, allowing defenders to position themselves and tag the attacker.Source: §4.2 · p. 15, §4.3 · p. 16

4.1 Experimental Setup

  • Randomized trials use ten starting configurations per graph; the 100-vertex graph tests Baseline and Patrolling defenders, while the 200-vertex graph reports Patrolling results.The OSM scenarios use two attackers and two defenders, with two spread-out flags on the 100-vertex graph and three clustered flags on the 200-vertex graph.Source: §4.1 · p. 13, §4.4 · pp. 16–17

4.4 Randomized Trials

  • Across both defender heuristics and both graphs, Algorithm 1 improves mean defense payoff over full visibility, while random profiles are disadvantageous on average.Some trials show no improvement, either because initial conditions leave no mathematical room to improve or because the Profile Oracle may not find a beneficial profile.Source: §4.4 · p. 17, Table 2 · p. 17

4.5 200-Vertex Case Study

  • In the 200-vertex case study, each newly added attacker policy receives the highest equilibrium weight, suggesting profiles may perform poorly against policies not yet in the sub-game.The observed evolution shifts from Receding Horizon to mixing with Shortest Path, then to Evasive Routing subsuming Shortest Path.Source: §4.5 · p. 18, Figure 4 · p. 18
  • In the 200-vertex case study, the final profile achieves zero flag captures, the maximum improvement from the full-visibility equilibrium of two captures.The equilibrium capture count fluctuates as attacker policies enter and the profile adapts; iteration 6 is an exception, with zero captures reached after the profile generated at iteration 7.Source: §4.5 · p. 18, Figure 4 · p. 18

5 Conclusions and Future Directions

The paper introduces a decentralized-heuristic, multi-agent zero-sum Capture the Flag game and a Double Oracle algorithm with a GNN-approximated Profile Oracle. Experiments indicate that visibility control can elicit improved behavior from a fixed defense policy, while visibility profiles may overfit to attacker policies seen in the sub-game.

5 Conclusions and Future Directions

  • The Double Oracle algorithm and approximate Profile Oracle can be effective in practice, and observation changes can elicit improved behavior from a fixed policy.The Profile Oracle is approximated by a graph neural network.Source: §5 · p. 19
  • Visibility profiles generated as best responses tend to specialize to the attacker policies weighted in the sub-game, creating a risk of overfitting to seen policies.The authors identify transferability to policies outside Πa and improved generalization as future-work directions.Source: §5 · p. 19
  • Future extensions include letting both teams reason over policy libraries and visibility profiles, and allowing time-varying observation control and policy adaptation.The latter could provide the defense with a greater range of behaviors than the static formulation.Source: §5 · p. 19
Loading 2609.06178v1…