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