AGTA Tutorial 6
Please attempt the question before your tutorial.
1. Consider the following 2-player win-lose game on a graph. We are given a finite 2-player game graph G = (V, E, v0, F ), where the vertices V = V1 ∪ V2, are partitioned into the vertices V1 belonging to player 1 and the vertices V2 belonging to player 2. We are also given a start vertex v0 ∈ V , and a set F ⊂ V of “good” states. Starting from v0, the player who owns the current state, vi, chooses an neighbor vi+1 ∈ V such that (vi, vi+1) ∈ E. This determines an (infinite) play, π = v0v1v2 . . .. The winner is determined as follows. Let inf(π) denote the set of vertices in V that occur infinitely often along the play π. The play π is a win for player 1 if inf(π)∩F ̸= ∅, and otherwise it is loss for player 1 (i.e., a win for player 2).
In other words, player 1’s goal is to force the play to visit some vertex in F infinitely often, whereas player 2’s goal is to make sure this does not happen. These games are in fact memorylessly determined.
Copyright By PowCoder代写 加微信 powcoder
Describe an efficient (polynomial time, and as efficient as you can get it) algorithm for determining the winning player (i.e., the one with a winning strategy), and for computing a memoryless winning strategy for that player, given such a game.
(Hint: repeatedly use the algorithm given in class for determining the winner in a game on a graph where the goal of player 1 is to reach some target states, whereas the goal of player 2 is to make sure this does not happen.)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com