We investigate concurrent two-player win/lose stochastic games on finite graphs with prefix-independent objectives. We characterize subgame optimal strategies and use this characterization to show various memory transfer results: 1) For a given (prefix-independent) objective, if every game that has a subgame almost-surely winning strategy also has a positional one, then every game that has a subgame optimal strategy also has a positional one; 2) Assume that the (prefix-independent) objective has a neutral color. If every turn-based game that has a subgame almost-surely winning strategy also has a positional one, then every game that has a finite-choice (notion to be defined) subgame optimal strategy also has a positional one. We collect or design examples to show that our results are tight in several ways. We also apply our results to B\"uchi, co-B\"uchi, parity, mean-payoff objectives, thus yielding simpler statements.
翻译:我们同时调查两个玩家在具有前缀独立目标的定点图上双玩赢/关闭随机游戏。 我们给子游戏优化策略定性, 并使用这种定性来显示各种记忆传输结果:1) 对于给定的( 前缀独立)目标, 如果每个有子游戏几乎肯定获胜策略的游戏也有一个位置性目标, 那么每个有子游戏最佳策略的游戏也有一个位置性目标; 那么每个有子游戏最佳策略的游戏也有一个位置性战略; 2) 假设( 前缀独立) 目标有一个中性颜色。 如果每个具有子游戏几乎肯定获胜策略的回合性游戏都有一个位置性战略, 那么每个拥有有限选择( 注意待定) 子游戏最佳策略的游戏也有一个位置性战略。 我们收集或设计实例来显示我们的结果在几种方式上是紧凑的。 我们还将我们的结果应用到 B\\ uchi, co-B\\\\" uchi, 等、 等、 等等、 平均、 平均回报目标, 从而产生更简单的语句。