concerns on negamax material implementation

[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.

[hgm]

You should expect nonsense moves and scores if you don't do quiescence. If you want to know how the engine actually got the scores, you should try to follow the PV. I always do that by printing a list of moves and scores in one particular node of the tree (singled out by testing the path of moves leading to it). Then you can see which mve it thinks best, and repeat the print-out in the node where it leads to, etc.

If you think another move than the one chosen in the node should have been better, you can follow that move, and see how it is refuted (and if you agree with that).

[Fguy64]

Thanks HG, I'll follow those ideas. Anyways, it sounds like my implemention so far is fine, and the examples I gave aren't out of line given the lack of quiescense.

best regards,
Fred.

[Sven]

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.

After 1.a4 b5 2.axb5 and any next black move, white will capture the black a-pawn, no matter how. Then you stop after 5 plies, so "+2 pawns" is the expected result for this kind of search.

After 1.b3 <any> 2.Bb2 <any>, white will capture at least a black pawn on g7 (or even f6). Again, you stop after 5 plies, so always "+1 pawn" for white after 1.b3.

So your current problem is the lack of quiescence search.

Sven

[plattyaj]

Hmm, I'm not so sure you don't have bugs in your implementation. From the starting position, with just a material evaluation and no quiescence search, a 5 ply search should give a 0 score - no material gain or loss.

Here's what my little engine Schola did when I removed evaluation (except material) and quiescent search for a 5 ply search from the start position:

Code: Select all

sd 5
go
1 0 0 0 Nc3
2 0 0 21 Nc3 Nc6
2 0 0 40 Nc3 Nc6
3 0 0 83 Nc3 Nc6 Rb1
3 0 0 102 Nc3 Nc6 Rb1
4 0 1 167 Nc3 Nc6 Rb1 Rb8
4 0 1 186 Nc3 Nc6 Rb1 Rb8
5 0 1 273 Nc3 Nc6 Rb1 Rb8 Ra1
5 0 1 715 Nc3 Nc6 Rb1 Rb8 Ra1

Definitely implement a PV though to check what it thinks the reply to the reply to the reply will be ...

Andy.

[plattyaj]

After 1.a4 b5 2.axb5 and any next black move, white will capture the black a-pawn, no matter how. Then you stop after 5 plies, so "+2 pawns" is the expected result for this kind of search.

After 1.b3 <any> 2.Bb2 <any>, white will capture at least a black pawn on g7 (or even f6). Again, you stop after 5 plies, so always "+1 pawn" for white after 1.b3.

So your current problem is the lack of quiescence search.

Sven

But it shouldn't suggest b5 as the reply because there are 5 ply searches from 1.a4 that will not lead to loss of material. So I think the -negamax is broken first.

Andy.

[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.

[elpapa]

At the final ply (ply 1) we don't look for replies, just calculate the material balance.

Shouldn't you call eval at depth 0? Going from 5 to 1 would only make 4 half-moves. Probably not your main problem, but you may have a little bug there, depending on your implementation.

[Fguy64]

At the final ply (ply 1) we don't look for replies, just calculate the material balance.

Shouldn't you call eval at depth 0? Going from 5 to 1 would only make 4 half-moves. Probably not your main problem, but you may have a little bug there, depending on your implementation.

Duly noted Patrik, I agree, but I think we are just talking about semantics. What I call ply 1 is should probably be called ply 0, but I am 95% sure we are talking the same thing. because I am getting 5 half moves. in my analysis. Sven's reply makes perfect sense to me. Terminology is not a strength with me.

Anyways, I should probably make the algorithm available so people can see for themselves. Maybe later this evening.

regards.

[plattyaj]

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.