Реализация 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

X X O
X O O
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

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

спасибо @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 () мы бы соответственно изменили реализацию 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;
}

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;

}

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

0

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

Решение

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

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

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

isWon ()

evaluateGameStateNega ()

generateMoves ()

Другие решения