MonteCarloTreeSearch.java

packagecom.thealgorithms.searches;

importjava.util.ArrayList;
importjava.util.Collections;
importjava.util.Comparator;
importjava.util.Random;

/**
 * Monte Carlo Tree Search (MCTS) is a heuristic search algorithm used in
 * decition taking problems especially games.
 *
 * See more: https://en.wikipedia.org/wiki/Monte_Carlo_tree_search,
 * https://www.baeldung.com/java-monte-carlo-tree-search
 */
publicclassMonteCarloTreeSearch {

publicclassNode {

Nodeparent;
ArrayList<Node> childNodes;
booleanisPlayersTurn; // True if it is the player's turn.
booleanplayerWon; // True if the player won; false if the opponent won.
intscore;
intvisitCount;

publicNode() {
 }

publicNode(Nodeparent, booleanisPlayersTurn) {
this.parent = parent;
childNodes = newArrayList<>();
this.isPlayersTurn = isPlayersTurn;
playerWon = false;
score = 0;
visitCount = 0;
 }
 }

staticfinalintWIN_SCORE = 10;
staticfinalintTIME_LIMIT = 500; // Time the algorithm will be running for (in milliseconds).

/**
 * Explores a game tree using Monte Carlo Tree Search (MCTS) and returns the
 * most promising node.
 *
 * @param rootNode Root node of the game tree.
 * @return The most promising child of the root node.
 */
publicNodemonteCarloTreeSearch(NoderootNode) {
NodewinnerNode;
doubletimeLimit;

// Expand the root node.
addChildNodes(rootNode, 10);

timeLimit = System.currentTimeMillis() + TIME_LIMIT;

// Explore the tree until the time limit is reached.
while (System.currentTimeMillis() < timeLimit) {
NodepromisingNode;

// Get a promising node using UCT.
promisingNode = getPromisingNode(rootNode);

// Expand the promising node.
if (promisingNode.childNodes.size() == 0) {
addChildNodes(promisingNode, 10);
 }

simulateRandomPlay(promisingNode);
 }

winnerNode = getWinnerNode(rootNode);
printScores(rootNode);
System.out.format("%nThe optimal node is: %02d%n", rootNode.childNodes.indexOf(winnerNode) + 1);

returnwinnerNode;
 }

publicvoidaddChildNodes(Nodenode, intchildCount) {
for (inti = 0; i < childCount; i++) {
node.childNodes.add(newNode(node, !node.isPlayersTurn));
 }
 }

/**
 * Uses UCT to find a promising child node to be explored.
 *
 * UCT: Upper Confidence bounds applied to Trees.
 *
 * @param rootNode Root node of the tree.
 * @return The most promising node according to UCT.
 */
publicNodegetPromisingNode(NoderootNode) {
NodepromisingNode = rootNode;

// Iterate until a node that hasn't been expanded is found.
while (promisingNode.childNodes.size() != 0) {
doubleuctIndex = Double.MIN_VALUE;
intnodeIndex = 0;

// Iterate through child nodes and pick the most promising one
// using UCT (Upper Confidence bounds applied to Trees).
for (inti = 0; i < promisingNode.childNodes.size(); i++) {
NodechildNode = promisingNode.childNodes.get(i);
doubleuctTemp;

// If child node has never been visited
// it will have the highest uct value.
if (childNode.visitCount == 0) {
nodeIndex = i;
break;
 }

uctTemp = ((double) childNode.score / childNode.visitCount) + 1.41 * Math.sqrt(Math.log(promisingNode.visitCount) / (double) childNode.visitCount);

if (uctTemp > uctIndex) {
uctIndex = uctTemp;
nodeIndex = i;
 }
 }

promisingNode = promisingNode.childNodes.get(nodeIndex);
 }

returnpromisingNode;
 }

/**
 * Simulates a random play from a nodes current state and back propagates
 * the result.
 *
 * @param promisingNode Node that will be simulated.
 */
publicvoidsimulateRandomPlay(NodepromisingNode) {
Randomrand = newRandom();
NodetempNode = promisingNode;
booleanisPlayerWinner;

// The following line randomly determines whether the simulated play is a win or loss.
// To use the MCTS algorithm correctly this should be a simulation of the nodes' current
// state of the game until it finishes (if possible) and use an evaluation function to
// determine how good or bad the play was.
// e.g. Play tic tac toe choosing random squares until the game ends.
promisingNode.playerWon = (rand.nextInt(6) == 0);

isPlayerWinner = promisingNode.playerWon;

// Back propagation of the random play.
while (tempNode != null) {
tempNode.visitCount++;

// Add wining scores to bouth player and opponent depending on the turn.
if ((tempNode.isPlayersTurn && isPlayerWinner) || (!tempNode.isPlayersTurn && !isPlayerWinner)) {
tempNode.score += WIN_SCORE;
 }

tempNode = tempNode.parent;
 }
 }

publicNodegetWinnerNode(NoderootNode) {
returnCollections.max(rootNode.childNodes, Comparator.comparing(c -> c.score));
 }

publicvoidprintScores(NoderootNode) {
System.out.println("N.\tScore\t\tVisits");

for (inti = 0; i < rootNode.childNodes.size(); i++) {
System.out.printf("%02d\t%d\t\t%d%n", i + 1, rootNode.childNodes.get(i).score, rootNode.childNodes.get(i).visitCount);
 }
 }
}