diff options
| -rw-r--r-- | Algorithm.py | 52 |
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
|