AGTA Tutorial sheet 6 (solutions)
1 Question 1
Consider a game graph G = (V, E, v0, F ), where the (finite) set of vertices V = V1 V2 is partitioned into set of vertices V1 (belonging to player 1) and set of vertices V2 (belonging to player 2), E being the set of edges of G. We are also given a start vertex v0 ∈ V , and a set F ⊂ V of good (target) states. Denote E(v) the set of all successor vertices for v, i.e E(v) = {v′ ∈ V |(v, v′) ∈ E}. We assume that ∀v, E(v) ̸= ∅, i.e every state has a successor state (no deadlocks). Let Π denote the set of infinite paths in G. For π ∈ Π, π = v0v1…, let us denote the set of states that appear infinitely often in π as
inf(π)={v∈V|∀i≥0,∃j≥i,vi =v}
Copyright By PowCoder代写 加微信 powcoder
The play π is a win for player 1 if inf(π)∩F ̸= ∅, and otherwise it is a win for player 2 (i.e a loss for player 1). Describe an efficient algorithm to find which player wins, and to extract a memoryless winning strategy, given such a game.
1.1 An Algorithm
For any set of nodes S ⊆ V, let Win′1(S) denote the set of nodes v ∈ V such that, starting from v player 1 has a winning strategy to force the game to reach a vertex in S in one or more steps (so, we do not necessarily have S ⊆ Win′1(S)).
It is easy to adapt the algorithm given in class for the win-lose reachability game on a graph (see the slides for Lecture 12, page 8), to compute the set W in′1(S).
Namely, in that algorithm, in step 1., instead of initializing W in1 := Good, we simply instead initialize W in1 as follows
Win1 :={v∈V1 |∃(v,v′)∈Esuchthatv′ ∈S}∪{v∈V2 |∀(v,v′)∈Ev′ ∈S}
(In the above V1 denotes the vertices of the game graph belonging to player 1, and V2 denotes the vertices belonging to player 2.)
The rest of that algorithm remains unchanged. This revised version of that algorithm will compute precisely the set W in′1 (S ). Note that algorithm also computes, a memoryless strategy for player 1, such that using that strategy, starting from every vertex v ∈ Win′1(S) the play will reach a vertex in S (no matter what player 2 does).
Suppose F is the set of “target” vertices that player 1 would like to visit infinitely often in the game. Let us now consider the following sequence of subsets of F.
Let F0 := F, and for all integers i ≥ 0, let
Fi+1 :=F∩Win′1(Fi)
In other words, Fi denotes the set of target vertices v ∈ F such that player 1 has a strategy to revisit target vertices in F at least i times, starting from v. Note that we can computing the sets Fi+1 by just repeatedly using reacha-
bility game algorithm to compute the sets Win′1(Fi). It is easy to show (by induction on i) that:
F =F0 ⊇F1 ⊇F2 ⊇F3…
In other words, Fi ⊇ Fi+1, for all i ∈ N.
Thus, for each i ∈ N, either Fi ⊂ Fi+1, in which case |Fi+1| ≤ |Fi| − 1, or else Fi = Fi+1. Now, notice that F is a finite set. Thus if |F| = k then, clearly there is some smallest i ≤ k such that Fi = Fi+1 = Fi+2 = ….
Let F∗ be equal to Fi for (the smallest) i ≤ k such that Fi = Fi+1.
But then, player 1 has a memoryless strategy, using which, starting at every v ∈ F∗, the play reaches a vertex in F∗ in one or more steps. Hence in fact (by reusing those same memoryless strategies starting from each node in F∗), starting from every vertex v ∈ F ∗ player 1 has a strategy to infinitely often visit a node in F∗.
Finally, F∗ ∪Win′1(F∗) is the set of all vertices (including vertices not in F) starting from which player 1 has a winning strategy to force visiting vertices in F infinitely often.
The algorithm for solving a reachability game on a graph (i.e., computing a set W in′1(S)), can be done in linear time O(|E| + |V |) in the size of the game graph. Thus computing each Fi at iteration i of the algorithm requires O(|E| + |V |) running time. Since there are at most |F | = k iterations, the running time of the algorithm is O(|F |(|E| + |V |)).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com