文章目錄

五子棋基本棋型介紹

評估方法介紹

簡單AI介紹

代碼實現

完整代碼

main.py
GameMap.py
ChessAI.py

五子棋基本棋型介紹

最常見的基本棋型大體有以下幾種：連五，活四，沖四，活三，眠三，活二，眠二。

① 連五：顧名思義，五顆同色棋子連在一起，不需要多講。

② 活四：有兩個連五點（即有兩個點可以形成五），圖中白點即為連五點。
稍微思考一下就能發現活四出現的時候，如果對方單純過來防守的話，是已經無法阻止自己連五了。

③ 沖四：有一個連五點，如下面三圖，均為沖四棋型。圖中白點為連五點。
相對比活四來說，沖四的威脅性就小了很多，因為這個時候，對方只要跟著防守在那個唯一的連五點上，沖四就沒法形成連五。

④ 活三：可以形成活四的三，如下圖，代表兩種最基本的活三棋型。圖中白點為活四點。

活三棋型是我們進攻中最常見的一種，因為活三之後，如果對方不以理會，將可以下一手將活三變成活四，而我們知道活四是已經無法單純防守住了。所以，當我們面對活三的時候，需要非常謹慎對待。在自己沒有更好的進攻手段的情況下，需要對其進行防守，以防止其形成可怕的活四棋型。

⑤ 眠三：只能夠形成沖四的三，如下各圖，分別代表最基礎的六種眠三形狀。圖中白點代表沖四點。眠三的棋型與活三的棋型相比，危險係數下降不少，因為眠三棋型即使不去防守，下一手它也只能形成沖四，而對於單純的沖四棋型，我們知道，是可以防守住的。

如上所示，眠三的形狀是很豐富的。對於初學者，在下棋過程中，很容易忽略不常見的眠三形狀，例如圖2-13所示的眠三。

有新手學了活三眠三後，會提出疑問，說活三也可以形成沖四啊，那豈不是也可以叫眠三？

會提出這個問題，說明對眠三定義看得不夠仔細：眠三的的定義是，只能夠形成沖四的三。而活三可以形成眠三，但也能夠形成活四。

此外，在五子棋中，活四棋型比沖四棋型具有更大的優勢，所以，我們在既能夠形成活四又能夠形成沖四時，會選擇形成活四。

溫馨提示：學會判斷一個三到底是活三還是眠三是非常重要的。所以，需要好好體會。

後邊禁手判斷的時候也會有所應用。

⑥ 活二：能夠形成活三的二，如下圖，是三種基本的活二棋型。圖中白點為活三點。

活二棋型看起來似乎很無害，因為他下一手棋才能形成活三，等形成活三，我們再防守也不遲。但其實活二棋型是非常重要的，尤其是在開局階段，我們形成較多的活二棋型的話，當我們將活二變成活三時，才能夠令自己的活三綿綿不絕微風裡，讓對手防不勝防。

⑦眠二：能夠形成眠三的二。圖中四個為最基本的眠二棋型，細心且喜歡思考的同學會根據眠三介紹中的圖2-13找到與下列四個基本眠二棋型都不一樣的眠二。圖中白點為眠三點。

評估方法介紹

由上面的介紹可知，有7種有效的棋型（連五，活四，沖四，活三，眠三，活二，眠二），我們可以創建黑棋和白棋兩個數組，記錄棋盤上黑棋和白棋分別形成的所有棋型的個數，然後按照一定的規則進行評分。

如何記錄棋盤上的棋形個數，一個很直觀的方法是，棋盤上有15條水平線，15條豎直線，不考慮長度小於5的斜線，有21條從左上到右下的斜線，21條從左下到右上的斜線。然後對每一條線分別對黑棋和白棋查找是否有符合的棋型。這種方法比較直觀，但是實現起來不方便。有興趣的可以嘗試下。

這裡用的方法是，對整個棋盤進行遍歷，對於每一個白棋或黑棋，以它為中心，記錄符合的棋型個數。

具體實現方式如下：

遍歷棋盤上的每個點，如果是黑棋或白旗，則對這個點所在四個方向形成的四條線分別進行評估。四個方向即水平，豎直，兩個斜線( \ , / ），四個方向依次按照從左到右，從上到下，從左上到右下，從左下到右上來檢測。
對於具體的一條線，如下圖，已選取點為中心，取該方向上前面四個點，後面四個點，組成一個長度為9的數組。

然後找下和中心點相連的同色棋子有幾個，比如下圖，相連的白色棋子有3個，根據相連棋子的個數再分別進行判斷，最後得出這行屬於上面說的哪一種棋型。具體判斷可以看代碼中的 analysisLine 函數.

這裡有個注意點，在評估白旗1的時候，白棋3和5已經被判斷過，所以要標記下，下次遍歷到這個方向的白棋3和5，需要跳過，避免重複統計棋型。

3.根據棋盤上黑棋和白棋的棋型統計信息，按照一定規則進行評分。

假設形成該棋局的最後一步是黑棋下的，則最後的評分是（黑棋得分 - 白棋得分），在相同棋型相同個數的情況下，白棋會占優，因為下一步是白棋下。比如黑棋有個沖四，白棋有個沖四，顯然白棋占優，因為下一步白棋就能成連五。

按照下面的規則依次匹配，下面設的評分值是可以優化調整的：

前面9條為必殺情況，會直接返回評分，

黑棋連5，評分為10000
白棋連5，評分為 -10000
黑棋兩個沖四可以當成一個活四
白棋有活四，評分為 -9050
白棋有沖四，評分為 -9040
黑棋有活四，評分為 9030
黑棋有沖四和活三，評分為 9020
黑棋沒有沖四，且白棋有活三，評分為 9010
黑棋有2個活三，且白棋沒有活三或眠三，評分為 9000
下面針對黑棋或白棋的活三，眠三，活二，眠二的個數依次增加分數，評分為（黑棋得分 - 白棋得分）

簡單AI介紹

有了評估函數，輪到AI下棋時，就要針對當前的棋局，找到一個最有利的位置來下。AI會嘗試在每個空點下棋，形成一個新的棋局，然後用評估函數來獲取這個棋局時的評分。從中選取評分最高的位置來就行了。

AI 獲取最有利位置的邏輯：

遍歷棋盤上的每一個空點：
在這個空點下棋，獲取新的棋局的評分
如果是更高的評分，則保存該位置
將這個位置恢復為空點
獲得最高評分的位置

上面這段邏輯我們在後續的文章中會不斷優化，使得AI越來越厲害。

代碼實現

AI的實現都在ChessAI類中，record數組記錄所有位置的四個方向是否被檢測過。count二維數組記錄黑棋和白棋的棋型個數統計。pos_score 給棋盤上每個位置設一個初始分數，越靠近棋盤中心，分數越高，用來在最開始沒有任何棋型時的，AI優先選取靠中心的位置。

reset函數每次調用評估函數前都需要清一下之前的統計數據。

class ChessAI(): def __init__(self, chess_len): 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)] 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

findBestChess 函數就是AI的入口函數。
search 函數是上面AI邏輯的代碼實現，先通過 genmove 函數獲取棋盤上所有的空點，然後依次嘗試，獲得評分最高的位置並返回。

 # 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 def search(self, board, turn): moves = self.genmove(board, turn) bestmove = None max_score = -0x7fffffff for score, x, y in moves: board[y][x] = turn.value score = self.evaluate(board, turn) board[y][x] = 0 if score > max_score: max_score = score bestmove = (max_score, x, y) return bestmove def findBestChess(self, board, turn): time1 = time.time() score, x, y = self.search(board, turn) time2 = time.time() print('time[%f] (%d, %d), score[%d] save[%d]' % ((time2-time1), x, y, score, self.save_count)) return (x, y)

evaluate函數, 就是上面評估方法的代碼實現，參數turn表示最近一手棋是誰下的，根據turn決定的mine（表示自己棋的值）和oppoent（表示對手棋的值，下一步棋由對手下），在對棋型評分時會用到。checkWin 是遊戲用來判斷是否有一方獲勝了。

其中調用的getScore函數就是對黑棋和白棋進行評分。

evaluatePoint函數就是對於一個位置的四個方向分別進行檢查。

 def evaluate(self, board, turn, checkWin=False): self.reset() if turn == MAP_ENTRY_TYPE.MAP_PLAYER_ONE: mine = 1 opponent = 2 else: mine = 2 opponent = 1 for y in range(self.len): for x in range(self.len): if board[y][x] == mine: self.evaluatePoint(board, x, y, mine, opponent) elif board[y][x] == opponent: self.evaluatePoint(board, x, y, opponent, mine) mine_count = self.count[mine-1] opponent_count = self.count[opponent-1] if checkWin: return mine_count[FIVE] > 0 else: mscore, oscore = self.getScore(mine_count, opponent_count) return (mscore - oscore) def evaluatePoint(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(4): if self.record[y][x][i] == 0: self.analysisLine(board, x, y, i, dir_offset[i], mine, opponent, self.count[mine-1]) else: self.save_count += 1

analysisLine函數是判斷一條線上自己棋能形成棋型的代碼， mine表示自己棋的值，opponent表示對手棋的值。

要根據中心點相鄰己方棋子能連成的個數來分別判斷，己方棋值設為M，對方棋值設為P，空點值設為X。具體可以看代碼中的注釋。

連成5個點，可以直接返回
連成4個點，要考慮是否被對手棋檔著，比如 PMMMMX
連成3個點，要考慮隔一個空點的情況，比如 MXMMMX。
連成2個點，要考慮隔一個空點的如情況，比如 MXMMX，MMXMM。
只有1個點，要考慮隔一個或二個空點的情況，比如 XMXMX，XMXXMX。

getLine函數，根據棋子的位置和方向，獲取上面說的長度為9的線。有個取巧的地方，如果線上的位置超出了棋盤範圍，就將這個位置的值設為對手的值，因為超出範圍和被對手棋擋著，對棋型判斷的結果是一樣的。

setRecord函數標記已經檢測過，需要跳過的棋子。

 # line is fixed len 9: XXXXMXXXX def getLine(self, board, x, y, dir_offset, mine, opponent): line = [0 for i in range(9)] tmp_x = x + (-5 * dir_offset[0]) tmp_y = y + (-5 * dir_offset[1]) for i in range(9): tmp_x += dir_offset[0] tmp_y += dir_offset[1] if (tmp_x < 0 or tmp_x >= self.len or tmp_y < 0 or tmp_y >= self.len): line[i] = opponent # set out of range as opponent chess else: line[i] = board[tmp_y][tmp_x] return line def analysisLine(self, board, x, y, dir_index, dir_offset, mine, opponent, count): # record line range[left, right] as analysized def setRecord(self, x, y, left, right, dir_index, dir_offset): tmp_x = x + (-5 + left) * dir_offset[0] tmp_y = y + (-5 + left) * dir_offset[1] for i in range(left, right+1): tmp_x += dir_offset[0] tmp_y += dir_offset[1] self.record[tmp_y][tmp_x][dir_index] = 1 empty = MAP_ENTRY_TYPE.MAP_EMPTY.value left_idx, right_idx = 4, 4 line = self.getLine(board, x, y, dir_offset, mine, opponent) while right_idx < 8: if line[right_idx+1] != mine: break right_idx += 1 while left_idx > 0: if line[left_idx-1] != mine: break left_idx -= 1 left_range, right_range = left_idx, right_idx while right_range < 8: if line[right_range+1] == opponent: break right_range += 1 while left_range > 0: if line[left_range-1] == opponent: break left_range -= 1 chess_range = right_range - left_range + 1 if chess_range < 5: setRecord(self, x, y, left_range, right_range, dir_index, dir) return CHESS_TYPE.NONE setRecord(self, x, y, left_idx, right_idx, dir_index, dir) m_range = right_idx - left_idx + 1 # M:mine chess, P:opponent chess or out of range, X: empty if m_range == 5: count[FIVE] += 1 # Live Four : XMMMMX # Chong Four : XMMMMP, PMMMMX if m_range == 4: left_empty = right_empty = False if line[left_idx-1] == empty: left_empty = True if line[right_idx+1] == empty: right_empty = True if left_empty and right_empty: count[FOUR] += 1 elif left_empty or right_empty: count[SFOUR] += 1 # Chong Four : MXMMM, MMMXM, the two types can both exist # Live Three : XMMMXX, XXMMMX # Sleep Three : PMMMX, XMMMP, PXMMMXP if m_range == 3: left_empty = right_empty = False left_four = right_four = False if line[left_idx-1] == empty: if line[left_idx-2] == mine: # MXMMM setRecord(self, x, y, left_idx-2, left_idx-1, dir_index, dir) count[SFOUR] += 1 left_four = True left_empty = True if line[right_idx+1] == empty: if line[right_idx+2] == mine: # MMMXM setRecord(self, x, y, right_idx+1, right_idx+2, dir_index, dir) count[SFOUR] += 1 right_four = True right_empty = True if left_four or right_four: pass elif left_empty and right_empty: if chess_range > 5: # XMMMXX, XXMMMX count[THREE] += 1 else: # PXMMMXP count[STHREE] += 1 elif left_empty or right_empty: # PMMMX, XMMMP count[STHREE] += 1 # Chong Four: MMXMM, only check right direction # Live Three: XMXMMX, XMMXMX the two types can both exist # Sleep Three: PMXMMX, XMXMMP, PMMXMX, XMMXMP # Live Two: XMMX # Sleep Two: PMMX, XMMP if m_range == 2: left_empty = right_empty = False left_three = right_three = False if line[left_idx-1] == empty: if line[left_idx-2] == mine: setRecord(self, x, y, left_idx-2, left_idx-1, dir_index, dir) if line[left_idx-3] == empty: if line[right_idx+1] == empty: # XMXMMX count[THREE] += 1 else: # XMXMMP count[STHREE] += 1 left_three = True elif line[left_idx-3] == opponent: # PMXMMX if line[right_idx+1] == empty: count[STHREE] += 1 left_three = True left_empty = True if line[right_idx+1] == empty: if line[right_idx+2] == mine: if line[right_idx+3] == mine: # MMXMM setRecord(self, x, y, right_idx+1, right_idx+2, dir_index, dir) count[SFOUR] += 1 right_three = True elif line[right_idx+3] == empty: #setRecord(self, x, y, right_idx+1, right_idx+2, dir_index, dir) if left_empty: # XMMXMX count[THREE] += 1 else: # PMMXMX count[STHREE] += 1 right_three = True elif left_empty: # XMMXMP count[STHREE] += 1 right_three = True right_empty = True if left_three or right_three: pass elif left_empty and right_empty: # XMMX count[TWO] += 1 elif left_empty or right_empty: # PMMX, XMMP count[STWO] += 1 # Live Two: XMXMX, XMXXMX only check right direction # Sleep Two: PMXMX, XMXMP if m_range == 1: left_empty = right_empty = False if line[left_idx-1] == empty: if line[left_idx-2] == mine: if line[left_idx-3] == empty: if line[right_idx+1] == opponent: # XMXMP count[STWO] += 1 left_empty = True if line[right_idx+1] == empty: if line[right_idx+2] == mine: if line[right_idx+3] == empty: if left_empty: # XMXMX #setRecord(self, x, y, left_idx, right_idx+2, dir_index, dir) count[TWO] += 1 else: # PMXMX count[STWO] += 1 elif line[right_idx+2] == empty: if line[right_idx+3] == mine and line[right_idx+4] == empty: # XMXXMX count[TWO] += 1 return CHESS_TYPE.NONE

完整代碼

一共有三個文件，新增加了一個ChessAI.py。

main.py

增加了對於ChessAI類的 findBestChess 函數的調用，獲取AI選擇的下棋位置。

import pygamefrom pygame.locals import *from GameMap import *from ChessAI import *class Button(): def __init__(self, screen, text, x, y, color, enable): self.screen = screen self.width = BUTTON_WIDTH self.height = BUTTON_HEIGHT self.button_color = color self.text_color = (255, 255, 255) self.enable = enable self.font = pygame.font.SysFont(None, BUTTON_HEIGHT*2//3) self.rect = pygame.Rect(0, 0, self.width, self.height) self.rect.topleft = (x, y) self.text = text self.init_msg() def init_msg(self): if self.enable: self.msg_image = self.font.render(self.text, True, self.text_color, self.button_color[0]) else: self.msg_image = self.font.render(self.text, True, self.text_color, self.button_color[1]) self.msg_image_rect = self.msg_image.get_rect() self.msg_image_rect.center = self.rect.center def draw(self): if self.enable: self.screen.fill(self.button_color[0], self.rect) else: self.screen.fill(self.button_color[1], self.rect) self.screen.blit(self.msg_image, self.msg_image_rect) class StartButton(Button): def __init__(self, screen, text, x, y): super().__init__(screen, text, x, y, [(26, 173, 25),(158, 217, 157)], True) def click(self, game): if self.enable: game.start() game.winner = None self.msg_image = self.font.render(self.text, True, self.text_color, self.button_color[1]) self.enable = False return True return False def unclick(self): if not self.enable: self.msg_image = self.font.render(self.text, True, self.text_color, self.button_color[0]) self.enable = True class GiveupButton(Button): def __init__(self, screen, text, x, y): super().__init__(screen, text, x, y, [(230, 67, 64),(236, 139, 137)], False) def click(self, game): if self.enable: game.is_play = False if game.winner is None: game.winner = game.map.reverseTurn(game.player) self.msg_image = self.font.render(self.text, True, self.text_color, self.button_color[1]) self.enable = False return True return False def unclick(self): if not self.enable: self.msg_image = self.font.render(self.text, True, self.text_color, self.button_color[0]) self.enable = Trueclass Game(): def __init__(self, caption): pygame.init() self.screen = pygame.display.set_mode([SCREEN_WIDTH, SCREEN_HEIGHT]) pygame.display.set_caption(caption) self.clock = pygame.time.Clock() self.buttons = [] self.buttons.append(StartButton(self.screen, 'Start', MAP_WIDTH + 30, 15)) self.buttons.append(GiveupButton(self.screen, 'Giveup', MAP_WIDTH + 30, BUTTON_HEIGHT + 45)) self.is_play = False self.map = Map(CHESS_LEN, CHESS_LEN) self.player = MAP_ENTRY_TYPE.MAP_PLAYER_ONE self.action = None self.AI = ChessAI(CHESS_LEN) self.useAI = False self.winner = None def start(self): self.is_play = True self.player = MAP_ENTRY_TYPE.MAP_PLAYER_ONE self.map.reset() def play(self): self.clock.tick(60) light_yellow = (247, 238, 214) pygame.draw.rect(self.screen, light_yellow, pygame.Rect(0, 0, MAP_WIDTH, SCREEN_HEIGHT)) pygame.draw.rect(self.screen, (255, 255, 255), pygame.Rect(MAP_WIDTH, 0, INFO_WIDTH, SCREEN_HEIGHT)) for button in self.buttons: button.draw() if self.is_play and not self.isOver(): if self.useAI: x, y = self.AI.findBestChess(self.map.map, self.player) self.checkClick(x, y, True) self.useAI = False if self.action is not None: self.checkClick(self.action[0], self.action[1]) self.action = None if not self.isOver(): self.changeMouseShow() if self.isOver(): self.showWinner() self.map.drawBackground(self.screen) self.map.drawChess(self.screen) def changeMouseShow(self): map_x, map_y = pygame.mouse.get_pos() x, y = self.map.MapPosToIndex(map_x, map_y) if self.map.isInMap(map_x, map_y) and self.map.isEmpty(x, y): pygame.mouse.set_visible(False) light_red = (213, 90, 107) pos, radius = (map_x, map_y), CHESS_RADIUS pygame.draw.circle(self.screen, light_red, pos, radius) else: pygame.mouse.set_visible(True) def checkClick(self,x, y, isAI=False): self.map.click(x, y, self.player) if self.AI.isWin(self.map.map, self.player): self.winner = self.player self.click_button(self.buttons[1]) else: self.player = self.map.reverseTurn(self.player) if not isAI: self.useAI = True def mouseClick(self, map_x, map_y): if self.is_play and self.map.isInMap(map_x, map_y) and not self.isOver(): x, y = self.map.MapPosToIndex(map_x, map_y) if self.map.isEmpty(x, y): self.action = (x, y) def isOver(self): return self.winner is not None def showWinner(self): def showFont(screen, text, location_x, locaiton_y, height): font = pygame.font.SysFont(None, height) font_image = font.render(text, True, (0, 0, 255), (255, 255, 255)) font_image_rect = font_image.get_rect() font_image_rect.x = location_x font_image_rect.y = locaiton_y screen.blit(font_image, font_image_rect) if self.winner == MAP_ENTRY_TYPE.MAP_PLAYER_ONE: str = 'Winner is White' else: str = 'Winner is Black' showFont(self.screen, str, MAP_WIDTH + 25, SCREEN_HEIGHT - 60, 30) pygame.mouse.set_visible(True) def click_button(self, button): if button.click(self): for tmp in self.buttons: if tmp != button: tmp.unclick() def check_buttons(self, mouse_x, mouse_y): for button in self.buttons: if button.rect.collidepoint(mouse_x, mouse_y): self.click_button(button) break game = Game("FIVE CHESS " + GAME_VERSION)while True: game.play() pygame.display.update() for event in pygame.event.get(): if event.type == pygame.QUIT: pygame.quit() exit() elif event.type == pygame.MOUSEBUTTONDOWN: mouse_x, mouse_y = pygame.mouse.get_pos() game.mouseClick(mouse_x, mouse_y) game.check_buttons(mouse_x, mouse_y)

GameMap.py

這個文件沒有修改，可以直接使用上一篇中的代碼。

ChessAI.py

AI實現的代碼，這個AI目前很簡單，只會思考一步，後續會增加思考的步數，比如2步或4步。

from GameMap import *from enum import IntEnumimport copyimport timeclass 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 = 8FIVE = CHESS_TYPE.LIVE_FIVE.valueFOUR, THREE, TWO = CHESS_TYPE.LIVE_FOUR.value, CHESS_TYPE.LIVE_THREE.value, CHESS_TYPE.LIVE_TWO.valueSFOUR, STHREE, STWO = CHESS_TYPE.CHONG_FOUR.value, CHESS_TYPE.SLEEP_THREE.value, CHESS_TYPE.SLEEP_TWO.value class ChessAI(): def __init__(self, chess_len): 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)] 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 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 def search(self, board, turn): moves = self.genmove(board, turn) bestmove = None max_score = -0x7fffffff for score, x, y in moves: board[y][x] = turn.value score = self.evaluate(board, turn) board[y][x] = 0 if score > max_score: max_score = score bestmove = (max_score, x, y) return bestmove def findBestChess(self, board, turn): time1 = time.time() score, x, y = self.search(board, turn) time2 = time.time() print('time[%f] (%d, %d), score[%d] save[%d]' % ((time2-time1), x, y, score, self.save_count)) return (x, y) # calculate score, FIXME: May Be Improved def getScore(self, mine_count, opponent_count): mscore, oscore = 0, 0 if mine_count[FIVE] > 0: return (10000, 0) if opponent_count[FIVE] > 0: return (0, 10000) if mine_count[SFOUR] >= 2: mine_count[FOUR] += 1 if opponent_count[FOUR] > 0: return (0, 9050) if opponent_count[SFOUR] > 0: return (0, 9040) if mine_count[FOUR] > 0: return (9030, 0) if mine_count[SFOUR] > 0 and mine_count[THREE] > 0: return (9020, 0) if opponent_count[THREE] > 0 and mine_count[SFOUR] == 0: return (0, 9010) if (mine_count[THREE] > 1 and opponent_count[THREE] == 0 and opponent_count[STHREE] == 0): return (9000, 0) if mine_count[SFOUR] > 0: mscore += 2000 if mine_count[THREE] > 1: mscore += 500 elif mine_count[THREE] > 0: mscore += 100 if opponent_count[THREE] > 1: oscore += 2000 elif opponent_count[THREE] > 0: oscore += 400 if mine_count[STHREE] > 0: mscore += mine_count[STHREE] * 10 if opponent_count[STHREE] > 0: oscore += opponent_count[STHREE] * 10 if mine_count[TWO] > 0: mscore += mine_count[TWO] * 4 if opponent_count[TWO] > 0: oscore += opponent_count[TWO] * 4 if mine_count[STWO] > 0: mscore += mine_count[STWO] * 4 if opponent_count[STWO] > 0: oscore += opponent_count[STWO] * 4 return (mscore, oscore) def evaluate(self, board, turn, checkWin=False): self.reset() if turn == MAP_ENTRY_TYPE.MAP_PLAYER_ONE: mine = 1 opponent = 2 else: mine = 2 opponent = 1 for y in range(self.len): for x in range(self.len): if board[y][x] == mine: self.evaluatePoint(board, x, y, mine, opponent) elif board[y][x] == opponent: self.evaluatePoint(board, x, y, opponent, mine) mine_count = self.count[mine-1] opponent_count = self.count[opponent-1] if checkWin: return mine_count[FIVE] > 0 else: mscore, oscore = self.getScore(mine_count, opponent_count) return (mscore - oscore) def evaluatePoint(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(4): if self.record[y][x][i] == 0: self.analysisLine(board, x, y, i, dir_offset[i], mine, opponent, self.count[mine-1]) else: self.save_count += 1 # line is fixed len 9: XXXXMXXXX def getLine(self, board, x, y, dir_offset, mine, opponent): line = [0 for i in range(9)] tmp_x = x + (-5 * dir_offset[0]) tmp_y = y + (-5 * dir_offset[1]) for i in range(9): tmp_x += dir_offset[0] tmp_y += dir_offset[1] if (tmp_x < 0 or tmp_x >= self.len or tmp_y < 0 or tmp_y >= self.len): line[i] = opponent # set out of range as opponent chess else: line[i] = board[tmp_y][tmp_x] return line def analysisLine(self, board, x, y, dir_index, dir, mine, opponent, count): def setRecord(self, x, y, left, right, dir_index, dir_offset): tmp_x = x + (-5 + left) * dir_offset[0] tmp_y = y + (-5 + left) * dir_offset[1] for i in range(left, right): tmp_x += dir_offset[0] tmp_y += dir_offset[1] self.record[tmp_y][tmp_x][dir_index] = 1 empty = MAP_ENTRY_TYPE.MAP_EMPTY.value left_idx, right_idx = 4, 4 line = self.getLine(board, x, y, dir, mine, opponent) while right_idx < 8: if line[right_idx+1] != mine: break right_idx += 1 while left_idx > 0: if line[left_idx-1] != mine: break left_idx -= 1 left_range, right_range = left_idx, right_idx while right_range < 8: if line[right_range+1] == opponent: break right_range += 1 while left_range > 0: if line[left_range-1] == opponent: break left_range -= 1 chess_range = right_range - left_range + 1 if chess_range < 5: setRecord(self, x, y, left_range, right_range, dir_index, dir) return CHESS_TYPE.NONE setRecord(self, x, y, left_idx, right_idx, dir_index, dir) m_range = right_idx - left_idx + 1 # M:mine chess, P:opponent chess or out of range, X: empty if m_range == 5: count[FIVE] += 1 # Live Four : XMMMMX # Chong Four : XMMMMP, PMMMMX if m_range == 4: left_empty = right_empty = False if line[left_idx-1] == empty: left_empty = True if line[right_idx+1] == empty: right_empty = True if left_empty and right_empty: count[FOUR] += 1 elif left_empty or right_empty: count[SFOUR] += 1 # Chong Four : MXMMM, MMMXM, the two types can both exist # Live Three : XMMMXX, XXMMMX # Sleep Three : PMMMX, XMMMP, PXMMMXP if m_range == 3: left_empty = right_empty = False left_four = right_four = False if line[left_idx-1] == empty: if line[left_idx-2] == mine: # MXMMM setRecord(self, x, y, left_idx-2, left_idx-1, dir_index, dir) count[SFOUR] += 1 left_four = True left_empty = True if line[right_idx+1] == empty: if line[right_idx+2] == mine: # MMMXM setRecord(self, x, y, right_idx+1, right_idx+2, dir_index, dir) count[SFOUR] += 1 right_four = True right_empty = True if left_four or right_four: pass elif left_empty and right_empty: if chess_range > 5: # XMMMXX, XXMMMX count[THREE] += 1 else: # PXMMMXP count[STHREE] += 1 elif left_empty or right_empty: # PMMMX, XMMMP count[STHREE] += 1 # Chong Four: MMXMM, only check right direction # Live Three: XMXMMX, XMMXMX the two types can both exist # Sleep Three: PMXMMX, XMXMMP, PMMXMX, XMMXMP # Live Two: XMMX # Sleep Two: PMMX, XMMP if m_range == 2: left_empty = right_empty = False left_three = right_three = False if line[left_idx-1] == empty: if line[left_idx-2] == mine: setRecord(self, x, y, left_idx-2, left_idx-1, dir_index, dir) if line[left_idx-3] == empty: if line[right_idx+1] == empty: # XMXMMX count[THREE] += 1 else: # XMXMMP count[STHREE] += 1 left_three = True elif line[left_idx-3] == opponent: # PMXMMX if line[right_idx+1] == empty: count[STHREE] += 1 left_three = True left_empty = True if line[right_idx+1] == empty: if line[right_idx+2] == mine: if line[right_idx+3] == mine: # MMXMM setRecord(self, x, y, right_idx+1, right_idx+2, dir_index, dir) count[SFOUR] += 1 right_three = True elif line[right_idx+3] == empty: #setRecord(self, x, y, right_idx+1, right_idx+2, dir_index, dir) if left_empty: # XMMXMX count[THREE] += 1 else: # PMMXMX count[STHREE] += 1 right_three = True elif left_empty: # XMMXMP count[STHREE] += 1 right_three = True right_empty = True if left_three or right_three: pass elif left_empty and right_empty: # XMMX count[TWO] += 1 elif left_empty or right_empty: # PMMX, XMMP count[STWO] += 1 # Live Two: XMXMX, XMXXMX only check right direction # Sleep Two: PMXMX, XMXMP if m_range == 1: left_empty = right_empty = False if line[left_idx-1] == empty: if line[left_idx-2] == mine: if line[left_idx-3] == empty: if line[right_idx+1] == opponent: # XMXMP count[STWO] += 1 left_empty = True if line[right_idx+1] == empty: if line[right_idx+2] == mine: if line[right_idx+3] == empty: if left_empty: # XMXMX #setRecord(self, x, y, left_idx, right_idx+2, dir_index, dir) count[TWO] += 1 else: # PMXMX count[STWO] += 1 elif line[right_idx+2] == empty: if line[right_idx+3] == mine and line[right_idx+4] == empty: # XMXXMX count[TWO] += 1 return CHESS_TYPE.NONE