Basic implementation

Co-authored-by: Andrea Smith <andrea-smith@users.noreply.github.com>

1 files changed, 51 insertions, 1 deletions

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