Variations: What if there are multiple coins?
Then you need to track the entire game state (all coin positions) and build a product graph. What if players alternate between different graphs?
Model this as a larger game with state (current graph, coin position). The core technique remains backward induction, but the state space becomes more complex. With coins each on a DAG of vertices, the state space grows to , which is only feasible for small .