Game Strategy

• complicated by the variable end position...simply fix the end position and iterate through all possible ends (N is small!)
• work backwards from each solution, finding states that allow us to force a winner
• Some sort of topological sort variant?
• From a high level, any state is a winning state for us if there is one option such that all possible states are also winning states
• Alice is guaranteed a win if all possible states are winning states, she chooses the winning end state such that the maximum distance from any node to the end state is minimized
• Bob chooses the maximum distance start state to the same end state that he can deduce alice chooses, or any non-winning state if one exists

Notes about the topological sort:

• We will go backwards relative to how the game is played, since we only know the end state
• We will use in/out nodes, where the IN notes are the sets of states (one for each set) that are available, and the OUT nodes are the positions themselves
• Run topological sort, but when any in-node would be added to the queue, instead add its out node, and mark the out node as winning, keeping track of the number of steps to get there.