c++ - C++ Minmax の失敗

Question

私はこれに長い間取り組んできたので、もう面白くありません。私は Tic Tac Toe に Minmax を実装しようとしています。適切な最初の動きをする AI のいくつかのバージョンを入手しましたが、絶対に負けない AI を作ることはできません。

私が解決できない問題の 1 つは、ヒューリスティック値です。現在、最初の Minmax 呼び出しで -10 を返していますが、0 を返す必要があります (何が起こっても描画できるはずです)。

もう 1 つの問題は、400,000 回の反復を実行することですが、322,000 が最大であり、初期の勝利状況を考えると、約 250,000 で停止することさえあります。

どんな助けでも無限に感謝します。

int MiniMax(TGameBoard _GameBoard)
{
    //Always goes for max of course, just expanded in case you wanted two AIs

    int iBestMove;      
    int iHeuristicReturned = 0;

    if (_GameBoard.ePlayer == COMPUTER)
    {
        iHeuristicReturned = MaxMove(_GameBoard, iBestMove);
    }
    else
    {
        iHeuristicReturned = MinMove(_GameBoard, iBestMove);
    }
    //cout<<"\nHeuristic is "<<iHeuristicReturned<<endl;

    g_iHeuristic = iHeuristicReturned;
    return iBestMove;
}

int MaxMove(TGameBoard _GameBoard, int& _iMove)
{
    //Logic
    //If its an end node, calculate the score
    //Otherwise, do minmax until the end node, and pass back the value
    //If returned value is greater than v, then pass the move back upwards
    ++g_iIterations;
    if(_GameBoard.CheckWinner(_GameBoard) || _GameBoard.IsFull())
    {
        int x;
        x = EvaluateStaticPosition(_GameBoard, MAX);
        return EvaluateStaticPosition(_GameBoard, MAX);
    }
    vector<int> moveList;
    GenerateMoveList(_GameBoard, moveList);
    int iNumMoves = moveList.size();
    int v = -10000;

    for(int i = 0; i < iNumMoves; ++i)
    {
        int iMove = moveList[i];

        _GameBoard.Set(iMove, CROSS);
        int opponentsBestMove;
        ++g_iDepth;
        int curRating = MinMove(_GameBoard, opponentsBestMove);
        --g_iDepth;
        if (curRating > v)
        {
            v = curRating;
            _iMove = iMove;
        }
        RetractMove(&_GameBoard, iMove);
    }
    return v;
}

int MinMove(TGameBoard _GameBoard, int& _iMove)
{
    ++g_iIterations;
    if (g_iIterations > 320000)
    {
        int x = 0;
    }

    if(_GameBoard.CheckWinner(_GameBoard) || _GameBoard.IsFull())
    {
        return EvaluateStaticPosition(_GameBoard, MIN);
    }

    vector<int> moveList;
    GenerateMoveList(_GameBoard, moveList);
    int iNumMoves = moveList.size();
    int v = 10000;

    for(int i = 0; i < iNumMoves; ++i)
    {
        int iMove = moveList[i];
        _GameBoard.Set(iMove, NAUGHT);
        int opponentsBestMove;
        ++g_iDepth;
        int curRating = MaxMove(_GameBoard, opponentsBestMove);
        --g_iDepth;
        if (curRating < v)
        {
            v = curRating;
            _iMove = iMove;
        }
        RetractMove(&_GameBoard, iMove);
    }
    return v;
}

int EvaluateStaticPosition(TGameBoard _GameBoard, EGoal _eGoal)
{
    if(_GameBoard.CheckWinner(_GameBoard, COMPUTER))
    {
        return 10;
    } 
    if(_GameBoard.CheckWinner(_GameBoard, PLAYER))
    {
        return -10;
    } 
    return 0;
}

他の関連する機能はここで確認できますが、大丈夫だと確信しています。 http://pastebin.com/eyaNfBsq

はい、不要なパラメーターがいくつかあることは承知しています。自分のバージョンに失敗した後、インターネットのチュートリアルに従ってみました。残念ながら、彼らは同じ結果を出しています。

私はこれを12時間続けていますが、とても簡単な作業のようで、何が問題なのかわかりません

score 1 · Accepted Answer

次のコードが役立つ場合があります。

(おまけ: 調べたボードが 8000 未満の alphabeta。)

#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>

enum class Square
{
    Empty,
    O,
    X
};

Square other(Square c) {
    switch (c) {
        case Square::O: return Square::X;
        case Square::X: return Square::O;
        default: assert(0); return Square::Empty;
    };
}

template <typename STREAM>
STREAM& operator << (STREAM& stream, Square c)
{
    switch (c)
    {
        case Square::Empty: stream << "."; break;
        case Square::X: stream << "X"; break;
        case Square::O: stream << "O"; break;
    }
    return stream;
}

class Board
{
public:
    Board() : board({{Square::Empty, Square::Empty, Square::Empty,
                    Square::Empty, Square::Empty, Square::Empty,
                    Square::Empty, Square::Empty, Square::Empty}})
    {}

    void display() const {
        for (int y = 0; y != 3; ++y) {
            for (int x = 0; x != 3; ++x) {
                std::cout << board[3 * y + x] << " ";
            }
            std::cout << std::endl;
        }
    }

    void play(unsigned int x, unsigned int y, Square c)
    {
        assert(x < 3);
        assert(y < 3);

        board[3 * y + x] = c;
    }
    void play(unsigned int offset, Square c)
    {
        assert(offset < 9);

        board[offset] = c;
    }

    bool isFull() const {
        return std::find(board.cbegin(), board.cend(), Square::Empty) == board.cend();
    }

    int computeScore(Square c) const
    {
        for (int i = 0; i < 3; ++i) {
            if (board[3 * i] != Square::Empty && board[3 * i] == board[3 * i + 1] && board[3 * i] == board[3 * i + 2]) {
                return board[3 * i] == c ? 1 : -1;
            }
            if (board[i] != Square::Empty && board[i] == board[i + 3] && board[i] == board[i + 6]) {
                return board[i] == c ? 1 : -1;
            }
        }
        if (board[4] == Square::Empty) {
            return 0;
        }
        if ((board[4] == board[0] && board[4] == board[8])
            || (board[4] == board[2] && board[4] == board[6])) {
            return board[4] == c ? 1 : -1;
        }
        return 0;
    }

    int minmax(Square c, unsigned int* counter, unsigned int* pos = NULL)
    {
        const int currentScore = computeScore(c);
        if (currentScore != 0 || isFull()) {
            if (counter) {++*counter; }
            return currentScore;
        }
        int bestScore = -10;

        for (unsigned int i = 0; i != 9; ++i) {
            if (board[i] != Square::Empty) { continue; }

            play(i, c);
            int score = -minmax(other(c), counter);
            if (bestScore < score) {
                bestScore = score;
                if (pos) { *pos = i; }
            }
            play(i, Square::Empty);
        }
        return bestScore;
    }

    int alphabeta(Square c, int alpha, int beta, unsigned int* counter, unsigned int* pos = NULL)
    {
        const int currentScore = computeScore(c);
        if (currentScore != 0 || isFull()) {
            if (counter) {++*counter; }
            return currentScore;
        }

        for (unsigned int i = 0; i != 9; ++i) {
            if (board[i] != Square::Empty) { continue; }

            play(i, c);
            int score = -alphabeta(other(c), -beta, -alpha, counter);
            if (beta <= score) {
                if (pos) { *pos = i; }
                play(i, Square::Empty);
                return score;
            }
            if (alpha < score) {
                alpha = score;
                if (pos) { *pos = i; }
            }
            play(i, Square::Empty);
        }
        return alpha;
    }

private:
    std::array<Square, 9> board;
};

int main()
{
    Board b;
    Square c = Square::X;

    while (b.computeScore(Square::X) == 0 && b.isFull() == false) {
        std::cout << c << " to play" << std::endl;
        b.display();
        unsigned int counter = 0;
        unsigned int pos;
        const int s = b.minmax(c, &counter, &pos);
        //const int s = b.alphabeta(c, -10, 10, &counter, &pos);
        b.play(pos, c);
        std::cout << "score for "<< c <<" = " << s << std::endl;
        std::cout << "#final boards examined = " << counter << std::endl;
        std::cout << "----------------" << std::endl;
        c = other(c);
    }
    std::cout << "Final score for X = " << b.computeScore(Square::X) << std::endl;
    b.display();

    return 0;
}

「繰り返し」の回数は、検査された最終的なボードの数です。

c++ - C++ Minmax の失敗

1 に答える 1

Related

Reference