From 8f11438e29a2b9cf7873341943fcfc66cbbe837e Mon Sep 17 00:00:00 2001 From: Matt Strapp Date: Mon, 26 Apr 2021 15:01:22 -0500 Subject: Revert "Test commit" This reverts commit 828f04ddf3d75d66026ebf607e82dc7d456c36f7. --- python/alphaBeta.py | 253 ++++++++++++++++++++++------------------------------ 1 file 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 -- cgit v1.2.3