I've written a minimax algorithm with alpha beta pruning for the game Checkers, and now I'm trying to rewrite it using the negamax approach. I'm expecting the two to be equivalent, since negamax is just a technique to write the minimax. But for some reason my two algorithms behave differently. When I run them both on the same input, the negamax version seems to evaluate more states, so I think something must be wrong with the alpha beta pruning.
The code below shows both algorithms (minimax
and negamax
functions), and at the bottom the play
function from which I call them. The evaluate
function is the basic heuristic which I use to evaluate states in both algorithms.
Any help with spotting the error would be much appriciated.
#include "player.hpp"
#include <algorithm>
#include <limits>
#include <cstdlib>
namespace checkers
{
int evaluatedStates = 0;
int evaluate(const GameState &state)
{
// FIXME: Improve heuristics.
int redScore = 0;
int whiteScore = 0;
int piece = 0;
for (int i = 1; i <= 32; ++i)
{
piece = state.at(i);
if (piece & CELL_RED) {
++redScore;
if (piece & CELL_KING)
redScore += 2; // King bonus.
} else if (piece & CELL_WHITE) {
++whiteScore;
if (piece & CELL_KING)
whiteScore += 2; // King bonus.
}
}
return state.getNextPlayer() == CELL_RED ? whiteScore - redScore : redScore - whiteScore;
}
int minimax(const GameState &state, int depth, int a, int b, bool max)
{
if (depth == 0 || state.isEOG()) {
++evaluatedStates;
return evaluate(state);
}
std::vector<GameState> possibleMoves;
state.findPossibleMoves(possibleMoves);
if (max) {
for (const GameState &move : possibleMoves) {
a = std::max(a, minimax(move, depth - 1, a, b, false));
if (b <= a)
return b; // β cutoff.
}
return a;
} else {
for (const GameState &move : possibleMoves) {
b = std::min(b, minimax(move, depth - 1, a, b, true));
if (b <= a)
return a; // α cutoff.
}
return b;
}
}
int negamax(const GameState &state, int depth, int a, int b)
{
if (depth == 0 || state.isEOG()) {
++evaluatedStates;
return evaluate(state);
}
std::vector<GameState> possibleMoves;
state.findPossibleMoves(possibleMoves);
for (const GameState &move : possibleMoves) {
a = std::max(a, -negamax(move, depth - 1, -b, -a));
if (b <= a)
return b; // β cutoff.
}
return a;
}
GameState Player::play(const GameState &pState, const Deadline &pDue)
{
GameState bestMove(pState, Move());
std::vector<GameState> possibleMoves;
pState.findPossibleMoves(possibleMoves);
int a = -std::numeric_limits<int>::max();
int b = std::numeric_limits<int>::max();
for (const GameState &move : possibleMoves) {
int v = negamax(move, 10, a, b);
//int v = minimax(move, 10, a, b, false);
if (v > a) {
a = v;
bestMove = move;
}
}
std::cerr << "Evaluated states: " << evaluatedStates << std::endl;
return bestMove;
}
/*namespace checkers*/ }
Best Answer
Your
minimax()
andnegamax()
functions are correct. I assume thatstate.getNextPlayer()
returns the player who has to move next. That means that yourevaluate()
andnegamax()
functions return a score from the perspective of that player.However, the
minimax()
returns a score from the perspective ofmax
. So if you try uncommentingminimax()
in yourplay()
function, that would lead to a bugReplacing the call to
minimax()
with atrue
parameter should solve it: