CODEWITHSUNDEEP
algorithmgraph
ealeon
ealeon

Reputation: 12460

Predicting path on a directed acyclic graph

I came across question and was wondering if it is possible to predict the end result.

It's a one vs one (alternating-move) game on a graph (directed acyclic graph).
From a starting point or a node, player 1 picks an edge to node v1. From node v1, player 2 picks an edge to node v3 and so forth.

How to win: a player that reaches a node with no out-edge loses.

Is it possible to come up with an algorithm where it can guarantee a win no matter what the other player does?

So, the starting node is s. player 1 can pick either C or A. so basically, is there a way for me to make a decision based on some sort of algorithm which can guarantee me a win?

In this case, I would win if i am at node D or B and choose the edge that goes to node E so then player 2 is stuck at node E.

*distance does not matter

Upvotes: 1

Views: 1787

Answers (2)

interjay
interjay

Reputation: 110202

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:

  • If there is an edge from N to a losing node, N is a winning node.
  • Otherwise, N is a losing node.

To categorize all nodes, go over the nodes in reverse topological 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.

Upvotes: 5

Origin
Origin

Reputation: 2017

In general, no. It will depend on your graph. Say you have a simple tree / chain of an odd number of nodes(=graph of n nodes and n-1 edges). Then player two will always win as you cannot force a win.

You can look at some min-max algorithms to guide your game strategy. With those you could determine who would win recursively by starting at the end and working your way back, determining the winner for each sub-DAG of the DAG.

Upvotes: 0

Related Questions