3

アルファ/ベータ法を含むウィキペディアにあるように、私はNegamaxを実装しました。

しかし、それは負けた動きを支持しているようであり、それは私の知る限り無効な結果です。

ゲームはTic-Tac-Toeです。ゲームプレイのほとんどを抽象化したので、アルゴリズム内のエラーを見つけるのはかなり簡単です。

#include <list>
#include <climits>
#include <iostream>

//#define DEBUG 1

using namespace std;

struct Move {
    int row, col;

    Move(int row, int col) : row(row), col(col) { }
    Move(const Move& m) { row = m.row; col = m.col; }
};

struct Board {
    char player;
    char opponent;
    char board[3][3];

    Board() { }

    void read(istream& stream) {
        stream >> player;
        opponent = player == 'X' ? 'O' : 'X';

        for(int row = 0; row < 3; row++) {
            for(int col = 0; col < 3; col++) {
                char playa;

                stream >> playa;
                board[row][col] = playa == '_' ? 0 : playa == player ? 1 : -1;
            }
        }
    }

    void print(ostream& stream) {
        for(int row = 0; row < 3; row++) {
            for(int col = 0; col < 3; col++) {
                switch(board[row][col]) {
                    case -1:
                        stream << opponent;
                        break;

                    case 0:
                        stream << '_';
                        break;

                    case 1:
                        stream << player;
                        break;

                }
            }
            stream << endl;
        }
    }

    void do_move(const Move& move, int player) {
        board[move.row][move.col] = player;
    }

    void undo_move(const Move& move) {
        board[move.row][move.col] = 0;
    }

    bool isWon() {
        if (board[0][0] != 0) {
            if (board[0][0] == board[0][1] &&
                    board[0][1] == board[0][2])
                return true;

            if (board[0][0] == board[1][0] &&
                    board[1][0] == board[2][0])
                return true;
        }

        if (board[2][2] != 0) {
            if (board[2][0] == board[2][1] &&
                    board[2][1] == board[2][2])
                return true;

            if (board[0][2] == board[1][2] &&
                    board[1][2] == board[2][2])
                return true;
        }

        if (board[1][1] != 0) {
            if (board[0][1] == board[1][1] &&
                    board[1][1] == board[2][1])
                return true;

            if (board[1][0] == board[1][1] &&
                    board[1][1] == board[1][2])
                return true;

            if (board[0][0] == board[1][1] &&
                    board[1][1] == board[2][2])
                return true;

            if (board[0][2] == board [1][1] &&
                    board[1][1] == board[2][0])
                return true;
        }

        return false;
    }

    list<Move> getMoves() {
        list<Move> moveList;

        for(int row = 0; row < 3; row++)
            for(int col = 0; col < 3; col++)
                if (board[row][col] == 0)
                    moveList.push_back(Move(row, col));

        return moveList;
    }
};

ostream& operator<< (ostream& stream, Board& board) {
    board.print(stream);
    return stream;
}

istream& operator>> (istream& stream, Board& board) {
    board.read(stream);
    return stream;
}

int evaluate(Board& board) {
    int score = board.isWon() ? 100 : 0;

    for(int row = 0; row < 3; row++)
        for(int col = 0; col < 3; col++)
            if (board.board[row][col] == 0)
                score += 1;

    return score;
}

int negamax(Board& board, int depth, int player, int alpha, int beta) {
    if (board.isWon() || depth <= 0) {
#if DEBUG > 1
        cout << "Found winner board at depth " << depth << endl;
        cout << board << endl;
#endif
        return player * evaluate(board);
    }

    list<Move> allMoves = board.getMoves();

    if (allMoves.size() == 0)
        return player * evaluate(board);

    for(list<Move>::iterator it = allMoves.begin(); it != allMoves.end(); it++) {
        board.do_move(*it, -player);
        int val = -negamax(board, depth - 1, -player, -beta, -alpha);
        board.undo_move(*it);

        if (val >= beta)
            return val;

        if (val > alpha)
            alpha = val;
    }

    return alpha;
}

void nextMove(Board& board) {
    list<Move> allMoves = board.getMoves();
    Move* bestMove = NULL;
    int bestScore = INT_MIN;

    for(list<Move>::iterator it = allMoves.begin(); it != allMoves.end(); it++) {
        board.do_move(*it, 1);
        int score = -negamax(board, 100, 1, INT_MIN + 1, INT_MAX);
        board.undo_move(*it);

#if DEBUG
        cout << it->row << ' ' << it->col << " = " << score << endl;
#endif

        if (score > bestScore) {
            bestMove = &*it;
            bestScore = score;
        }
    }

    if (!bestMove)
        return;

    cout << bestMove->row << ' ' << bestMove->col << endl;

#if DEBUG
    board.do_move(*bestMove, 1);
    cout << board;
#endif

}

int main() {
    Board board;

    cin >> board;
#if DEBUG
    cout << "Starting board:" << endl;
    cout << board;
#endif

    nextMove(board);
    return 0;
}

この入力を与える：

O
X__
___
___

アルゴリズムは、ピースを0、1に配置することを選択し、保証された損失を引き起こし、このトラップを実行します（勝つか引き分けで終了することはできません）。

XO_
X__
___

ゲームの実装は正しいと確信していますが、アルゴリズムも正しいはずです。

編集：更新されevaluate、nextMove。

EDIT2：最初の問題を修正しましたが、まだバグがあるようです

4

3 に答える 3

1

evaluate関数は空のスペースをカウントし、勝者のボードを認識しません。

編集：
には比較的小さな問題もありnextMoveます。行はする必要があります

int score = -negamax(board, 0, -1, INT_MIN + 1, INT_MAX);

それ（および）を修正するevaluateと、コードは正しい動きを選択します。

編集：

これはそれを修正します：

if (board.isWon() || depth <= 0) {
#if DEBUG > 1
  cout << "Found winner board at depth " << depth << endl;
  cout << board << endl;
#endif
  return -100;                                                      
}

これらの問題のほとんどすべては、の意味が明確でないことに起因しscoreます。の観点からですplayer。negamaxがプレーヤー1の位置を評価していて、プレーヤー1が勝てない場合、スコアは低くする必要があります（例：-100）。がnegamaxプレーヤー-1の位置を評価していて、プレーヤー-1が勝てない場合、スコアは低くする必要があります（例：-100）。プレーヤーを区別できない場合evaluate()は、のスコアを返すのplayer * evaluate(board)は間違っています。

于 2012-09-14T17:52:36.940 に答える
0

isWonプレーヤーの勝ち負けの両方に対してtrueを返します。それは役に立たない。

于 2012-09-14T17:52:43.603 に答える
0

プレイヤーの使い方には何かおかしなことがあるようです。

トップレベルのループは「board.do_move（* it、1）;」を呼び出します。次に、player=1でnegamaxを呼び出します。

次に、negamaxは「board.do_move（* it、player）;」を呼び出すので、最初のプレーヤーは事実上2つの動きを取得しているように見えます。

于 2012-09-14T18:31:21.043 に答える