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?