Skip to main content
1 of 1

Finite Games winning strategy exercises

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?