Package search.mcts

Class MCTS

java.lang.Object

search.AI

search.mcts.MCTS

public class MCTS
extends AI

An implementation of a Monte Carlo Tree Search for the game Jump Sturdy.

Field Summary

Fields

Modifier and Type	Field	Description
double	numberOfAllSimulations

Constructor Summary

Constructors

Constructor	Description
MCTS()

Method Summary

Modifier and Type	Method	Description
boolean	continueSearch(double endTime)	Checks whether the search should continue based on the end time-
MCTSNode	expandAndReturnRandomNode(MCTSNode node, MoveGenerator moveGenerator, Color color, LinkedList<Integer> children)	Expands the given MCTS node by creating new child nodes for each possible move and returns one of the created child nodes at random.
int	getBestMove(MCTSNode node)	Determines the average wins per visit for each child of a give node and chooses the child that maximizes this value.
String	orchestrator(String fen, SearchConfig config)	Orchestrates the AI on the given FEN position and search configuration.
void	propagateDataToRoot(MCTSNode node, int reward, Color colorOfExpandedPlayer)	Propagates the results of a simulation back up to the root of the Monte Carlo Tree Search (MCTS) tree.
String	showConfig()	Returns the configuration of the AI.
int	simulateToEnd(Color color, MoveGenerator moveGenerator, Color parentColor)	Simulates the game to the end using a probabilistic approach weighted by the number of possible moves or each player.
void	treePolicy(MoveGenerator moveGenerator, MCTSNode node, Color color)	Executes the tree policy for the Monte Carlo Tree Search (MCTS) algorithm.
MCTSNode	treeTraversal(double endtime, MCTSNode node, MoveGenerator moveGenerator)	Performs a tree traversal in the Monte Carlo Tree Search (MCTS) algorithm.

Methods inherited from class search.AI

toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Details

numberOfAllSimulations

public double numberOfAllSimulations

Constructor Details

MCTS

public MCTS()

Method Details

orchestrator

public String orchestrator(String fen,
 SearchConfig config)

Description copied from class: AI

Orchestrates the AI on the given FEN position and search configuration.

Specified by:

orchestrator in class AI

Parameters:

fen - The current position in FEN notation

config - The configuration object specifying the AI search parameters

Returns:

The best move determined by the search algorithm

showConfig

public String showConfig()

Description copied from class: AI

Returns the configuration of the AI.

Specified by:

showConfig in class AI

Returns:

The configuration object

getBestMove

public int getBestMove(MCTSNode node)

Determines the average wins per visit for each child of a give node and chooses the child that maximizes this value.

Parameters:

node - The MCTSNode representing the current state in the search tree.

Returns:

An integer representing the best move.

simulateToEnd

public int simulateToEnd(Color color,
 MoveGenerator moveGenerator,
 Color parentColor)

Simulates the game to the end using a probabilistic approach weighted by the number of possible moves or each player.

Parameters:

color - The color of the player to move.

moveGenerator - The MoveGenerator object used to generate and execute moves.

parentColor - The color of the root node in the Monte Carlo Tree Search (MCTS).

Returns:

An integer representing the simulation result: 1 if the parent color wins, otherwise 0

continueSearch

public boolean continueSearch(double endTime)

Checks whether the search should continue based on the end time-

Parameters:

endTime - The maximum time allowed for evaluating moves, in milliseconds.

Returns:

true if the current system time is less or equal than the end time, false if the current system time is more than the end time.

treeTraversal

public MCTSNode treeTraversal(double endtime,
 MCTSNode node,
 MoveGenerator moveGenerator)

Performs a tree traversal in the Monte Carlo Tree Search (MCTS) algorithm.

Parameters:

endtime - The time at which the search should stop, in milliseconds.

node - The current MCTSNode from which to start the traversal.

moveGenerator - The MoveGenerator object used to generate and execute moves.

Returns:

The MCTSNode reached at the end of the traversal.

expandAndReturnRandomNode

public MCTSNode expandAndReturnRandomNode(MCTSNode node,
 MoveGenerator moveGenerator,
 Color color,
 LinkedList<Integer> children)

Expands the given MCTS node by creating new child nodes for each possible move and returns one of the created child nodes at random.

Parameters:

node - The MCTSNode to be expanded.

moveGenerator - The MoveGenerator object used to generate and execute moves.

color - The color of the children.

children - A list of possible moves (as integers) from the current node.

Returns:

A randomly selected MCTSNode from the newly created children.

treePolicy

public void treePolicy(MoveGenerator moveGenerator,
 MCTSNode node,
 Color color)

Executes the tree policy for the Monte Carlo Tree Search (MCTS) algorithm. This traverses the search tree, expands nodes, and performs simulations to update the tree with new information.

Parameters:

moveGenerator - The MoveGenerator object used to generate and execute moves.

node - The current MCTSNode from which to start the tree policy.

color - The color of the current node making the move.

propagateDataToRoot

public void propagateDataToRoot(MCTSNode node,
 int reward,
 Color colorOfExpandedPlayer)

Propagates the results of a simulation back up to the root of the Monte Carlo Tree Search (MCTS) tree. This method updates the win and visit counts of the nodes.

Parameters:

node - The Leaf MCTSNode from which to start the propagation.

reward - The reward obtained from the simulation (1 for a win, 0 for a loss).

colorOfExpandedPlayer - The color of the leaf node (last expanded node).