diff options
| author | Matt Strapp <strap012@umn.edu> | 2021-04-26 13:07:08 -0500 |
|---|---|---|
| committer | Matt Strapp <strap012@umn.edu> | 2021-04-26 15:03:24 -0500 |
| commit | 136458d96e5f0ae683d42d49ec4c85124d255b22 (patch) | |
| tree | 438c299b8b869df29e43e7c0ce3ee917e5ad0f98 /python | |
| parent | Start work on AB (diff) | |
| download | csci4511w-136458d96e5f0ae683d42d49ec4c85124d255b22.tar csci4511w-136458d96e5f0ae683d42d49ec4c85124d255b22.tar.gz csci4511w-136458d96e5f0ae683d42d49ec4c85124d255b22.tar.bz2 csci4511w-136458d96e5f0ae683d42d49ec4c85124d255b22.tar.lz csci4511w-136458d96e5f0ae683d42d49ec4c85124d255b22.tar.xz csci4511w-136458d96e5f0ae683d42d49ec4c85124d255b22.tar.zst csci4511w-136458d96e5f0ae683d42d49ec4c85124d255b22.zip | |
Test commit
Diffstat (limited to 'python')
| -rw-r--r-- | python/alphaBeta.py | 253 |
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
|