Synthesis of Strategies for Games - The Unknown Component Problem: Theory and Applications - page 264

complement spec.aut spec_comp.aut
product fixed.aut spec_comp.aut product.aut
support cs0(7),cs1(7),cs2(7),p2(3),d2(7) product.aut\
product_supp.aut
complement product_supp.aut x.aut
progressive -i 3 x.aut xfsm.aut
minimize xfsm.aut xfsm_min.aut
We show the automaton xfsm min.aut in Fig. 17.3 at the end of this chapter.
The state names of the automaton xfsm min.aut do not carry any information,
but one can infer what state the game is in by looking at the outgoing edges of a
state. For example, state s00 has an outgoing edge labeled 321 . Note that the
inputs to the automaton are cs0(7) , cs1(7) , cs2(7) , p2(3) , d2(7) , so 321
refers to the state where the pile heights are 321 .The part of the label refers to
p2,d2 , and since player 1 went first, it does not matter what p2,d2 is on the first
move; hence . From state s01 , note that there are two outgoing arcs, one going
to s11 and the other to s14 .Thearcto s11 has two labels, 12111 and 31102 .The
first indicates that if we were in state 121 , then we would choose Pile 1 and take 1
coin away from it. Looking at the next state s11 , the only outgoing arc is labeled
111 , indicating that the game is in state 111 . This correlates with taking 1 coin
from Pile 1, thus changing the state from 121 to 111 . Similarly the label 31102
means that we take 2 coins from Pile 0, leaving 111 again. Thus considering all the
outgoing arcs of s01 , we see that state s01 represents the game being in any one
of game states f121; 311; 320; 221g . The state, s02 , is the winning state for Player
2. Note that there is always a path to s02 from any state. This means that there is a
winning strategy.
Many of the arcs into state s02 are caused by Player 1 making an illegal move.
Note that Player 1 is modeled by a random player since his moves are uncontrolled
inputs. Modeling any illegal move as a win for the other player is an easy way to
model a player making only legal moves.
Solving with the initial state set to 653 leads to a minimized FSM automaton with
39 states, and in examining the solution one can see that from every state there is
a path to the winning state. However, with initial state 553, the solution shows that
this is not the case because, after the operation to make it progressive, the solution
FSM is empty.
Problems
17.1. Consider the topology of the game of NIM in Fig. 17.1 , and revise it assuming
that the state of the game (encoded by variables cs0; cs1; cs2 ) is not exposed to
player 2. Moreover p 1 ;d 1 are given as an input also to player 2. Solve this modified
version of the NIM game and compare the solution with the one of the original
problem, where the state of the game was exposed to player 2.