Consider the following 2-player alternating-move game played on a Directed Acycl

Question

Consider the following 2-player alternating-move game played on a Directed Acyclic Graph (DAG) G, with some starting node s. First, player 1 picks an edge from s to some node v1. Then player 2 picks an edge from v1 to some node v2. Then player 1 picks an edge from v2 to some node v3 and so on. If we get to a node with no out-edges, then the current player (who has no edges to choose) loses. Give a polynomial-time algorithm to solve for whether the first player has a winning strategy in this game, i.e., can guarantee a win no matter what the other player does.

Explanation / Answer

You need to categorize the graph's nodes into two types: winning nodes and losing nodes. Winning nodes are nodes where the current player has a winning strategy if they're on that node, and losing nodes are ones where the current player will lose no matter how he plays (assuming his opponent plays correctly). Since this is a directed acyclic graph, all nodes are either winning or losing (because eventually a node with no outgoing edges will be reached).

Nodes with no outgoing edges are obviously losing nodes. For another node N:

To categorize all nodes, go over the nodes in reversetopological order. Categorize each node according to the rules above. The reverse topological order guarantees that you have categorized all nodes that can be reached from N before categorizing N.

Once you're done, if the start node is a winning node then there is a winning strategy: always pick an edge to a losing node.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.