diff options
| author | Matt Strapp <strap012@umn.edu> | 2021-04-25 21:26:14 -0500 |
|---|---|---|
| committer | Matt Strapp <strap012@umn.edu> | 2021-04-25 21:26:14 -0500 |
| commit | f93824e6d9694e26521aa7bdcfc44476d2404451 (patch) | |
| tree | 91b995ae0433c2f624501fd617c027509f9ce46a | |
| parent | Rearrange files (diff) | |
| download | csci4511w-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.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
|