Реализация Negamax C++ дает неверный результат

Question

Реализация Negamax C++ дает неверный результат

ПРИМЕЧАНИЕ. Пожалуйста, прокомментируйте, если вы считаете, что в этом посте нет достаточных деталей, например, кодов, результатов и прочего; Я буду редактировать пост соответственно.

ПРИМЕЧАНИЕ 2: Я написал эту программу вручную.

У меня есть реализация Negamax, результат которой мне показался очень неправильным. Я перепробовал много способов отладки, но я все еще не могу понять суть этого.

Прежде всего, это реализация Negamax для Tic Tac Toe, которая имеет плату 3X3.

Следующие коды являются полным набором для того, чтобы повторить ошибку, которую я имел с этим алгоритмом. пожалуйста, прокомментируйте ниже, если я что-то пропустил.

Примером может быть следующее:

int main {

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


}

Я ожидал бы, что игра закончилась вничью, потому что это компьютер (идеальный игрок) против компьютера (идеальный игрок), однако, используя следующий набор функций, я получил окончание игры, как показано ниже:

текущий максимальный ход: 0,0, текущий счет: -инф текущий максимальный ход: 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
X X ---

" - " означает, что в этой камере не делается никаких шагов, которая выглядела явно неправильно.

Сначала я реализовал свой минимакс, и этот negamax развивался в зависимости от моей реализации минимакса, что может быть причиной того, что я не вижу свою ошибку.

Я понял, что минимакс делает ходы с точки зрения 2 игроков и оценивает одинаковые оценки, тогда как negamax делает ходы с точки зрения 2 игроков, но оценивает счет только с точки зрения текущего игрока.

Я думаю, это немного смутило меня. Я не могу видеть, как моя реализация пошла не так здесь.

Я запускаю свою игру с помощью следующей функции:

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

вот доска.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;
}
}

generateMoves:

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

deleteMove:

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

1

c++ negamax

Источник

user4436572 01 май '16 в 21:13

1 ответ

Другие вопросы по тегам c++ negamax

user4436572 14 май '16 в 00:13 2016-05-14 00:13 · Answer 1 · 2016-05-14 00:13

Спасибо @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: немного почистить

Да, я просто должен признать, что этот фрагмент алгоритма был ужасно написан только для того, чтобы вырвать логику из моей головы и только потом быть склонным к ошибкам. По мере нашего продвижения мы все должны быть достаточно усердными, чтобы предотвратить это. Однако иногда нам по-прежнему нужно начинать логику:)

Я буду публиковать уборки только для того, чтобы заставить это работать, но не для всех уборок, которые должны сделать его идеальным. рад принять комментарий.

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. результат был совершенно ненужным. удали их. Я просто запутывал себя, усложняя дела.

evaluateGameStateNega()

следуя изменению в isWon(), мы соответственно изменили бы и реализацию defineGameStateNega():

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

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

generateMoves ()

Вышеупомянутых изменений достаточно, чтобы заставить его работать со всеми остальными частями, не затронутыми. таким образом, это добавить ценность.

   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;

}

очевидно, я написал избыточные коды. нам не нужно проверять, была ли клетка занята или нет; нам просто нужно генерировать ходы для всех пустых ячеек!

Реализация Negamax C++ дает неверный результат

1 ответ

Проблема 1: deleteMoveNega() && applyMoveNega()

Проблема 2: negaMax ()

Проблема 3: немного почистить

isWon()

evaluateGameStateNega()

generateMoves ()