Indian Computing Olympiad

Games and strategies

Scores (IOI 2001)

We are given a directed graph, with start vertex is 1. Each vertex is owned by Player 1 or Player 2. Each vertex has a value (integer).

The game starts at vertex 1. The player who owns vertex 1 starts the game. At each vertex, the owner picks up the value on the vertex and moves token to neighbouring vertex.

The game ends when the token returns to vertex 1. The winner is the one who has picked up the maximum value during the game.

Condition: The graph is such that the game always terminates in a finite number of moves.

Problem: Design an optimal strategy for Player 1 (who may or may not own Vertex 1)

Example:

                             --
Player 1 nodes are labelled |  |,                 ---           ===
                             --                --| 1 |<-------|| 2 ||<-
                              ==              |   ---       ->  ===    |
Player 2 nodes are labelled ||  ||            |           _/           |
                              ==              |          /             |
                                              |        _/
Values are stored inside the nodes.           |   --- /         ===    |
                                               ->| 3 |------->|| 4 ||--
Vertex 1 is the one on the top left corner.       ---           ===
      

Solution

Since the game always ends by returning to vertex 1,there is no cycle that does not involve vertex 1. Otherwise, the players can stay within a cycle forever without the game terminating. Therefore, if we eliminate all edges coming into vertex 1, we have a dag.

Now, how do we evaluate positions bottom up.

Label each node with a pair of values (m1,m2)—the interpretation is that if the game starts at this node, the maximum value that Player 1 can pick up is m1 and the maximum value that Player 2 can pick up is m2. This node is winning for Player 1 if m1 > m2.

We can initially evaluate these values for the leaf nodes in the dag—those from which the only outgoing edge is back to vertex 1.

How do we propagate these values?

An internal node in the dag has successors in the dag for which the game values are known. The node can also have a single back edge to vertex 1.

Computing the (m1,m2) value for a node that belongs to Player 1:

Case 1 (There is no back edge from this node to vertex 1)

Pick the successor in which Player 1 wins with his value maximum (i.e. in the successor node's label, Player 1's value is larger than Player 2's).

• Let this successor node be labelled (k1,k2). Let the value attached to the current node be l1.
• If l1 > k1 then Player 1 can afford to a play to a winning successor node labelled (n1,n2) in which n2 is minimum but n1 is not necessarily maximum among all winning successors. In this case, we label the current node (l1,n2).
• Otherwise (l1 ≤ k1), Player 1 should move to the successor labelled (k1,k2), so we label the current node (k1,k2).
• If all successors of this node are losing for Player 1, pick losing successor (k1,k2) such that k2 is minimum. Let l1 be value of the current mode. Label this node with (max(l1,k1),k2).

Case 2 (There is a back edge from this node to vertex 1)

As before, let (k1,k2) be the label of the best successor and let l1 be the value on the current node.

• If l1 ≥ k1, label the current node (l1,0) [Player 1 will move the game immediately back to Vertex 1 and win.]
• If l1 < k1, label the current node (k1,k2) [Player 1 will continue the game without returning to Vertex 1 at this point.]

We also have to propagate labels to vertices that belong to Player 2, using symmetric arguments.