Skip to content

Pursuit Exact-Graph Memory

Pursuit exact graphs (implemented by the internal guard builder) are public-state only: no hidden time channels are added to exact legal graphs or true-transition graphs.

Practical consequence

For 2-agent Pursuit, the public-state graph is small enough that exhaustive starts are usually fine.

For 3-agent Pursuit, even the reset-reachable closure creates a very large edge set without time augmentation:

  • state upper bound: (number of non-wall cells) ** n_agents
  • state--joint-action group upper bound: state_upper_bound * (action_size ** n_agents)
  • serialized successor-edge upper bound: the group bound times the product of per-agent successor-support bounds (up to five per agent for non-degenerate slip)

Because Graph.edges is still stored as Python Edge objects, the in-memory cost is dominated by edge count rather than node count.

Current policy

  • WM notebooks should build Pursuit legal graphs with include_all_starts=False, but that flag does not help when the reachable closure covers the full space.
  • The internal exact guard builder preflights the serialized successor-edge upper bound for both exhaustive and reset-reachable construction and raises a MemoryError when it is too large for the current representation.
  • If someone really needs the exhaustive graph, they can pass allow_large_graph=True explicitly and accept the memory risk.

Follow-up ideas

  • If 3-agent Pursuit graphs become important, the next improvement is a more compact or procedural edge representation rather than reintroducing hidden state.
  • Partial checkpointing is only useful if the graph representation can resume safely; preflight refusal is currently more reliable than hoping to catch an OS-level OOM kill.