''' Notice that we are using 2 unique moving functions for: fox_moves and eagle_moves varies on the two genres ''' import random from math import inf import collections piece_score = {"7": 180, "1": 200, "6": 150, "5": 100, "4": 60, "3": 50, "2": 81} mouse_score = [[13, 13, 13, 13, 12, 11, 10, 9, 8], [25, 20, 15, 18, 16, 13, 10, 9, 8], [50, 25, 20, 16, 15, 13, 10, 9, 8], [1919810, 50, 20, 11, 9, 9, 9, 9, 0], [50, 25, 20, 16, 14, 12, 8, 8, 8], [25, 20, 15, 17, 15, 12, 8, 8, 8], [11, 11, 10, 8, 8, 8, 8, 8, 8]] # eagle_score = [[11, 12, 14, 13, 12, 11, 10, 8, 8], # [15, 15, 14, 14, 0, 0, 0, 8, 8], # [50, 20, 20, 0, 0, 0, 0, 8, 8], # [100000, 50, 20, 13, 12, 11, 10, 8, 0], # [50, 20, 20, 14, 0, 0, 0, 8, 8], # [15, 12, 15, 14, 0, 0, 0, 8, 8], # [11, 12, 14, 13, 12, 11, 10, 8, 8]] eagle_score = [[14, 13, 10, 12, 14, 13, 10, 8, 7], [15, 15, 14, 0, 0, 0, 9, 8, 6], [50, 20, 20, 0, 0, 0, 7, 5, 4], [1919810, 50, 20, 14, 13, 11, 10, 8, 0], [50, 20, 20, 0, 0, 0, 7, 5, 4], [15, 12, 15, 0, 0, 0, 9, 8, 6], [14, 12, 10, 13, 14, 13, 10, 8, 7]] fox_score = [[11, 12, 14, 13, 12, 11, 10, 8, 8], [15, 15, 14, 0, 0, 0, 10, 14, 11], [50, 20, 20, 0, 0, 0, 10, 8, 10], [1919810, 50, 20, 13, 12, 11, 11, 10, 0], [50, 20, 20, 0, 0, 0, 10, 8, 11], [15, 12, 15, 0, 0, 0, 10, 14, 11], [11, 12, 14, 13, 12, 11, 10, 8, 8]] # wolf_score = [[11, 12, 14, 13, 12, 11, 10, 8, 8], # [15, 15, 14, 0, 0, 0, 10, 8, 8], # [50, 20, 20, 0, 0, 0, 10, 9, 10], # [1919810, 50, 20, 13, 12, 11, 11, 10, 0], # [50, 20, 20, 0, 0, 0, 10, 9, 10], # [15, 12, 15, 0, 0, 0, 10, 8, 8], # [11, 12, 14, 13, 12, 11, 10, 8, 8]] wolf_score = [[11, 12, 14, 13, 12, 11, 10, 10, 8], [15, 15, 14, 0, 0, 0, 10, 14, 10], [50, 20, 20, 0, 0, 0, 10, 12, 10], [1919810, 50, 20, 12, 11, 10, 11, 12, 0], [50, 20, 20, 0, 0, 0, 10, 13, 10], [15, 12, 15, 0, 0, 0, 13, 14, 8], [11, 12, 14, 13, 12, 10, 11, 12, 8]] leopard_score = [[11, 12, 14, 13, 12, 11, 10, 8, 8], [15, 15, 14, 0, 0, 0, 10, 8, 8], [50, 20, 20, 0, 0, 0, 10, 9, 10], [1919810, 50, 20, 13, 12, 11, 11, 10, 0], [50, 20, 20, 0, 0, 0, 10, 9, 10], [15, 12, 15, 0, 0, 0, 10, 8, 8], [11, 12, 14, 13, 12, 11, 10, 8, 8]] lion_score = [[20, 20, 18, 15, 12, 11, 14, 12, 5], [40, 25, 30, 0, 0, 0, 16, 12, 12], [50, 40, 30, 0, 0, 0, 16, 12, 12], [1919810, 50, 20, 15, 15, 15, 9, 12, 0], [50, 40, 30, 0, 0, 0, 16, 12, 12], [40, 25, 30, 0, 0, 0, 16, 12, 12], [20, 20, 18, 15, 12, 11, 14, 12, 5]] elephant_score = [[20, 20, 18, 15, 12, 11, 14, 12, 5], [40, 25, 30, 0, 0, 0, 16, 12, 12], [50, 40, 30, 0, 0, 0, 16, 12, 12], [1919810, 50, 20, 15, 15, 15, 9, 12, 0], [50, 40, 30, 0, 0, 0, 16, 12, 12], [40, 25, 30, 0, 0, 0, 16, 12, 12], [20, 20, 18, 15, 12, 11, 14, 12, 5]] piece_position_scores = {"r1": mouse_score, "b1": [line[::-1] for line in mouse_score[::-1]], "r2": eagle_score, "b2": [line[::-1] for line in eagle_score[::-1]], "r3": fox_score, "b3": [line[::-1] for line in fox_score[::-1]], "r4": wolf_score, "b4": [line[::-1] for line in wolf_score[::-1]], "r5": leopard_score, "b5": [line[::-1] for line in leopard_score[::-1]], "r6": lion_score, "b6": [line[::-1] for line in lion_score[::-1]], "r7": elephant_score, "b7": [line[::-1] for line in elephant_score[::-1]], } DEN_CONQUESTED = 10000 DRAW = 0 global DEPTH # =4 def findRandomMove(valid_moves): return valid_moves[random.randint(0, len(valid_moves) - 1)] # is greedy_move function used here? def find_GreadyMove(game_state, valid_moves): turnMultiplier = 1 if game_state.red_to_move else -1 maxScore = -DEN_CONQUESTED bestMove = None for playerMove in valid_moves: game_state.makeMove(playerMove) score = turnMultiplier * scoreMaterial(game_state) if score > maxScore: maxScore = score bestMove = playerMove game_state.undoMove() return bestMove def scoreMaterial(game_state): # get the score # input: current game_state score = 0 penalty_for_rep = 0 for row in range(len(game_state.board)): for col in range(len(game_state.board[row])): # 遍历整个棋盘 piece = game_state.board[row][col] if piece != "00": piece_position_score = 0 piece_position_score = piece_position_scores[piece][row][col] # 获得当前位置的得分 if piece_position_scores[piece][row][col] in last_moves: # 重复判罚 penalty_for_rep += 70 if piece[0] == 'r': score += piece_position_score + piece_score[piece[1]] - penalty_for_rep elif piece[0] == 'b': score -= piece_position_score + piece_score[piece[1]] - penalty_for_rep # 注意：这个默认没有考虑”淘汰“的可能性？ #待检查： return score def findMove_NegaMaxAlphaBeta(game_state, valid_moves, depth, DEPTH, alpha, beta, turn_multiplier): # 对于各个参数的理解： # game_state：当前状态 # valid_moves：可行的行动列表 # depth：当前深度 # DEPTH：限制深度 # alpha：alpha限制值 # beta：beta限制值 # turn_multiplier：NegaMax特性 global next_move if depth == 0: return turn_multiplier * scoreMaterial(game_state) max_score = -inf for move in valid_moves: game_state.makeMove(move) next_moves = game_state.getAllMoves() score = -findMove_NegaMaxAlphaBeta(game_state, next_moves, depth - 1, DEPTH, -beta, -alpha, -turn_multiplier) if score > max_score: # > or >= ?? max_score = score if depth == DEPTH: next_move = move game_state.undoMove() if max_score > alpha: alpha = max_score if alpha >= beta: break return max_score def findMove_MiniMaxAlphaBeta(game_state, valid_moves, depth, alpha, beta, turn_multiplier): global next_move def max_value(game_state, next_moves, alpha, beta, depth): if depth == 0: return turn_multiplier * scoreMaterial(game_state) v = -inf for move in valid_moves: next_moves = game_state.getAllMoves() v = max(v, min_value(game_state, next_moves, alpha, beta, depth - 1)) game_state.undoMove() if v >= beta: return v alpha = max(alpha, v) return v def min_value(game_state, next_moves, alpha, beta, depth): if depth == 0: return turn_multiplier * scoreMaterial(game_state) v = -inf for move in valid_moves: next_moves = game_state.getAllMoves() v = min(v, max_value(game_state, next_moves, alpha, beta, depth - 1)) game_state.undoMove() if v <= alpha: return v beta = min(beta, v) return v # Body of alpha_beta_search: best_score = -inf beta = inf best_action = None for move in valid_moves: v = min_value(game_state, valid_moves, best_score, beta, depth) if v > best_score: best_score = v best_action = move return best_action def find_BestMove(game_state, valid_moves, depth_p): global next_move DEPTH = depth_p next_move = None global last_moves last_moves = collections.deque(maxlen=12) random.shuffle(valid_moves) ordered_valid_moves = orderby_GreadyMove(game_state, valid_moves) # for i in valid_moves: # print(f"Possible: {i}") # for i in ordered_valid_moves: # print(f"New possible: {i}") findMove_NegaMaxAlphaBeta(game_state, ordered_valid_moves, depth_p, DEPTH, -DEN_CONQUESTED, DEN_CONQUESTED, 1 if game_state.red_to_move else -1) last_moves.append(next_move) return next_move def orderby_GreadyMove(game_state, valid_moves): turnMultiplier = 1 if game_state.red_to_move else -1 maxScore = -DEN_CONQUESTED de = collections.deque([]) for playerMove in valid_moves: game_state.makeMove(playerMove) score = turnMultiplier * scoreMaterial(game_state) if score > maxScore: maxScore = score de.appendleft(playerMove) else: de.append(playerMove) game_state.undoMove() return de