diff options
author | Matt Strapp <strap012@umn.edu> | 2021-04-26 15:01:22 -0500 |
---|---|---|
committer | Matt Strapp <strap012@umn.edu> | 2021-04-26 15:03:24 -0500 |
commit | 8f11438e29a2b9cf7873341943fcfc66cbbe837e (patch) | |
tree | 770568112e9b5ed437c1d4177be44ff981dcc61e /python | |
parent | Revert "Add files via upload" (diff) | |
download | csci4511w-8f11438e29a2b9cf7873341943fcfc66cbbe837e.tar csci4511w-8f11438e29a2b9cf7873341943fcfc66cbbe837e.tar.gz csci4511w-8f11438e29a2b9cf7873341943fcfc66cbbe837e.tar.bz2 csci4511w-8f11438e29a2b9cf7873341943fcfc66cbbe837e.tar.lz csci4511w-8f11438e29a2b9cf7873341943fcfc66cbbe837e.tar.xz csci4511w-8f11438e29a2b9cf7873341943fcfc66cbbe837e.tar.zst csci4511w-8f11438e29a2b9cf7873341943fcfc66cbbe837e.zip |
Revert "Test commit"
This reverts commit 828f04ddf3d75d66026ebf607e82dc7d456c36f7.
Diffstat (limited to '')
-rw-r--r-- | python/alphaBeta.py | 253 |
1 files 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 |