当前位置：首页 > news >正文

HarmonyOS 小游戏《对战五子棋》开发第14篇 - 困难AI实现：Minimax算法原理详解

news 2026/7/8 1:20:47

向前看两步——Minimax让AI学会"换位思考"

设计截图如下：

为什么需要Minimax

普通AI的局限：只看当前一步，不考虑对手的反击。

场景：AI可以选择形成活三（8000分）或冲四（10000分）。普通AI选冲四，但对手下一步会堵住冲四，AI的活三机会丢失了。

Minimax的核心思想：假设对手也会做出最优选择，选择对自己最不坏的结果。

Minimax算法原理

AI选择（最大化） / | \ 候选1 候选2 候选3 / \ / \ / \ 对手选择（最小化） ↓ ↓ ↓ ↓ ↓ ↓ 评估 评估 评估 评估 评估 评估

Max层（AI回合）：选择分数最高的走法
Min层（对手回合）：选择分数最低的走法（对AI最不利）
叶节点：用评估函数计算当前局面的分数

代码实现

privategetHardMove(board:number[][]):Move{constcandidates=this.getSortedCandidates(board);constmaxCandidates=Math.min(12,candidates.length);letbestMove:Move=candidates[0];letbestScore:number=-Infinity;letalpha:number=-Infinity;constbeta:number=Infinity;for(leti=0;i<maxCandidates;i++){constmove=candidates[i];board[move.row][move.col]=this.aiColor;// 如果直接获胜，立即返回if(this.checkWin(board,move.row,move.col,this.aiColor)){board[move.row][move.col]=EMPTY;returnmove;}// Minimax递归（对手回合，最小化）constscore=this.minimax(board,2,alpha,beta,false);board[move.row][move.col]=EMPTY;if(score>bestScore){bestScore=score;bestMove=move;}alpha=Math.max(alpha,score);}returnbestMove;}

minimax递归函数

privateminimax(board:number[][],depth:number,alpha:number,beta:number,isMaximizing:boolean):number{// 终止条件：深度为0时评估局面if(depth===0){returnthis.evaluateBoard(board);}constcandidates=this.getSortedCandidates(board);constmaxCandidates=Math.min(8,candidates.length);if(isMaximizing){// AI回合：找最大值letmaxEval:number=-Infinity;for(leti=0;i<maxCandidates;i++){constmove=candidates[i];board[move.row][move.col]=this.aiColor;if(this.checkWin(board,move.row,move.col,this.aiColor)){board[move.row][move.col]=EMPTY;returnSCORE_FIVE;// AI获胜}constevalScore=this.minimax(board,depth-1,alpha,beta,false);board[move.row][move.col]=EMPTY;maxEval=Math.max(maxEval,evalScore);alpha=Math.max(alpha,evalScore);if(beta<=alpha)break;// Alpha-Beta剪枝}returnmaxEval;}else{// 对手回合：找最小值letminEval:number=Infinity;for(leti=0;i<maxCandidates;i++){constmove=candidates[i];board[move.row][move.col]=this.humanColor;if(this.checkWin(board,move.row,move.col,this.humanColor)){board[move.row][move.col]=EMPTY;return-SCORE_FIVE;// 对手获胜（对AI最不利）}constevalScore=this.minimax(board,depth-1,alpha,beta,true);board[move.row][move.col]=EMPTY;minEval=Math.min(minEval,evalScore);beta=Math.min(beta,evalScore);if(beta<=alpha)break;// Alpha-Beta剪枝}returnminEval;}}

搜索树图解

假设AI在搜索深度2，候选3个：

深度2 AI选择(MAX) / | \ 深度1 对手(MIN) 对手(MIN) 对手(MIN) / \ / \ / \ 深度0 评估 评估 评估 评估 评估 评估 80 50 60 30 90 70 自底向上计算： 深度1: min(80,50)=50 min(60,30)=30 min(90,70)=70 深度2: max(50,30,70)=70 → 选择候选1

关键设计决策

1. 深度2的选择

constscore=this.minimax(board,2,alpha,beta,false);

深度1：只看对手反应——不够
深度2：看AI→对手→AI——合理
深度3：AI→对手→AI→对手——更好但计算量大

移动端选择深度2是性能与棋力的平衡。

2. 候选数量限制

// 顶层：12个候选constmaxCandidates=Math.min(12,candidates.length);// 递归层：8个候选constmaxCandidates=Math.min(8,candidates.length);

搜索树大小 = 12 × 8 × 8 = 768，在移动端可接受。

3. 立即获胜检查

if(this.checkWin(board,move.row,move.col,this.aiColor)){board[move.row][move.col]=EMPTY;returnmove;// 不需要继续搜索}

找到必胜走法立即返回，避免不必要的搜索。

4. 评估函数的差异

困难模式使用evaluateBoard（全盘评估），而非普通模式的evaluatePosition（单点评估）：

privateevaluateBoard(board:number[][]):number{letaiScore:number=0;lethumanScore:number=0;aiScore+=this.evaluateLines(board,this.aiColor);humanScore+=this.evaluateLines(board,this.humanColor);returnaiScore-humanScore*1.1;}