Value reduction

[stegemma]

This could be an answer even to the post

http://talkchess.com/forum/viewtopic.php?t=60426

After a lot of trying (without any or partial success) to solve the problem of choosing the short mate with TT, trying like this one:

- decrease the value for mate, depending on depth
- decrease the value of any ply with a costant value (+/-1)
- a mix of both

it seems that the only method that works is a "value reduction" obtained by multiplying any value returned by alfabeta by a constant. I've choose 63/64 because its easy to compute but even 127/128 could works (if your engine go very deep in search).

The idea is derivate from my old post related to "far plyes precision", where I talked about the lose of "precision" on the far plyes. In weak engines like Satana, we can't trust on the very far results even because Satana doesn't have Quiescence enabled, at present; so, at far plyes the alfabeta score is... almost a random value! if Satana think to capture a queen after 8 plyes... maybe it get mated after 10, so it is better to capture the queen well away from the horizon.

The "value reduction" is simple to apply and it can even be limited to mate only, where it works very well for both sides:

Code: Select all

#define VAL_REDUCTION(a) ((a)-((a)>>6))

val = -VAL_REDUCTION(AlfaBeta(-VAL_REDUCTION(beta), -VAL_REDUCTION(alfa), iDepth - 1));

It should be tested for extreme conditions, where returned values are near to alfa/beta, to avoid that rounding can get strange results. The same is for the TT, where you store value reducted depending on the analyzed depth (but this I think that could not be a problem).

[syzygy]

After a lot of trying (without any or partial success) to solve the problem of choosing the short mate with TT, trying like this one:

Maybe I'm misunderstanding you, but the solution to how to deal with (distance to) mate values and the TT is well understood:

- within the search, take distance from root to mate;
- when storing to/retrieving from the TT, convert to/from distance from current node to mate.

[hgm]

It should be tested for extreme conditions, where returned values are near to alfa/beta, to avoid that rounding can get strange results. The same is for the TT, where you store value reducted depending on the analyzed depth (but this I think that could not be a problem).

Thinking about it is a better method than testing.

In fact you do it the wrong way around: the correction on alpha and beta has to be the invers function of the correction you apply to the returned score. You want a move in the daughter to fail high when -VAL_REDUCTION(score) <= alpha in the parent. That means that in the daughter score >= VAL_REDUCTION_INVERSE(-alpha), or in other words that beta there = VAL_REDUCTION_INVERSE(-alpha). And then beta should be rounded up, and alpha rounded down, to make sure rounding would never make an out-of-window score map inside the window, and be mistaken for an exact result.

Also note that except for checkmates, this method does not have much effect, as you will be comparing scores that propagated from the leaves through an equal number of levels (for a fixed-depth search). So they all get multiplied by the same factor, which does not affect their comparisons. When you have reductions and extensions it even works the wrong way around: the scores from the deeper searches gets discounted more, while in fact they are expected to be more reliable.

If you think more about it, you will come to the conclusion that gains have to be devaluated based on the remaining depth after they materialize; a Pawn captured just one ply before the horizon can be easily poisoned (and the gain associated with its capture thus illusory), while when you have searched on 10ply after its capture and the advantage is still there, you can be pretty sure that you will cleanly win a Pawn by gobbling it up.

One way to do that would be to weight in a small (possibly remaining-depth-dependent) amount of static eval (or better yet, QS score) together with the score of the best move. E.g. if you would reduce all stand-pat scores to 90% of their normal value, but weight in 5% QS score in a 1-ply node, 3% in a 2-ply node, and 1% in a 3-, 4- and 5-ply node, a gain cashed more than 5 ply before the horizon would be fully counted, while a gain made in the last ply would only count for 90%.

[stegemma]

It should be tested for extreme conditions, where returned values are near to alfa/beta, to avoid that rounding can get strange results. The same is for the TT, where you store value reducted depending on the analyzed depth (but this I think that could not be a problem).

Thinking about it is a better method than testing.

In fact you do it the wrong way around: the correction on alpha and beta has to be the invers function of the correction you apply to the returned score. You want a move in the daughter to fail high when -VAL_REDUCTION(score) <= alpha in the parent. That means that in the daughter score >= VAL_REDUCTION_INVERSE(-alpha), or in other words that beta there = VAL_REDUCTION_INVERSE(-alpha). And then beta should be rounded up, and alpha rounded down, to make sure rounding would never make an out-of-window score map inside the window, and be mistaken for an exact result.

Also note that except for checkmates, this method does not have much effect, as you will be comparing scores that propagated from the leaves through an equal number of levels (for a fixed-depth search). So they all get multiplied by the same factor, which does not affect their comparisons. When you have reductions and extensions it even works the wrong way around: the scores from the deeper searches gets discounted more, while in fact they are expected to be more reliable.

If you think more about it, you will come to the conclusion that gains have to be devaluated based on the remaining depth after they materialize; a Pawn captured just one ply before the horizon can be easily poisoned (and the gain associated with its capture thus illusory), while when you have searched on 10ply after its capture and the advantage is still there, you can be pretty sure that you will cleanly win a Pawn by gobbling it up.

One way to do that would be to weight in a small (possibly remaining-depth-dependent) amount of static eval (or better yet, QS score) together with the score of the best move. E.g. if you would reduce all stand-pat scores to 90% of their normal value, but weight in 5% QS score in a 1-ply node, 3% in a 2-ply node, and 1% in a 3-, 4- and 5-ply node, a gain cashed more than 5 ply before the horizon would be fully counted, while a gain made in the last ply would only count for 90%.

Your first note is very true, in effect I was not sure on results near to alfa/beta. For mate value it works great, maybe because the mate is very distant from any other value.

I'm not sure to understand your second note.... but after a while in fact I've found the problem. Evaluate() has be called at leaves and contains positional factors and piece value factors; I add piece value when captured to the board.value at the ply when the capture has been done but I add board.value only at leaves, so, in effect, the piece capture takes effect only at leaves. Maybe I should scale board.value to, when I call Alfabeta() to go to the next ply.

The actual effect of the idea is that Satana plays better when there are a checkmate but worse in any other situation (and the other cases appears more times, for Satana!).

I will try the correction to alfa/beta value reductions and add the board.value reduction, just to see what happens.

[stegemma]

After a lot of trying (without any or partial success) to solve the problem of choosing the short mate with TT, trying like this one:

Maybe I'm misunderstanding you, but the solution to how to deal with (distance to) mate values and the TT is well understood:

- within the search, take distance from root to mate;
- when storing to/retrieving from the TT, convert to/from distance from current node to mate.

Thanks but... I like to experiment!

[Luis Babboni]

This could be an answer even to the post

http://talkchess.com/forum/viewtopic.php?t=60426

After a lot of trying (without any or partial success) to solve the problem of choosing the short mate with TT, trying like this one:

- decrease the value for mate, depending on depth
- decrease the value of any ply with a costant value (+/-1)
- a mix of both

it seems that the only method that works is a "value reduction" obtained by multiplying any value returned by alfabeta by a constant...

Glup!
I just tried the first option:
"- decrease the value for mate, depending on depth"

Code: Select all

If Abs(Score)=100000 Then	
	If Score=100000 Then Score=Score-p
	If Score=-100000 Then Score=Score+p
EndIf

where p is the ply after actual position.
And seems to me that works perfectly.

Could I did not test enough?
Could just works to my engine cause the fact that Soberango just evaluates material?

[stegemma]

This could be an answer even to the post

http://talkchess.com/forum/viewtopic.php?t=60426

After a lot of trying (without any or partial success) to solve the problem of choosing the short mate with TT, trying like this one:

- decrease the value for mate, depending on depth
- decrease the value of any ply with a costant value (+/-1)
- a mix of both

it seems that the only method that works is a "value reduction" obtained by multiplying any value returned by alfabeta by a constant...

Glup!
I just tried the first option:
"- decrease the value for mate, depending on depth"

Code: Select all

If Abs(Score)=100000 Then	
	If Score=100000 Then Score=Score-p
	If Score=-100000 Then Score=Score+p
EndIf

where p is the ply after actual position.
And seems to me that works perfectly.

Could I did not test enough?
Could just works to my engine cause the fact that Soberango just evaluates material?

No, just I've missed "in my engine"

In effect I'm testing now this simplest solution:

Code: Select all

#define VAL_MATE_REDUCTION(a) if(a >= valKing) --a; else if(a <= -valKing) ++a;

val = -AlfaBeta(-valInfinity, -alfa, iDepth - 1);
VAL_MATE_REDUCTION(val);

For mate is ok, the same as "value reduction". The VR idea must be tested further, for normal search.

[hgm]

In Fairy-Max I do this only for the negative scores. Once per two ply is enough, as scores on odd and even plies will never be compared to each other. An I do not only do it for mate scores, but for any score below the current eval. So that it would take the fastest route to any particular node where it gains something.