Test commit

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