aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMatt Strapp <strap012@umn.edu>2021-04-25 21:26:14 -0500
committerMatt Strapp <strap012@umn.edu>2021-04-25 21:26:14 -0500
commitf93824e6d9694e26521aa7bdcfc44476d2404451 (patch)
tree91b995ae0433c2f624501fd617c027509f9ce46a
parentRearrange files (diff)
downloadcsci4511w-f93824e6d9694e26521aa7bdcfc44476d2404451.tar
csci4511w-f93824e6d9694e26521aa7bdcfc44476d2404451.tar.gz
csci4511w-f93824e6d9694e26521aa7bdcfc44476d2404451.tar.bz2
csci4511w-f93824e6d9694e26521aa7bdcfc44476d2404451.tar.lz
csci4511w-f93824e6d9694e26521aa7bdcfc44476d2404451.tar.xz
csci4511w-f93824e6d9694e26521aa7bdcfc44476d2404451.tar.zst
csci4511w-f93824e6d9694e26521aa7bdcfc44476d2404451.zip
Basic implementation
Co-authored-by: Andrea Smith <andrea-smith@users.noreply.github.com>
-rw-r--r--Algorithm.py52
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