注: この投稿にコード、結果、その他の情報が不足していると思われる場合は、コメントしてください。それに応じて投稿を編集します。
注 2: このプログラムは自分で手で書きました。
私はnegamaxの実装を持っていますが、その結果は私には非常に間違っているように見えました。デバッグする多くの方法を試しましたが、まだ核心をつかむことができないようです.
まず、これは 3X3 のボードを持つ Tic Tac Toe のネガマックス実装です。
次のコードは、このアルゴリズムで発生したエラーを再現するための完全なセットです。何か見逃した場合は、以下にコメントしてください。
例では、このメインを実行できます。
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 ---
「 - 」は、そのセルで移動が行われないことを意味しますが、これは明らかに間違っているように見えます。
最初にミニマックスを実装しましたが、このネガマックスはミニマックスの実装に基づいて進化していたため、エラーが表示されない可能性があります。
ミニマックスは 2 人のプレイヤーの視点から動き、スコアも同様に評価するのに対し、ネガマックスは 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
}
これが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;
}