From f93824e6d9694e26521aa7bdcfc44476d2404451 Mon Sep 17 00:00:00 2001 From: Matt Strapp Date: Sun, 25 Apr 2021 21:26:14 -0500 Subject: Basic implementation Co-authored-by: Andrea Smith --- Algorithm.py | 52 +++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 51 insertions(+), 1 deletion(-) diff --git a/Algorithm.py b/Algorithm.py index 85a9f15..5a2e4f8 100644 --- a/Algorithm.py +++ b/Algorithm.py @@ -65,4 +65,54 @@ class Algo: # A class for defining algorithms used (minimax and alpha-beta pruni if Result < Beta: return Result - return Minimum_Score \ No newline at end of file + return Minimum_Score +class MCTS: + # main function for the Monte Carlo Tree Search + + def monte_carlo_tree_search(root): + + while resources_left(time, computational power): + leaf = traverse(root) + simulation_result = rollout(leaf) + backpropagate(leaf, simulation_result) + + return best_child(root) + +# function for node traversal + + + def traverse(node): + while fully_expanded(node): + node = best_uct(node) + + # in case no children are present / node is terminal + return pick_univisted(node.children) or node + +# function for the result of the simulation + + + def rollout(node): + while non_terminal(node): + node = rollout_policy(node) + return result(node) + +# function for randomly selecting a child node + + + def rollout_policy(node): + return pick_random(node.children) + +# function for backpropagation + + + def backpropagate(node, result): + if is_root(node) return + node.stats = update_stats(node, result) + backpropagate(node.parent) + +# function for selecting the best child +# node with highest number of visits + + + def best_child(node): + #pick child with highest number of visits -- cgit v1.2.3