Given n nodes, 2 players play a game by constructing a directed edge between 2 nodes in each turn by following the 4 rules below.
1)Each player has to create 1 edge in his turn, starting from the node reached by the previous move of the opponent. Ex:- if player A creates an edge from node 2 to node 3 in his turn, player B has to start the edge from node 3. 2) Two nodes can't have more than 1 directed edge between them. Ex:- if an edge exists from node 2 to node 3. then another edge from node 3 to node 2 is not allowed. 3)edge can be from and to the same node . Ex:- edge from node 2 to node 2 is allowed. 4) First move at the start of game can be started by first player between any two arbitrary nodes. The player who can't make a valid move loses. what is the optimal strategy that a player can follow to win? given a partially filled graph, assuming both players play optimally, how do you determine who wins(first player or second player)? my strategy: If condition 3 is not there i.e. No self loops are allowed then I can think of a solution. Assuming initial state to be n unconnected nodes. I claim that my strategy (which I will elaborate in next few lines) will always enable the first player to WIN. In order to WIN first movers will create a directed edge so as to maintain two nodes such that two nodes lets call them C1 and C2 will always have a directed edge between all the (so far) discovered nodes. So the onus of discovering a new node will always be on the second player. At one point there will be no new nodes which are to be discovered because of which second player wont be able to make a move and hence will lose. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
