Decisions.. Decisions..

The past month I have been working on bot logic and a decision graph implementation along with the various refactoring needed for it to seamlessly integrate and easily extract the data it needs mid game. Good news is, it is finished and works great from my testing so far, bad news (for me anyway) is it kind of grew some legs and became a mess. Luckily it is still manageable, and I’m not going to spend time on re-writing it atm just to appease my code OCD.

I started off with a simple node structure that each house a list of decisions that need evaluate true for a node to “activate” after which if it was a decision node. If the decisions evaluated true it begins traversal of it children nodes, and continuing down until either reaching an action node (sending the bots action to the game state) which returns true and pops back up to the root node, or reaching a node that return false, in which case it would pop back up until reaching a parent node with un-traversed children remaining and traversing down them. This process repeats with the goal reaching a decision state that leads to a valid and playable action node based of that decision. The action nodes each contain one action that relates to an action in game (potion, attack, ability) that is then broadcast with parameters from mutable state that is pass along during the traversal and updated/overwritten via the decisions node as to correspond with the action to be performed.

The state part is what added a lot of the mess, as the decisions and nodes part is easy, but to integrate the action parameters that are need to inform the actions of what their goals and targets should be is messy, as this now becomes a “decision” at the end of certain decision list, that always evaluates true, and just updates the state with the parameters it needs. While this is simple in theory it adds a slew of de-bugging issue if any mistakes are made during the implementation of these. Luckily this hasn’t been an issue so far, but it definitely starts making things messy quick. To help offset de-bugging issues and to allow for validation I added in json logging of bot decisions that let me see the flow of decisions and updates to the state, which in the end is a good thing and will help a lot when reimplementing different logic. I plan later to rewrite the state interactions, as to allow the bot the have programmable strategies and larger “awareness” to it state. Due to doing this all in code, there is also the mess of a lot of boilerplate. All of the decisions need to be an overridden object, and all of the nodes need to be instanced, and then the graph can be made by combining the nodes to each other to form the graph . The graph is only like 100 lines of code, with most being extra formatting I added for easier reading. The decisions don’t matter that much as they are gonna be a fair amount of code either way. But there is a ton of boilerplate of instancing the nodes and adding the decisions to them, before I can even add their children.

To start the implementation and to be able to visualize everything to keep things in order, I used a flow chart representing the graph and kept it updated during the implementation of the decisions and nodes needed as to have a reference of that was need and to refer to when combining them.

This ended up thinning out more during implementation as I noticed I could simplify things at times and the brackets are single decisions that are combined into a decision list for a single node.

For the code, there are Actions Node, Actions, Decisions Nodes and Decisions, with the Nodes extending a Node class. The Action node extended to include it’s action, and the decision node to include a list of decisions. These all override the base method of Node which was “travel”. The the Actions and Decisions classes each were abstract and had an overridden method to implement their logic.

    // Node Base Class
    public abstract class Node {
        protected final String name;
        protected final Type type;
        protected final ArrayList<Node> adjacentNodes = new ArrayList<>(10);

        public Node(Type type, String name) {
            this.type = Type.ROOT;
            this.name = name;
        }

        public abstract boolean travel(BotPlayerState botPlayerState, TreeFocusState focusState, PawnIndex selfIndex);

        public Type getType() {
            return type;
        }

        public ArrayList<Node> getAdjacentNodes() {
            return adjacentNodes;
        }

        public String getName() {
            return name;
        }

        public void addAdjacent(Node node) {
            if (type == Type.ACTION) return;
            if (adjacentNodes.contains(node)) return;
            adjacentNodes.add(node);
        }

        public enum Type {
            ROOT,
            DECISION,
            ACTION
        }
    }


    // Decision Node

    public class DecisionNode extends Node{
        private final Decision[] decisions;

        public DecisionNode(String name, Decision[] decisions) {
            super(DECISION, name);
            this.decisions = decisions;
        }

        @Override
        public boolean travel(BotPlayerState botPlayerState, TreeFocusState focusState, PawnIndex selfIndex) {

            for (Decision decision : decisions) {

                var rtn = decision.getDecision(botPlayerState, focusState , selfIndex);

                if (rtn) focusState.decisions.add(name);
                if (!rtn) return false;

            }

            for (Node node : adjacentNodes) {

                if (node.travel(botPlayerState, focusState, selfIndex)) {
                    return true;
                }
            }
            return false;
        }
    }


    // Action Node

    public ActionNode(Action action, String name) {
        super(ACTION, name);
        this.action = action;
    }

    @Override
    public boolean travel(BotPlayerState botPlayerState, TreeFocusState focusState, PawnIndex selfIndex) {

        var rtn =  action.doAction(botPlayerState, focusState, selfIndex);
        if (rtn) focusState.action = name;
        return rtn;
    }


    // Decision

    public abstract class Decision {
        private final String name;

        public Decision(String name) {
            this.name = name;
        }

        public abstract boolean getDecision(BotPlayerState botPlayerState, TreeFocusState focusState, PawnIndex selfIndex);

        public String getName() {
            return name;
        }

    }

    //Action

    public abstract class Action {
        public abstract boolean doAction(BotPlayerState botPlayerState, TreeFocusState focusState, PawnIndex selfIndex);
    }

Then the actions and decisions had their implementations declared in an Actions and Decisions class. Decisions would get their data from the BotPlayerState, and here I used a lot of java streams for imperative processing of data used for the basis of the decisions, with the use of short circuiting to avoid pointless calculations once futile.

Then a final implementation looked like this (These are just parts, cant reveal the whole bot logic).

  public final Node canBuff50Pct = new DecisionNode("CanBUff50/50", new Decision[]{
            Decisions.chance50Pct,
            Decisions.canBuff
    });

    public final Node doBuff = new ActionNode(Actions.selectBestBuff, "DoBuff");


// Formatted like this for easier visual parsing
// Can is the decisions node, do is the action
// Then the were all chained together, with the burden of
// staying mindful to existing ones, as multiple nodes feed into each other.

playerEqualHP.addAdjacent(canBuff50Pct);
    {
        canBuff50Pct.addAdjacent(doBuff);
    }
    ...

It all started a simple tree structure, but evolved to a graph, then kind of became a mess realizing I needed to add a state to it, as I battled implementing it half way through and felt the final results could’ve been better if designing around it.