On the Analysis of Strategies of Buechi Games

Authors: Ahmad Termimi Ab Ghani, Kojiro Higuchi

Abstract:

In this paper, we present some results of simultaneous infinite games. We mainly work with generalized reachability games and Buechi games. These games are two-player concurrent games where each player chooses simultaneously their moves at each step. Our goal is to give simple expressions of values for each game. Moreover, we are interested in the question of what type of optimal (ε-optimal) strategy exists for both players depending on the type of games. We first show the determinacy (optimal value) and optimal (ε-optimal) strategies in generalized reachability games. We provide a simple expressions of value of this game and prove the existence of memoryless randomized ε-optimal strategy for Player I in any generalized reachability games. We then observe games with more complex objectives, games with Buechi objectives. We present how to compute an ε-optimal strategies and approximate a value of game in some way. Specifically, the results of generalized reachability games are used to show the value of Buechi games can be approximated as values of some generalized reachability games.

Keywords: optimal Strategies, generalized reachability games, Buechi games