Tapered evaluation

[crybotmark]

Hello, i'm sorry if it has already been asked, but i could not find an answer:
I'm trying to implement interpolation between midgame values and endgame values in order to limit evaluation discontinuity. I understood the concept behind tapered evaluation, but I just can't realize how they arrived to the actual implementation: https://chessprogramming.wikispaces.com/Tapered+Eval

Because I do not like add things I do not understand into my engine, I would like to know what's the theory behind phase calculation and score interpolation.
Is there something I could read, which is not the chessprogramming wiki, to help me clarifying my ideas?
Also, I'd like to know from someone with a reasonable experience if this approach actually helps and, if so, what's the gain.
Thank you all for the time

[elcabesa]

I can't understand completely your question but I'll try to reply to you.

let say that:
a position with a king and a pawn versus a king is clearly an endgame,
a position with all the pieces and pawn is clearly a midgame.

when in a leaf you have to evalutate a position you have to understand if it's a midgame or an endame because endgame&midgame needs different evalutation.
for example in a midgame you probably need to care a lot for your king safety, while in an endgame you need to care less for king safety but you probably need to have the king near the passed pawn.

you have to choose whether evalutate a position as a opening or as an endgame. elder programs choose to evalutate each position as a midgame or as an endgame.

This lead to some problem, think to midgame with all the pawns and a queen and a rook for each player. here the king need to defend himself.
as soon you exchan the 2 queens the king need to hurry in the centre of the board or near the passed pawns. so you have a very big disconitnuity between evalutation from before just befor to just after the exchange.

to mitigate this problem programmers create tapered eval where you always calculate both midgame/endgame evalutation and then do a mix of both of them choosing to weight more midgame eval or endgame eval.

the actual code for tapered evalutation is probably a good mix from speed and correctness.

you decide the game phase ( midgam/endgame) based on the number/value of non-pawn pieces.
and then you linearly interpolate (it's faster than other interpolation) between the two term.

Ciao da Firenze

[crybotmark]

Thanks for your answer, but I think you misunderstood the point of my question (perhaps i've not been clear): I understand what tapered eval is and why it is used. What I can't understand is how to determine the parameter of the formula used to calculate the game phase, which is

Code: Select all

(phase * 256 + (TotalPhase / 2)) / TotalPhase)

, like 256.

regarding the final interpolated score, I have to linear interpolate three values: phase, midgame score and endgame score, right? If so, the same question arise: what's the meaning behind the parameter of the formula (the same '256' as before) used to interpolate the values?

I hope i've been clear now. Thank you

p.s. Ti saluto anche io da Firenze

[hgm]

I think 'evaluation discontinuity' is not really the main reason why you would want 'tapered evaluation'. The idea is really a very natural one. The prospects of winning the game, for which evaluation is supposed to give a heuristic estimate, depends not purely on the presence of an advantage (say that Knight that you are ahead), but also on how much material there is is still on the board ('game phase'). It is often the relative advantage that counts, K+N vs K (with equal Pawns) is usually a trivial win, but add two Rooks and a Queen for each side and everything is still possible. In other cases (e.g. King Safety), the advantage becomes less important if there is less material on the board. Having your King safely tucked away in a corner behind Pawns becomes a bit pointless when the opponent only has a Knight left.

But these advantages do not change abruptly, but graduately. There isn't a point in the game where you can say "before trading this Knight, King safety is all important, but now they are traded, it has no importance at all". Sometimes the presence of a Queen is taken as the defining characteristic of an end-game, but taking a King stroll through the center is still completely suicidal if the opponent has no Queen, but still two Rooks, Bishops and Knights. While if he only has a Queen, you can, and often must chance it.

So common sense dictates that the advantage of a better King Safety does not disappear all at once, but gradually as material is traded away. Obviously trading away Queens does more to making the board safer without Pawn shield than trading away minors. But trading away all minors does help a great deal as well. To reflect that in the evaluation you need to 'taper' the King-safety bonus gradually from large to zero when (opponent) material decreases from maximum to bare King. That this makes the evaluation more continuous is just an additional advantage thrown in for free. However, if the search had been such that discontinuous jumps where the best thing in the world for it, it would still have been very wrong to use it. Because it does not reflect the reality of the game.

Interpolating with some game-phase variable based on some weighted counting of the present material does provide an incentive to the program to advance the game phase when it possesses an advantage that is more important in the end-game. E.g. when you are a Knight ahead, and the end-game value of a Knight is higher than the opening value, it can increase its score by trading equal material, because that advances the game-phase towards the end-game. You want that to hold for any material, not just for trading Queens. Or even when you weight in other pieces, you don't want the bonus for trading to only occur when the material drops from above a certain value to below it, and not care about further trading afterwards. Any equal trade will help to express that extra Knight better.

But trading Pawns just makes the game more drawish when you are a minor ahead. Therefore it is a bad idea to weight Pawns into the game phase. This is a good thing, because Pawns also don't provide very much danger to a King, so that you can use the same game-phase measure to interpolate King-Safety and piece values.

[elcabesa]

the formula on chess wiki is

eval = ((opening * (256 - phase)) + (endgame * phase)) / 256

phase is a value between 0 (MIDGAME) and 256 (ENDGAME) telling you the actual game phase.



phase = (phase * 256 + (TotalPhase / 2)) / TotalPhase
(total phase/2) is a fixed point dsp trick to round the variable the the nearer integer

written in floating point it could be written
gamePhase = actualPieces*256/maxPieces;

this is an evaluatation of gamephase wich can go from 0 to 256

maxPieces is a value indicating how much pieces there are on the board at the begining of the game.
actualPiecesis the amount of pieces now on the board.

so you calculate the phase o the game.

[hgm]

Thanks for your answer, but I think you misunderstood the point of my question (perhaps i've not been clear): I understand what tapered eval is and why it is used. What I can't understand is how to determine the parameter of the formula used to calculate the game phase, which is

Code: Select all

(phase * 256 + (TotalPhase / 2)) / TotalPhase)

, like 256.

regarding the final interpolated score, I have to linear interpolate three values: phase, midgame score and endgame score, right? If so, the same question arise: what's the meaning behind the parameter of the formula (the same '256' as before) used to interpolate the values?

I hope i've been clear now. Thank you

p.s. Ti saluto anche io da Firenze

The 256 in the Wiki example is just the maximum possible value of the game phase (TotalPhase in the other example). So gamephase increases (linearly) from 0 to 256, while at the same time 256-gamephase decreases from 256 to 0. Their sum is always 256, so you divide by that to get the weighted average.

In phase = (phase * 256 + TotalPhase/2)/TotalPhase the multipliation with 256 is there to start working in units of 1/256, so that you can use integer variables for representing a fraction. As phase/TotalPhase would always be smaller than 1, and thus rounded to 0 with integer division. (The adding of TotalPhase/2 produces nearest rounding.) Because of this normalization the phase now becomes a number that ranges from 0 to 256.

[crybotmark]

the formula on chess wiki is

eval = ((opening * (256 - phase)) + (endgame * phase)) / 256

phase is a value between 0 (MIDGAME) and 256 (ENDGAME) telling you the actual game phase.

That make sense. Thank you.

I think 'evaluation discontinuity' is not really the main reason why you would want 'tapered evaluation'. The idea is really a very natural one. The prospects of winning the game, for which evaluation is supposed to give a heuristic estimate, depends not purely on the presence of an advantage (say that Knight that you are ahead), but also on how much material there is is still on the board ('game phase'). It is often the relative advantage that counts, K+N vs K (with equal Pawns) is usually a trivial win, but add two Rooks and a Queen for each side and everything is still possible. In other cases (e.g. King Safety), the advantage becomes less important if there is less material on the board. Having your King safely tucked away in a corner behind Pawns becomes a bit pointless when the opponent only has a Knight left.

I understand. thanks for the information, it makes all more clear.

[velmarin]

You can find a practical example engine Maverick of Steve Maughan
http://www.chessprogramming.net/

Code: Select all

t_chess_value calc_evaluation(struct t_board *board, struct t_chess_eval *eval) {

	t_chess_value score;
//-- Are we in the middle game, endgame or somewhere in between
	calc_game_phase(board, eval);

	
	//-- Return the rights score
    score = (1 - 2 * board->to_move) * (((eval->middlegame * eval->game_phase) + (eval->endgame * (256 - eval->game_phase))) / 256);

	//-- Store the score
    eval->static_score = score;
    return score;

}

inline void calc_game_phase(struct t_board *board, struct t_chess_eval *eval) {
    //-- Phase of the game
    eval->game_phase = 2 * popcount(board->piecelist[WHITEPAWN] ^ board->piecelist[BLACKPAWN]);
    eval->game_phase += 44 * popcount(board->piecelist[WHITEQUEEN] ^ board->piecelist[BLACKQUEEN]);
    eval->game_phase += 16 * popcount(board->piecelist[WHITEROOK] ^ board->piecelist[BLACKROOK]);
    eval->game_phase += 12 * popcount(board->piecelist[WHITEBISHOP] ^ board->piecelist[BLACKBISHOP]);
    eval->game_phase += 6 * popcount(board->piecelist[WHITEKNIGHT] ^ board->piecelist[BLACKKNIGHT]);
}

I have something simpler in my projects:
Only white pieces, no pawns

Code: Select all

	
fase += (pos->pceNum[wQueen]*10);
fase += (pos->pceNum[wRook]*5);
fase += (pos->pceNum[wBishop]*3);
fase += (pos->pceNum[wNkingth]*3);
score = ((fase * OPEN + (32 - fase) * ENDG) / 32); 

[crybotmark]

the formula on chess wiki is

eval = ((opening * (256 - phase)) + (endgame * phase)) / 256

phase is a value between 0 (MIDGAME) and 256 (ENDGAME) telling you the actual game phase.



phase = (phase * 256 + (TotalPhase / 2)) / TotalPhase
(total phase/2) is a fixed point dsp trick to round the variable the the nearer integer

written in floating point it could be written
gamePhase = actualPieces*256/maxPieces;

this is an evaluatation of gamephase wich can go from 0 to 256

maxPieces is a value indicating how much pieces there are on the board at the begining of the game.
actualPiecesis the amount of pieces now on the board.

so you calculate the phase o the game.

What if the position has promoted pieces? the phase could get negative (if we look at the wiki calculation of it):

Code: Select all

Q1bqkbnr/p1p2ppp/8/8/8/8/P1P2PPP/q1BQKBNR w Kk - 0 1

in this position, for example, there are 4 queens and the phase would be something around -40.

[hgm]

I guess no one worries about that. It happens in 0% of the games, so even if it would make the engine that is 4 Queens ahead spontaneously resign, it still has no impact on Elo.

The linear formula would extrapolate to 'before the opening'. Usually not enough to make material truly negative, though, just makes it worth less. And put an enormous emphasis on King Safety. Which is not such a bad idea with all those Queens roaming the board.

Fairy-Max also keeps a game-phase variable (only updated in the root, though). But it does not have a dual evaluation or interpolation, other than that the Pawn-push bonus gets linearly higher towards the end-game. And it uses it to decide if it should null-move, and when it should un-freeze the King. Because Fairy-Max also plays Capablanca Chess, it is actually quite normal that it starts with 6 queen-class pieces on the board, so that the game phase is much higher, and Pawn pushes are even more suppressed than in a FIDE opening. This seems good strategy.