Let's say we have a simple connected and undirected graph $G(V,E)$. The game is played with two players. For each game, player A starts at a node $t$, and player B at a node $v$. There is also a node $d$ which is the same for every game.

In the game, player A always plays first. His goal is to reach node $d$ before player B reaches him (player B can't go to node $d$). Player B's goal, on the other hand, is to reach the node where A is. If players A,B have been in nodes $x,y$, respectively, in a previous round, and these positions are repeated again, the match ends in a tie. In every round the player which has priority must move to a neighboring node.

What I need is to make an algorithm that gives as output the result of this game for every possible starting combination $t,v \in V$ (where $t\ne v$).

What I've done so far is a dynamic programming $O(|V|^3)$ solution. We can record all possible states of this game as (position of player A, position of player B, next player to move), and find all the possible resulting states for every state.

Could this be done any better?

  • $\begingroup$ In "an algorithm that gives as output the result of this game", I assume you meant the best result for A in this game with B playing in the smartest way. Is tie a better result for A than the situation when B reaches $d$ before A reaches $d$? If B has reaches $d$, can a tie happen after that? Is tie a worse result for A than the situation when none of them reaches $d$? You did not specify explicitly that A and B play in turn, which must be, I assume, the case. $\endgroup$
    – John L.
    Dec 30, 2018 at 18:58
  • $\begingroup$ We assume that A,B always make the best possible choice.Player B can't visit node d.Yes in each turn only one player plays starting with player A in turn 1 continuing with B,again A...etc $\endgroup$ Dec 30, 2018 at 19:08
  • $\begingroup$ "A dynamic programming $O(|V|^3)$ solution" looks like non-trivial to me. Can you share that solution of yours? $\endgroup$
    – John L.
    Dec 30, 2018 at 22:03


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.