如何在无递归环境下用栈实现Minimax算法开发tic tac toe程序

一、栈元素核心结构 #

要模拟递归Minimax的深度优先遍历（DFS），栈中每个元素需要存储以下信息，用于追踪节点状态和回溯计算：

• board: 一维数组（0-8索引），记录当前棋盘状态（0=空，1=人类玩家，2=电脑）
• currentPlayer: 当前行动玩家（1=最小化玩家/人类，2=最大化玩家/电脑）
• parentIndex: 父节点在栈数组中的索引（-1表示根节点）
• processedChildren: 已处理完成的子节点数量
• tempScore: 当前节点的临时得分（用于回溯时更新父节点）
• isExpanded: 标记节点是否已展开所有子节点
• movePos: 当前节点对应的落子位置（0-8，用于记录最优决策）

二、栈模拟递归的核心流程 #

递归Minimax本质是先深度遍历所有子节点，再回溯计算当前节点得分。用栈实现时需严格遵循这个逻辑：

1. 初始化栈：将当前游戏的初始棋盘作为根节点（电脑为当前玩家）压入栈，标记为「未展开」。
2. 循环处理栈：直到栈为空
   • 弹出栈顶节点，若为「未展开」状态：
     1. 检查棋盘是否为终止状态（胜负已分或平局）：如果是，计算对应得分（电脑赢+10，人类赢-10，平局0），标记为「已处理」后重新压入栈，等待回溯。
     2. 若未终止，生成所有合法落子的子节点（遍历空格子，生成新棋盘）。
     3. 将当前节点标记为「已展开」，初始化临时得分（最大化玩家初始为-∞，最小化玩家初始为+∞），重新压入栈。
     4. 按逆序将所有子节点压入栈（保证栈顶是第一个要处理的子节点，符合DFS顺序）。
   • 弹出栈顶节点，若为「已处理」状态：
     1. 若为根节点，直接记录其movePos作为最优落子。
     2. 若非根节点，找到父节点并更新其临时得分：
        • 父节点是最大化玩家：取父节点当前得分与当前节点得分的最大值，同步记录对应落子位置。
        • 父节点是最小化玩家：取父节点当前得分与当前节点得分的最小值，同步记录对应落子位置。
     3. 父节点的已处理子节点数加1，若已处理数量等于总子节点数，标记父节点为「已处理」并重新压入栈，继续回溯。

三、结构化文本（ST）伪代码实现 #

TYPE MinimaxNode :
STRUCT
    board: ARRAY[0..8] OF INT; // 0=空,1=人类玩家,2=电脑
    currentPlayer: INT; // 1=最小化玩家,2=最大化玩家
    parentIndex: INT; // 父节点索引，-1为根节点
    processedChildren: INT; // 已处理子节点数
    tempScore: INT; // 临时得分
    isExpanded: BOOL; // 是否已展开子节点
    movePos: INT; // 对应落子位置
END_STRUCT
END_TYPE

VAR
    stack: ARRAY[0..100] OF MinimaxNode; // 栈数组，井字棋树深度有限，100足够
    stackTop: INT := -1; // 栈顶指针，初始为空
    rootNode: MinimaxNode;
    bestMove: INT := -1; // 最终最优落子位置
END_VAR

// 初始化根节点
rootNode.board := currentGameBoard; // 传入当前游戏棋盘
rootNode.currentPlayer := 2; // 电脑作为最大化玩家先手
rootNode.parentIndex := -1;
rootNode.processedChildren := 0;
rootNode.tempScore := -999; // 最大化玩家初始极值
rootNode.isExpanded := FALSE;
rootNode.movePos := -1;
stackTop := stackTop + 1;
stack[stackTop] := rootNode;

// 栈处理主循环
WHILE stackTop >= 0 DO
    VAR_TEMP
        currentNode: MinimaxNode;
        childCount: INT;
        children: ARRAY[0..8] OF MinimaxNode;
        i: INT;
        gameResult: INT; // -1=人类赢,0=平局,1=电脑赢,2=未结束
    END_VAR

    // 弹出栈顶节点
    currentNode := stack[stackTop];
    stackTop := stackTop - 1;

    IF NOT currentNode.isExpanded THEN
        // 检查游戏是否终止
        gameResult := CheckGameResult(currentNode.board);
        IF gameResult <> 2 THEN
            // 计算终止状态得分
            CASE gameResult OF
                1: currentNode.tempScore := 10;
                -1: currentNode.tempScore := -10;
                0: currentNode.tempScore := 0;
            END_CASE;
            currentNode.isExpanded := TRUE;
            // 压回栈等待回溯
            stackTop := stackTop + 1;
            stack[stackTop] := currentNode;
        ELSE
            // 生成所有合法子节点
            childCount := 0;
            FOR i := 0 TO 8 DO
                IF currentNode.board[i] = 0 THEN
                    children[childCount].board := currentNode.board;
                    children[childCount].board[i] := currentNode.currentPlayer;
                    children[childCount].currentPlayer := 3 - currentNode.currentPlayer; // 切换玩家（1和2互转）
                    children[childCount].parentIndex := stackTop + 1; // 父节点即将被压回，索引为stackTop+1
                    children[childCount].processedChildren := 0;
                    // 初始化子节点临时得分
                    children[childCount].tempScore := IIF(children[childCount].currentPlayer=2, -999, 999);
                    children[childCount].isExpanded := FALSE;
                    children[childCount].movePos := i;
                    childCount := childCount + 1;
                END_IF;
            END_FOR;

            // 标记当前节点为已展开，压回栈
            currentNode.isExpanded := TRUE;
            currentNode.processedChildren := 0;
            stackTop := stackTop + 1;
            stack[stackTop] := currentNode;

            // 逆序压入子节点，保证DFS遍历顺序
            FOR i := childCount - 1 DOWNTO 0 DO
                stackTop := stackTop + 1;
                stack[stackTop] := children[i];
            END_FOR;
        END_IF;
    ELSE
        // 回溯更新父节点得分
        IF currentNode.parentIndex <> -1 THEN
            VAR_TEMP
                parentNode: MinimaxNode;
                parentChildCount: INT := 0;
                j: INT;
            END_VAR
            parentNode := stack[currentNode.parentIndex];

            // 根据父节点类型更新得分
            IF parentNode.currentPlayer = 2 THEN
                IF currentNode.tempScore > parentNode.tempScore THEN
                    parentNode.tempScore := currentNode.tempScore;
                    parentNode.movePos := currentNode.movePos;
                END_IF;
            ELSE
                IF currentNode.tempScore < parentNode.tempScore THEN
                    parentNode.tempScore := currentNode.tempScore;
                    parentNode.movePos := currentNode.movePos;
                END_IF;
            END_IF;

            parentNode.processedChildren := parentNode.processedChildren + 1;

            // 计算父节点的总子节点数
            FOR j := 0 TO 8 DO
                IF parentNode.board[j] = 0 THEN
                    parentChildCount := parentChildCount + 1;
                END_IF;
            END_FOR;

            // 若所有子节点处理完成，标记父节点为已处理
            IF parentNode.processedChildren = parentChildCount THEN
                parentNode.isExpanded := TRUE;
            END_IF;

            // 更新栈中的父节点
            stack[currentNode.parentIndex] := parentNode;
        ELSE
            // 根节点处理完成，记录最优落子
            bestMove := currentNode.movePos;
        END_IF;
    END_IF;
END_WHILE;

// 检查游戏结果函数
FUNCTION CheckGameResult : INT
VAR_INPUT
    board: ARRAY[0..8] OF INT;
END_VAR
VAR_TEMP
    i: INT;
END_VAR

// 检查行
FOR i := 0 TO 6 STEP 3 DO
    IF board[i] <> 0 AND board[i] = board[i+1] AND board[i] = board[i+2] THEN
        CheckGameResult := IIF(board[i]=2, 1, -1);
        RETURN;
    END_IF;
END_FOR;

// 检查列
FOR i := 0 TO 2 DO
    IF board[i] <> 0 AND board[i] = board[i+3] AND board[i] = board[i+6] THEN
        CheckGameResult := IIF(board[i]=2, 1, -1);
        RETURN;
    END_IF;
END_FOR;

// 检查对角线
IF board[0] <> 0 AND board[0] = board[4] AND board[0] = board[8] THEN
    CheckGameResult := IIF(board[0]=2, 1, -1);
    RETURN;
END_IF;
IF board[2] <> 0 AND board[2] = board[4] AND board[2] = board[6] THEN
    CheckGameResult := IIF(board[2]=2, 1, -1);
    RETURN;
END_IF;

// 检查平局
FOR i := 0 TO 8 DO
    IF board[i] = 0 THEN
        CheckGameResult := 2; // 游戏未结束
        RETURN;
    END_IF;
END_FOR;

CheckGameResult := 0; // 平局
END_FUNCTION

关键注意事项 #

• 栈大小：井字棋游戏树因提前终止（胜负已分），实际节点远少于9!，栈数组设为100完全足够。
• 节点状态标记：「未展开」和「已处理」的区分是模拟递归回溯的核心，不能省略。
• 最优落子记录：父节点更新得分时同步记录子节点的落子位置，最终根节点的movePos就是电脑的最优决策。

内容的提问来源于stack exchange，提问作者WorldOfWheat