concerns on negamax material implementation

[Fguy64]

Thanks Andy, but lets put aside the meaning of the word negamax, which I probably have wrong anyways, and make sure we are on the same page with what I have actually done, based on the description I gave.

First of all, all calculation stops with white's 3rd move, there is no 5 ply from 1.h4 there is 5 ply from the starting position.

there is no "suggestion" of 1...b5 involved, I am not actually acting on these evaluations yet, just calculating the evals. No pruning at all is being done. yet.

All I am doing is feeding the engine a position and asking for a move. then full stop no more computing is done.

Being on the same page is a good idea. Here's what I would do. Set it to one ply - e.g. just the direct moves in response to the position. From the starting point - or almost all those posted - the evaluation should be 0. Anything else and it's a bug obviously.

Now do two ply. Same thing from the start position - everything should be random.

Then ply three ... here's where things get more interesting because there are three ply searches that can "gain" material (1. d4 h6 2. Bxh6) - at least when you stop at ply three. None of those should be chosen because the bishop capture refutes h6 and you want to make sure that's not taken. In fact it should be a long time before the score changes from 0.

Andy.

Ok thanks, that makes things a little clearer. I'm pretty sure you are a little further along than I was. I hadn't actually progressed to the point where I was making a choice based on the evaluations that were filtering back through the tree. I was just trying to make sure that the evals were correct

In your example I agree with your h6 eval, and my algorithm would do the same. And when I actually implemented decision making, it wouldn't be chosen either, or rather, white's choice would be based on the assumption that Black wouldn't play h6.

[bob]

Greetings.

I am trying to implement a little minimax (negamax?) material evaluation into my engine, and I am not sure how to interpret the results. At this point I don't care if my strategy is good or bad, only that the results are to be expected given what I have done. There is as yet no alpha beta pruning, and no quiescense, which might be my problem. As you can no doubt tell, I'm kind of new at actually doing this stuff.

- Ok, I have a recursive algorithm that is currently set at 5 ply, but the actual number shouldn't matter.
- For each move at each ply, the engine generates a list of legal moves, this part is working fine.
- At the final ply (ply 1) we don't look for replies, just calculate the material balance. Material balance is only calculated at the final ply. The material calculation works fine.
- When the ply is an even number, a move eval is the maximum of all the reply evals. When the ply is an odd number, the move eval is the minimum eval of all the replies. Thus at the very first ply, the eval for each possible engine move is the minimum value of all the possible replies. The engine will then choose the move with the maximum eval.
- My material calc uses the following: P=10, N=25, B=30, R=50, Q=90.

As an example, consider the move 1.a4 The algorithm assigns the reply 1...b5 a value of 20 in white's favor. This surprises me somewhat, I would have expected that given a correct minimax implementation, the value would be 10 ( 1 pawn ) given correct subsequent play on a material basis.

Another example is every reply to 1.b3 evaluating to 10 in favor of white.


The question is whether this is all because of no quiescense, or some serious flaw in my logic that I can't see. If needed, I can post some code, it's in pretty good shape.

Thanks.

simple answer. when using negamax, scores for current side on move always have to be +=good for side to move, -=bad for side to move. So if it is white to move, you evaluate by summing white material and subtracting black material. If it is black to move you do the opposite.

Note that if you don't do a q-search and just do a pure type-A algorithm, the last move in a PV will almost always be a capture, since that side can capture with impunity since there is no opponent move beyond that point. Scores will always be oddly biased because of this.

[sje]

I've always thought that "negamax" is a misnomer of sorts. It really should be called "maxnega" as the value of a position is the maximum of the negated values of its immediate sub-positions.

----

In Symbolic, the literal values for the color constants "white" and "black" are never used unless truly needed. Instead, the side on the move is represented by the variable "good" which takes a value of white or black. The variable "evil" represents the side not on the move and will take the complement of good.

When a move is made (or unmade):

Code: Select all

const Color tmpcolor = good;  good = evil;  evil = tmpcolor;

[plattyaj]

Code: Select all

const Color tmpcolor = good;  good = evil;  evil = tmpcolor;

Very Orwellian!

Andy.

[bob]

I've always thought that "negamax" is a misnomer of sorts. It really should be called "maxnega" as the value of a position is the maximum of the negated values of its immediate sub-positions.

----

In Symbolic, the literal values for the color constants "white" and "black" are never used unless truly needed. Instead, the side on the move is represented by the variable "good" which takes a value of white or black. The variable "evil" represents the side not on the move and will take the complement of good.

When a move is made (or unmade):

Code: Select all

const Color tmpcolor = good;  good = evil;  evil = tmpcolor;

I think Ken coined the term "negamax" as his representation of recursive minimax eliminated the "min" completely and replaced it with the negate idea instead. IE you recursively call Search() for each move at a ply, negate the result (change the POV to current side) and then take the Max() of these negated values.

[Fguy64]

Greetings.

I am trying to implement a little minimax (negamax?) material evaluation into my engine, and I am not sure how to interpret the results. At this point I don't care if my strategy is good or bad, only that the results are to be expected given what I have done. There is as yet no alpha beta pruning, and no quiescense, which might be my problem. As you can no doubt tell, I'm kind of new at actually doing this stuff.

- Ok, I have a recursive algorithm that is currently set at 5 ply, but the actual number shouldn't matter.
- For each move at each ply, the engine generates a list of legal moves, this part is working fine.
- At the final ply (ply 1) we don't look for replies, just calculate the material balance. Material balance is only calculated at the final ply. The material calculation works fine.
- When the ply is an even number, a move eval is the maximum of all the reply evals. When the ply is an odd number, the move eval is the minimum eval of all the replies. Thus at the very first ply, the eval for each possible engine move is the minimum value of all the possible replies. The engine will then choose the move with the maximum eval.
- My material calc uses the following: P=10, N=25, B=30, R=50, Q=90.

As an example, consider the move 1.a4 The algorithm assigns the reply 1...b5 a value of 20 in white's favor. This surprises me somewhat, I would have expected that given a correct minimax implementation, the value would be 10 ( 1 pawn ) given correct subsequent play on a material basis.

Another example is every reply to 1.b3 evaluating to 10 in favor of white.


The question is whether this is all because of no quiescense, or some serious flaw in my logic that I can't see. If needed, I can post some code, it's in pretty good shape.

Thanks.

simple answer. when using negamax, scores for current side on move always have to be +=good for side to move, -=bad for side to move. So if it is white to move, you evaluate by summing white material and subtracting black material. If it is black to move you do the opposite.

Note that if you don't do a q-search and just do a pure type-A algorithm, the last move in a PV will almost always be a capture, since that side can capture with impunity since there is no opponent move beyond that point. Scores will always be oddly biased because of this.

Thanks, that is helpful. Here's another way of describing the situation which seems to be pretty much the flip side of the coin. Assume the engine is playing the white side and no quiescence. Then if your final material eval is on a position after a white move, then the engine will overvalue its bad moves, if it's after a black move then the engine will undervalue its good moves.

Funny things can happen with negamax and pruning without quiescence. I tried ending with an eval after a black move, and my engine seemed to be reluctant to move its pieces off the back rank, and even seemed to avoid opening up lines for them when possible, for fear of losing them I guess. That should encourage me, as it seems to suggest that my algorithm is correct so far, and once I can implement a proper quiescence, I should be in pretty good shape.

[Fguy64]

OK, it's a couple days later, and this stuff is making my head spin. I thought I'd write down my algorithm is pseudo code and post it here. It seems right to me, but I guess I'll see about that.

OK this represents an arbitrary ply n, negamax algorithm, pruning is not yet represented, I'll make sure I have this part correct. first.

Note that details about quiscense are buried in the material evaluation function.

how does it look so far? Thanks.

Code: Select all

makeMove() {
	ply = n;
	fen = arbitrary starting position and game state;

	list1 = possiblesMoves(fen);	// possibleMoves is non recursive.
	max = -10,000;					// initial value is lower than any possible eval

	for each move m in list1 {
		fen1 = position after m
		m.eval = evaluate(m, ply)
		if( m.eval > max ) max = m.eval
	}

	return random selection from moves where eval = max.
}

evaluate( fen1, ply ) {			// evaluate is recursive function.

	if( ply == 1) return material eval of fen1, including quiescence.
	
	max = -10,000;

	list2 = possibleMoves( fen1 );
	for each move m in list2 {
		fen2 = posn after m;
		m.eval = evaluate( fen2, ply-1 );		// recursion step.
		if( m.eval > max ) max = m.eval;
	}
	
	return -max;								// why we call it negamax ?
}

[diep]

Greetings.

I am trying to implement a little minimax (negamax?) material evaluation into my engine, and I am not sure how to interpret the results. At this point I don't care if my strategy is good or bad, only that the results are to be expected given what I have done. There is as yet no alpha beta pruning, and no quiescense, which might be my problem. As you can no doubt tell, I'm kind of new at actually doing this stuff.

- Ok, I have a recursive algorithm that is currently set at 5 ply, but the actual number shouldn't matter.
- For each move at each ply, the engine generates a list of legal moves, this part is working fine.
- At the final ply (ply 1) we don't look for replies, just calculate the material balance. Material balance is only calculated at the final ply. The material calculation works fine.
- When the ply is an even number, a move eval is the maximum of all the reply evals. When the ply is an odd number, the move eval is the minimum eval of all the replies. Thus at the very first ply, the eval for each possible engine move is the minimum value of all the possible replies. The engine will then choose the move with the maximum eval.
- My material calc uses the following: P=10, N=25, B=30, R=50, Q=90.

As an example, consider the move 1.a4 The algorithm assigns the reply 1...b5 a value of 20 in white's favor. This surprises me somewhat, I would have expected that given a correct minimax implementation, the value would be 10 ( 1 pawn ) given correct subsequent play on a material basis.

Another example is every reply to 1.b3 evaluating to 10 in favor of white.


The question is whether this is all because of no quiescense, or some serious flaw in my logic that I can't see. If needed, I can post some code, it's in pretty good shape.

Thanks.

Negamax = search
material considerations = evaluation

I see those as 2 different entities actually.

minimax material evaluation, what do you mean by that,
that the root of it should give a good static material evaluation?

Or do you mean you want to build a fast searcher with just material evaluation at first?

Whatever you do in that case, you can't escape using a qsearch.

[Fguy64]

Greetings.

I am trying to implement a little minimax (negamax?) material evaluation into my engine, and I am not sure how to interpret the results. At this point I don't care if my strategy is good or bad, only that the results are to be expected given what I have done. There is as yet no alpha beta pruning, and no quiescense, which might be my problem. As you can no doubt tell, I'm kind of new at actually doing this stuff.

- Ok, I have a recursive algorithm that is currently set at 5 ply, but the actual number shouldn't matter.
- For each move at each ply, the engine generates a list of legal moves, this part is working fine.
- At the final ply (ply 1) we don't look for replies, just calculate the material balance. Material balance is only calculated at the final ply. The material calculation works fine.
- When the ply is an even number, a move eval is the maximum of all the reply evals. When the ply is an odd number, the move eval is the minimum eval of all the replies. Thus at the very first ply, the eval for each possible engine move is the minimum value of all the possible replies. The engine will then choose the move with the maximum eval.
- My material calc uses the following: P=10, N=25, B=30, R=50, Q=90.

As an example, consider the move 1.a4 The algorithm assigns the reply 1...b5 a value of 20 in white's favor. This surprises me somewhat, I would have expected that given a correct minimax implementation, the value would be 10 ( 1 pawn ) given correct subsequent play on a material basis.

Another example is every reply to 1.b3 evaluating to 10 in favor of white.


The question is whether this is all because of no quiescense, or some serious flaw in my logic that I can't see. If needed, I can post some code, it's in pretty good shape.

Thanks.

Negamax = search
material considerations = evaluation

I see those as 2 different entities actually.

minimax material evaluation, what do you mean by that,
that the root of it should give a good static material evaluation?

Or do you mean you want to build a fast searcher with just material evaluation at first?

Whatever you do in that case, you can't escape using a qsearch.

Ok, it seems I use the terminology improperly. That doesn't surprise me. Anyways, This post you quoted is kind of old, I just posted an algorithm in my previous post, I'm more interested in that now. I am hoping the pseudo code will speak for itself.

[diep]

Greetings.

I am trying to implement a little minimax (negamax?) material evaluation into my engine, and I am not sure how to interpret the results. At this point I don't care if my strategy is good or bad, only that the results are to be expected given what I have done. There is as yet no alpha beta pruning, and no quiescense, which might be my problem. As you can no doubt tell, I'm kind of new at actually doing this stuff.

- Ok, I have a recursive algorithm that is currently set at 5 ply, but the actual number shouldn't matter.
- For each move at each ply, the engine generates a list of legal moves, this part is working fine.
- At the final ply (ply 1) we don't look for replies, just calculate the material balance. Material balance is only calculated at the final ply. The material calculation works fine.
- When the ply is an even number, a move eval is the maximum of all the reply evals. When the ply is an odd number, the move eval is the minimum eval of all the replies. Thus at the very first ply, the eval for each possible engine move is the minimum value of all the possible replies. The engine will then choose the move with the maximum eval.
- My material calc uses the following: P=10, N=25, B=30, R=50, Q=90.

As an example, consider the move 1.a4 The algorithm assigns the reply 1...b5 a value of 20 in white's favor. This surprises me somewhat, I would have expected that given a correct minimax implementation, the value would be 10 ( 1 pawn ) given correct subsequent play on a material basis.

Another example is every reply to 1.b3 evaluating to 10 in favor of white.


The question is whether this is all because of no quiescense, or some serious flaw in my logic that I can't see. If needed, I can post some code, it's in pretty good shape.

Thanks.

Negamax = search
material considerations = evaluation

I see those as 2 different entities actually.

minimax material evaluation, what do you mean by that,
that the root of it should give a good static material evaluation?

Or do you mean you want to build a fast searcher with just material evaluation at first?

Whatever you do in that case, you can't escape using a qsearch.

Ok, it seems I use the terminology improperly. That doesn't surprise me. Anyways, This post you quoted is kind of old, I just posted an algorithm in my previous post, I'm more interested in that now. I am hoping the pseudo code will speak for itself.

You're forgetting to make moves in your evaluation, which actually is the search. The call to the function to count material (or you could do it incremental) is what we call evaluation normally spoken.

So you keep evaluating the same position, position never changes. Also you're doing the compare at depth==1 instead of depth <= 0

adding making moves and unmaking moves fixes all this.

Vincent