I'm prototyping a deterministic Risk like game. A player can move units from one node to a connected node if he has more than 1 unit the in origin node (must leave 1 unit behind). The player wins if he conquers the enemy's home node. Battles are settled by multiplying the node's defensive units by the defensive rate and then subtracting the attacking units; if the result is a number higher than 0 the attacking player conquers the node and the surviving units are moved to the conquered node. A node has a spawn rate that spawns units (belonging to the player controlling the node) every x turns.
I don't have much experience with graphs so I'm hoping I can get some help finding an algorithm that can calculate either the shortest possible winning move (if we are in a winning position) or the list of possible defensive moves that can be taken to avoid the other player win (if the other player has a shot at winning, but we can do something about it).
[EDIT] On each node there are two numbers: the top number represents the number of units in that node, and the bottom number represents the spawn rate, which for this examples is always 0
Node indexes that I'll use bellow: [First level] 0,0 [Second level] 1,0; 1,1 [Third level] 2,0; 2,1, 2,2 ...
For this example the nodes are only connected from one level to the other; one diagonal away. This will not matter for the algorithm as every node will know which nodes it has connection with.
(1,0 is connected with: 0,0; 2,0; 2,1)
(2,1 is connected with: 1,0; 1,1; 3,1; 3,2), etc
Home node is 0,0
Red to move
Red has two possible winning moves:
[Shortest] 3,0 -> 2,0 -> 1,0 -> 0,0 + 2,2 -> 1,1 -> 0,0
[Longest (should be ignored)] 3,0 -> 2,0 -> 1,0 -> 0,0 + 3,2 -> 2,1 / 2,2 -> 1,1 -> 0,0
Green to move
Green has four moves he must choose from to avoid certain defeat:
3,1 -> 2,0 | 3,1 -> 2,1 | 3,2 -> 2,1 | 2,2 -> 1,1
The algorithm doesn't need to take into account the defensive rate and the spawn rate. I can figure that part out.
Hopefully this will be not too difficult for someone with graph related algorithm experience.
To clarify something asked in the comments: The players take turns doing moves, sequentially, and may only move units (from one node to another) once per turn. The algorithm must take into account possible counter play by the opponent, and discard solutions where the opponent was able to defend in time.
It is important to chose the shortest winning move so that in cases where the opponent also has a a winning move (on another graph, an inverted triangle from the one depicted in the image, but with the "home node" colored red, belonging to the opponent), we can then compare the winning move sequence length and see who gets there first.
I don't want an algorithm to solve the entire game, only the sub game depicted in the example. For the entire game I'm using MCTS where other moves are considered, like which nodes to update, etc. This algorithm will be used for selection / expand, and possibly rollout in the MCTS, if I get something very fast.
Currently I'm looking into backwards induction, it is straight forward to implement, but it is quite expensive, even with lots of optimizations (discussion in the comments). So a more performant alternative would be great!