Finite controllers face limits in achieving exact game values under strict rules

Attaining Optimal Values under Sure Constraints

Computer Science and Game TheoryLogic in Computer Science

Summary

Some games allow players to get close to the best possible score using simple strategies, but not to exactly reach that score. The authors analyze this problem in games where certain safety rules must always hold, even on very unlikely scenarios. They show how hard it is to decide if exact scores can be reached and how complex the required strategies need to be to guarantee these outcomes. This includes understanding memory needs for strategies under strict winning conditions and rewards.

What this means in practice

  • For game developers: Determine the computational limits of designing finite controllers that guarantee exact outcomes under strict rules in complex stochastic games.
  • For automated control system designers: Understand memory and strategy complexity required for controllers to satisfy hard safety constraints with guaranteed performance in probabilistic environments.

A theory result. No direct application yet.

Authors

Takuto Yamauchi, Kenji Tei

Abstract

A game may have, for each target below its value, a finite controller meeting that target, yet no finite controller attaining the value itself. We study finite stochastic games with a hard specification that must hold on every supported execution, including paths of probability zero. Max uses a pure finite controller; Min may use any pure public-history strategy. We distinguish three numerical questions: can a supplied target be met, can the unspecified optimum be attained, and what is one exact value? For explicit hard and Boolean soft Streett conditions, the strict and non-strict supplied-threshold problems are coNP-complete, attainment of the unsupplied supremum is $\mathrm P^{\mathrm{NP}}$-complete, and one exact reduced fraction is $\mathrm{FP}^{\mathrm{NP}}$-complete under polynomial metric reductions. The proofs preserve both the value and its finite attainability when fixing a single opponent, and encode adaptive queries without computing unknown subgame values. The same construction yields matching value-comparison and exact-output lower bounds for ordinary stochastic Streett games with unrestricted randomized history strategies. We also bound the memory needed for optimal finite implementations for arbitrary Muller hard conditions and rational rewards in $[0,1]$ determined by infinitely recurring states. One controller is sure from the entire original sure region and attains at every finitely attained start, with no attainment premise on the other states. For $n$ states in that region it uses $2^{O(n\log(n+1))}Q(1+\log R)$ modes, where $Q$ is the product of the least common denominators of full original chance rows sourced in that sure region and $R$ clears all reward values. Its joint dependence on $Q$ and $R$ is worst-case sharp at each fixed $n\ge6$ when $Q,R\ge2$. Optimal dependence on arena size and efficient general synthesis are not resolved here.