Revert "Test commit"

This reverts commit 828f04ddf3d75d66026ebf607e82dc7d456c36f7.

1 files changed, 105 insertions, 148 deletions

diff --git a/python/alphaBeta.py b/python/alphaBeta.py
index 7279368..8e041fe 100644
--- a/python/alphaBeta.py
+++ b/python/alphaBeta.py
@@ -1,148 +1,105 @@
-# 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        

+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