1 files changed, 148 insertions, 105 deletions
diff --git a/python/alphaBeta.py b/python/alphaBeta.py
index 8e041fe..7279368 100644
--- a/python/alphaBeta.py
+++ b/python/alphaBeta.py
@@ -1,105 +1,148 @@
-from GameState import GameState
-class GameController(object):
-    def get_next_move(self, state):
-        # when you get a new move, it is assumed that the game is not ended yet
-        assert state.get_moves()
-
-
-def alpha_beta(node, alpha, beta):
-
-    # Based on https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning#Pseudocode
-    # node needs to support three operations: isTerminal(), value(), getChildren(), maximizingPlayer()
-
-    if node.isTerminal():
-        return node.value()
-
-    if node.maximizingPlayer():
-
-        v = float("-inf")
-        for child in node.getChildren():
-
-            v = max(v, alpha_beta(child, alpha, beta))
-            alpha = max(alpha, v)
-            if beta <= alpha:
-                break
-
-    else:
-
-        v = float("inf")
-        for child in node.getChildren():
-
-            v = min(v, alpha_beta(child, alpha, beta))
-            beta = min(beta, v)
-            if beta <= alpha:
-                break
-
-    return v
-
-
-# A class for defining algorithms used (minimax and alpha-beta pruning)
-class AlphaBeta:
-
-    def miniMax(State, Ply_num):  # Function for the minimax algorithm
-
-        for i in range(State.Current.dimY):
-            for j in range(State.Current.dimX):
-                if State.Current.Mat[i][j] == ' ' and (j, i) not in State.children:
-                    State.Make(j, i, True)
-                    if Ply_num < 2:
-                        return (i, j)
-
-        Minimum_Score = 1000
-        i = 0
-
-        j = 0
-        for k, z in State.children.items():
-            Result = Algo.Maximum(z, Ply_num - 1, Minimum_Score)
-            if Minimum_Score > Result:
-                Minimum_Score = Result
-                i = k[0]
-                j = k[1]
-
-        return (i, j)
-
-    # Alpha-beta pruning function for taking care of Alpha values
-    def Maximum(State, Ply_num, Alpha):
-        if Ply_num == 0:
-            return State.CurrentScore
-
-        for i in range(State.Current.dimY):
-            for j in range(State.Current.dimX):
-                if State.Current.Mat[i][j] == ' ' and (j, i) not in State.children:
-                    State.Make(j, i, False)
-
-        Maximum_Score = -1000
-        i = 0
-        j = 0
-        for k, z in State.children.items():
-            Result = Algo.Minimum(z, Ply_num - 1, Maximum_Score)
-            if Maximum_Score < Result:
-                Maximum_Score = Result
-            if Result > Alpha:
-                return Result
-
-        return Maximum_Score
-
-    def Minimum(State, Ply_num, Beta):  # Alpha-beta pruning function for taking care of Beta values
-        if Ply_num == 0:
-            return State.CurrentScore
-
-        for i in range(State.Current.dimY):
-            for j in range(State.Current.dimX):
-                if State.Current.Mat[i][j] == ' ' and (j, i) not in State.children:
-                    State.Make(j, i, True)
-
-        Minimum_Score = 1000
-        i = 0
-        j = 0
-        for k, z in State.children.items():
-            Result = Algo.Maximum(z, Ply_num - 1, Minimum_Score)
-            if Minimum_Score > Result:
-                Minimum_Score = Result
-            if Result < Beta:
-                return Result
-
-        return Minimum_Score
+# 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
+
+        for i in range(State.Current.dimY):
+            for j in range(State.Current.dimX):
+                if State.Current.Mat[i][j] == ' ' and (j, i) not in State.children:
+                    State.Make(j, i, True)
+                    if Ply_num < 2:
+                        return (i, j)
+
+        Minimum_Score = 1000
+        i = 0
+
+        
+        j = 0
+        for k, z in State.children.items():
+            Result = Algo.Maximum(z, Ply_num - 1, Minimum_Score)
+            if Minimum_Score > Result:
+                Minimum_Score = Result
+                i = k[0]
+                j = k[1]
+
+        return (i, j)
+
+
+    def Maximum(State, Ply_num, Alpha): # Alpha-beta pruning function for taking care of Alpha values
+        if Ply_num == 0:
+            return State.CurrentScore
+
+        for i in range(State.Current.dimY):
+            for j in range(State.Current.dimX):
+                if State.Current.Mat[i][j] == ' ' and (j, i) not in State.children:
+                    State.Make(j, i, False)
+
+        Maximum_Score = -1000
+        i = 0
+        j = 0
+        for k, z in State.children.items():
+            Result = Algo.Minimum(z, Ply_num - 1, Maximum_Score)
+            if Maximum_Score < Result:
+                Maximum_Score = Result
+            if Result > Alpha:
+                return Result
+
+        return Maximum_Score
+
+
+    def Minimum(State, Ply_num, Beta): # Alpha-beta pruning function for taking care of Beta values
+        if Ply_num == 0:
+            return State.CurrentScore
+
+        for i in range(State.Current.dimY):
+            for j in range(State.Current.dimX):
+                if State.Current.Mat[i][j] == ' ' and (j, i) not in State.children:
+                    State.Make(j, i, True)
+
+        Minimum_Score = 1000
+        i = 0
+        j = 0
+        for k, z in State.children.items():
+            Result = Algo.Maximum(z, Ply_num - 1, Minimum_Score)
+            if Minimum_Score > Result:
+                Minimum_Score = Result
+            if Result < Beta:
+                return Result
+
+        return Minimum_Score
+
+# 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