Finite Games winning strategy exercises

Question

I'm currently studying finite games from the textbook "Automata Theory and its Applications" by Bakhadyr Khoussainov and Anil Nerode and am having trouble with this exercise with the following questions:

Exercise 4.2.4 Consider the example pictured in Figure 4.2 with winning sets 
W(B) = {g6} and W(G) = {b1}. 
1. Determine all the positions from which Blue wins. 
2. Determine all the positions from which Green wins. 
3. Determine all the positions from which no player wins.

By "all positions from which X wins", are they asking about positions from which X will definitely win (e.g. B will win from position b6 as (b6, g6) is the only possible move) or positions from which it is possible for X to win (e.g. Would g4 be a position from which Blue wins? Since it can potentially result in either Blue winning if it goes to b4, or Green winning if it goes to b3). Are there any positions from which no player wins, seeing as there doesn't seem to be any loop that can't reach a winning position?

Answer 1

The term “wins” is defined on the preceding page:

Definition 4.2.3 We say that Blue wins the game from a position $q$ if Blue has a finite game strategy $f$, called a winning strategy, with the following property: any time Blue plays from $q$ following $f$, Blue eventually reaches the set $W(B)$.

Thus, the term means neither of the two alternatives you proposed; it means that Blue will eventually reach the winning set with optimal play.

Answer 2

In game theory one usually assumes players that know the game and always chose the best strategy. A winning position for some player A is thus a position where no matter what the other players do, the player A can win. Because the perfect other players would always find the single method to not let player A win.

So at "g4", green would always go to "b3", as the game would then eventually end up in "b1", and green would win. So "g4" is a winning position for green. Being the perfect player he is, green would never chose "b4", because he would not win then. Conversely for blue, he can't force green to chose "b4", so it is not a winning position for blue.

I situation where no one can force a win occurs at "g5". If green chose to go to "b6", the game would end in a win for blue at "g6". So green will never go to "b6" and always go to "b5". There we have our infinite loop. So in "g5", no player wins.

I hope this is enough for you to figure out the rest of the exercise.