From 32118bd22ae3acf5aea9c473db405498831e13ad Mon Sep 17 00:00:00 2001
From: Matt Strapp <strap012@umn.edu>
Date: Mon, 26 Apr 2021 13:07:08 -0500
Subject: Test commit

---
 Algorithm.py | 128 ++++++++++++++++++++++++++++++++++++-----------------------
 1 file changed, 79 insertions(+), 49 deletions(-)

(limited to 'Algorithm.py')

diff --git a/Algorithm.py b/Algorithm.py
index 5a2e4f8..99488a8 100644
--- a/Algorithm.py
+++ b/Algorithm.py
@@ -1,3 +1,11 @@
+# import MCTS
+import math
+from copy import deepcopy
+from time import clock
+from random import choice
+
+from GameState import GameState
+
 class Algo: # A class for defining algorithms used (minimax and alpha-beta pruning)
     
     def miniMax(State, Ply_num): # Function for the minimax algorithm
@@ -66,53 +74,75 @@ class Algo: # A class for defining algorithms used (minimax and alpha-beta pruni
                 return Result
 
         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
+# class MCTSNode(object):
+#     """Monte Carlo Tree Node.
+#     Each node encapsulates a particular game state, the moves that
+#     are possible from that state and the strategic information accumulated
+#     by the tree search as it progressively samples the game space.
+#     """
+
+#     def __init__(self, state, parent=None, move=None):
+#         self.parent = parent
+#         self.move = move
+#         self.state = state
+
+#         self.plays = 0
+#         self.score = 0
+
+#         self.pending_moves = state.get_moves()
+#         self.children = []
+
+#     def select_child_ucb(self):
+#         # Note that each node's plays count is equal
+#         # to the sum of its children's plays
+#         def ucb(child):
+#             win_ratio = child.score / child.plays \
+#                         + math.sqrt(2 * math.log(self.plays) / child.plays)
+#             return win_ratio
+
+#         return max(self.children, key=ucb)
+
+#     def expand_move(self, move):
+#         self.pending_moves.remove(move)  # raises KeyError
+
+#         child_state = deepcopy(self.state)
+#         child_state.play_move(move)
+
+#         child = MCTSNode(state=child_state, parent=self, move=move)
+#         self.children.append(child)
+#         return child
+
+#     def get_score(self, result):
+#         # return result
+#         if result == 0.5:
+#             return result
+
+#         if self.state.player == 2:
+#             if self.state.next_turn_player == result:
+#                 return 0.0
+#             else:
+#                 return 1.0
+#         else:
+#             if self.state.next_turn_player == result:
+#                 return 1.0
+#             else:
+#                 return 0.0
+
+#         if self.state.next_turn_player == result:
+#             return 0.0
+#         else:
+#             return 1.0
+
+#     def __repr__(self):
+#         s = 'ROOT\n' if self.parent is None else ''
+
+#         children_moves = [c.move for c in self.children]
+
+#         s += """Score ratio: {score} / {plays}
+# Pending moves: {pending_moves}
+# Children's moves: {children_moves}
+# State:
+# {state}\n""".format(children_moves=children_moves, **self.__dict__)
+
+#         return s        
\ No newline at end of file
-- 
cgit v1.2.3