Acquire maximum nodes (score) in a graph

Question

I'm given a graph G with n vertices, labelled from 1 to n (2<=n<=10^5). Each vertex has a score related with it. Two friends A and B play a game. A starts with vertex 1 and B from n. In any step, player can move to a vertex if it is not already occupied and is adjacent to any of the vertex already occupied by the same player. A starts first. The final score is the sum of all the scores you get from nodes visited. The player with more score wins. Which of A or B wins the game? If both players have the same score, B wins.

My attempt:

If G is a tree, I can get the path from 1 to n. Say it is

1 -> a_1 -> a_2 -> ... a_k -> n

A will then occupy all the nodes that are "child" of 1, a_1, ... a_x (where x = ceil(k/2) ) and B will occupy the rest. We can see who gets more and get the winner.

If G is a graph (more than n-1 edges), above approach won't work because there can be more than one path to a vertex from a given starting point. So, I made a max heap for A and other for B. Then:

Start with adding 1s and ns adjacent vertices' scores in respective heaps.
Get index with max score, remove it. Add its adjacent vertices' scores in the respective heap.

The one with higher score wins.

Correct? No. This is a greedy approach and gives wrong answer in many cases. What should be the optimal strategy for this case?

Example

Suppose n = 5. The following vertices are adjacent:

The scores associated with each vertex are respectively:

10 20 30 40 50

A initially has score 10 and B 50. A can only visit 2 (final score = 10 + 20) while B can visit 3 and 4 (final score = 30 + 40 + 50). Hence B wins the game.

We could reach a situation when one player has moves available while the other does not. Does the game stop in this case? — hilberts_drinking_problem
@hilberts_drinking_problem no. In that case the other person continues until he has moves available — Ankit Kumar
Question is not really clear to me. Do players gain scores as they go to each node (so sum the scores of all nodes you visited), or do they only have the score of their current node in the end of the game. Also, if you pass through a node, can you revisit it? and other player simply cannot use it? Because then you might want to visit nodes with small scores to block access to large chunks and then collect them later when other player has no moves left etc. Please clarify the problem. — ozgeneral
Wont a dynamic programming approach work? Where each step, all adjacent vertices are considered? — Xander
because there are simply too many combinations in the game. Say you have a node that acts as a passage to many high score nodes, if you get the entrance although the score of that node is zero, you will win eventually because you can collect all high score nodes that will be reserved to you. In some other situations you might need to go greedy and just collect nodes with highest scores. In some other cases you might be interested in removing best case actions of your opponents, or trap your opponent by encircling him etc. So, it depends greatly on the game state, its a "minmax" problem — ozgeneral

Masoud Keshavarz Masoud Keshavarz · Accepted Answer · 2019-08-14T05:41:19

As already mentioned in comments this is a complex problem, many situations should be considered like a chess game and decisions highly depend on how graph would be initialized and it seems graph is initializing randomly. Hence in my opinion there is not a simple approach to win and it requires a heuristic algorithm.

Things prove that it requires a heuristic algorithm: (as mentioned in comments)

Need to visit a node with small score to block access to a large one and then collect it later when other player has no moves left
Need to make other player out of moves
Situations where need to force to go for nodes with highest scores first

I believe to make a logical decision for next move a minimax tree should be created (just like what happens in a normal chess game). Each node should be labeled with a value which indicates how good it is to be reached and this value should be calculated by a position evaluation function. Finally player A makes the move with considering player B next possible move. To make it optimal an alpha-beta pruning algorithm could be considered.

It is much likely player B have higher chance to win most of games because he starts with highest score. But if graph be initialized in a way that player A could block player B's access to other node player A could win. Consider this graph:

Acquire maximum nodes (score) in a graph

1 Answers