aboutsummaryrefslogtreecommitdiffstats
path: root/python/alphaBeta.py
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--python/alphaBeta.py125
1 files changed, 97 insertions, 28 deletions
diff --git a/python/alphaBeta.py b/python/alphaBeta.py
index 01f82cf..31fa578 100644
--- a/python/alphaBeta.py
+++ b/python/alphaBeta.py
@@ -1,30 +1,99 @@
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
+
+ # 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