AI五子棋：極大極小值搜索與alpha beta剪枝實戰(zhàn))
簡介這是一份面向Python初學(xué)者與AI算法愛好者的五子棋AI實戰(zhàn)項目源碼圍繞極大極小值搜索與Alpha-Beta剪枝兩大經(jīng)典決策樹技術(shù)展開幫助讀者理解零和博弈中的搜索策略與剪枝優(yōu)化思路。壓縮包共12個文件約150KB以py源碼為主輔以xml配置、pyc緩存、iml工程文件及doc、pdf參考文檔涵蓋游戲規(guī)則、AI決策、玩家交互與主程序等模塊結(jié)構(gòu)清晰便于按功能閱讀。目前已有3017人學(xué)習(xí)下載適合作為課程設(shè)計、畢業(yè)設(shè)計或算法練手素材。讀者可從中掌握評估函數(shù)設(shè)計、遞歸搜索實現(xiàn)、Alpha-Beta邊界剪枝及棋局緩存優(yōu)化等關(guān)鍵環(huán)節(jié)并借助附帶的論文與說明文檔加深對搜索效率與代碼組織方式的理解快速搭建可人機對弈的完整五子棋程序。1. 從一盤被 AI 反殺的棋說起極大極小值搜索到底在算什么很多人第一次寫五子棋 AI都會經(jīng)歷同一個場景棋盤畫好了落子邏輯也通了結(jié)果自己隨手下了十幾手AI 卻像睡著一樣明明活三擺在眼前也不堵。問題不在界面而在「AI 到底怎么選點」這一步。基于 Python 的 AI 五子棋實現(xiàn)核心就是讓程序在有限時間內(nèi)評估未來若干步選出對自己最有利的落子。而支撐這套決策的經(jīng)典算法就是極大極小值搜索配合 alpha beta 剪枝。這套方案適合兩類人一類是剛學(xué)完 Python 基礎(chǔ)、想找一個能跑通又有成就感的練手項目另一類是想理解博弈樹搜索、為后面做更復(fù)雜棋類或決策系統(tǒng)打底的人。它不需要深度學(xué)習(xí)框架不依賴顯卡一臺普通筆記本就能跑。難點也不在 Python 語法而在「怎么把棋局變成分數(shù)」「怎么在爆炸的狀態(tài)空間里砍掉無用分支」。下面我按自己實際寫過的順序把選型、評估函數(shù)、搜索框架、剪枝和調(diào)參一層層拆開。2. 棋盤表示與評估函數(shù)AI 的「眼睛」怎么造2.1 用二維列表還是 NumPy 數(shù)組棋盤表示決定了后面所有代碼的寫法。最常見的做法是用 15×15 的二維列表0 表示空1 表示黑2 表示白。優(yōu)點是直觀、調(diào)試方便打印出來一眼就能看懂。缺點是每次評估都要遍歷大量格子純 Python 循環(huán)在深層搜索時會明顯拖慢速度。如果你已經(jīng)裝了 NumPy可以用np.zeros((15,15), dtypenp.int8)內(nèi)存更緊湊切片和向量化統(tǒng)計也更快。但要注意極大極小值搜索里大量操作是「試下—評估—撤銷」NumPy 的拷貝開銷反而可能拖后腿。我一般會先用二維列表把邏輯跑通確認搜索深度和剪枝正確后再針對熱點函數(shù)做局部優(yōu)化。新手直接上 NumPy 容易在索引和拷貝上翻車血淚經(jīng)驗是先讓 AI 能下棋再讓它下得快。# 棋盤初始化15x150空 1黑 2白 BOARD_SIZE 15 board [[0] * BOARD_SIZE for _ in range(BOARD_SIZE)] def print_board(board): # 簡單打印方便調(diào)試 for row in board: print( .join(str(x) for x in row))這段代碼沒有復(fù)雜邏輯重點在board的結(jié)構(gòu)。后面所有落子、撤銷、評估都圍繞它展開。BOARD_SIZE單獨抽出來是為了后面改棋盤大小時不用滿文件找數(shù)字。2.2 評估函數(shù)把棋型翻譯成分數(shù)評估函數(shù)是 AI 的「眼睛」。它把當前棋盤掃一遍統(tǒng)計雙方形成了哪些棋型再折算成分數(shù)。五子棋常見棋型按威脅從高到低大致是連五、活四、沖四、活三、眠三、活二、眠二。分值可以設(shè)成棋型黑方分值白方分值說明連五100000100000已經(jīng)贏了活四1000010000兩頭都能成五沖四10001000只有一頭能成五活三10001000能變活四眠三100100受限的三活二100100有發(fā)展空間眠二1010受限的二實際寫的時候不需要對每個格子做復(fù)雜模式匹配常見做法是掃描每條橫、豎、斜線把連續(xù)同色段提取出來再根據(jù)兩端是否被封判斷棋型。下面是一個簡化版的行掃描思路def evaluate_line(line, role): # line 是一串 0/1/2role 是當前評估的一方 score 0 count 0 for cell in line: if cell role: count 1 else: if count 5: score 100000 elif count 4: score 10000 elif count 3: score 1000 elif count 2: score 100 elif count 1: score 10 count 0 # 處理行尾連續(xù)段 if count 5: score 100000 elif count 4: score 10000 elif count 3: score 1000 elif count 2: score 100 elif count 1: score 10 return score這段代碼只統(tǒng)計了「連續(xù)同色」的粗略分數(shù)沒有區(qū)分活四和沖四。真實項目里需要額外記錄連續(xù)段兩端是否為空才能把活四和沖四分開。參數(shù)上連五必須遠大于其他棋型之和否則 AI 可能為了堵一個活三而放棄自己成五。我一般會讓連五分值至少是活四的 10 倍以上避免「贏了不贏」的玄學(xué)局面。2.3 評估整盤棋遍歷四個方向單行評估只是基礎(chǔ)整盤評估要把橫、豎、兩條斜線都掃一遍。常見做法是分別提取所有行、所有列、所有主對角線和副對角線對每條線調(diào)用評估函數(shù)最后把 AI 方得分減去對手得分得到當前局面的凈分數(shù)。def evaluate_board(board, ai_role, human_role): total 0 # 橫向 for row in board: total evaluate_line(row, ai_role) total - evaluate_line(row, human_role) # 縱向 for col in range(BOARD_SIZE): line [board[row][col] for row in range(BOARD_SIZE)] total evaluate_line(line, ai_role) total - evaluate_line(line, human_role) # 主對角線 for d in range(-BOARD_SIZE 1, BOARD_SIZE): line [board[i][i - d] for i in range(BOARD_SIZE) if 0 i - d BOARD_SIZE] total evaluate_line(line, ai_role) total - evaluate_line(line, human_role) # 副對角線 for d in range(2 * BOARD_SIZE - 1): line [board[i][d - i] for i in range(BOARD_SIZE) if 0 d - i BOARD_SIZE] total evaluate_line(line, ai_role) total - evaluate_line(line, human_role) return total這里ai_role和human_role分別代表 AI 和玩家的棋子編號。凈分數(shù)為正說明 AI 占優(yōu)為負說明玩家占優(yōu)。搜索時 AI 會盡量讓這個分數(shù)變大玩家則相反。注意對角線提取時索引邊界容易寫錯建議先用小棋盤比如 5×5驗證每條線長度是否正確再換回 15×15。3. 極大極小值搜索把「我走一步、你走一步」變成一棵樹3.1 搜索樹的基本結(jié)構(gòu)極大極小值搜索把對局看成一棵樹根節(jié)點是當前局面每個子節(jié)點代表一種落子后的新局面。AI 層希望分數(shù)越大越好玩家層希望分數(shù)越小越好。搜索到指定深度后用評估函數(shù)給葉子節(jié)點打分再逐層回傳AI 層取最大值玩家層取最小值。def minimax(board, depth, is_ai, ai_role, human_role): # 到達深度限制或終局返回評估分 if depth 0 or game_over(board): return evaluate_board(board, ai_role, human_role) if is_ai: best -float(inf) for (r, c) in get_empty_cells(board): board[r][c] ai_role score minimax(board, depth - 1, False, ai_role, human_role) board[r][c] 0 best max(best, score) return best else: best float(inf) for (r, c) in get_empty_cells(board): board[r][c] human_role score minimax(board, depth - 1, True, ai_role, human_role) board[r][c] 0 best min(best, score) return bestdepth控制搜索層數(shù)is_ai標記當前該誰走。每次試下后立刻撤銷保證棋盤狀態(tài)可復(fù)用。get_empty_cells返回所有空位實際項目里不會真的遍歷 225 個點而是只考慮已有棋子周圍兩格內(nèi)的候選點否則第一層就展開兩百多個分支深度 4 基本跑不動。3.2 候選點生成別在空棋盤上瞎搜五子棋大部分格子是空的真正值得考慮的是已有棋子附近的位置。常見做法是維護一個候選集合只把距離已有棋子不超過 2 的空白點加入搜索。def get_candidates(board, radius2): candidates set() for r in range(BOARD_SIZE): for c in range(BOARD_SIZE): if board[r][c] ! 0: for dr in range(-radius, radius 1): for dc in range(-radius, radius 1): nr, nc r dr, c dc if 0 nr BOARD_SIZE and 0 nc BOARD_SIZE: if board[nr][nc] 0: candidates.add((nr, nc)) return list(candidates)radius2是經(jīng)驗值。太小會漏掉跳活三的防守點太大分支數(shù)暴漲。如果發(fā)現(xiàn) AI 偶爾不堵關(guān)鍵位置先把 radius 調(diào)到 3 試試確認是候選集問題還是評估函數(shù)問題。這個函數(shù)在每層遞歸里都會被調(diào)用可以緩存或增量更新但新手先保證正確性。3.3 深度與性能的取舍純極大極小值搜索的復(fù)雜度是分支數(shù)的深度次方。假設(shè)每層 30 個候選點深度 4 就是 81 萬次評估純 Python 可能要跑好幾秒。深度 5 直接上千萬基本不可接受。所以實際項目里必須配合剪枝把無效分支砍掉。下面這張表是我在不同深度下的粗略體感搜索深度無剪枝耗時加 alpha beta 后棋力表現(xiàn)2很快很快只會看一步容易被騙3可接受很快能堵活三進攻弱4明顯卡頓可接受業(yè)余新手能打5基本跑不動較慢需要優(yōu)化評估函數(shù)6不可用勉強必須配合候選點裁剪我一般會把默認深度設(shè)成 4讓 AI 在可接受時間內(nèi)有基本攻防。如果機器性能好可以嘗試 5但一定要先做剪枝和候選點限制。4. alpha beta 剪枝砍掉那些「不用看也知道沒用」的分支4.1 剪枝到底在剪什么alpha beta 剪枝的核心思想是如果已經(jīng)發(fā)現(xiàn)某個分支的結(jié)果不可能比當前已知的最優(yōu)選擇更好就不用繼續(xù)展開這個分支。alpha 記錄 AI 層當前能保證的最好分數(shù)beta 記錄玩家層當前能保證的最差分數(shù)。當 alpha beta 時說明這個分支對雙方都沒有繼續(xù)看的價值直接返回。def alphabeta(board, depth, alpha, beta, is_ai, ai_role, human_role): if depth 0 or game_over(board): return evaluate_board(board, ai_role, human_role) if is_ai: best -float(inf) for (r, c) in get_candidates(board): board[r][c] ai_role score alphabeta(board, depth - 1, alpha, beta, False, ai_role, human_role) board[r][c] 0 best max(best, score) alpha max(alpha, best) if alpha beta: break # 剪枝 return best else: best float(inf) for (r, c) in get_candidates(board): board[r][c] human_role score alphabeta(board, depth - 1, alpha, beta, True, ai_role, human_role) board[r][c] 0 best min(best, score) beta min(beta, best) if alpha beta: break # 剪枝 return bestalpha初始為負無窮beta初始為正無窮。AI 層更新 alpha玩家層更新 beta。一旦 alpha 超過 beta說明這個分支的結(jié)果已經(jīng)被之前的更好選擇覆蓋繼續(xù)搜索沒有意義。剪枝效果高度依賴候選點的順序如果先搜到好棋剪枝會砍掉大量分支如果先搜到差棋剪枝效果大打折扣。4.2 候選點排序讓剪枝真正生效一個實用技巧是在展開子節(jié)點前先按「粗略威脅分」排序把可能形成活四、沖四、活三的點排在前面。這樣 alpha beta 能更早遇到好棋剪枝效率明顯提升。def sort_candidates(board, candidates, role): def rough_score(pos): r, c pos board[r][c] role s evaluate_board(board, role, 3 - role) board[r][c] 0 return s return sorted(candidates, keyrough_score, reverseTrue)role是當前落子方3 - role得到對手編號。這個排序本身有開銷但換來的剪枝收益通常更大。如果發(fā)現(xiàn)加了排序反而變慢說明評估函數(shù)太重需要先簡化評估或減少候選點數(shù)量。4.3 終局判斷與勝負分搜索到連五時必須立刻返回一個極大或極小的分數(shù)而不是繼續(xù)用評估函數(shù)。否則 AI 可能因為評估函數(shù)沒給連五足夠高的分而錯過必勝點。def game_over(board): # 檢查是否有連五 for r in range(BOARD_SIZE): for c in range(BOARD_SIZE): if board[r][c] 0: continue role board[r][c] for dr, dc in [(0,1),(1,0),(1,1),(1,-1)]: count 1 nr, nc r dr, c dc while 0 nr BOARD_SIZE and 0 nc BOARD_SIZE and board[nr][nc] role: count 1 nr dr nc dc if count 5: return True return False這個函數(shù)在每層遞歸都會被調(diào)用效率不高但邏輯清晰。優(yōu)化做法是只在落子位置周圍檢查四個方向而不是全盤掃描。新手先用全盤版保證正確后面再改。5. 避坑與排查那些讓我熬夜的翻車現(xiàn)場5.1 AI 明明能贏卻去堵對方現(xiàn)象AI 自己已經(jīng)活四下一手就能成五卻跑去堵玩家的活三。 原因評估函數(shù)里活四和活三分值太接近或者連五分值不夠高導(dǎo)致搜索回傳時「贏棋」和「堵棋」分數(shù)差不多。 解決把連五分值調(diào)到遠大于其他棋型之和并在game_over里對連五直接返回勝負分不走普通評估。5.2 搜索深度一加就卡死現(xiàn)象深度設(shè)成 4 還能跑設(shè)成 5 直接幾十秒沒響應(yīng)。 原因候選點沒有限制每層展開兩百多個分支加上評估函數(shù)每次全盤掃描計算量爆炸。 解決用get_candidates限制候選點評估函數(shù)改成增量更新或只掃描落子附近必要時把深度降回 4。5.3 剪枝后棋力反而下降現(xiàn)象加了 alpha beta 之后AI 偶爾下出明顯臭棋。 原因候選點順序太差剪枝把正確分支提前砍掉了或者 alpha、beta 更新寫反AI 層和玩家層搞混。 解決先關(guān)掉剪枝驗證純極大極小值結(jié)果確認評估和搜索邏輯正確再逐步加剪枝和排序。檢查is_ai分支里更新的是 alpha玩家分支更新的是 beta。5.4 棋盤邊界索引越界現(xiàn)象對角線提取或連五判斷時報IndexError。 原因斜線遍歷時沒有正確限制行列范圍負索引在 Python 里會繞回末尾導(dǎo)致邏輯錯誤而不是報錯。 解決所有索引操作前加0 nr BOARD_SIZE判斷對角線提取用列表推導(dǎo)時顯式過濾邊界。5.5 評估函數(shù)正負號寫反現(xiàn)象AI 一直往角落下完全不進攻。 原因evaluate_board里 AI 分和玩家分減反了導(dǎo)致 AI 以為自己的棋對對手有利。 解決打印幾個典型局面的評估分手動算一遍預(yù)期值確認 AI 方得分是加、玩家方得分是減。6. 進階技巧用置換表和迭代加深把棋力再抬一檔當基礎(chǔ)版本跑通后最值得做的兩個優(yōu)化是置換表和迭代加深。置換表用字典緩存已經(jīng)搜索過的局面鍵可以用棋盤字符串加當前深度和輪次。同一個局面在搜索樹里可能通過不同順序到達緩存后能省下大量重復(fù)計算。transposition {} def board_key(board, depth, is_ai): return (str(board), depth, is_ai) def alphabeta_with_tt(board, depth, alpha, beta, is_ai, ai_role, human_role): key board_key(board, depth, is_ai) if key in transposition: return transposition[key] # ... 原有搜索邏輯 ... transposition[key] best return best注意置換表要限制大小否則內(nèi)存會持續(xù)增長。我一般設(shè)一個上限超過就清空或按簡單策略淘汰。迭代加深則是從深度 1 開始搜逐步加深每次用上一層的最優(yōu)走法作為下一層的首選候選點這樣 alpha beta 剪枝效率更高還能在時間不夠時隨時返回當前最優(yōu)解。另一個實用技巧是「只搜關(guān)鍵點」如果 AI 或玩家已經(jīng)有活四直接返回勝負分不再展開。這個判斷放在搜索入口能省掉大量無意義遞歸。最后說個我自己的習(xí)慣每次改完評估函數(shù)或剪枝邏輯先用幾個固定局面做回歸測試比如「AI 活四必須贏」「玩家活四必須堵」「雙活三必須防」確認沒有退化再繼續(xù)調(diào)參。這套基于 Python 的 AI 五子棋實現(xiàn)真正花時間的不是寫搜索框架而是反復(fù)調(diào)評估函數(shù)和驗證邊界。希望幫到你。本文還有配套的精品資源點擊獲取 Python實現(xiàn)AI五子棋：極大極小值搜索與alpha beta剪枝實戰(zhàn)
簡介這是一份面向Python初學(xué)者與AI算法愛好者的五子棋AI實戰(zhàn)項目源碼圍繞極大極小值搜索與Alpha-Beta剪枝兩大經(jīng)典決策樹技術(shù)展開幫助讀者理解零和博弈中的搜索策略與剪枝優(yōu)化思路。壓縮包共12個文件約150KB以py源碼為主輔以xml配置、pyc緩存、iml工程文件及doc、pdf參考文檔涵蓋游戲規(guī)則、AI決策、玩家交互與主程序等模塊結(jié)構(gòu)清晰便于按功能閱讀。目前已有3017人學(xué)習(xí)下載適合作為課程設(shè)計、畢業(yè)設(shè)計或算法練手素材。讀者可從中掌握評估函數(shù)設(shè)計、遞歸搜索實現(xiàn)、Alpha-Beta邊界剪枝及棋局緩存優(yōu)化等關(guān)鍵環(huán)節(jié)并借助附帶的論文與說明文檔加深對搜索效率與代碼組織方式的理解快速搭建可人機對弈的完整五子棋程序。1. 從一盤被 AI 反殺的棋說起極大極小值搜索到底在算什么很多人第一次寫五子棋 AI都會經(jīng)歷同一個場景棋盤畫好了落子邏輯也通了結(jié)果自己隨手下了十幾手AI 卻像睡著一樣明明活三擺在眼前也不堵。問題不在界面而在「AI 到底怎么選點」這一步。基于 Python 的 AI 五子棋實現(xiàn)核心就是讓程序在有限時間內(nèi)評估未來若干步選出對自己最有利的落子。而支撐這套決策的經(jīng)典算法就是極大極小值搜索配合 alpha beta 剪枝。這套方案適合兩類人一類是剛學(xué)完 Python 基礎(chǔ)、想找一個能跑通又有成就感的練手項目另一類是想理解博弈樹搜索、為后面做更復(fù)雜棋類或決策系統(tǒng)打底的人。它不需要深度學(xué)習(xí)框架不依賴顯卡一臺普通筆記本就能跑。難點也不在 Python 語法而在「怎么把棋局變成分數(shù)」「怎么在爆炸的狀態(tài)空間里砍掉無用分支」。下面我按自己實際寫過的順序把選型、評估函數(shù)、搜索框架、剪枝和調(diào)參一層層拆開。2. 棋盤表示與評估函數(shù)AI 的「眼睛」怎么造2.1 用二維列表還是 NumPy 數(shù)組棋盤表示決定了后面所有代碼的寫法。最常見的做法是用 15×15 的二維列表0 表示空1 表示黑2 表示白。優(yōu)點是直觀、調(diào)試方便打印出來一眼就能看懂。缺點是每次評估都要遍歷大量格子純 Python 循環(huán)在深層搜索時會明顯拖慢速度。如果你已經(jīng)裝了 NumPy可以用np.zeros((15,15), dtypenp.int8)內(nèi)存更緊湊切片和向量化統(tǒng)計也更快。但要注意極大極小值搜索里大量操作是「試下—評估—撤銷」NumPy 的拷貝開銷反而可能拖后腿。我一般會先用二維列表把邏輯跑通確認搜索深度和剪枝正確后再針對熱點函數(shù)做局部優(yōu)化。新手直接上 NumPy 容易在索引和拷貝上翻車血淚經(jīng)驗是先讓 AI 能下棋再讓它下得快。# 棋盤初始化15x150空 1黑 2白 BOARD_SIZE 15 board [[0] * BOARD_SIZE for _ in range(BOARD_SIZE)] def print_board(board): # 簡單打印方便調(diào)試 for row in board: print( .join(str(x) for x in row))這段代碼沒有復(fù)雜邏輯重點在board的結(jié)構(gòu)。后面所有落子、撤銷、評估都圍繞它展開。BOARD_SIZE單獨抽出來是為了后面改棋盤大小時不用滿文件找數(shù)字。2.2 評估函數(shù)把棋型翻譯成分數(shù)評估函數(shù)是 AI 的「眼睛」。它把當前棋盤掃一遍統(tǒng)計雙方形成了哪些棋型再折算成分數(shù)。五子棋常見棋型按威脅從高到低大致是連五、活四、沖四、活三、眠三、活二、眠二。分值可以設(shè)成棋型黑方分值白方分值說明連五100000100000已經(jīng)贏了活四1000010000兩頭都能成五沖四10001000只有一頭能成五活三10001000能變活四眠三100100受限的三活二100100有發(fā)展空間眠二1010受限的二實際寫的時候不需要對每個格子做復(fù)雜模式匹配常見做法是掃描每條橫、豎、斜線把連續(xù)同色段提取出來再根據(jù)兩端是否被封判斷棋型。下面是一個簡化版的行掃描思路def evaluate_line(line, role): # line 是一串 0/1/2role 是當前評估的一方 score 0 count 0 for cell in line: if cell role: count 1 else: if count 5: score 100000 elif count 4: score 10000 elif count 3: score 1000 elif count 2: score 100 elif count 1: score 10 count 0 # 處理行尾連續(xù)段 if count 5: score 100000 elif count 4: score 10000 elif count 3: score 1000 elif count 2: score 100 elif count 1: score 10 return score這段代碼只統(tǒng)計了「連續(xù)同色」的粗略分數(shù)沒有區(qū)分活四和沖四。真實項目里需要額外記錄連續(xù)段兩端是否為空才能把活四和沖四分開。參數(shù)上連五必須遠大于其他棋型之和否則 AI 可能為了堵一個活三而放棄自己成五。我一般會讓連五分值至少是活四的 10 倍以上避免「贏了不贏」的玄學(xué)局面。2.3 評估整盤棋遍歷四個方向單行評估只是基礎(chǔ)整盤評估要把橫、豎、兩條斜線都掃一遍。常見做法是分別提取所有行、所有列、所有主對角線和副對角線對每條線調(diào)用評估函數(shù)最后把 AI 方得分減去對手得分得到當前局面的凈分數(shù)。def evaluate_board(board, ai_role, human_role): total 0 # 橫向 for row in board: total evaluate_line(row, ai_role) total - evaluate_line(row, human_role) # 縱向 for col in range(BOARD_SIZE): line [board[row][col] for row in range(BOARD_SIZE)] total evaluate_line(line, ai_role) total - evaluate_line(line, human_role) # 主對角線 for d in range(-BOARD_SIZE 1, BOARD_SIZE): line [board[i][i - d] for i in range(BOARD_SIZE) if 0 i - d BOARD_SIZE] total evaluate_line(line, ai_role) total - evaluate_line(line, human_role) # 副對角線 for d in range(2 * BOARD_SIZE - 1): line [board[i][d - i] for i in range(BOARD_SIZE) if 0 d - i BOARD_SIZE] total evaluate_line(line, ai_role) total - evaluate_line(line, human_role) return total這里ai_role和human_role分別代表 AI 和玩家的棋子編號。凈分數(shù)為正說明 AI 占優(yōu)為負說明玩家占優(yōu)。搜索時 AI 會盡量讓這個分數(shù)變大玩家則相反。注意對角線提取時索引邊界容易寫錯建議先用小棋盤比如 5×5驗證每條線長度是否正確再換回 15×15。3. 極大極小值搜索把「我走一步、你走一步」變成一棵樹3.1 搜索樹的基本結(jié)構(gòu)極大極小值搜索把對局看成一棵樹根節(jié)點是當前局面每個子節(jié)點代表一種落子后的新局面。AI 層希望分數(shù)越大越好玩家層希望分數(shù)越小越好。搜索到指定深度后用評估函數(shù)給葉子節(jié)點打分再逐層回傳AI 層取最大值玩家層取最小值。def minimax(board, depth, is_ai, ai_role, human_role): # 到達深度限制或終局返回評估分 if depth 0 or game_over(board): return evaluate_board(board, ai_role, human_role) if is_ai: best -float(inf) for (r, c) in get_empty_cells(board): board[r][c] ai_role score minimax(board, depth - 1, False, ai_role, human_role) board[r][c] 0 best max(best, score) return best else: best float(inf) for (r, c) in get_empty_cells(board): board[r][c] human_role score minimax(board, depth - 1, True, ai_role, human_role) board[r][c] 0 best min(best, score) return bestdepth控制搜索層數(shù)is_ai標記當前該誰走。每次試下后立刻撤銷保證棋盤狀態(tài)可復(fù)用。get_empty_cells返回所有空位實際項目里不會真的遍歷 225 個點而是只考慮已有棋子周圍兩格內(nèi)的候選點否則第一層就展開兩百多個分支深度 4 基本跑不動。3.2 候選點生成別在空棋盤上瞎搜五子棋大部分格子是空的真正值得考慮的是已有棋子附近的位置。常見做法是維護一個候選集合只把距離已有棋子不超過 2 的空白點加入搜索。def get_candidates(board, radius2): candidates set() for r in range(BOARD_SIZE): for c in range(BOARD_SIZE): if board[r][c] ! 0: for dr in range(-radius, radius 1): for dc in range(-radius, radius 1): nr, nc r dr, c dc if 0 nr BOARD_SIZE and 0 nc BOARD_SIZE: if board[nr][nc] 0: candidates.add((nr, nc)) return list(candidates)radius2是經(jīng)驗值。太小會漏掉跳活三的防守點太大分支數(shù)暴漲。如果發(fā)現(xiàn) AI 偶爾不堵關(guān)鍵位置先把 radius 調(diào)到 3 試試確認是候選集問題還是評估函數(shù)問題。這個函數(shù)在每層遞歸里都會被調(diào)用可以緩存或增量更新但新手先保證正確性。3.3 深度與性能的取舍純極大極小值搜索的復(fù)雜度是分支數(shù)的深度次方。假設(shè)每層 30 個候選點深度 4 就是 81 萬次評估純 Python 可能要跑好幾秒。深度 5 直接上千萬基本不可接受。所以實際項目里必須配合剪枝把無效分支砍掉。下面這張表是我在不同深度下的粗略體感搜索深度無剪枝耗時加 alpha beta 后棋力表現(xiàn)2很快很快只會看一步容易被騙3可接受很快能堵活三進攻弱4明顯卡頓可接受業(yè)余新手能打5基本跑不動較慢需要優(yōu)化評估函數(shù)6不可用勉強必須配合候選點裁剪我一般會把默認深度設(shè)成 4讓 AI 在可接受時間內(nèi)有基本攻防。如果機器性能好可以嘗試 5但一定要先做剪枝和候選點限制。4. alpha beta 剪枝砍掉那些「不用看也知道沒用」的分支4.1 剪枝到底在剪什么alpha beta 剪枝的核心思想是如果已經(jīng)發(fā)現(xiàn)某個分支的結(jié)果不可能比當前已知的最優(yōu)選擇更好就不用繼續(xù)展開這個分支。alpha 記錄 AI 層當前能保證的最好分數(shù)beta 記錄玩家層當前能保證的最差分數(shù)。當 alpha beta 時說明這個分支對雙方都沒有繼續(xù)看的價值直接返回。def alphabeta(board, depth, alpha, beta, is_ai, ai_role, human_role): if depth 0 or game_over(board): return evaluate_board(board, ai_role, human_role) if is_ai: best -float(inf) for (r, c) in get_candidates(board): board[r][c] ai_role score alphabeta(board, depth - 1, alpha, beta, False, ai_role, human_role) board[r][c] 0 best max(best, score) alpha max(alpha, best) if alpha beta: break # 剪枝 return best else: best float(inf) for (r, c) in get_candidates(board): board[r][c] human_role score alphabeta(board, depth - 1, alpha, beta, True, ai_role, human_role) board[r][c] 0 best min(best, score) beta min(beta, best) if alpha beta: break # 剪枝 return bestalpha初始為負無窮beta初始為正無窮。AI 層更新 alpha玩家層更新 beta。一旦 alpha 超過 beta說明這個分支的結(jié)果已經(jīng)被之前的更好選擇覆蓋繼續(xù)搜索沒有意義。剪枝效果高度依賴候選點的順序如果先搜到好棋剪枝會砍掉大量分支如果先搜到差棋剪枝效果大打折扣。4.2 候選點排序讓剪枝真正生效一個實用技巧是在展開子節(jié)點前先按「粗略威脅分」排序把可能形成活四、沖四、活三的點排在前面。這樣 alpha beta 能更早遇到好棋剪枝效率明顯提升。def sort_candidates(board, candidates, role): def rough_score(pos): r, c pos board[r][c] role s evaluate_board(board, role, 3 - role) board[r][c] 0 return s return sorted(candidates, keyrough_score, reverseTrue)role是當前落子方3 - role得到對手編號。這個排序本身有開銷但換來的剪枝收益通常更大。如果發(fā)現(xiàn)加了排序反而變慢說明評估函數(shù)太重需要先簡化評估或減少候選點數(shù)量。4.3 終局判斷與勝負分搜索到連五時必須立刻返回一個極大或極小的分數(shù)而不是繼續(xù)用評估函數(shù)。否則 AI 可能因為評估函數(shù)沒給連五足夠高的分而錯過必勝點。def game_over(board): # 檢查是否有連五 for r in range(BOARD_SIZE): for c in range(BOARD_SIZE): if board[r][c] 0: continue role board[r][c] for dr, dc in [(0,1),(1,0),(1,1),(1,-1)]: count 1 nr, nc r dr, c dc while 0 nr BOARD_SIZE and 0 nc BOARD_SIZE and board[nr][nc] role: count 1 nr dr nc dc if count 5: return True return False這個函數(shù)在每層遞歸都會被調(diào)用效率不高但邏輯清晰。優(yōu)化做法是只在落子位置周圍檢查四個方向而不是全盤掃描。新手先用全盤版保證正確后面再改。5. 避坑與排查那些讓我熬夜的翻車現(xiàn)場5.1 AI 明明能贏卻去堵對方現(xiàn)象AI 自己已經(jīng)活四下一手就能成五卻跑去堵玩家的活三。 原因評估函數(shù)里活四和活三分值太接近或者連五分值不夠高導(dǎo)致搜索回傳時「贏棋」和「堵棋」分數(shù)差不多。 解決把連五分值調(diào)到遠大于其他棋型之和并在game_over里對連五直接返回勝負分不走普通評估。5.2 搜索深度一加就卡死現(xiàn)象深度設(shè)成 4 還能跑設(shè)成 5 直接幾十秒沒響應(yīng)。 原因候選點沒有限制每層展開兩百多個分支加上評估函數(shù)每次全盤掃描計算量爆炸。 解決用get_candidates限制候選點評估函數(shù)改成增量更新或只掃描落子附近必要時把深度降回 4。5.3 剪枝后棋力反而下降現(xiàn)象加了 alpha beta 之后AI 偶爾下出明顯臭棋。 原因候選點順序太差剪枝把正確分支提前砍掉了或者 alpha、beta 更新寫反AI 層和玩家層搞混。 解決先關(guān)掉剪枝驗證純極大極小值結(jié)果確認評估和搜索邏輯正確再逐步加剪枝和排序。檢查is_ai分支里更新的是 alpha玩家分支更新的是 beta。5.4 棋盤邊界索引越界現(xiàn)象對角線提取或連五判斷時報IndexError。 原因斜線遍歷時沒有正確限制行列范圍負索引在 Python 里會繞回末尾導(dǎo)致邏輯錯誤而不是報錯。 解決所有索引操作前加0 nr BOARD_SIZE判斷對角線提取用列表推導(dǎo)時顯式過濾邊界。5.5 評估函數(shù)正負號寫反現(xiàn)象AI 一直往角落下完全不進攻。 原因evaluate_board里 AI 分和玩家分減反了導(dǎo)致 AI 以為自己的棋對對手有利。 解決打印幾個典型局面的評估分手動算一遍預(yù)期值確認 AI 方得分是加、玩家方得分是減。6. 進階技巧用置換表和迭代加深把棋力再抬一檔當基礎(chǔ)版本跑通后最值得做的兩個優(yōu)化是置換表和迭代加深。置換表用字典緩存已經(jīng)搜索過的局面鍵可以用棋盤字符串加當前深度和輪次。同一個局面在搜索樹里可能通過不同順序到達緩存后能省下大量重復(fù)計算。transposition {} def board_key(board, depth, is_ai): return (str(board), depth, is_ai) def alphabeta_with_tt(board, depth, alpha, beta, is_ai, ai_role, human_role): key board_key(board, depth, is_ai) if key in transposition: return transposition[key] # ... 原有搜索邏輯 ... transposition[key] best return best注意置換表要限制大小否則內(nèi)存會持續(xù)增長。我一般設(shè)一個上限超過就清空或按簡單策略淘汰。迭代加深則是從深度 1 開始搜逐步加深每次用上一層的最優(yōu)走法作為下一層的首選候選點這樣 alpha beta 剪枝效率更高還能在時間不夠時隨時返回當前最優(yōu)解。另一個實用技巧是「只搜關(guān)鍵點」如果 AI 或玩家已經(jīng)有活四直接返回勝負分不再展開。這個判斷放在搜索入口能省掉大量無意義遞歸。最后說個我自己的習(xí)慣每次改完評估函數(shù)或剪枝邏輯先用幾個固定局面做回歸測試比如「AI 活四必須贏」「玩家活四必須堵」「雙活三必須防」確認沒有退化再繼續(xù)調(diào)參。這套基于 Python 的 AI 五子棋實現(xiàn)真正花時間的不是寫搜索框架而是反復(fù)調(diào)評估函數(shù)和驗證邊界。希望幫到你。本文還有配套的精品資源點擊獲取