Negamax framework

[tetra]

I understand how the negamax works. It takes the equivalente that max{min{x1, x2, ...}, min{y1, y2...}} = max{ -max, -max}

But I'm not getting the right results when combining the negamax alpha-beta with the evaluation function. Can someone explain me what changes I have to do in the evaluation function instead of just returning the actual score?

[hyatt]

I understand how the negamax works. It takes the equivalente that max{min{x1, x2, ...}, min{y1, y2...}} = max{ -max, -max}

But I'm not getting the right results when combining the negamax alpha-beta with the evaluation function. Can someone explain me what changes I have to do in the evaluation function instead of just returning the actual score?

Your evaluation has to return a score based on the point of view of the side to move when you call it from Quiesce(). Otherwise the sign will be wrong and you will see nonsensical PVs...

[User923005]

Code: Select all

//The score is negated if black.  Here is the algorithm for pure negamax (no alpha-beta) but the score method is identical for when alpha-beta is used:
// WARNING, not compiled or tested.  But I think that the idea is plain enough and this simple format makes it obvious why it should work.
#define WHITE 1
#define BLACK -1
int negamax(node, depth, side)
{
    NODE movelist[MAX_MOVES]; // 218 should always work for MAX_MOVES in chess.
    if (depth == 0) 
    {
        int score = eval(node); // This is a leaf node.  Calculate the score from white's perspective.
        return side * score; // assumes WHITE == 1, black == -1.  Else use if (side==white ? 1 : -1).  This is what you are looking for.
        }
    int bestValue = -32767; // worst case scenario, I am in CHECKMATE.  A real search can do better than this.
    int count = gen_nodes(node, movelist); // generate every legal child position for this node.  There are 'count' of them.
    for (i = 0; i < count; i++)
    {
        node cnode = movelist[i]; // collect the current child node
        int val = -negamax(cnode, depth - 1, -side);
        bestValue = max( bestValue, val )
    }
    return bestValue;
}

[tetra]

I am doing that. I'm returning the score on the point of view of the side to move but still get wrong evaluations.

Code: Select all

int negamax(Chessboard *b, uint8_t depth, int c){
	if(!depth)
		return c * eval(b);
	
	int value, best = -INF;
	Move moves[MAX_MOVES];
	Move *it = moves, *end = gen_moves(b, moves, false, false);
	
	for(; it != end; it++){
		make_move(b, *it);
		value = -negamax(b, depth-1, -c);
		undo_move(b, *it);
		
		best = max(best, value);
	}
	return best;
}

The negamax is called in this function:

Code: Select all

int deepit(Chessboard *b, int max_depth){
	struct timespec begin, end;
	long double time;
	int d, g;

   int c = b->turn ? 1 : -1;
	clock_gettime(CLOCK_REALTIME, &begin);

	for(d = 1; d < max_depth; d++){
		g = negamax(b, d, c);

		clock_gettime(CLOCK_REALTIME, &end);
		time = ( end.tv_sec  - begin.tv_sec ) 
			  + ((end.tv_nsec - begin.tv_nsec) 
			  / 1000000000.0L);
		
		printf("depth %02d = %.2f in %.09Lfs\n", d, (double)f / 100, time);
	}
	return g;
}

And the evaluation function, pretty simple, just evaluating the material for readability of the score:

Code: Select all

int eval(Chessboard *b){
	int score = 0;
	
	score += material(b, !b->turn) - material(b, b->turn); // !b->turn - b->turn because make_move changes side to move right?
	// material function return positive score;
	
	return score; 
}

With less material for white, for example a bishop, I get this:

depth 01 = -3.05 in 0.000023996s // Correct
depth 02 = 3.05 in 0.000078731s // Wrong..
depth 03 = -3.05 in 0.000784126s
depth 04 = 3.05 in 0.016390447s

Can you spot the error in the code?
The code is clean I think so it's easy to read.

[User923005]

Did you notice this:
int score = eval(node); // This is a leaf node. Calculate the score from white's perspective.
Compare that to what you are doing.

Now, it is fine to calculate for the side to move's perspective. In fact, that is what most programs really do. But if you do that, you won't need to negate the score, now will you?


See, it was simple like you thought.

[tetra]

Did you notice this:
int score = eval(node); // This is a leaf node. Calculate the score from white's perspective.
Compare that to what you are doing.

Now, it is fine to calculate for the side to move's perspective. In fact, that is what most programs really do. But if you do that, you won't need to negate the score, now will you?


See, it was simple like you thought.

But I'm doing that!! Check negamax function:

Code: Select all

if(!depth)
		return c * eval(b);

Even tho I return the score for the side to move perspective I get wrong score.

But are you really trying to explain with "you won't need to negate the score, now will you"?
Are you trying to say that if I return the score in the perspective of the player the negamax call inside the for loop that make and unmakes the moves don't need to be negated? I don't agree with that.

[User923005]

Your evaluation takes into account the person whose turn it is.
Hence, a score of +300 for white will be -300 for black.

int eval(Chessboard *b){
int score = 0;

score += material(b, !b->turn) - material(b, b->turn); // !b->turn - b->turn because make_move changes side to move right?
// material function return positive score;

return score;
}

[tetra]

Your evaluation takes into account the person whose turn it is.
Hence, a score of +300 for white will be -300 for black.

int eval(Chessboard *b){
int score = 0;

score += material(b, !b->turn) - material(b, b->turn); // !b->turn - b->turn because make_move changes side to move right?
// material function return positive score;

return score;
}

So the trick is calculate who's the maximizer and the minimizer in the beginning of the iterative deepening right? Like this:

Code: Select all

int deepit(Chessboard *b, int max_depth){
	int d, g;

	maximizer = b->turn;
	minimizer = !b->turn;

	int c = b->turn ? 1 : -1;

	for(d = 1; d < max_depth; d++){
		g = negamax(b, d, c);
	}

	return g;
}

And then in the evaluation function I calculate the score in the form of maximizer minus minimizer right?

Code: Select all

int eval(Chessboard *b){
	int score = 0;
	
	score += material(b, maximizer) - material(b, minimizer);
	
	return score;
}

Tell me if this is correct.

[User923005]

There is nothing wrong with that approach. In fact, it is what almost everyone does.
However, if your evaluation function takes into account whose turn it is to play when deciding on the evaluation score, then you don't need to negate it.
In fact, the only reason that the score gets negated in the "classical" version is that the evaluation is from the standpoint of white in that version.

Just think of it this way:
"Why does the classical version negate the score?"

Once you clearly understand why they do that, then you will understand why you do not need to do it.