一千萬個為什麽

搜索

在沒有遞歸的情況下實現Minimax

我正在建造一個Tic Tac Toe解決機器人。為了練習,我使用minimax算法編寫了一個Tic Tac Toe遊戲,該算法非常有效。當我想將代碼移植到控制器時,我發現該控制器的C/C ++編譯器都不支持遞歸函數。因此,我需要幫助將此遞歸minimax函數轉換為使用叠代或內部堆棧的函數:

int miniMax (char board[BOARD_DIM][BOARD_DIM], _Bool minNode, int *xBest, int *yBest)
{
    int possibleMoves[NSQUARES][2];
    int nPossibleMoves = generateMoves(board, possibleMoves);
    char boardChild [BOARD_DIM][BOARD_DIM];
    int ind, x_ind, y_ind;
    int minScore, maxScore;
    if (gameOver(board))
        return evaluateState(board);
    else if (minNode)
    {
        minScore = +INFINITY;
        for (ind = 0 ; ind < nPossibleMoves; ind++) 
        {
            duplicateBoard(board, boardChild);
            x_ind = possibleMoves[ind][0];
            y_ind = possibleMoves[ind][1];
            updateboard(boardChild, x_ind, y_ind, cPlayer);
            int score = miniMax(boardChild,!minNode ,&x_ind ,&y_ind);
            if (minScore > score)
                minScore = score;
        }
        return minScore;
    }
    else if (!minNode)
    {
        maxScore = -INFINITY;
        for (ind = 0 ; ind < nPossibleMoves; ind++) 
        {
            duplicateBoard(board, boardChild);
            x_ind = possibleMoves[ind][0];
            y_ind = possibleMoves[ind][1];
            updateboard(boardChild, x_ind, y_ind, cComputer);
            int score = miniMax(boardChild,!minNode ,&x_ind ,&y_ind);
            if (maxScore < score)
            {
                maxScore = score;
                *xBest = x_ind;
                *yBest = y_ind;
            }
        }
        return maxScore;
    }

我完全迷失了如何做到這一點。 我感謝任何幫助:)

最佳答案

如果它是嵌入式的我會的

  • 以二進制編碼位置(位矩陣而不是2dim字節數組)
  • 編碼完整的解決方案圖,所以一切都只是查找(線性查找可以很好地處理這種復雜性)

enter image description here

轉載註明原文: 在沒有遞歸的情況下實現Minimax