2

三目並べ解決ロボットを作っています。練習用に、非常にうまく機能するミニマックス アルゴリズムを使用して Tic Tac Toe ゲームを作成しました。コードをコントローラーに移植したいと思ったとき、このコントローラー用の C/C++ コンパイラーのどれも再帰関数をサポートしていないことがわかりました。したがって、この再帰的なミニマックス関数を反復または内部スタックを使用する関数に変換する助けが必要です:

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;
    }

私はこれを行う方法について完全に迷っています。助けていただければ幸いです:)

4

1 に答える 1

7

組み込み用の場合は

  • 位置をバイナリでエンコードします（2dimバイト配列の代わりにビット行列）
  • 完全なソリューションマップをエンコードするため、すべてがルックアップのみになります（線形ルックアップはこの複雑さに対して問題なく機能します）

ここに画像の説明を入力してください

于 2011-11-14T07:36:46.800 に答える