Permalink
Cannot retrieve contributors at this time
Name already in use
A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Konane/state.py
Go to fileThis commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
272 lines (252 sloc)
11 KB
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import math, copy | |
WHITE = "W" | |
BLACK = "B" | |
players = [BLACK, WHITE] | |
playerColor = WHITE | |
opponentColor = BLACK | |
max_depth = 3 | |
def Minimax(state, depth, maximizingPlayer, alpha, beta): | |
if depth == max_depth: | |
return state.eval(state.board, playerColor, opponentColor), None | |
if maximizingPlayer == playerColor: | |
best_move = None | |
for successor_state in state.generate_successors(state.board, maximizingPlayer): | |
if players[0] == maximizingPlayer: | |
val, move = Minimax(successor_state, depth + 1, players[1], alpha, beta) | |
else: | |
val, move = Minimax(successor_state, depth + 1, players[0], alpha, beta) | |
if val == max(val, alpha): | |
alpha = val | |
best_move = successor_state.last_move | |
if alpha >= beta: | |
return beta, best_move | |
#best_val = max(best_move, val) | |
#alpha = max(alpha, best_move) | |
#if beta <= alpha: | |
# break | |
return alpha, best_move | |
else: | |
best_move = None | |
for successor_state in state.generate_successors(state.board, maximizingPlayer): | |
if players[0] == maximizingPlayer: | |
val, move = Minimax(successor_state, depth + 1, players[1], alpha, beta) | |
else: | |
val, move = Minimax(successor_state, depth + 1, players[0], alpha, beta) | |
if val == min(val, beta): | |
beta = val | |
best_move = successor_state.last_move | |
if beta <= alpha: | |
return alpha, best_move | |
#best_move = min(best_move, val) | |
#beta = min(beta, best_move) | |
#if beta <= alpha: | |
# break | |
#print(best_move) | |
return beta, best_move | |
class State: | |
def __init__(self, board = [], player = 'B', last_move = (), playerMode = 1): | |
self.nrows = 18 | |
self.ncols = 18 | |
self.board = board | |
self.last_move = last_move | |
if board == []: | |
self.setup() | |
self.gameOver = 0 | |
self.playerMode = playerMode | |
def setup(self): | |
for row in range(self.nrows): | |
self.board.append([]) | |
for col in range(self.ncols): | |
if((row + col) % 2 == 0): | |
self.board[row].append(BLACK) | |
else: | |
self.board[row].append(WHITE) | |
def piece(self, row, col): | |
return self.board[row][col] | |
def removePiece(self, row, col): | |
self.board[row][col] = ' ' | |
def placePiece(self, row, col, color): | |
if self.board[row][col] == ' ': | |
self.board[row][col] = color | |
else: | |
print("Error: attempted to place piece on occupied spot") | |
def movePiece(self, from_position, to_position): | |
#print("Hello") | |
piece_color = self.piece(from_position[0],from_position[1]) | |
#print(from_position[0], to_position[0]+1) | |
#print(from_position[1], to_position[1]+1) | |
row_range = range(*sorted([from_position[0], to_position[0]+1])) | |
column_range = range(*sorted([from_position[1], to_position[1]+1])) | |
#print("row_range: ", row_range) | |
#print("column_range: ", column_range) | |
self.removePiece(from_position[0], from_position[1]) | |
for x in row_range: | |
#print("row: ", x) | |
for y in column_range: | |
#print("column: ", y) | |
self.removePiece(x,y) | |
self.placePiece(to_position[0], to_position[1], piece_color) | |
def __str__(self): | |
string = "" | |
for row in range(self.nrows): | |
string += str(self.board[row]) + "\n" | |
return string | |
def first_moves_set(self): | |
firstMoves = [] | |
firstMoves.append((0, 0)) | |
firstMoves.append((0, 17)) | |
firstMoves.append((17, 0)) | |
firstMoves.append((17, 17)) | |
firstMoves.append((8, 8)) | |
firstMoves.append((8, 9)) | |
firstMoves.append((9, 8)) | |
firstMoves.append((9, 9)) | |
return firstMoves | |
def second_moves_set(self): | |
secondMoves = [] | |
#If bottom left corner of the board is removed | |
if (self.board[0][0] == ' '): | |
secondMoves.append((0, 1)) | |
secondMoves.append((1, 0)) | |
return secondMoves | |
#Top left corner is removed | |
elif (self.board[0][17] == ' '): | |
secondMoves.append((0, 16)) | |
secondMoves.append((1, 17)) | |
return secondMoves | |
#Top right | |
elif (self.board[17][17] == ' '): | |
secondMoves.append((16, 17)) | |
secondMoves.append((17, 16)) | |
return secondMoves | |
#Bottom right | |
elif (self.board[17][0] == ' '): | |
secondMoves.append((16, 0)) | |
secondMoves.append((17, 1)) | |
return secondMoves | |
#Middle game states, bottom left | |
elif (self.board[8][8] == ' '): | |
secondMoves.append((8, 9)) | |
secondMoves.append((8, 7)) | |
secondMoves.append((7, 8)) | |
secondMoves.append((9, 8)) | |
return secondMoves | |
#Mid top left | |
elif (self.board[8][9] == ' '): | |
secondMoves.append((8, 10)) | |
secondMoves.append((8, 8)) | |
secondMoves.append((9, 9)) | |
secondMoves.append((7, 9)) | |
return secondMoves | |
#Mid top right | |
elif (self.board[9][9] == ' '): | |
secondMoves.append((8, 9)) | |
secondMoves.append((10, 9)) | |
secondMoves.append((9, 8)) | |
secondMoves.append((9, 10)) | |
return secondMoves | |
#Mid bot right | |
elif (self.board[9][8] == ' '): | |
secondMoves.append((10, 8)) | |
secondMoves.append((8, 8)) | |
secondMoves.append((9, 9)) | |
secondMoves.append((9, 7)) | |
return secondMoves | |
#Function to generate all possible moves, including multiple jumps | |
def generate_moves(self, board, color): | |
possible_moves = [] | |
jump_to = (0, 0) | |
up = down = left = right = 2 | |
for row in range(self.nrows): | |
#print("row: ", row ) | |
for col in range(self.ncols): | |
#print("col: ", col ) | |
#Checking if it should search for black or white moves. | |
if (board[row][col] == color): | |
#Searching moves that can go up | |
#Current position | |
curr_pos = (row, col) | |
#Is move within the scope of the board? | |
while ((curr_pos[0] - up) >= 0): | |
jump_to = (curr_pos[0] - up, col) | |
#print(jump_to[0], jump_to[1]) | |
#Is there a blank space where we need to jump, and is there an opponent's piece to jump over? | |
if (board[jump_to[0]][jump_to[1]] == ' ' and board[jump_to[0]+1][jump_to[1]] != ' '): | |
#Append move if possible | |
possible_moves.append(((row, col), (jump_to[0], jump_to[1]))) | |
#Update how far it'll jump next time (for multiple jumps) | |
curr_pos = jump_to | |
else: | |
break | |
#Searching moves that can go down | |
curr_pos = (row, col) | |
#Is move within the scope of the board? | |
while ((curr_pos[0] + down) < self.ncols): | |
jump_to = (curr_pos[0] + down, col) | |
#print(jump_to[0], jump_to[1]) | |
#Is there a blank space where we need to jump, and is there an opponent's piece to jump over? | |
if (board[jump_to[0]][jump_to[1]] == ' ' and board[jump_to[0]-1][jump_to[1]] != ' '): | |
#Append move if possible | |
possible_moves.append(((row, col), (jump_to[0], jump_to[1]))) | |
#Update how far it'll jump next time (for multiple jumps) | |
curr_pos = jump_to | |
else: | |
break | |
#Searching for moves that can go left of the board | |
#Current position | |
curr_pos = (row, col) | |
#Is move within scope of the board? | |
while ((curr_pos[1] + right) < self.nrows): | |
jump_to = (row, curr_pos[1] + right) | |
#print(jump_to[0], jump_to[1]) | |
#Is there a blank space where we need to jump, and is there an opponent's piece to jump over? | |
if (board[jump_to[0]][jump_to[1]] == ' ' and board[jump_to[0]][jump_to[1]-1] != ' '): | |
#Append move if possible | |
possible_moves.append(((row, col), (jump_to[0], jump_to[1]))) | |
#Update how far you'll jump next time (for multiple jumps) | |
curr_pos = jump_to | |
else: | |
break | |
#Searching for moves that can go right | |
curr_pos = (row, col) | |
#Is move within scope of the board? | |
while ((curr_pos[1] - left) >= 0): | |
jump_to = (row, curr_pos[1] - left) | |
#print(jump_to[0], jump_to[1]) | |
#Is there a blank space where we need to jump, and is there an opponent's piece to jump over? | |
if (board[jump_to[0]][jump_to[1]] == ' ' and board[jump_to[0]][jump_to[1]+1] != ' '): | |
#Append move if possible | |
possible_moves.append(((row, col), (jump_to[0], jump_to[1]))) | |
#Update how far it'll jump next time (for multiple jumps) | |
curr_pos = jump_to | |
else: | |
break | |
return possible_moves | |
#Generate successors for moves, needs implemented | |
def generate_successors(self, board, color): | |
successors = [] | |
for move in self.generate_moves(board, color): | |
board_copy = copy.deepcopy(State(board)) | |
board_copy.movePiece(move[0], move[1]) | |
if color == BLACK: | |
successors.append(State(board_copy.board, WHITE, move)) | |
else: | |
successors.append(State(board_copy.board, BLACK, move)) | |
return successors | |
#Evaluation function | |
def eval(self, board, playerColor, opponentColor): | |
player_moves = self.generate_moves(board, playerColor) | |
opponent_moves = self.generate_moves(board, opponentColor) | |
if player_moves == 0: | |
return -1 * math.inf | |
if opponent_moves == 0: | |
return math.inf | |
return len(player_moves)/(len(opponent_moves)*4) | |
def makeMove(self, color): | |
if len(self.generate_moves(self.board, color)) > 0: | |
move = Minimax(self, 0, color, math.inf * -1, math.inf) | |
#self.movePiece(move[1][0], move[1][1]) | |
return move[1] | |
else: | |
self.gameOver = 1 | |
return 1 |