1

注意：如果您认为这篇文章看起来没有足够的细节，例如代码、结果和其他内容，请发表评论；我将相应地编辑帖子。

注2：我自己手工编写了这个程序。

我有一个 negamax 实现，它的结果对我来说看起来很错误我已经尝试了很多调试它的方法，但我似乎仍然无法理解它的症结所在。

首先，这是 Tic Tac Toe 的 negamax 实现，它具有 3X3 板。

以下代码是完整的集合，以复制我在此算法中遇到的错误。如果我错过了什么，请在下面发表评论。

一个例子可以做这个主要的：

int main {

Board board;
board.startGameNage(0,0);


}

我希望游戏以平局结束，因为这是计算机（完美玩家）与计算机（完美玩家），但是，使用以下一组函数，我得到了如下所示的游戏结局：

当前最大移动是：0,0，当前分数是：-inf 当前最大移动是：0,2，当前分数是：3 当前最大移动是：0,1，当前分数是：-3 当前最大移动是：1 ,1, 当前分数是: 3 当前最大移动是: 2,0, 当前分数是: -3 当前最大移动是: 1,2, 当前分数是: 3 当前最大移动是: 2,1, 当前分数是: -3 当前最大移动为：1,0，当前分数为：3 当前最大移动为：1,0，当前分数为：-3

XXO
XOO
XX ---

“ - ”表示该单元格中没有任何动作，这看起来显然是错误的。

我首先实现了我的极小极大值，而这个负极大值在某种程度上基于我的极小极大值实现而发展，这可能是我看不到我的错误的原因。

我知道 minimax 从 2 名玩家的角度进行动作并评估分数也相同，而 negamax 从 2 名玩家的角度进行动作但仅从当前玩家的角度评估分数。

我想这是让我感到困惑的一点。我似乎看不出我的实现在这里出了什么问题。

我通过 main 中的以下函数开始我的游戏：

// in  main I will just give the following function a coordinate, e.g. (0,0)

void Board::startGameNega(const int & row, const int & col){

Move move(row, col);
int player = 1;
for (int depth = 0; depth < 9; depth++){
    applyMoveNega(move, player);
    Move current_move = move;
    move = negaMax(depth, player, move);
    player = -player;
    cout << "current Max move is: " << current_move.getRow()
        << " , "
        << current_move.getCol()
        << ", Current score is: "
        << current_move.getScore() << endl;
}
print(); // print the end of game board
}

这是board.hpp：

#define LENGTH 3
#define WIDTH 3
#define CROSS 1
#define NOUGHT -1


#include <iostream>
#include <vector>
#include <array>
#include <map> 
#include "Move.hpp"

using namespace std;

#pragma once

typedef vector<Move> Moves;

struct Board {

// constructors;
Board(int width, int length) :m_width(width), m_length(width){};
Board(){};

// destructor;
~Board(){};

// negamax;
Move negaMax(const int & depth, const int & player, const Move & initialMove);
void startGameNega(const int & row, const int & col);
void applyMoveNega(const Move & move, const int & player);
bool isWon(const int & player);
bool isGameComplete();
int evaluateGameStateNega(const int & depth, const int & player);

// share;
int getOpponent(const int & player);
void deleteMove(const Move & move);
void deleteMoves(const Move & initialMove);

// utilities;
static int defaultBoard[WIDTH][LENGTH];
int getWidth() const { return m_width; }
int getLength() const { return m_length; }
void setWidth(int width){ m_width = width; }
void setLength(int length){ m_length = length; }
void print();
int getCurrentPlayer();

private:

    int m_width;
    int m_length;
    enum isWin{ yes, no, draw };
    int result;
    int m_player;
};

此处列出的一些关键要素：

打印：

void Board::print(){
for (int i = 0; i < WIDTH; i++) {
    for (int j = 0; j < LENGTH; j++) {
        switch (defaultBoard[i][j]) {
        case CROSS:
            cout << "X";
            break;
        case NOUGHT:
            cout << "O";
            break;
        default:
            cout << "-";
            break;
        }
        cout << " ";
    }
    cout << endl;
}
}

生成动作：

Moves Board::generateMoves(const int &rowIndex, const int &colIndex){

Moves Moves;

if (defaultBoard){

    for (int i = 0; i < WIDTH; i++)
    {
        for (int j = 0; j < LENGTH; j++)
        {
            if (i == rowIndex && j == colIndex)
            {
                continue;
            }
            else if (defaultBoard[i][j] == 1 || defaultBoard[i][j] == 4)
            {
                continue;
            }
            else if (defaultBoard[i][j] == 0)
            {
                Move move(i, j);
                Moves.push_back(move);
            }

        }
    }

}

return Moves;

}

applyMovesNega：

void Board::applyMoveNega(const Move & move, const int & player){

if (player == 1){
    defaultBoard[move.getRow()][move.getCol()] = CROSS;
}
else if (player == -1)
{
    defaultBoard[move.getRow()][move.getCol()] = NOUGHT;
}
}

isGameComplete:

bool Board::isGameComplete(){

if (defaultBoard[0][0] == defaultBoard[0][1] && defaultBoard[0][1] == defaultBoard[0][2] && defaultBoard[0][0] != 0 ||
    defaultBoard[1][0] == defaultBoard[1][1] && defaultBoard[1][1] == defaultBoard[1][2] && defaultBoard[1][0] != 0 ||
    defaultBoard[2][0] == defaultBoard[2][1] && defaultBoard[2][1] == defaultBoard[2][2] && defaultBoard[2][0] != 0 ||
    defaultBoard[0][0] == defaultBoard[1][0] && defaultBoard[1][0] == defaultBoard[2][0] && defaultBoard[0][0] != 0 ||
    defaultBoard[0][1] == defaultBoard[1][1] && defaultBoard[1][1] == defaultBoard[2][1] && defaultBoard[0][1] != 0 ||
    defaultBoard[0][2] == defaultBoard[1][2] && defaultBoard[1][2] == defaultBoard[2][2] && defaultBoard[0][2] != 0 ||
    defaultBoard[0][0] == defaultBoard[1][1] && defaultBoard[1][1] == defaultBoard[2][2] && defaultBoard[0][0] != 0 ||
    defaultBoard[2][0] == defaultBoard[1][1] && defaultBoard[1][1] == defaultBoard[0][2] && defaultBoard[2][0] != 0){

    return true;
}

return false;

}

评估分数：

int Board::evaluateGameStateNega(const int & depth, const int & player){

int new_score;
isWon(player);

if (result == isWin::yes)
    new_score = 10 - depth;
else if (result == isWin::no)
    new_score = depth - 10;
else
    new_score = 0;

return new_score;
}

删除移动：

void Board::deleteMove(const Move & move){


defaultBoard[move.getRow()][move.getCol()] = 0;}

这是 move.hpp：

struct Move{

Move(){};
Move(const int & index) :m_rowIndex(index / 3),m_colIndex(index % 3){};
Move(const int & row, const int & col) :m_rowIndex(row), m_colIndex(col){};
Move(const int & row, const int & col, const int & score):m_rowIndex(row), m_colIndex(col), m_score(score){};

~Move(){};

//member functions;
int getRow() const { return m_rowIndex; };
int getCol() const { return m_colIndex; };
void setRow(const int & row){ m_rowIndex = row; };
void setCol(const int & col){ m_colIndex = col; };
void setScore(const int & score){ m_score = score; };
int getScore() const { return m_score; }

private:

    int m_rowIndex;
    int m_colIndex;
    int m_score;

    };

这是实际的 NegaMax 函数：

Move Board::negaMax(const int & depth, const int & curPlayer, const Move & initialMove){

int row = initialMove.getRow();
int col = initialMove.getCol();
int _depth = depth;
int _curplayer = curPlayer;
Moves moves = generateMoves(row, col);

Move bestMove;
Move proposedNextMove;

//change to isGameComplete as of 15/10;
if (_depth == 8 || isGameComplete())
{
    int score = evaluateGameStateNega(_depth, _curplayer);
    bestMove.setScore(score);
    bestMove.setRow(initialMove.getRow());
    bestMove.setCol(initialMove.getCol());
}
else{

    _depth += 1;
    int bestScore = -1000;

    for (auto move : moves){

        applyMoveNega(move, -_curplayer);
        proposedNextMove = negaMax(_depth, -_curplayer, move);
        int tScore = -proposedNextMove.getScore();
        proposedNextMove.setScore(tScore);

        if (proposedNextMove.getScore() > bestScore){
            bestScore = proposedNextMove.getScore();
            bestMove.setScore(bestScore);
            bestMove.setRow(move.getRow());
            bestMove.setCol(move.getCol());
        }

        deleteMove(move);
    }

}

    return bestMove;

}

我使用以下函数评估游戏状态：

bool Board::isWon(const int & player){


if (defaultBoard[0][0] == defaultBoard[0][1] && defaultBoard[0][1] == defaultBoard[0][2] && defaultBoard[0][0] == player ||
    defaultBoard[1][0] == defaultBoard[1][1] && defaultBoard[1][1] == defaultBoard[1][2] && defaultBoard[1][0] == player ||
    defaultBoard[2][0] == defaultBoard[2][1] && defaultBoard[2][1] == defaultBoard[2][2] && defaultBoard[2][0] == player ||
    defaultBoard[0][0] == defaultBoard[1][0] && defaultBoard[1][0] == defaultBoard[2][0] && defaultBoard[0][0] == player ||
    defaultBoard[0][1] == defaultBoard[1][1] && defaultBoard[1][1] == defaultBoard[2][1] && defaultBoard[0][1] == player ||
    defaultBoard[0][2] == defaultBoard[1][2] && defaultBoard[1][2] == defaultBoard[2][2] && defaultBoard[0][2] == player ||
    defaultBoard[0][0] == defaultBoard[1][1] && defaultBoard[1][1] == defaultBoard[2][2] && defaultBoard[0][0] == player ||
    defaultBoard[2][0] == defaultBoard[1][1] && defaultBoard[1][1] == defaultBoard[0][2] && defaultBoard[2][0] == player){

    result = isWin::yes;
    return true;
}
else if (defaultBoard[0][0] == defaultBoard[0][1] && defaultBoard[0][1] == defaultBoard[0][2] && defaultBoard[0][0] == -player ||
    defaultBoard[1][0] == defaultBoard[1][1] && defaultBoard[1][1] == defaultBoard[1][2] && defaultBoard[1][0] == -player ||
    defaultBoard[2][0] == defaultBoard[2][1] && defaultBoard[2][1] == defaultBoard[2][2] && defaultBoard[2][0] == -player ||
    defaultBoard[0][0] == defaultBoard[1][0] && defaultBoard[1][0] == defaultBoard[2][0] && defaultBoard[0][0] == -player ||
    defaultBoard[0][1] == defaultBoard[1][1] && defaultBoard[1][1] == defaultBoard[2][1] && defaultBoard[0][1] == -player ||
    defaultBoard[0][2] == defaultBoard[1][2] && defaultBoard[1][2] == defaultBoard[2][2] && defaultBoard[0][2] == -player ||
    defaultBoard[0][0] == defaultBoard[1][1] && defaultBoard[1][1] == defaultBoard[2][2] && defaultBoard[0][0] == -player ||
    defaultBoard[2][0] == defaultBoard[1][1] && defaultBoard[1][1] == defaultBoard[0][2] && defaultBoard[2][0] == -player)
{

    result = isWin::no;
    return true;

}

    result = isWin::draw;
    return false;
}
4

1 回答 1

0

感谢@PaulMckenzie 指出我的一些代码问题。

但它们与我在 Negamax 的核心逻辑上犯的错误无关。

我将一一列出，希望它也可以帮助其他想学习 Negamax 的人。如果我错过了什么只是评论，我会在之后编辑。

*

请记住将所有新字段初始化为一个值，不要将它们留给逻辑来决定初始值是什么。这有助于调试，这只是一个很好的代码实践。感谢@PaulMcKenzie

*

  • 问题 1：deleteMoveNega() && applyMoveNega()

他们所做的只是删除提议的移动/应用提议的移动；他们不会在轮到当前玩家时回馈/传球。因为该步被提议为当前玩家的对手的最佳步，所以一旦我们完成计算此提议的步（A）的分数并且我们想要测试下一个提议的步（B），我们将需要删除 A 并给出转回当前玩家。（或者，对于某些人来说，它更好地理解为以前的玩家。）当我们应用提议的移动时，同样适用。

因此应该是：

    void Board::deleteMoveNega(const Move & move){

    defaultBoard[move.getRow()][move.getCol()] = EMPTY;
    m_player = getOpponent(m_player); // give turn back to current player;
}

    void Board::applyMoveNega(const Move & move){

    defaultBoard[move.getRow()][move.getCol()] = m_player;
    m_player = getOpponent(m_player); // pass on the turn to current player;
}

这是我犯的最重要的错误，因为使用旧代码我只会建议移动并计算分数，因为无论谁开始游戏；因为我在startGameNage()中手动将玩家设置为对手，然后我将游戏作为对手提出动作并仅作为对手计算分数（而我真的应该切换上下文并处于两个玩家的位置） . 这发生在 negamax 函数的每次迭代中。这并没有强制执行以当前玩家身份思考的概念，因为当我应该以当前玩家身份玩时，我却以对手身份玩。

这在 negamax 中是根本错误的。

一旦我们解决了这个问题，我们就不需要手动设置startGameNage()因此：

player = -player;

应该被删除并且：

int player = 1;

将改为：

m_player = 1;

  • 问题 2：negaMax()

整理好deleteMove()和applyMove()之后，我们现在可以看看我们的 negamax 引擎了。

applyMoveNega(move, -_curplayer);
proposedNextMove = negaMax(_depth, -_curplayer, move);

首先，我不需要当前播放器参数。 我有可以使用的私人m_player 。

其次，更重要的是，使用旧的deleteMove()和applyMove()并在 startGameNega() 中手动设置转弯，这里对玩家 (-_curplayer) 的否定是非常错误的。

例如，我们为-_curplayer申请/采取行动；接下来发生的提议动作应该是针对对手，在我们的例子中，应该是_curplayer。我仍在传递-_curplayer，这将从一开始就为错误的玩家生成动作。

一个新的核心 negamax 就像：

    Move Board::negaMax(const int & depth, const Move & initialMove){

    int row = initialMove.getRow();
    int col = initialMove.getCol();
    int _depth = depth;

    Move bestMove;
    Move proposedNextMove;

    //change to isGameComplete as of 15/10;
    if (_depth == 8 || isGameComplete())
    {
        int score = evaluateGameStateNega(_depth);
        bestMove.setScore(score);
        bestMove.setRow(initialMove.getRow());
        bestMove.setCol(initialMove.getCol());
    }
    else{
        Moves moves = generateMoves(row, col);

        _depth += 1;
        int bestScore = -1000;

        for (auto move : moves){

            applyMoveNega(move);
            proposedNextMove = negaMax(_depth, move);
            int tScore = -proposedNextMove.getScore();
            proposedNextMove.setScore(tScore);

            if (proposedNextMove.getScore() > bestScore){
                bestScore = proposedNextMove.getScore();
                bestMove.setScore(bestScore);
                bestMove.setRow(move.getRow());
                bestMove.setCol(move.getCol());
            }

            deleteMoveNega(move);
        }
    }
    return bestMove;
}

  • 问题3：清理一下

是的，我不得不承认这段算法写得很糟糕，只是为了冲出我脑海中的逻辑，而且以后容易出错。随着我们的进步，我们都应该努力防止这种情况发生。然而，有时我们仍然需要先让逻辑开始:)

我将发布清理工作以使其正常工作，但并非所有使其完美的清理工作。乐于接受评论。

  1. isWon()

    bool Board::isWon(const int & currentPlayer){

    if (defaultBoard[0][0] == defaultBoard[0][1] && defaultBoard[0][1] == defaultBoard[0][2] && defaultBoard[0][0] == currentPlayer ||
    defaultBoard[1][0] == defaultBoard[1][1] && defaultBoard[1][1] == defaultBoard[1][2] && defaultBoard[1][0] == currentPlayer ||
    defaultBoard[2][0] == defaultBoard[2][1] && defaultBoard[2][1] == defaultBoard[2][2] && defaultBoard[2][0] == currentPlayer ||
    defaultBoard[0][0] == defaultBoard[1][0] && defaultBoard[1][0] == defaultBoard[2][0] && defaultBoard[0][0] == currentPlayer ||
    defaultBoard[0][1] == defaultBoard[1][1] && defaultBoard[1][1] == defaultBoard[2][1] && defaultBoard[0][1] == currentPlayer ||
    defaultBoard[0][2] == defaultBoard[1][2] && defaultBoard[1][2] == defaultBoard[2][2] && defaultBoard[0][2] == currentPlayer ||
    defaultBoard[0][0] == defaultBoard[1][1] && defaultBoard[1][1] == defaultBoard[2][2] && defaultBoard[0][0] == currentPlayer ||
    defaultBoard[2][0] == defaultBoard[1][1] && defaultBoard[1][1] == defaultBoard[0][2] && defaultBoard[2][0] == currentPlayer){

    return true;
}

return false;

    }

现在我意识到我不必检查两个玩家；那是错误的，我只会检查当前玩家；并且代码更清晰，只需一个 if 语句即可阅读。结果是完全没有必要的。删除它们。我只是把事情复杂化了。

  1. 评估GameStateNega()

随着isWon()的改变，我们也将相应地改变evaluateGameStateNega()的实现：

    int Board::evaluateGameStateNega(const int & depth){

    if (isWon(m_player))
        return 10 - depth;
    if (isWon(getOpponent(m_player)))
        return depth - 10;
    else
        return 0;
}

  1. 生成移动（）

以上更改足以使其与所有其他未触及的部分一起工作。因此，这一点是为了增加价值。

   Moves Board::generateMoves(const int &rowIndex, const int &colIndex){

Moves Moves;

if (defaultBoard){

    for (int i = 0; i < WIDTH; i++)
    {
        for (int j = 0; j < LENGTH; j++)
        {
           if (defaultBoard[i][j] == 0)
            {
                Move move(i, j);
                Moves.push_back(move);
            }

        }
    }

}

return Moves;

}

显然我写了多余的代码。我们不需要检查单元是否被占用；我们只需要为所有空单元格生成移动！

于 2016-05-14T00:13:00.440 回答