python五子棋AI代码

from GameMap import * from enum import IntEnum from random import randint import copy import time AI_SEARCH_DEPTH = 4 AI_LIMITED_MOVE_NUM = 20 # play mode USER_VS_USER_MODE = 0 USER_VS_AI_MODE = 1 AI_VS_AI_MODE = 2 GAME_PLAY_MODE = 1 # who run first AI_RUN_FIRST = True DEBUG_LEVEL = 2 DEBUG_NONE = 0 DEBUG_ERROR = 1 DEBUG_WARN = 2 DEBUG_INFO = 3 def DEBUG(LEVEL, *args): if DEBUG_LEVEL >= LEVEL: len_args = range(len(args)) for Index in len_args: print(args[Index]) class CHESS_TYPE(IntEnum): NONE = 0, SLEEP_TWO = 1, LIVE_TWO = 2, SLEEP_THREE = 3 LIVE_THREE = 4, CHONG_FOUR = 5, LIVE_FOUR = 6, LIVE_FIVE = 7, CHESS_TYPE_NUM = 8 FIVE = CHESS_TYPE.LIVE_FIVE.value FOUR, THREE, TWO = CHESS_TYPE.LIVE_FOUR.value, CHESS_TYPE.LIVE_THREE.value, CHESS_TYPE.LIVE_TWO.value SFOUR, STHREE, STWO = CHESS_TYPE.CHONG_FOUR.value, CHESS_TYPE.SLEEP_THREE.value, CHESS_TYPE.SLEEP_TWO.value SCORE_MAX = 0x7fffffff SCORE_MIN = -1 * SCORE_MAX SCORE_FIVE, SCORE_FOUR, SCORE_SFOUR = 100000, 10000, 1000 SCORE_THREE, SCORE_STHREE, SCORE_TWO, SCORE_STWO = 100, 10, 8, 2 class ZobristHash(): def __init__(self, chess_len): self.max = 2**32 self.player1 = [[self.getRandom() for x in range(chess_len)] for y in range(chess_len)] self.player2 = [[self.getRandom() for x in range(chess_len)] for y in range(chess_len)] self.data = [self.player1, self.player2] self.code = self.getRandom() self.cache = {} def getRandom(self): return randint(1, self.max) def generate(self, index, x, y): self.code = self.code ^ self.data[index][y][x] def resetCache(self): self.cache = {} def getCache(self): if self.code in self.cache: return self.cache[self.code] else: return None def setCache(self, depth, score): DEBUG(DEBUG_INFO, 'code[%d], depth[%d], score[%d]' % (self.code, depth, score)) self.cache[self.code] = (depth, score) class ChessAI(): def __init__(self, chess_len, cache=True): self.len = chess_len # [horizon, vertical, left diagonal, right diagonal] self.record = [[[0,0,0,0] for x in range(chess_len)] for y in range(chess_len)] self.count = [[0 for x in range(CHESS_TYPE_NUM)] for i in range(2)] self.pos_score = [[(7 - max(abs(x - 7), abs(y - 7))) for x in range(chess_len)] for y in range(chess_len)] self.number = 0 self.save_count = 0 self.cache = cache self.cacheGet = 0 if self.cache: self.zobrist = ZobristHash(chess_len) def reset(self): for y in range(self.len): for x in range(self.len): for i in range(4): self.record[y][x][i] = 0 for i in range(len(self.count)): for j in range(len(self.count[0])): self.count[i][j] = 0 self.save_count = 0 def click(self, map, x, y, turn): self.number += 1 map.click(x, y, turn) if self.cache: self.zobrist.generate(turn.value - 1, x, y) def set(self, board, x, y, turn): self.number += 1 board[y][x] = turn.value if self.cache: self.zobrist.generate(turn.value - 1, x, y) def remove(self, board, x, y, turn): self.number -= 1 board[y][x] = 0 if self.cache: self.zobrist.generate(turn.value - 1, x, y) def isWin(self, board, turn): return self.__evaluate(board, turn, True) # get all positions that is empty def genmove(self, board, turn): moves = [] for y in range(self.len): for x in range(self.len): if board[y][x] == 0: score = self.pos_score[y][x] moves.append((score, x, y)) moves.sort(reverse=True) return moves # evaluate score of point, to improve pruning efficiency def evaluatePointScore(self, board, x, y, mine, opponent): dir_offset = [(1, 0), (0, 1), (1, 1), (1, -1)] # direction from left to right for i in range(len(self.count)): for j in range(len(self.count[0])): self.count[i][j] = 0 board[y][x] = mine self.evaluatePoint(board, x, y, mine, opponent, self.count[mine-1]) mine_count = self.count[mine-1] board[y][x] = opponent self.evaluatePoint(board, x, y, opponent, mine, self.count[opponent-1]) opponent_count = self.count[opponent-1] board[y][x] = 0 mscore = self.getPointScore(mine_count) oscore = self.getPointScore(opponent_count) if mscore >= SCORE_FIVE or oscore >= SCORE_FIVE: DEBUG(DEBUG_INFO, '(%d, %d), %d:%d, %d:%d' % (x, y, mine-1, mscore, opponent-1, oscore)) return (mscore, oscore) # check if has a none empty position in it's radius range def hasNeighbor(self, board, x, y, radius): start_x, end_x = (x - radius), (x + radius) start_y, end_y = (y - radius), (y + radius) for i in range(start_y, end_y+1): for j in range(start_x, end_x+1): if i >= 0 and i < self.len and j >= 0 and j < self.len: if board[i][j] != 0: return True return False # get all positions near chess def genmove1(self, board, turn, only_threes=False): fives = [] mfours, ofours = [], [] msfours, osfours = [], [] if turn == MAP_ENTRY_TYPE.MAP_PLAYER_ONE: mine = 1 opponent = 2 else: mine = 2 opponent = 1 moves = [] for y in range(self.len): for x in range(self.len): if board[y][x] == 0 and self.hasNeighbor(board, x, y, 1): mscore, oscore = self.evaluatePointScore(board, x, y, mine, opponent) point = (max(mscore, oscore), x, y) if (only_threes and point[0] < SCORE_THREE): continue if mscore >= SCORE_FIVE or oscore >= SCORE_FIVE: fives.append(point) elif mscore >= SCORE_FOUR: mfours.append(point) elif oscore >= SCORE_FOUR: ofours.append(point) elif mscore >= SCORE_SFOUR: msfours.append(point) elif oscore >= SCORE_SFOUR: osfours.append(point) moves.append(point) if len(fives) > 0: return fives if len(mfours) > 0: return mfours if len(ofours) > 0: if len(msfours) == 0: return ofours else: return ofours + msfours moves.sort(reverse=True) DEBUG(DEBUG_INFO, 'len:', len(moves), ' ', moves) if (only_threes): return moves # FIXME: decrease think time: only consider limited moves with higher score if self.maxdepth > 2 and len(moves) > AI_LIMITED_MOVE_NUM: moves = moves[:AI_LIMITED_MOVE_NUM] return moves def __search(self, board, turn, depth, alpha = SCORE_MIN, beta = SCORE_MAX): score = self.evaluate(board, turn, self.maxdepth - depth) if depth <= 0 or abs(score) >= SCORE_FIVE: return score only_threes = False if self.number >= 10 and (self.maxdepth - depth) > 1: only_threes = True elif (self.maxdepth - depth) > 3: only_threes = True moves = self.genmove1(board, turn, only_threes) bestmove = None self.alpha += len(moves) for dump, x, y in moves: self.set(board, x, y, turn) if turn == MAP_ENTRY_TYPE.MAP_PLAYER_ONE: op_turn = MAP_ENTRY_TYPE.MAP_PLAYER_TWO else: op_turn = MAP_ENTRY_TYPE.MAP_PLAYER_ONE score = - self.__search(board, op_turn, depth - 1, -beta, -alpha) self.remove(board, x, y, turn) self.belta += 1 # alpha/beta pruning if score > alpha: alpha = score bestmove = (x, y) if alpha >= beta: break if depth == self.maxdepth and bestmove: self.bestmove = bestmove if self.cache and bestmove and abs(alpha) <= SCORE_FIVE: self.zobrist.setCache(self.maxdepth - depth, alpha) return alpha def search(self, board, turn, depth = 4): if self.number == 0: return 0, 7, 7 if self.number <= 6: depth = 4 for i in range(2, depth+1, 2): self.maxdepth = i self.bestmove = None self.zobrist.resetCache() score = self.__search(board, turn, i) if abs(score) >= SCORE_FIVE: DEBUG(DEBUG_WARN, i, score) break x, y = self.bestmove return score, x, y def findBestChess(self, board, turn): time1 = time.time() self.alpha = 0 self.belta = 0 score, x, y =