How to find an algorithm to calculate the best move for this graph based strategy game?

Question

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).

Examples

[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.

[EDIT]

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!

Answer 1

Following Arno suggestion in the comments I've done a C# backwards induction implementation that includes dealing with state transposition. Here is the code for the runner class, the node class should be very straight forward to do. Hopefully it will help someone!

public class BackwardsInduction
{
    private Func<IGameState, Move[]> moveSelectionFunc;
    private Func<IGameState, double[]> scoresFunc;
    private readonly double defaultScore;
    private readonly int nodeStartLevel;
    private readonly int nodeEndLevel;
    private List<List<BINode>> nodesPerLevel;

    private List<IGameState> gameStates;

    private Dictionary<int, BINode> visitedGameStatesHash;

    public BackwardsInduction(Func<IGameState, Move[]> moveSelectionFunc, Func<IGameState, double[]> scoresFunc, double defaultScore, int nodeStartLevel, int nodeEndLevel)
    {
        this.moveSelectionFunc = moveSelectionFunc;
        this.scoresFunc = scoresFunc;
        this.defaultScore = defaultScore;
        this.nodeStartLevel = nodeStartLevel;
        this.nodeEndLevel = nodeEndLevel;
        nodesPerLevel = new List<List<BINode>>();
        gameStates = new List<IGameState>();
        visitedGameStatesHash = new Dictionary<int, BINode>();
    }


    public BINode RunGetRootNode(IGameState rootState, int? maxDepth)
    {
        var rootNode = new BINode(playerJustMoved: rootState.PlayerToMove, defaultScore: defaultScore);
        nodesPerLevel.Add(new List<BINode>() { rootNode });
        Run(rootState, rootNode, maxDepth);
        if (rootNode == null)
        {
            return null;
        }
        BackFillScores();

        return rootNode;
    }

    public void Run(IGameState currentState, BINode currentNode, int? maxDepth, int currentLevel = 0)
    {
        var availableMoves = moveSelectionFunc(currentState);
        if (availableMoves.Length == 0)
        {
            currentNode.Scores = scoresFunc(currentState);
        }
        if (nodesPerLevel.Count <= currentLevel)
        {
            nodesPerLevel.Add(new List<BINode>());
        }
        if (maxDepth == null || currentLevel < maxDepth.Value)
        {
            foreach (var move in availableMoves)
            {
                var newState = currentState.Clone() as IGameState;
                var thisNodePlayerJustMoved = newState.PlayerToMove;
                newState.DoMove(move);
                var gameStateHash = GetGameStateHashCode(newState);
                if (visitedGameStatesHash.TryGetValue(gameStateHash, out BINode transposedNode))
                {
                    currentNode.AddTransposedNode(transposedNode);
                    continue;
                }

                var newNode = currentNode.AddChildGetNode(move, thisNodePlayerJustMoved, newState);
                visitedGameStatesHash.Add(gameStateHash, newNode);

                nodesPerLevel[currentLevel].Add(newNode);

                Run(newState, newNode, maxDepth, currentLevel + 1);
            }
        }
    }

    public void BackFillScores()
    {
        for (int i = nodesPerLevel.Count - 2; i >= 0; i--)
        {
            foreach (var node in nodesPerLevel[i])
            {
                if (node.ChildNodes.Any())
                {
                    node.Scores = node.ChildNodes.MinObject(x => x.Scores[x.PlayerJustMoved.Id]).Scores;
                }
            }
        }
    }

    private int GetGameStateHashCode(IGameState gameState)
    {
        unchecked
        {
            int hash = 17;
            for (int level = nodeStartLevel; level <= nodeEndLevel; level++)
            {
                var levelNodes = gameState.Nodes[level];
                for (int index = 0; index < levelNodes.Length; index++)
                {
                    hash = hash * 23 + levelNodes[index].GetSimplifiedHash();
                }
            }
            hash = hash * 23 + gameState.PlayerToMove.Id;
            hash = hash * 23 + gameState.PlayerToMove.MoveCount;
            return hash;
        }
    }
}

This is not the optimal solution for my scenario because it has to process a huge state tree and is quite expensive. But it solves my problem for now and outputs the correct result.