aboutsummaryrefslogtreecommitdiffstats
path: root/dotsandboxes/agents/algorithms/alphaBeta.py
diff options
context:
space:
mode:
Diffstat (limited to 'dotsandboxes/agents/algorithms/alphaBeta.py')
-rw-r--r--dotsandboxes/agents/algorithms/alphaBeta.py105
1 files changed, 105 insertions, 0 deletions
diff --git a/dotsandboxes/agents/algorithms/alphaBeta.py b/dotsandboxes/agents/algorithms/alphaBeta.py
new file mode 100644
index 0000000..8e041fe
--- /dev/null
+++ b/dotsandboxes/agents/algorithms/alphaBeta.py
@@ -0,0 +1,105 @@
+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