Position: Profiling Game Worlds by Transition Complexity

Lele Cao

Source-linked AI summary

Position: Profiling Game Worlds by Transition Complexity

Lele Cao

arXiv:2608.18079v1May 29, 2026cs.AI

TL;DR

Transition-prediction difficulty is rarely quantified at the declared interface, confounding comparisons in game-world modeling and reinforcement learning. This paper proposes the reproducible Transition Complexity Profile, whose worked example shows that declared interfaces and protocols give TCP measurements unambiguous meaning.

Problem
Transition-prediction difficulty is rarely reported at declared interfaces, making comparisons across benchmarks, protocols, and representations easily confounded.
Method
TCP measures one-step branching, interaction-induced uncertainty and opponent influence, and temporal/spatial dependency span under declared interfaces, distributions, protocols, and measurement budgets.
Results
Once the interface, reference distribution, and step protocol are declared, TCP measurements have an unambiguous meaning, as illustrated by tic-tac-toe.
Takeaways & Limitations
TCP is proposed as a standard reproducible benchmark-metadata layer that complements returns, qualitative rollouts, and prediction losses.
Takeaways & Limitations
Direct TCP comparisons require matching the interface, protocol, and reference distribution, and different-interface profiles lack a generally justified scalar ordering.

Abstract

from arXiv · show

Game world modeling (GWM) and reinforcement learning (RL) are often confounded because research papers rarely quantify how difficult the underlying transition prediction problem is at the declared interface (pixels/tokens/latents with finite history). We propose the Transition Complexity Profile (TCP): a small, reproducible set of metrics that characterizes an environment's (or gameplay dataset's) induced transition kernel by (i) intrinsic one-step branching, (ii) interaction-induced uncertainty and opponent influence when observable, and (iii) temporal/spatial dependency span via standardized probe curves. TCP is reported with an explicit reference distribution, protocol stochasticity, and a versioned measurement budget (sampling/resampling and fixed probe compute), enabling comparable numbers across benchmarks. We outline how common game families and modern "neural game engine" domains populate this landscape and call for TCP to become standard benchmark metadata and a required statistic in GWM and RL papers.

1. Introduction

The paper argues that GWM and RL evaluations rarely quantify the transition-kernel difficulty posed at a declared interface, leaving comparisons and benchmark selection confounded. It proposes standardized Transition Complexity Profiles (TCPs) to report branching, interaction-induced uncertainty, and dependency span alongside existing evaluation measures.

Motivation: Current world-model evaluations emphasize downstream return, visual or qualitative rollout quality, and incompatible one-step prediction losses rather than transition-kernel difficulty.These measures are useful but do not directly answer how complex the environment’s transition kernel is for the model to learn.
Motivation: Without a shared operational notion of transition complexity, comparisons across games and even Atari protocols are confounded by differences in branching, dependency span, and interaction uncertainty.Different Arcade Learning Environment configurations can introduce action-repeat, or sticky-action, stochasticity with varying probabilities.
Implications: A shared map of environments by transition complexity could make benchmark selection less ad hoc and inform architectural choices because world-model families handle branching and long-range dependencies differently.The paper frames this as guidance for evaluating capabilities needed by the next generation of GWM.
Contribution: TCP standardizes reporting for each game environment or gameplay dataset by quantifying transition branching, opponent- or human-induced uncertainty, and dependency span at the declared interface.The proposal places TCP alongside return, qualitative rollouts, and one-step prediction losses.
Scope and limitations: TCP is not a universal scalar of game complexity and excludes Kolmogorov or rule-description complexity, computational complexity, solver difficulty, and architecture-specific approximation error.The scope is narrower: TCP characterizes transition complexity at the declared interface, while predictor difficulty can differ for low-entropy chaotic systems or high-entropy simple samplers.

2. Game Complexity and Related Work

The section argues that GWM and RL need a dedicated, algorithm-independent measurement layer for the difficulty of predicting state transitions at the model’s information interface. Existing complexity measures and evaluation practices address policy learning, representation equivalence, passive processes, game combinatorics, or task-specific performance rather than directly characterizing the induced transition problem.

Motivation: The paper’s contribution is a measurement layer that characterizes transition-prediction difficulty independently of any algorithm or reward objective.It does not propose a new world-model architecture.
Related work: RL complexity measures target exploration and control under a hypothesis class, not the induced next-state prediction problem.Examples include Eluder dimension, Bellman rank, witness-rank-style parameters, and low-rank transition assumptions.
Related work: State abstraction, bisimulation, and process-complexity measures emphasize equivalence, compression, or passive time-series structure rather than quantitative descriptors of interactive transition dynamics.Information-theoretic measures are difficult to apply directly when actions, opponents, and standardized evaluation procedures matter.
Related work: Classic game analysis and computational game theory measure difficulty through state-space size, branching, information sets, or formal complexity classes, but do not characterize the transition mapping relevant to world models.Without explicitly measuring transition structure and difficulty, progress across games, datasets, and modeling approaches is difficult to interpret.
Related work: Modern world-model and neural-game-engine work commonly reports downstream return, predictive loss, or qualitative rollout fidelity under task- and protocol-specific choices.These practices can obscure dynamics quality and uncertainty even when return-based evaluations are similar.
Motivation: TCP evaluates the transition kernel induced by the information available to the model or agent and decomposes uncertainty into chance, interaction, and finite-history dependence.This supports locating why a world model is uncertain or brittle under a given interface and protocol.

3. Preliminaries

The preliminaries formulate game worlds as Markov games with latent state, actions, opponent actions, and exogenous chance, while distinguishing latent state from the finite information state available to a model. TCP therefore measures the transition kernel induced by the chosen observation and history-construction interface, including residual uncertainty and dependency span.

Environment formulation: The environment is modeled as a Markov game with latent state, agent action, opponent joint action, and exogenous chance variable.The chance variable captures simulator randomness, procedural generation, random shuffles, and other stochasticity; stochastic kernels can be represented deterministically using this auxiliary variable.
Observation interface: A world model predicts from an information state constructed from interaction history, which may equal a full board state or use finite frame and action context.Fully observed chess or Go can provide a Markov information state, whereas Atari-like and high-dimensional gameplay settings use stacked frames or finite context windows.
Observation interface: Changing the state-construction mapping changes the effective transition kernel at the model’s interface, so TCP evaluates the sufficiency of that representation.When the information state is non-Markov, finite-window models approximate the conditional dynamics using truncated history; dependency-span probes vary retained history length k.
Temporal dependency: At finite history, hidden variables and unobserved opponents appear as residual uncertainty, while increasing k tests whether prediction improves or reaches saturation.If performance keeps improving across all evaluated context lengths, the report should state “no saturation within the evaluated range.”
Scope and limitations: TCP captures combinatorial effects only when they change next-interface multiplicity or the history structure needed for prediction; long-horizon strategic difficulty remains complementary.Strategic difficulty should still be assessed with return, planning, or game-theoretic metrics.

4. Transition Complexity Profile (TCP)

TCP characterizes transition difficulty as a reproducible profile rather than a single scalar, covering intrinsic branching, opponent-driven uncertainty and influence, and temporal or spatial dependency span. Its measurements are tied to a declared interface, reference distribution, protocol, probe family, and compute budget.

Profile design: TCP uses complementary, mathematically defined metrics computed from logged transitions or instrumented simulators, with logarithms measured in bits.The profile avoids reducing complexity to one potentially misleading scalar.
Measurement protocol: TCP reports must declare the interface, reference distribution, step protocol, probe version, training protocol, sampling or resampling, and fixed measurement budget for reproducibility.The reference kit includes TCP-Ref-GRU-v1 and TCP-Ref-TX-v1, with new probe variants introduced as new versions.
Intrinsic branching: 2H2 is an effective support size for next-state distributions, and its geometric mean yields a branching statistic less sensitive to heavy tails.This collision-entropy measure captures intrinsic multiplicity under state-action pairs and makes transition difficulty comparable across domains.
Opponent effects: Opponent uncertainty separates within-policy stochasticity from population heterogeneity, while opponent influence measures how much opponent variation induces branching in next-state distributions.If opponent actions have little effect on state evolution, their uncertainty is less relevant to transition modeling; unobserved opponent actions should be marked unobservable at the declared interface.
Dependency span: TCP operationalizes temporal memory depth and spatial dependency radius through fixed probe families and ε-based predictive-performance saturation.These measures address long-range dependencies caused by spatial coupling, cascades, or occluded state, even when one-step entropy is small.

5. Sanity properties

The sanity properties establish that refinement lowers conditional entropy only for a fixed prediction target, while TCP comparisons require matching interface, protocol, and reference distribution. They also connect unobserved chance and opponent variables to next-state uncertainty and recommend source-entropy diagnostics.

Refinement: For a fixed prediction target Y′, refining conditioning information cannot increase conditional entropy: H(Y′ | U, A) ≤ H(Y′ | V, A) when V is a deterministic coarsening of U.This theorem does not order TCP values when the predicted next-interface variable changes across interfaces.
Comparability: TCP comparisons require matching the interface, protocol, and reference distribution; reports should cover both the model’s native interface and any community-standard public interface.A deterministic coarsening permits same-target entropy comparisons but not a general scalar ordering of full TCP profiles.
Uncertainty sources: Unobserved opponent actions and exogenous randomness explain next-state uncertainty, with I((B, Ω); X′ | X, A) = H(X′ | X, A) under deterministic updates given those sources.Reporting H(B, Ω | X, A) gives an upper bound, while separate H(Ω | X, A) and H(B | X, A) help attribute uncertainty to chance versus interaction.

6. Operational aspects of TCP

TCP should be reported as an explicit, reproducible benchmark statistic whose value depends on the declared interface, measurement budget, reference distribution, and full transition protocol. Operational reports should distinguish simulator-based estimates from log-only proxies and expose uncertainty, probe details, and protocol-induced changes.

Reporting requirements: TCP is a domain/benchmark statistic, not an additional hidden tuning axis, and reports must declare the interface, tokenizer, context window, and full measurement budget.Required budget fields include sampled (x, a) pairs, simulator resamples M, probe architectures/version strings, training tokens or updates, and seeds.
Versioned tiers: TCP-Lite-v1 uses 5,000 sampled (x, a) pairs, M=8 resamples when available, and 200M probe-training tokens with 3 seeds; TCP-Std-v1 uses 20,000 pairs, M=32, and 1B tokens.TCP-Std-v1 is recommended for benchmark publication, while model papers may report TCP-Lite-v1 under limited compute if they declare the tier.
Distributions and uncertainty: TCP should be reported under both ddata and dprobe, with means, medians, and 90th percentiles; fixed sample counts are comparable budgets, not variance guarantees.High-branching regimes may produce collision-limited estimates or wide confidence intervals, which should be reported rather than hidden by ad hoc budget increases.
Simulator measurements: Simulator protocols reset to each sampled interface state, apply action a, generate M i.i.d. next-interface samples by resampling exogenous randomness and applicable opponents, and estimate branching from collisions.When collisions are absent, report bpcoll = 0 and mark the estimate collision-limited; for high-dimensional observations, collision-based bH2 is primary on a declared discretization.
Logged-gameplay measurements: For logged gameplay without fixed-(x, a) resampling, Axis I uses probe cross-entropy L in bits per token, Axis III reports k 7→Lk and Cmem(ε), and Axis II requires logged opponent actions.Log-only TCP is a property of the dataset slice under ddata, not an environment-wide constant; reports should include coverage, behavior source, splits, and filtering.
Protocol dependence: Any action-execution or randomness protocol change modifies the induced transition kernel, so TCP reports must specify parameters; at p=0.25, sticky actions contribute h2(0.25) ≈0.811 bits in applicable regimes.This illustrates why nominally identical benchmark results are not directly comparable without the full transition protocol.

7. Call to Action: TCP as Benchmark Meta

The paper calls for TCP to become standardized benchmark metadata rather than an optional post-hoc analysis. Adoption is organized across benchmark maintainers, model and dataset papers, suite designers, regression tests, and a lightweight reference implementation.

Benchmark maintainers: Benchmark maintainers should publish TCP cards for each public benchmark-protocol-interface triple, including kernel declarations, canonical dprobe, TCP-Std-v1 values with uncertainty, preprocessing, and reproduction scripts.Simulator-backed benchmarks should also expose reset/replay hooks and controllable resampling of exogenous randomness.
Model and dataset papers: Every GWM/RL paper should report the minimal TCP table for each environment or gameplay dataset, citing published TCP-Std-v1 cards when setups are unmodified.When behavior distributions differ, such papers may report TCP-Lite-v1 under ddata; kernel-changing modifications require separate reporting.
Suite designers: Benchmark suites should span TCP axes, including chance-dominant, interaction-dominant, mixed, and high temporal/spatial dependency settings, with paired variants treated as distinct induced kernels.Examples include sticky actions on/off, deterministic versus stochastic resets, and board-state versus pixel interfaces.
Worked examples as regression tests: The tic-tac-toe and sticky-action calculations are proposed as regression tests for protocol interpretation and wrapper-induced changes to the transition kernel.Tic-tac-toe fixes X, d, and the step definition; sticky actions illustrate that changing a wrapper can alter the kernel while keeping the game name fixed.
Reference implementation plan: Adoption requires a lightweight TCP-Ref package with estimators, reference probe configurations, a TCP-card schema and table generator, and unit-test examples.The planned package includes collision-entropy and cross-entropy estimators with bootstrap confidence intervals and TCP-Ref-GRU-v1, TCP-Ref-TX-v1, and TCP-Ref-Loc-v1 scripts.

8. Alternative Views

The paper argues that return alone cannot establish transition fidelity, because distinct kernels may yield identical returns and miscalibrated structure matters for broader uses. It defines TCP as an interface- and distribution-relative profile of branching, interaction effects, and dependency span, while explicitly excluding several other forms of complexity.

Return and fidelity: Return is necessary but not sufficient: distinct transition kernels can produce identical returns under a fixed policy and evaluation protocol.World models are also reused for transfer, editing, counterfactual reasoning, and interactive simulation, where miscalibrated branching or dependence length can dominate performance.
Representation dependence: TCP measures the effective transition kernel induced on the agent’s information state when seeds or latent variables are unobserved.It is explicitly defined relative to the model’s state interface, making representation dependence a feature rather than a flaw.
Structured models: TCP complements structured transition models by diagnosing when conditional-independence and bounded-locality assumptions succeed or fail.Resolver-based, event-driven games with cascades and long-range effects provide counterexamples where bounded-locality assumptions fail.
Scope of complexity: TCP measures branching, interaction effects, and dependency span, but not rule-description/Kolmogorov complexity, computational complexity, solver difficulty, or model-class approximation error.Semantic equivalence must be handled by the declared interface or tokenizer, while strategic difficulty should be reported through return, planning, or game-theoretic metrics.

9. Conclusion … A.3. Diagnostic implication

The paper argues that transition prediction difficulty at a declared interface is rarely measured, confounding comparisons across benchmarks, protocols, and representations. It proposes the Transition Complexity Profile (TCP) as reproducible metadata covering branching, interaction-induced uncertainty, and dependency span under explicit measurement conditions.

9. Conclusion: TCP targets the transition kernel at a declared pixels/tokens/latents interface with finite history, where prediction difficulty is currently underreported.This underreporting makes comparisons across benchmarks, protocols, and representations difficult to interpret.
9. Conclusion: TCP reports one-step branching, interaction-induced uncertainty and opponent influence when observable, and temporal/spatial dependency span.The profile is defined under an explicit interface, reference distribution, protocol, and versioned measurement budget.
9. Conclusion: TCP complements rather than replaces return metrics or qualitative rollouts by providing a measurement layer for interpreting them.The paper argues that adoption could support cross-domain comparisons, deliberate benchmark design, and clearer claims about learned capabilities.
A. Mapping common game domains into the TCP landscape: Common game families are mapped qualitatively into TCP space, while quantitative releases should report measured values under a declared interface Xt, reference distribution d(x, a), protocol, and measurement tier.The qualitative entries are schematic bins rather than computed TCP measurements.
A.1. Axes and reporting convention: Axis I uses one-step branching measures C(1) H (d) and/or C(1) B (d), or probe cross-entropy proxies when only logs are available.The appendix presents these quantities as the notation used to summarize TCP axes.
A.1. Axes and reporting convention: Opponent influence C_opp infl (d, Π) is reported only when opponent actions Bt are observed at the declared interface; otherwise it is marked unobservable.Axis III uses Cmem(ε) and, when spatial indexing is meaningful, Crad(·; ε) through TCP-Ref probe curves.
A.1. Axes and reporting convention: The default interface is an observation—board, pixels, or tokens—plus ego action, with other agents’ controls treated as latent unless explicitly logged.This convention determines whether opponent-related quantities are observable.
A.3. Diagnostic implication: Standard world-model benchmarks are often single-agent with Axis II unobservable, moderate branching, and moderate dependency span, whereas neural game-engine directions emphasize high-span regimes and may hide multi-actor uncertainty in Axis I.TCP makes these domain differences explicit as reportable benchmark metadata.

A.4. Using the map in practice

The practical TCP block specifies the declared interface, transition protocol, reference distributions, and measurement tier or budget. It then reports metrics for intrinsic branching, observable opponent influence, and temporal or spatial dependency.

Declare the interface X_t, including tokenization and context length, together with the full transition protocol.
Specify reference distributions d_data and d_probe and the TCP tier or budget, such as TCP-Lite-v1 or TCP-Std-v1.
Report Axis I using C(1)_H(d) / C(1)_B(d) for simulators or probe cross-entropy proxies in log-only settings.
When observable, report Axis II metrics for opponent mixing and influence; otherwise mark the quantities “unobservable”.The listed metrics are C_mix^opp, C_mix^within when available, and C_opp^infl.
Report Axis III probe curves and C_mem(ε), adding C_rad when meaningful.

A.5. Worked numeric TCP example: tic-tac-toe under a fixed probe policy … B.2. TCP-spanning suites

The tic-tac-toe example shows that TCP yields reproducible numeric measurements when the interface, reference distribution, and transition protocol are fixed. The recommendations then extend TCP into routine paper reporting and benchmark-suite design spanning distinct transition-complexity regimes.

A.5. Worked numeric TCP example: tic-tac-toe under a fixed probe policy: For tic-tac-toe, one step is our legal move followed by the opponent response on a fully observed 3×3 board.The reference distribution starts from the empty board, with both players choosing uniformly among legal moves until termination.
A.5. Worked numeric TCP example: tic-tac-toe under a fixed probe policy: Per-(x, a) entropies take values in {0, 1, 2, log2 6, 3}, with median 2 bits and 90th percentile 3 bits.Conditional next-state distributions are uniform over opponent legal replies when nonterminal.
A.5. Worked numeric TCP example: tic-tac-toe under a fixed probe policy: At this interface, tic-tac-toe has no chance, so all one-step branching comes from the opponent; with the full board, Cmem(ε) = 1 for any ε > 0.The spatial radius is bounded by the 3×3 board, and declaring Xt, d(x, a), and the protocol enables numerical TCP reporting.
B. Research agenda and community recommendations: TCP should characterize the induced transition kernel at a declared interface, reference distribution, and protocol, with standardized reporting adopted across world-model and benchmark practice.The proposed community actions include standardizing TCP reporting in papers.
B.1. TCP in papers: Every game-world-model paper should report the minimal TCP table for each benchmark together with a kernel declaration making the induced transition kernel unambiguous.The declaration covers the environment and version, wrappers, modeled interface and history construction, and reference distributions.
B.1. TCP in papers: Axis I should use collision-based branching bH2(X′ | x, a) when reset/resampling is available, while log-only settings should report probe cross-entropy L (bits/token) as a proxy/upper bound.Axis III should include the full k 7→Lk curve and Cmem(ε) at ε ∈{0.01, 0.1}, using fixed probe versions and budgets.
B.2. TCP-spanning suites: Benchmark suites should span TCP axes intentionally, including Axis I-dominant, Axis II-dominant, mixed chance-plus-interaction, and long-dependency regimes.The suite should evaluate architectural and objective choices against specific transition-kernel properties rather than only modality or reward structure.
B.2. TCP-spanning suites: Protocol and interface variants should be paired within suites, and each benchmark-protocol-interface triple should ship with canonical dprobe definitions and published TCP-Std-v1 numbers.Examples include sticky-action on/off, deterministic versus stochastic resets, single-agent versus multi-agent variants, and public Markov versus partially observed interfaces.

B.3. Benchmark instrumentation

The paper recommends making TCP measurable by default through benchmark instrumentation that separates uncertainty sources and reproduces the induced kernel. With standardized hooks, datasets, and scripts, transition complexity becomes comparable, versioned benchmark metadata rather than paper-specific analysis.

Recommendation: Benchmarks should expose hooks for separating chance from interaction uncertainty and reproducing the induced transition kernel under declared protocols.This is framed as basic experimental control rather than extra analysis.
Simulator-backed benchmarks: Simulator-backed benchmarks should support latent-state reset/replay, controlled resampling of exogenous randomness and opponents, and logging of wrapper parameters and executed actions.These capabilities enable unbiased collision-based Axis I estimates and meaningful comparisons across implementations.
Log-only benchmarks: Log-only benchmarks can compute TCP through probe-based proxies only when they provide aligned histories, claimed Axis-II fields, and a fixed evaluation split with reference scripts.Without opponent-branching fields such as Bt, Axis II must be marked unobservable rather than inferred.
Outcome: With these hooks, TCP becomes comparable and versioned benchmark metadata, making progress in GWMs interpretable across environments, protocols, and interfaces.The paper compares this role to metadata such as observation resolution or action-repeat.