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