注意：如果您认为这篇文章对您没有足够的详细信息（例如，代码，结果和其他内容；我将相应地编辑帖子。
注意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
X X O
设
X X-
“-”表示该单元格中没有任何移动，这显然是错误的。
我首先实现了minimax，而这种negamax是基于我的minimax实现而发展的，这可能就是我看不到错误的原因。
我知道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;
}
}
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;
}
最佳答案
感谢@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（）中手动设置turn，这里对玩家（-_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语句即可读取。结果完全没有必要。删除它们。我只是通过使事情复杂化而使自己困惑。
EvaluationGameStateNega（）
在isWon（）中的更改之后，我们也将相应地更改valuateGameStateNega（）的实现：
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;
}
显然我写了多余的代码。我们不需要检查牢房是否被占用；我们只需要为所有空单元格生成移动！
关于c++ - Negamax C++实现产生错误结果，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36972029/