Generic domain independent Monte Carlo Tree Search methods library

Question

I've written this small generic library for the purpose of my Bachelor's thesis. It's fully functional and unit tested and I want to get as many opinions as possible regarding overall code quality (readability, naming, structure, coupling, cohesion, etc.).

GitHub (this project is licensed under the terms of the MIT license)

Usage

Mcts<State, Action, Player> mcts = Mcts.initializeIterations(NUMBER_OF_ITERATIONS);
Action mostPromisingAction = mcts.uctSearchWithExploration(state, explorationParameter);

Interfaces

public interface MctsDomainState<ActionT, AgentT extends MctsDomainAgent> {

    boolean isTerminal();
    AgentT getCurrentAgent();
    AgentT getPreviousAgent();
    int getNumberOfAvailableActionsForCurrentAgent();
    List<ActionT> getAvailableActionsForCurrentAgent();
    MctsDomainState performActionForCurrentAgent(ActionT action);
    MctsDomainState skipCurrentAgent();
}

public interface MctsDomainAgent<StateT extends MctsDomainState> {

    StateT getTerminalStateByPerformingSimulationFromState(StateT state);
    double getRewardFromTerminalState(StateT terminalState);
}

Class that iteratively builds the search tree

public class Mcts<StateT extends MctsDomainState<ActionT, AgentT>, ActionT, AgentT extends MctsDomainAgent<StateT>> {

    private static final double NO_EXPLORATION = 0;

    private final int numberOfIterations;
    private double explorationParameter;
    private final Cloner cloner;

    public static<StateT extends MctsDomainState<ActionT, AgentT>, ActionT, AgentT extends MctsDomainAgent<StateT>>
        Mcts<StateT, ActionT, AgentT> initializeIterations(int numberOfIterations) {
            Cloner cloner = new Cloner();
            return new Mcts<>(numberOfIterations, cloner);
    }

    private Mcts(int numberOfIterations, Cloner cloner) {
        this.numberOfIterations = numberOfIterations;
        this.cloner = cloner;
    }

    public void dontClone(final Class<?>... classes) {
        cloner.dontClone(classes);
    }

    public ActionT uctSearchWithExploration(StateT state, double explorationParameter) {
        setExplorationForSearch(explorationParameter);
        MctsTreeNode<StateT, ActionT, AgentT> rootNode = new MctsTreeNode<>(state, cloner);
        for (int i = 0; i < numberOfIterations; i++) {
            performMctsIteration(rootNode, state.getCurrentAgent());
        }
        return getNodesMostPromisingAction(rootNode);
    }

    private void setExplorationForSearch(double explorationParameter) {
        this.explorationParameter = explorationParameter;
    }

    private void performMctsIteration(MctsTreeNode<StateT, ActionT, AgentT> rootNode, AgentT agentInvoking) {
        MctsTreeNode<StateT, ActionT, AgentT> selectedChildNode = treePolicy(rootNode);
        StateT terminalState = getTerminalStateFromDefaultPolicy(selectedChildNode, agentInvoking);
        backPropagate(selectedChildNode, terminalState);
    }

    private MctsTreeNode<StateT, ActionT, AgentT> treePolicy(MctsTreeNode<StateT, ActionT, AgentT> node) {
        while (!node.representsTerminalState()) {
            if (!node.representedStatesCurrentAgentHasAvailableActions())
                return expandWithoutAction(node);
            else if (!node.isFullyExpanded())
                return expandWithAction(node);
            else
                node = getNodesBestChild(node);
        }
        return node;
    }


    private MctsTreeNode<StateT, ActionT, AgentT> expandWithoutAction(MctsTreeNode<StateT, ActionT, AgentT> node) {
        return node.addNewChildWithoutAction();
    }

    private MctsTreeNode<StateT, ActionT, AgentT> expandWithAction(MctsTreeNode<StateT, ActionT, AgentT> node) {
        ActionT randomUntriedAction = getRandomActionFromNodesUntriedActions(node);
        return node.addNewChildFromAction(randomUntriedAction);
    }

    private ActionT getRandomActionFromNodesUntriedActions(MctsTreeNode<StateT, ActionT, AgentT> node) {
        List<ActionT> untriedActions = node.getUntriedActionsForCurrentAgent();
        Collections.shuffle(untriedActions);
        return untriedActions.get(0);
    }

    private MctsTreeNode<StateT, ActionT, AgentT> getNodesBestChild(MctsTreeNode<StateT, ActionT, AgentT> node) {
        validateBestChildComputable(node);
        return getNodesBestChildConfidentlyWithExploration(node, explorationParameter);
    }

    private void validateBestChildComputable(MctsTreeNode<StateT, ActionT, AgentT> node) {
        if (!node.hasChildNodes())
            throw new UnsupportedOperationException("Error: operation not supported if child nodes empty");
        else if (!node.isFullyExpanded())
            throw new UnsupportedOperationException("Error: operation not supported if node not fully expanded");
        else if (node.hasUnvisitedChild())
            throw new UnsupportedOperationException(
                    "Error: operation not supported if node contains an unvisited child");
    }

    private ActionT getNodesMostPromisingAction(MctsTreeNode<StateT, ActionT, AgentT> node) {
        validateBestChildComputable(node);
        MctsTreeNode<StateT, ActionT, AgentT> bestChildWithoutExploration =
                getNodesBestChildConfidentlyWithExploration(node, NO_EXPLORATION);
        return bestChildWithoutExploration.getIncomingAction();
    }

    private MctsTreeNode<StateT, ActionT, AgentT> getNodesBestChildConfidentlyWithExploration(
            MctsTreeNode<StateT, ActionT, AgentT> node, double explorationParameter) {
        return node.getChildNodes().stream()
                .max((node1, node2) -> Double.compare(
                        calculateUctValue(node1, explorationParameter),
                        calculateUctValue(node2, explorationParameter))).get();
    }

    private double calculateUctValue(MctsTreeNode<StateT, ActionT, AgentT> node, double explorationParameter) {
        return node.getDomainTheoreticValue()
                + explorationParameter
                * (Math.sqrt((2 * Math.log(node.getParentsVisitCount())) / node.getVisitCount()));
    }

    private StateT getTerminalStateFromDefaultPolicy(
            MctsTreeNode<StateT, ActionT, AgentT> node, AgentT agentInvoking) {
        StateT nodesStateClone = node.getDeepCloneOfRepresentedState();
        return agentInvoking.getTerminalStateByPerformingSimulationFromState(nodesStateClone);
    }

    private void backPropagate(MctsTreeNode<StateT, ActionT, AgentT> node, StateT terminalState) {
        while (node != null) {
            updateNodesDomainTheoreticValue(node, terminalState);
            node = node.getParentNode();
        }
    }

    private void updateNodesDomainTheoreticValue(MctsTreeNode<StateT, ActionT, AgentT> node, StateT terminalState) {
        // violation of the law of demeter
        AgentT parentsStatesCurrentAgent = node.getRepresentedStatesPreviousAgent();
        double reward = parentsStatesCurrentAgent.getRewardFromTerminalState(terminalState);
        node.updateDomainTheoreticValue(reward);
    }
}

Class that represents the tree node

class MctsTreeNode<StateT extends MctsDomainState<ActionT, AgentT>, ActionT, AgentT extends MctsDomainAgent> {

    private final MctsTreeNode<StateT, ActionT, AgentT> parentNode;
    private final ActionT incomingAction;
    private final StateT representedState;
    private int visitCount;
    private double totalReward;
    private List<MctsTreeNode<StateT, ActionT, AgentT>> childNodes;
    private final Cloner cloner;

    protected MctsTreeNode(StateT representedState, Cloner cloner) {
        this(null, null, representedState, cloner);
    }

    private MctsTreeNode(MctsTreeNode<StateT, ActionT, AgentT> parentNode, ActionT incomingAction,
                         StateT representedState, Cloner cloner) {
        this.parentNode = parentNode;
        this.incomingAction = incomingAction;
        this.representedState = representedState;
        this.visitCount = 0;
        this.totalReward = 0.0;
        this.childNodes = new ArrayList<>();
        this.cloner = cloner;
    }

    protected MctsTreeNode<StateT, ActionT, AgentT> getParentNode() {
        return parentNode;
    }

    protected ActionT getIncomingAction() {
        return incomingAction;
    }

    protected int getVisitCount() {
        return visitCount;
    }

    protected int getParentsVisitCount() {
        return parentNode.getVisitCount();
    }

    protected List<MctsTreeNode<StateT, ActionT, AgentT>> getChildNodes() {
        return childNodes;
    }

    protected boolean hasChildNodes() {
        return childNodes.size() > 0;
    }

    protected boolean representsTerminalState() {
        return representedState.isTerminal();
    }

    protected AgentT getRepresentedStatesPreviousAgent() {
        return representedState.getPreviousAgent();
    }

    protected boolean representedStatesCurrentAgentHasAvailableActions() {
        return representedState.getNumberOfAvailableActionsForCurrentAgent() > 0;
    }

    protected boolean isFullyExpanded() {
        return representedState.getNumberOfAvailableActionsForCurrentAgent() == childNodes.size();
    }

    protected boolean hasUnvisitedChild () {
        return childNodes.stream()
                .anyMatch(MctsTreeNode::isUnvisited);
    }

    private boolean isUnvisited() {
        return visitCount == 0;
    }

    protected MctsTreeNode<StateT, ActionT, AgentT> addNewChildWithoutAction() {
        StateT childNodeState = getDeepCloneOfRepresentedState();
        childNodeState.skipCurrentAgent();
        return appendNewChildInstance(childNodeState, null);
    }

    protected MctsTreeNode<StateT, ActionT, AgentT> addNewChildFromAction(ActionT action) {
        if (!isUntriedAction(action))
            throw new IllegalArgumentException("Error: invalid action passed as function parameter");
        else
            return addNewChildFromUntriedAction(action);
    }

    private boolean isUntriedAction(ActionT action) {
        return getUntriedActionsForCurrentAgent().contains(action);
    }

    protected List<ActionT> getUntriedActionsForCurrentAgent() {
        List<ActionT> availableActions = representedState.getAvailableActionsForCurrentAgent();
        List<ActionT> untriedActions = new ArrayList<>(availableActions);
        List<ActionT> triedActions = getTriedActionsForCurrentAgent();
        untriedActions.removeAll(triedActions);
        return untriedActions;
    }

    private List<ActionT> getTriedActionsForCurrentAgent() {
        return childNodes.stream()
                .map(MctsTreeNode::getIncomingAction)
                .collect(Collectors.toList());
    }

    private MctsTreeNode<StateT, ActionT, AgentT> addNewChildFromUntriedAction(ActionT incomingAction) {
        StateT childNodeState = getNewStateFromAction(incomingAction);
        return appendNewChildInstance(childNodeState, incomingAction);
    }

    private StateT getNewStateFromAction(ActionT action) {
        StateT representedStateClone = getDeepCloneOfRepresentedState();
        representedStateClone.performActionForCurrentAgent(action);
        return representedStateClone;
    }

    protected StateT getDeepCloneOfRepresentedState() {
        return cloner.deepClone(representedState);
    }

    private MctsTreeNode<StateT, ActionT, AgentT> appendNewChildInstance(
            StateT representedState, ActionT incomingAction) {
        MctsTreeNode<StateT, ActionT, AgentT> childNode = new MctsTreeNode<>(
                this, incomingAction, representedState, cloner);
        childNodes.add(childNode);
        return childNode;
    }

    protected void updateDomainTheoreticValue(double rewardAddend) {
        visitCount += 1;
        totalReward += rewardAddend;
    }

    protected double getDomainTheoreticValue() {
        return totalReward / visitCount;
    }
}

Answer 1

It's really nice to see code like this up for review. I have had to do some reading up on what the Monte Carlo tree search actually is, but I have enough of an idea now that I can see where you have applied the various concepts to your code.

First up, at first, I really like the API you have managed to present. The use case is particularly neat. After digging in to it, though, I started seeing holes....

Generics

As I say, at first glance, the generics appeared good, but then I actually pulled your code, and realized there are a number of problems. The most obvious place is that I failed to compile your factory method:

public static <StateT extends MctsDomainState<ActionT, AgentT>, ActionT, AgentT extends MctsDomainAgent<StateT>>
    Mcts<StateT, ActionT, AgentT> initializeIterations(int numberOfIterations) {
        Cloner cloner = new Cloner();
        return new Mcts<>(numberOfIterations, cloner);
}

My compiler complained that it was not able to match the generics for the constructor. Normally, a problem like this would make me close-vote the question, but it's possible that my issue is environmental - my Java version may be different to yours....

Still, the problem is hard to describe, but let's look at the generic type of Mtcs, MtcsDomainAgent, and MtcsDomainState....

• MctsDomainState:

  <
   ActionT,
   AgentT extends MctsDomainAgent
  >
  

• MctsDomainAgent

  <
   StateT extends MctsDomainState
  >
  

• Mcts:

  <
    StateT extends MctsDomainState<ActionT, AgentT>,
    ActionT,
    AgentT extends MctsDomainAgent<StateT>
  >
  

The first "obvious" thing here is that your Agent and State classes don't specify the generic type of the 'nested' State/Agent. For example, there should be something "here" (where "here" is represented by <!!!!, ????>):

MctsDomainAgent <StateT extends MctsDomainState<!!!!, ????> > ....

The second 'obvious' issue is the lack of generic types on your interface methods (indicated with <****>):

public interface MctsDomainState<ActionT, AgentT extends MctsDomainAgent> {

    boolean isTerminal();
    AgentT getCurrentAgent();
    AgentT getPreviousAgent();
    int getNumberOfAvailableActionsForCurrentAgent();
    List<ActionT> getAvailableActionsForCurrentAgent();
    MctsDomainState<****> performActionForCurrentAgent(ActionT action);
    MctsDomainState<****> skipCurrentAgent();
}

What this really boils down to is the circular generic dependency you have in the state and agent classes. The way to solve a circular dependency is to introduce an additional, self-referencing generic type.

While trying to do that, I introduced a mess of build hangs in my eclipse environment .... the circular nature really messes with things.

So, I upgraded from eclipse Luna to eclipse Mars.... and that appears to have fixed it..... but, two things:

1. the circular dependency is real, and, as a result, you can't have TicTacToePlayer linked with both StaticState, and TicTacToeState. It works with only one.
2. you will need to rebuild your test cases - they are now horribly broken.

So, how have I "fixed" your dependencies? Here's the code I have. Note that it compiles with no warnings on any of the Generics:

package io.github.nejc92.mcts;

import java.util.List;

public interface MctsDomainState<S extends MctsDomainState<S, M, A>, M, A extends MctsDomainAgent<A, M, S>> {

    boolean isTerminal();

    A getCurrentAgent();

    A getPreviousAgent();

    int getNumberOfAvailableActionsForCurrentAgent();

    List<M> getAvailableActionsForCurrentAgent();

    MctsDomainState<S, M, A> performActionForCurrentAgent(M action);

    MctsDomainState<S, M, A> skipCurrentAgent();
}

There's a big change in there from a code-style perspective. Java generics by convention have just a single-letter token. I have chosen the names S for State, M for Move, and A for Agent. I was tempted to make the A a P for Player. Your call. A single-letter token makes it easier to see where there's a generic template in place. It also makes the declaration more concise.

Before I explain the declaration, here's the Agent interface:

package io.github.nejc92.mcts;

public interface MctsDomainAgent<A extends MctsDomainAgent<A, M, S>, M, S extends MctsDomainState<S, M, A>> {

    S getTerminalStateByPerformingSimulationFromState(S state);

    double getRewardFromTerminalState(S terminalState);
}

Here are the two interface declarations next to each other... there are some similarities (I have reformatted it to be clearer):

public interface MctsDomainState
       <S extends MctsDomainState<S, M, A>,
       M,
       A extends MctsDomainAgent<A, M, S>> { ..... }

public interface MctsDomainAgent
       <A extends MctsDomainAgent<A, M, S>,
       M,
       S extends MctsDomainState<S, M, A>> { ..... }

Note that the first generic is a self-referential one, and has the pattern X extends MySelf<X, ....>. This is how self referencing generics are done. The most important part about this declaration, is that it declares ourselves! Now, with that declaration, we can reuse the generic token in other parts of the declaration. For example, here:

public interface MctsDomainState
       <S extends MctsDomainState<S, M, A>,
       M,
       A extends MctsDomainAgent<A, M, S>> { ..... }

we declare S to be self-referential, and then we use S to declare the type of A which is a MctsDomainAgent.

Using these classes is surprisingly easy:

public class TicTacToePlayer
     implements MctsDomainAgent<TicTacToePlayer, String, TicTacToeState> { ....

and also:

public class TicTacToeState
    // Note: ^^^^^^^^^^^^^^ <- the class name TicTacToeState
    //          is used here    vvvvvvvvvvvvvv  as the first generic type.
     implements MctsDomainState<TicTacToeState, String, TicTacToePlayer> { ....

(see how the class name is used as the first generic token? I have added that as a comment in the second declaration...)

With the above changes, your generics are "fixed". The implementations for TicTacToe examples had to be "corrected" to have the correct return types and order for the generics as a result, though. Specifically, the Move/Action was not originally part of the generic type for the Agent, but it had to be added to correctly reference the State.

Wow, that's a lot to digest, but I hope it makes sense.

Cloning

The use of the Cloning class is odd. I realize you think it may make cloning simpler, but the truth is, I don't think it will. When you have a need for specific style of cloning, and you also have control over the classes you are cloning, then it's simpler to just add a special clone method to the class. For example, I recommend adding duplicate() to the interfaces. Note that you now have a nice generic type as well to return the value in (which clone does not):

public interface MctsDomainState<S extends MctsDomainState<S, M, A>, M, A extends MctsDomainAgent<A, M, S>> {

    ......

    S duplicate();
}

and

public interface MctsDomainAgent<A extends MctsDomainAgent<A, M, S>, M, S extends MctsDomainState<S, M, A>> {

    ....        

    A duplicate();
}

Now the duplicate functionality is clearly available, and conveniently included in the interface. The implementations now also get to choose how deep the clone should be - which is probably a detail of control that is useful to include in the class, not as parameters to some Cloner instance.

Factory methods

I have removed two of your factory methods. I find factory methods to be an anti-pattern unless subclassing is prohibited (i.e. if the class is final). For example, in your Mcts class you have:

public static<StateT extends MctsDomainState<ActionT, AgentT>, ActionT, AgentT extends MctsDomainAgent<StateT>>
    Mcts<StateT, ActionT, AgentT> initializeIterations(int numberOfIterations) {
        Cloner cloner = new Cloner();
        return new Mcts<>(numberOfIterations, cloner);
}

Why is that needed? The only place a cloner can be added, is in that method, so why not just have the cloner added in the constructor (and make that public)?

public Mcts(int numberOfIterations) {
    this.numberOfIterations = numberOfIterations;
    this.cloner = new Cloner();
}

Your TicTacToePlayer is another broken factory method. Here's the code (as it currently is in my environment):

public class TicTacToePlayer implements MctsDomainAgent<TicTacToePlayer, String, TicTacToeState> {

    private final char boardPositionMarker;

    public enum Type {
        NOUGHT, CROSS
    }

    public static TicTacToePlayer create(Type type) {
        switch (type) {
            case NOUGHT:
                return new TicTacToePlayer('O');
            case CROSS:
                return new TicTacToePlayer('X');
            default:
                throw new IllegalArgumentException("Error: invalid player type passed as function parameter");
        }
    }

    private TicTacToePlayer(char boardPositionMarker) {
        this.boardPositionMarker = boardPositionMarker;
    }

Note that the right place for the board-marker is part of the enum type. It should be:

    public enum Type {
        NOUGHT('O'),
        CROSS('X');

        private final char marker;

        Type(char marker) {
            this.marker = marker;
        }
        public char getMarker() {
            return marker;
        }
    }

Now, when you create a player, it should be a simple constructor:

    public TicTacToePlayer(Type playerType) {
        this.boardPositionMarker = playerType.getMarker();
    }

You do know that you don't really use the enum as well as you should, right? A lot more logic can be put in there.

Still, I suggest that you have far too much in the way of factory methods going on there.