Negamax implementation doesn't appear to work with tic-tac-toe
-
02-07-2021 - |
Question
I've implemented Negamax as it can be found on wikipedia, which includes alpha/beta pruning.
However, it seems to favor a losing move, which is an invalid result to my knowledge.
The game is Tic-Tac-Toe, I've abstracted most of the game play so it should be rather easy to spot an error within the algorithm.
#include <list>
#include <climits>
#include <iostream>
//#define DEBUG 1
using namespace std;
struct Move {
int row, col;
Move(int row, int col) : row(row), col(col) { }
Move(const Move& m) { row = m.row; col = m.col; }
};
struct Board {
char player;
char opponent;
char board[3][3];
Board() { }
void read(istream& stream) {
stream >> player;
opponent = player == 'X' ? 'O' : 'X';
for(int row = 0; row < 3; row++) {
for(int col = 0; col < 3; col++) {
char playa;
stream >> playa;
board[row][col] = playa == '_' ? 0 : playa == player ? 1 : -1;
}
}
}
void print(ostream& stream) {
for(int row = 0; row < 3; row++) {
for(int col = 0; col < 3; col++) {
switch(board[row][col]) {
case -1:
stream << opponent;
break;
case 0:
stream << '_';
break;
case 1:
stream << player;
break;
}
}
stream << endl;
}
}
void do_move(const Move& move, int player) {
board[move.row][move.col] = player;
}
void undo_move(const Move& move) {
board[move.row][move.col] = 0;
}
bool isWon() {
if (board[0][0] != 0) {
if (board[0][0] == board[0][1] &&
board[0][1] == board[0][2])
return true;
if (board[0][0] == board[1][0] &&
board[1][0] == board[2][0])
return true;
}
if (board[2][2] != 0) {
if (board[2][0] == board[2][1] &&
board[2][1] == board[2][2])
return true;
if (board[0][2] == board[1][2] &&
board[1][2] == board[2][2])
return true;
}
if (board[1][1] != 0) {
if (board[0][1] == board[1][1] &&
board[1][1] == board[2][1])
return true;
if (board[1][0] == board[1][1] &&
board[1][1] == board[1][2])
return true;
if (board[0][0] == board[1][1] &&
board[1][1] == board[2][2])
return true;
if (board[0][2] == board [1][1] &&
board[1][1] == board[2][0])
return true;
}
return false;
}
list<Move> getMoves() {
list<Move> moveList;
for(int row = 0; row < 3; row++)
for(int col = 0; col < 3; col++)
if (board[row][col] == 0)
moveList.push_back(Move(row, col));
return moveList;
}
};
ostream& operator<< (ostream& stream, Board& board) {
board.print(stream);
return stream;
}
istream& operator>> (istream& stream, Board& board) {
board.read(stream);
return stream;
}
int evaluate(Board& board) {
int score = board.isWon() ? 100 : 0;
for(int row = 0; row < 3; row++)
for(int col = 0; col < 3; col++)
if (board.board[row][col] == 0)
score += 1;
return score;
}
int negamax(Board& board, int depth, int player, int alpha, int beta) {
if (board.isWon() || depth <= 0) {
#if DEBUG > 1
cout << "Found winner board at depth " << depth << endl;
cout << board << endl;
#endif
return player * evaluate(board);
}
list<Move> allMoves = board.getMoves();
if (allMoves.size() == 0)
return player * evaluate(board);
for(list<Move>::iterator it = allMoves.begin(); it != allMoves.end(); it++) {
board.do_move(*it, -player);
int val = -negamax(board, depth - 1, -player, -beta, -alpha);
board.undo_move(*it);
if (val >= beta)
return val;
if (val > alpha)
alpha = val;
}
return alpha;
}
void nextMove(Board& board) {
list<Move> allMoves = board.getMoves();
Move* bestMove = NULL;
int bestScore = INT_MIN;
for(list<Move>::iterator it = allMoves.begin(); it != allMoves.end(); it++) {
board.do_move(*it, 1);
int score = -negamax(board, 100, 1, INT_MIN + 1, INT_MAX);
board.undo_move(*it);
#if DEBUG
cout << it->row << ' ' << it->col << " = " << score << endl;
#endif
if (score > bestScore) {
bestMove = &*it;
bestScore = score;
}
}
if (!bestMove)
return;
cout << bestMove->row << ' ' << bestMove->col << endl;
#if DEBUG
board.do_move(*bestMove, 1);
cout << board;
#endif
}
int main() {
Board board;
cin >> board;
#if DEBUG
cout << "Starting board:" << endl;
cout << board;
#endif
nextMove(board);
return 0;
}
Giving this input:
O
X__
___
___
The algorithm chooses to place a piece at 0, 1, causing a guaranteed loss, do to this trap(nothing can be done to win or end in a draw):
XO_
X__
___
I'm pretty sure the game implementation is correct, but the algorithm should be aswell.
EDIT: Updated evaluate
and nextMove
.
EDIT2: Fixed first problem, there still seem to be bugs though
Solution
Your evaluate
function counts the empty spaces, and does not recognize a winning board.
EDIT:
There's also a relatively minor problem in nextMove
. The line should be
int score = -negamax(board, 0, -1, INT_MIN + 1, INT_MAX);
Fix that (and evaluate
), and the code chooses the right move.
EDIT:
This fixes it:
if (board.isWon() || depth <= 0) {
#if DEBUG > 1
cout << "Found winner board at depth " << depth << endl;
cout << board << endl;
#endif
return -100;
}
Almost all of these problems stem from not being clear about the meaning of score
. It is from the point of view of player
. If negamax
is evaluating the position of player 1, and player 1 cannot win, the score should be low (e.g. -100); if negamax
is evaluating the position of player -1, and player -1 cannot win, the score should be low (e.g. -100). If evaluate()
can't distinguish the players, then returning a score of player * evaluate(board)
is just wrong.
OTHER TIPS
isWon
returns true for both a win or a loss of the player. That can't be helping.
There seems to be something funny with the use of player.
Your toplevel loop calls "board.do_move(*it, 1);" then calls negamax with player=1.
Then negamax will call "board.do_move(*it, player);", so it looks like the first player is effectively getting 2 moves.