WLDEntryPiece -> WDLEntryPiece for consistency
[stockfish] / src / evaluate.cpp
1 /*
2   Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3   Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
4   Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad
5   Copyright (C) 2015-2017 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad
6
7   Stockfish is free software: you can redistribute it and/or modify
8   it under the terms of the GNU General Public License as published by
9   the Free Software Foundation, either version 3 of the License, or
10   (at your option) any later version.
11
12   Stockfish is distributed in the hope that it will be useful,
13   but WITHOUT ANY WARRANTY; without even the implied warranty of
14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15   GNU General Public License for more details.
16
17   You should have received a copy of the GNU General Public License
18   along with this program.  If not, see <http://www.gnu.org/licenses/>.
19 */
20
21 #include <algorithm>
22 #include <cassert>
23 #include <cstring>   // For std::memset
24 #include <iomanip>
25 #include <sstream>
26
27 #include "bitboard.h"
28 #include "evaluate.h"
29 #include "material.h"
30 #include "pawns.h"
31
32 namespace {
33
34   const Bitboard LongDiagonals = 0x8142241818244281ULL; // A1..H8 | H1..A8
35   const Bitboard Center        = (FileDBB | FileEBB) & (Rank4BB | Rank5BB);
36   const Bitboard QueenSide     = FileABB | FileBBB | FileCBB | FileDBB;
37   const Bitboard CenterFiles   = FileCBB | FileDBB | FileEBB | FileFBB;
38   const Bitboard KingSide      = FileEBB | FileFBB | FileGBB | FileHBB;
39
40   const Bitboard KingFlank[FILE_NB] = {
41     QueenSide, QueenSide, QueenSide, CenterFiles, CenterFiles, KingSide, KingSide, KingSide
42   };
43
44   namespace Trace {
45
46     enum Tracing {NO_TRACE, TRACE};
47
48     enum Term { // The first 8 entries are for PieceType
49       MATERIAL = 8, IMBALANCE, MOBILITY, THREAT, PASSED, SPACE, TOTAL, TERM_NB
50     };
51
52     double scores[TERM_NB][COLOR_NB][PHASE_NB];
53
54     double to_cp(Value v) { return double(v) / PawnValueEg; }
55
56     void add(int idx, Color c, Score s) {
57       scores[idx][c][MG] = to_cp(mg_value(s));
58       scores[idx][c][EG] = to_cp(eg_value(s));
59     }
60
61     void add(int idx, Score w, Score b = SCORE_ZERO) {
62       add(idx, WHITE, w); add(idx, BLACK, b);
63     }
64
65     std::ostream& operator<<(std::ostream& os, Term t) {
66
67       if (t == MATERIAL || t == IMBALANCE || t == Term(PAWN) || t == TOTAL)
68           os << "  ---   --- |   ---   --- | ";
69       else
70           os << std::setw(5) << scores[t][WHITE][MG] << " "
71              << std::setw(5) << scores[t][WHITE][EG] << " | "
72              << std::setw(5) << scores[t][BLACK][MG] << " "
73              << std::setw(5) << scores[t][BLACK][EG] << " | ";
74
75       os << std::setw(5) << scores[t][WHITE][MG] - scores[t][BLACK][MG] << " "
76          << std::setw(5) << scores[t][WHITE][EG] - scores[t][BLACK][EG] << " \n";
77
78       return os;
79     }
80   }
81
82   using namespace Trace;
83
84   // Evaluation class contains various information computed and collected
85   // by the evaluation functions.
86   template<Tracing T = NO_TRACE>
87   class Evaluation {
88
89   public:
90     Evaluation() = delete;
91     Evaluation(const Position& p) : pos(p) {}
92     Evaluation& operator=(const Evaluation&) = delete;
93
94     Value value();
95
96   private:
97     // Evaluation helpers (used when calling value())
98     template<Color Us> void initialize();
99     template<Color Us> Score evaluate_king();
100     template<Color Us> Score evaluate_threats();
101     template<Color Us> Score evaluate_passed_pawns();
102     template<Color Us> Score evaluate_space();
103     template<Color Us, PieceType Pt> Score evaluate_pieces();
104     ScaleFactor evaluate_scale_factor(Value eg);
105     Score evaluate_initiative(Value eg);
106
107     // Data members
108     const Position& pos;
109     Material::Entry* me;
110     Pawns::Entry* pe;
111     Bitboard mobilityArea[COLOR_NB];
112     Score mobility[COLOR_NB] = { SCORE_ZERO, SCORE_ZERO };
113
114     // attackedBy[color][piece type] is a bitboard representing all squares
115     // attacked by a given color and piece type (can be also ALL_PIECES).
116     Bitboard attackedBy[COLOR_NB][PIECE_TYPE_NB];
117
118     // attackedBy2[color] are the squares attacked by 2 pieces of a given color,
119     // possibly via x-ray or by one pawn and one piece. Diagonal x-ray through
120     // pawn or squares attacked by 2 pawns are not explicitly added.
121     Bitboard attackedBy2[COLOR_NB];
122
123     // kingRing[color] is the zone around the king which is considered
124     // by the king safety evaluation. This consists of the squares directly
125     // adjacent to the king, and (only for a king on its first rank) the
126     // squares two ranks in front of the king. For instance, if black's king
127     // is on g8, kingRing[BLACK] is a bitboard containing the squares f8, h8,
128     // f7, g7, h7, f6, g6 and h6.
129     Bitboard kingRing[COLOR_NB];
130
131     // kingAttackersCount[color] is the number of pieces of the given color
132     // which attack a square in the kingRing of the enemy king.
133     int kingAttackersCount[COLOR_NB];
134
135     // kingAttackersWeight[color] is the sum of the "weights" of the pieces of the
136     // given color which attack a square in the kingRing of the enemy king. The
137     // weights of the individual piece types are given by the elements in the
138     // KingAttackWeights array.
139     int kingAttackersWeight[COLOR_NB];
140
141     // kingAdjacentZoneAttacksCount[color] is the number of attacks by the given
142     // color to squares directly adjacent to the enemy king. Pieces which attack
143     // more than one square are counted multiple times. For instance, if there is
144     // a white knight on g5 and black's king is on g8, this white knight adds 2
145     // to kingAdjacentZoneAttacksCount[WHITE].
146     int kingAdjacentZoneAttacksCount[COLOR_NB];
147   };
148
149   #define V(v) Value(v)
150   #define S(mg, eg) make_score(mg, eg)
151
152   // MobilityBonus[PieceType-2][attacked] contains bonuses for middle and end game,
153   // indexed by piece type and number of attacked squares in the mobility area.
154   const Score MobilityBonus[][32] = {
155     { S(-75,-76), S(-57,-54), S( -9,-28), S( -2,-10), S(  6,  5), S( 14, 12), // Knights
156       S( 22, 26), S( 29, 29), S( 36, 29) },
157     { S(-48,-59), S(-20,-23), S( 16, -3), S( 26, 13), S( 38, 24), S( 51, 42), // Bishops
158       S( 55, 54), S( 63, 57), S( 63, 65), S( 68, 73), S( 81, 78), S( 81, 86),
159       S( 91, 88), S( 98, 97) },
160     { S(-58,-76), S(-27,-18), S(-15, 28), S(-10, 55), S( -5, 69), S( -2, 82), // Rooks
161       S(  9,112), S( 16,118), S( 30,132), S( 29,142), S( 32,155), S( 38,165),
162       S( 46,166), S( 48,169), S( 58,171) },
163     { S(-39,-36), S(-21,-15), S(  3,  8), S(  3, 18), S( 14, 34), S( 22, 54), // Queens
164       S( 28, 61), S( 41, 73), S( 43, 79), S( 48, 92), S( 56, 94), S( 60,104),
165       S( 60,113), S( 66,120), S( 67,123), S( 70,126), S( 71,133), S( 73,136),
166       S( 79,140), S( 88,143), S( 88,148), S( 99,166), S(102,170), S(102,175),
167       S(106,184), S(109,191), S(113,206), S(116,212) }
168   };
169
170   // Outpost[knight/bishop][supported by pawn] contains bonuses for minor
171   // pieces if they can reach an outpost square, bigger if that square is
172   // supported by a pawn. If the minor piece occupies an outpost square
173   // then score is doubled.
174   const Score Outpost[][2] = {
175     { S(22, 6), S(36,12) }, // Knight
176     { S( 9, 2), S(15, 5) }  // Bishop
177   };
178
179   // RookOnFile[semiopen/open] contains bonuses for each rook when there is no
180   // friendly pawn on the rook file.
181   const Score RookOnFile[] = { S(20, 7), S(45, 20) };
182
183   // ThreatByMinor/ByRook[attacked PieceType] contains bonuses according to
184   // which piece type attacks which one. Attacks on lesser pieces which are
185   // pawn-defended are not considered.
186   const Score ThreatByMinor[PIECE_TYPE_NB] = {
187     S(0, 0), S(0, 33), S(45, 43), S(46, 47), S(72, 107), S(48, 118)
188   };
189
190   const Score ThreatByRook[PIECE_TYPE_NB] = {
191     S(0, 0), S(0, 25), S(40, 62), S(40, 59), S(0, 34), S(35, 48)
192   };
193
194   // ThreatByKing[on one/on many] contains bonuses for king attacks on
195   // pawns or pieces which are not pawn-defended.
196   const Score ThreatByKing[] = { S(3, 62), S(9, 138) };
197
198   // Passed[mg/eg][Rank] contains midgame and endgame bonuses for passed pawns.
199   // We don't use a Score because we process the two components independently.
200   const Value Passed[][RANK_NB] = {
201     { V(5), V( 5), V(31), V(73), V(166), V(252) },
202     { V(7), V(14), V(38), V(73), V(166), V(252) }
203   };
204
205   // PassedFile[File] contains a bonus according to the file of a passed pawn
206   const Score PassedFile[FILE_NB] = {
207     S(  9, 10), S( 2, 10), S( 1, -8), S(-20,-12),
208     S(-20,-12), S( 1, -8), S( 2, 10), S(  9, 10)
209   };
210
211   // KingProtector[PieceType-2] contains a bonus according to distance from king
212   const Score KingProtector[] = { S(-3, -5), S(-4, -3), S(-3, 0), S(-1, 1) };
213
214   // Assorted bonuses and penalties used by evaluation
215   const Score MinorBehindPawn     = S( 16,  0);
216   const Score BishopPawns         = S(  8, 12);
217   const Score LongRangedBishop    = S( 22,  0);
218   const Score RookOnPawn          = S(  8, 24);
219   const Score TrappedRook         = S( 92,  0);
220   const Score WeakQueen           = S( 50, 10);
221   const Score OtherCheck          = S( 10, 10);
222   const Score CloseEnemies        = S(  7,  0);
223   const Score PawnlessFlank       = S( 20, 80);
224   const Score ThreatByHangingPawn = S( 71, 61);
225   const Score ThreatBySafePawn    = S(182,175);
226   const Score ThreatByRank        = S( 16,  3);
227   const Score Hanging             = S( 48, 27);
228   const Score WeakUnopposedPawn   = S(  5, 25);
229   const Score ThreatByPawnPush    = S( 38, 22);
230   const Score HinderPassedPawn    = S(  7,  0);
231   const Score TrappedBishopA1H1   = S( 50, 50);
232
233   #undef S
234   #undef V
235
236   // KingAttackWeights[PieceType] contains king attack weights by piece type
237   const int KingAttackWeights[PIECE_TYPE_NB] = { 0, 0, 78, 56, 45, 11 };
238
239   // Penalties for enemy's safe checks
240   const int QueenCheck  = 780;
241   const int RookCheck   = 880;
242   const int BishopCheck = 435;
243   const int KnightCheck = 790;
244
245   // Threshold for lazy and space evaluation
246   const Value LazyThreshold  = Value(1500);
247   const Value SpaceThreshold = Value(12222);
248
249
250   // initialize() computes king and pawn attacks, and the king ring bitboard
251   // for a given color. This is done at the beginning of the evaluation.
252
253   template<Tracing T> template<Color Us>
254   void Evaluation<T>::initialize() {
255
256     const Color  Them = (Us == WHITE ? BLACK : WHITE);
257     const Square Up   = (Us == WHITE ? NORTH : SOUTH);
258     const Square Down = (Us == WHITE ? SOUTH : NORTH);
259     const Bitboard LowRanks = (Us == WHITE ? Rank2BB | Rank3BB: Rank7BB | Rank6BB);
260
261     // Find our pawns on the first two ranks, and those which are blocked
262     Bitboard b = pos.pieces(Us, PAWN) & (shift<Down>(pos.pieces()) | LowRanks);
263
264     // Squares occupied by those pawns, by our king, or controlled by enemy pawns
265     // are excluded from the mobility area.
266     mobilityArea[Us] = ~(b | pos.square<KING>(Us) | pe->pawn_attacks(Them));
267
268     // Initialise the attack bitboards with the king and pawn information
269     b = attackedBy[Us][KING] = pos.attacks_from<KING>(pos.square<KING>(Us));
270     attackedBy[Us][PAWN] = pe->pawn_attacks(Us);
271
272     attackedBy2[Us]            = b & attackedBy[Us][PAWN];
273     attackedBy[Us][ALL_PIECES] = b | attackedBy[Us][PAWN];
274
275     // Init our king safety tables only if we are going to use them
276     if (pos.non_pawn_material(Them) >= RookValueMg + KnightValueMg)
277     {
278         kingRing[Us] = b;
279         if (relative_rank(Us, pos.square<KING>(Us)) == RANK_1)
280             kingRing[Us] |= shift<Up>(b);
281
282         kingAttackersCount[Them] = popcount(b & pe->pawn_attacks(Them));
283         kingAdjacentZoneAttacksCount[Them] = kingAttackersWeight[Them] = 0;
284     }
285     else
286         kingRing[Us] = kingAttackersCount[Them] = 0;
287   }
288
289
290   // evaluate_pieces() assigns bonuses and penalties to the pieces of a given
291   // color and type.
292
293   template<Tracing T>  template<Color Us, PieceType Pt>
294   Score Evaluation<T>::evaluate_pieces() {
295
296     const Color Them = (Us == WHITE ? BLACK : WHITE);
297     const Bitboard OutpostRanks = (Us == WHITE ? Rank4BB | Rank5BB | Rank6BB
298                                                : Rank5BB | Rank4BB | Rank3BB);
299     const Square* pl = pos.squares<Pt>(Us);
300
301     Bitboard b, bb;
302     Square s;
303     Score score = SCORE_ZERO;
304
305     attackedBy[Us][Pt] = 0;
306
307     while ((s = *pl++) != SQ_NONE)
308     {
309         // Find attacked squares, including x-ray attacks for bishops and rooks
310         b = Pt == BISHOP ? attacks_bb<BISHOP>(s, pos.pieces() ^ pos.pieces(Us, QUEEN))
311           : Pt ==   ROOK ? attacks_bb<  ROOK>(s, pos.pieces() ^ pos.pieces(Us, ROOK, QUEEN))
312                          : pos.attacks_from<Pt>(s);
313
314         if (pos.pinned_pieces(Us) & s)
315             b &= LineBB[pos.square<KING>(Us)][s];
316
317         attackedBy2[Us] |= attackedBy[Us][ALL_PIECES] & b;
318         attackedBy[Us][ALL_PIECES] |= attackedBy[Us][Pt] |= b;
319
320         if (b & kingRing[Them])
321         {
322             kingAttackersCount[Us]++;
323             kingAttackersWeight[Us] += KingAttackWeights[Pt];
324             kingAdjacentZoneAttacksCount[Us] += popcount(b & attackedBy[Them][KING]);
325         }
326
327         int mob = popcount(b & mobilityArea[Us]);
328
329         mobility[Us] += MobilityBonus[Pt - 2][mob];
330
331         // Bonus for this piece as a king protector
332         score += KingProtector[Pt - 2] * distance(s, pos.square<KING>(Us));
333
334         if (Pt == BISHOP || Pt == KNIGHT)
335         {
336             // Bonus for outpost squares
337             bb = OutpostRanks & ~pe->pawn_attacks_span(Them);
338             if (bb & s)
339                 score += Outpost[Pt == BISHOP][!!(attackedBy[Us][PAWN] & s)] * 2;
340             else
341             {
342                 bb &= b & ~pos.pieces(Us);
343                 if (bb)
344                    score += Outpost[Pt == BISHOP][!!(attackedBy[Us][PAWN] & bb)];
345             }
346
347             // Bonus when behind a pawn
348             if (    relative_rank(Us, s) < RANK_5
349                 && (pos.pieces(PAWN) & (s + pawn_push(Us))))
350                 score += MinorBehindPawn;
351
352             if (Pt == BISHOP)
353             {
354                 // Penalty for pawns on the same color square as the bishop
355                 score -= BishopPawns * pe->pawns_on_same_color_squares(Us, s);
356
357                 // Bonus for bishop on a long diagonal without pawns in the center
358                 if (    (LongDiagonals & s)
359                     && !(attackedBy[Them][PAWN] & s)
360                     && !(Center & PseudoAttacks[BISHOP][s] & pos.pieces(PAWN)))
361                     score += LongRangedBishop;
362             }
363
364             // An important Chess960 pattern: A cornered bishop blocked by a friendly
365             // pawn diagonally in front of it is a very serious problem, especially
366             // when that pawn is also blocked.
367             if (   Pt == BISHOP
368                 && pos.is_chess960()
369                 && (s == relative_square(Us, SQ_A1) || s == relative_square(Us, SQ_H1)))
370             {
371                 Square d = pawn_push(Us) + (file_of(s) == FILE_A ? EAST : WEST);
372                 if (pos.piece_on(s + d) == make_piece(Us, PAWN))
373                     score -= !pos.empty(s + d + pawn_push(Us))                ? TrappedBishopA1H1 * 4
374                             : pos.piece_on(s + d + d) == make_piece(Us, PAWN) ? TrappedBishopA1H1 * 2
375                                                                               : TrappedBishopA1H1;
376             }
377         }
378
379         if (Pt == ROOK)
380         {
381             // Bonus for aligning with enemy pawns on the same rank/file
382             if (relative_rank(Us, s) >= RANK_5)
383                 score += RookOnPawn * popcount(pos.pieces(Them, PAWN) & PseudoAttacks[ROOK][s]);
384
385             // Bonus when on an open or semi-open file
386             if (pe->semiopen_file(Us, file_of(s)))
387                 score += RookOnFile[!!pe->semiopen_file(Them, file_of(s))];
388
389             // Penalty when trapped by the king, even more if the king cannot castle
390             else if (mob <= 3)
391             {
392                 Square ksq = pos.square<KING>(Us);
393
394                 if (   ((file_of(ksq) < FILE_E) == (file_of(s) < file_of(ksq)))
395                     && !pe->semiopen_side(Us, file_of(ksq), file_of(s) < file_of(ksq)))
396                     score -= (TrappedRook - make_score(mob * 22, 0)) * (1 + !pos.can_castle(Us));
397             }
398         }
399
400         if (Pt == QUEEN)
401         {
402             // Penalty if any relative pin or discovered attack against the queen
403             Bitboard pinners;
404             if (pos.slider_blockers(pos.pieces(Them, ROOK, BISHOP), s, pinners))
405                 score -= WeakQueen;
406         }
407     }
408
409     if (T)
410         Trace::add(Pt, Us, score);
411
412     return score;
413   }
414
415
416   // evaluate_king() assigns bonuses and penalties to a king of a given color
417
418   template<Tracing T>  template<Color Us>
419   Score Evaluation<T>::evaluate_king() {
420
421     const Color Them    = (Us == WHITE ? BLACK : WHITE);
422     const Square Up     = (Us == WHITE ? NORTH : SOUTH);
423     const Bitboard Camp = (Us == WHITE ? AllSquares ^ Rank6BB ^ Rank7BB ^ Rank8BB
424                                        : AllSquares ^ Rank1BB ^ Rank2BB ^ Rank3BB);
425
426     const Square ksq = pos.square<KING>(Us);
427     Bitboard kingOnlyDefended, undefended, b, b1, b2, safe, other;
428     int kingDanger;
429
430     // King shelter and enemy pawns storm
431     Score score = pe->king_safety<Us>(pos, ksq);
432
433     // Main king safety evaluation
434     if (kingAttackersCount[Them] > (1 - pos.count<QUEEN>(Them)))
435     {
436         // Find the attacked squares which are defended only by our king...
437         kingOnlyDefended =   attackedBy[Them][ALL_PIECES]
438                           &  attackedBy[Us][KING]
439                           & ~attackedBy2[Us];
440
441         // ... and those which are not defended at all in the larger king ring
442         undefended =   attackedBy[Them][ALL_PIECES]
443                     & ~attackedBy[Us][ALL_PIECES]
444                     &  kingRing[Us]
445                     & ~pos.pieces(Them);
446
447         // Initialize the 'kingDanger' variable, which will be transformed
448         // later into a king danger score. The initial value is based on the
449         // number and types of the enemy's attacking pieces, the number of
450         // attacked and weak squares around our king, the absence of queen and
451         // the quality of the pawn shelter (current 'score' value).
452         kingDanger =        kingAttackersCount[Them] * kingAttackersWeight[Them]
453                     + 102 * kingAdjacentZoneAttacksCount[Them]
454                     + 191 * popcount(kingOnlyDefended | undefended)
455                     + 143 * !!pos.pinned_pieces(Us)
456                     - 848 * !pos.count<QUEEN>(Them)
457                     -   9 * mg_value(score) / 8
458                     +  40;
459
460         // Analyse the safe enemy's checks which are possible on next move
461         safe  = ~pos.pieces(Them);
462         safe &= ~attackedBy[Us][ALL_PIECES] | (kingOnlyDefended & attackedBy2[Them]);
463
464         b1 = pos.attacks_from<  ROOK>(ksq);
465         b2 = pos.attacks_from<BISHOP>(ksq);
466
467         // Enemy queen safe checks
468         if ((b1 | b2) & attackedBy[Them][QUEEN] & safe)
469             kingDanger += QueenCheck;
470
471         // For minors and rooks, also consider the square safe if attacked twice,
472         // and only defended by our queen.
473         safe |=  attackedBy2[Them]
474                & ~(attackedBy2[Us] | pos.pieces(Them))
475                & attackedBy[Us][QUEEN];
476
477         // Some other potential checks are also analysed, even from squares
478         // currently occupied by the opponent own pieces, as long as the square
479         // is not attacked by our pawns, and is not occupied by a blocked pawn.
480         other = ~(   attackedBy[Us][PAWN]
481                   | (pos.pieces(Them, PAWN) & shift<Up>(pos.pieces(PAWN))));
482
483         // Enemy rooks safe and other checks
484         if (b1 & attackedBy[Them][ROOK] & safe)
485             kingDanger += RookCheck;
486
487         else if (b1 & attackedBy[Them][ROOK] & other)
488             score -= OtherCheck;
489
490         // Enemy bishops safe and other checks
491         if (b2 & attackedBy[Them][BISHOP] & safe)
492             kingDanger += BishopCheck;
493
494         else if (b2 & attackedBy[Them][BISHOP] & other)
495             score -= OtherCheck;
496
497         // Enemy knights safe and other checks
498         b = pos.attacks_from<KNIGHT>(ksq) & attackedBy[Them][KNIGHT];
499         if (b & safe)
500             kingDanger += KnightCheck;
501
502         else if (b & other)
503             score -= OtherCheck;
504
505         // Transform the kingDanger units into a Score, and substract it from the evaluation
506         if (kingDanger > 0)
507             score -= make_score(kingDanger * kingDanger / 4096, kingDanger / 16);
508     }
509
510     // King tropism: firstly, find squares that opponent attacks in our king flank
511     File kf = file_of(ksq);
512     b = attackedBy[Them][ALL_PIECES] & KingFlank[kf] & Camp;
513
514     assert(((Us == WHITE ? b << 4 : b >> 4) & b) == 0);
515     assert(popcount(Us == WHITE ? b << 4 : b >> 4) == popcount(b));
516
517     // Secondly, add the squares which are attacked twice in that flank and
518     // which are not defended by our pawns.
519     b =  (Us == WHITE ? b << 4 : b >> 4)
520        | (b & attackedBy2[Them] & ~attackedBy[Us][PAWN]);
521
522     score -= CloseEnemies * popcount(b);
523
524     // Penalty when our king is on a pawnless flank
525     if (!(pos.pieces(PAWN) & KingFlank[kf]))
526         score -= PawnlessFlank;
527
528     if (T)
529         Trace::add(KING, Us, score);
530
531     return score;
532   }
533
534
535   // evaluate_threats() assigns bonuses according to the types of the attacking
536   // and the attacked pieces.
537
538   template<Tracing T>  template<Color Us>
539   Score Evaluation<T>::evaluate_threats() {
540
541     const Color Them        = (Us == WHITE ? BLACK      : WHITE);
542     const Square Up         = (Us == WHITE ? NORTH      : SOUTH);
543     const Square Left       = (Us == WHITE ? NORTH_WEST : SOUTH_EAST);
544     const Square Right      = (Us == WHITE ? NORTH_EAST : SOUTH_WEST);
545     const Bitboard TRank3BB = (Us == WHITE ? Rank3BB    : Rank6BB);
546
547     Bitboard b, weak, defended, stronglyProtected, safeThreats;
548     Score score = SCORE_ZERO;
549
550     // Non-pawn enemies attacked by a pawn
551     weak = (pos.pieces(Them) ^ pos.pieces(Them, PAWN)) & attackedBy[Us][PAWN];
552
553     if (weak)
554     {
555         b = pos.pieces(Us, PAWN) & ( ~attackedBy[Them][ALL_PIECES]
556                                     | attackedBy[Us][ALL_PIECES]);
557
558         safeThreats = (shift<Right>(b) | shift<Left>(b)) & weak;
559
560         score += ThreatBySafePawn * popcount(safeThreats);
561
562         if (weak ^ safeThreats)
563             score += ThreatByHangingPawn;
564     }
565
566     // Squares strongly protected by the opponent, either because they attack the
567     // square with a pawn, or because they attack the square twice and we don't.
568     stronglyProtected =  attackedBy[Them][PAWN]
569                        | (attackedBy2[Them] & ~attackedBy2[Us]);
570
571     // Non-pawn enemies, strongly protected
572     defended =  (pos.pieces(Them) ^ pos.pieces(Them, PAWN))
573               & stronglyProtected;
574
575     // Enemies not strongly protected and under our attack
576     weak =   pos.pieces(Them)
577           & ~stronglyProtected
578           &  attackedBy[Us][ALL_PIECES];
579
580     // Add a bonus according to the kind of attacking pieces
581     if (defended | weak)
582     {
583         b = (defended | weak) & (attackedBy[Us][KNIGHT] | attackedBy[Us][BISHOP]);
584         while (b)
585         {
586             Square s = pop_lsb(&b);
587             score += ThreatByMinor[type_of(pos.piece_on(s))];
588             if (type_of(pos.piece_on(s)) != PAWN)
589                 score += ThreatByRank * (int)relative_rank(Them, s);
590         }
591
592         b = (pos.pieces(Them, QUEEN) | weak) & attackedBy[Us][ROOK];
593         while (b)
594         {
595             Square s = pop_lsb(&b);
596             score += ThreatByRook[type_of(pos.piece_on(s))];
597             if (type_of(pos.piece_on(s)) != PAWN)
598                 score += ThreatByRank * (int)relative_rank(Them, s);
599         }
600
601         score += Hanging * popcount(weak & ~attackedBy[Them][ALL_PIECES]);
602
603         b = weak & attackedBy[Us][KING];
604         if (b)
605             score += ThreatByKing[more_than_one(b)];
606     }
607
608     // Bonus for opponent unopposed weak pawns
609     if (pos.pieces(Us, ROOK, QUEEN))
610         score += WeakUnopposedPawn * pe->weak_unopposed(Them);
611
612     // Find squares where our pawns can push on the next move
613     b  = shift<Up>(pos.pieces(Us, PAWN)) & ~pos.pieces();
614     b |= shift<Up>(b & TRank3BB) & ~pos.pieces();
615
616     // Keep only the squares which are not completely unsafe
617     b &= ~attackedBy[Them][PAWN]
618         & (attackedBy[Us][ALL_PIECES] | ~attackedBy[Them][ALL_PIECES]);
619
620     // Add a bonus for each new pawn threats from those squares
621     b =  (shift<Left>(b) | shift<Right>(b))
622        &  pos.pieces(Them)
623        & ~attackedBy[Us][PAWN];
624
625     score += ThreatByPawnPush * popcount(b);
626
627     if (T)
628         Trace::add(THREAT, Us, score);
629
630     return score;
631   }
632
633
634   // evaluate_passed_pawns() evaluates the passed pawns and candidate passed
635   // pawns of the given color.
636
637   template<Tracing T>  template<Color Us>
638   Score Evaluation<T>::evaluate_passed_pawns() {
639
640     const Color Them = (Us == WHITE ? BLACK : WHITE);
641     const Square Up  = (Us == WHITE ? NORTH : SOUTH);
642
643     Bitboard b, bb, squaresToQueen, defendedSquares, unsafeSquares;
644     Score score = SCORE_ZERO;
645
646     b = pe->passed_pawns(Us);
647
648     while (b)
649     {
650         Square s = pop_lsb(&b);
651
652         assert(!(pos.pieces(Them, PAWN) & forward_file_bb(Us, s + Up)));
653
654         bb = forward_file_bb(Us, s) & (attackedBy[Them][ALL_PIECES] | pos.pieces(Them));
655         score -= HinderPassedPawn * popcount(bb);
656
657         int r = relative_rank(Us, s) - RANK_2;
658         int rr = r * (r - 1);
659
660         Value mbonus = Passed[MG][r], ebonus = Passed[EG][r];
661
662         if (rr)
663         {
664             Square blockSq = s + Up;
665
666             // Adjust bonus based on the king's proximity
667             ebonus +=  distance(pos.square<KING>(Them), blockSq) * 5 * rr
668                      - distance(pos.square<KING>(  Us), blockSq) * 2 * rr;
669
670             // If blockSq is not the queening square then consider also a second push
671             if (relative_rank(Us, blockSq) != RANK_8)
672                 ebonus -= distance(pos.square<KING>(Us), blockSq + Up) * rr;
673
674             // If the pawn is free to advance, then increase the bonus
675             if (pos.empty(blockSq))
676             {
677                 // If there is a rook or queen attacking/defending the pawn from behind,
678                 // consider all the squaresToQueen. Otherwise consider only the squares
679                 // in the pawn's path attacked or occupied by the enemy.
680                 defendedSquares = unsafeSquares = squaresToQueen = forward_file_bb(Us, s);
681
682                 bb = forward_file_bb(Them, s) & pos.pieces(ROOK, QUEEN) & pos.attacks_from<ROOK>(s);
683
684                 if (!(pos.pieces(Us) & bb))
685                     defendedSquares &= attackedBy[Us][ALL_PIECES];
686
687                 if (!(pos.pieces(Them) & bb))
688                     unsafeSquares &= attackedBy[Them][ALL_PIECES] | pos.pieces(Them);
689
690                 // If there aren't any enemy attacks, assign a big bonus. Otherwise
691                 // assign a smaller bonus if the block square isn't attacked.
692                 int k = !unsafeSquares ? 18 : !(unsafeSquares & blockSq) ? 8 : 0;
693
694                 // If the path to the queen is fully defended, assign a big bonus.
695                 // Otherwise assign a smaller bonus if the block square is defended.
696                 if (defendedSquares == squaresToQueen)
697                     k += 6;
698
699                 else if (defendedSquares & blockSq)
700                     k += 4;
701
702                 mbonus += k * rr, ebonus += k * rr;
703             }
704             else if (pos.pieces(Us) & blockSq)
705                 mbonus += rr + r * 2, ebonus += rr + r * 2;
706         } // rr != 0
707
708         // Scale down bonus for candidate passers which need more than one
709         // pawn push to become passed or have a pawn in front of them.
710         if (!pos.pawn_passed(Us, s + Up) || (pos.pieces(PAWN) & forward_file_bb(Us, s)))
711             mbonus /= 2, ebonus /= 2;
712
713         score += make_score(mbonus, ebonus) + PassedFile[file_of(s)];
714     }
715
716     if (T)
717         Trace::add(PASSED, Us, score);
718
719     return score;
720   }
721
722
723   // evaluate_space() computes the space evaluation for a given side. The
724   // space evaluation is a simple bonus based on the number of safe squares
725   // available for minor pieces on the central four files on ranks 2--4. Safe
726   // squares one, two or three squares behind a friendly pawn are counted
727   // twice. Finally, the space bonus is multiplied by a weight. The aim is to
728   // improve play on game opening.
729
730   template<Tracing T>  template<Color Us>
731   Score Evaluation<T>::evaluate_space() {
732
733     const Color Them = (Us == WHITE ? BLACK : WHITE);
734     const Bitboard SpaceMask =
735       Us == WHITE ? CenterFiles & (Rank2BB | Rank3BB | Rank4BB)
736                   : CenterFiles & (Rank7BB | Rank6BB | Rank5BB);
737
738     // Find the safe squares for our pieces inside the area defined by
739     // SpaceMask. A square is unsafe if it is attacked by an enemy
740     // pawn, or if it is undefended and attacked by an enemy piece.
741     Bitboard safe =   SpaceMask
742                    & ~pos.pieces(Us, PAWN)
743                    & ~attackedBy[Them][PAWN]
744                    & (attackedBy[Us][ALL_PIECES] | ~attackedBy[Them][ALL_PIECES]);
745
746     // Find all squares which are at most three squares behind some friendly pawn
747     Bitboard behind = pos.pieces(Us, PAWN);
748     behind |= (Us == WHITE ? behind >>  8 : behind <<  8);
749     behind |= (Us == WHITE ? behind >> 16 : behind << 16);
750
751     // Since SpaceMask[Us] is fully on our half of the board...
752     assert(unsigned(safe >> (Us == WHITE ? 32 : 0)) == 0);
753
754     // ...count safe + (behind & safe) with a single popcount.
755     int bonus = popcount((Us == WHITE ? safe << 32 : safe >> 32) | (behind & safe));
756     int weight = pos.count<ALL_PIECES>(Us) - 2 * pe->open_files();
757
758     return make_score(bonus * weight * weight / 16, 0);
759   }
760
761
762   // evaluate_initiative() computes the initiative correction value for the
763   // position, i.e., second order bonus/malus based on the known attacking/defending
764   // status of the players.
765
766   template<Tracing T>
767   Score Evaluation<T>::evaluate_initiative(Value eg) {
768
769     int kingDistance =  distance<File>(pos.square<KING>(WHITE), pos.square<KING>(BLACK))
770                       - distance<Rank>(pos.square<KING>(WHITE), pos.square<KING>(BLACK));
771     bool bothFlanks = (pos.pieces(PAWN) & QueenSide) && (pos.pieces(PAWN) & KingSide);
772
773     // Compute the initiative bonus for the attacking side
774     int initiative = 8 * (pe->pawn_asymmetry() + kingDistance - 17) + 12 * pos.count<PAWN>() + 16 * bothFlanks;
775
776     // Now apply the bonus: note that we find the attacking side by extracting
777     // the sign of the endgame value, and that we carefully cap the bonus so
778     // that the endgame score will never change sign after the bonus.
779     int v = ((eg > 0) - (eg < 0)) * std::max(initiative, -abs(eg));
780
781     return make_score(0, v);
782   }
783
784
785   // evaluate_scale_factor() computes the scale factor for the winning side
786
787   template<Tracing T>
788   ScaleFactor Evaluation<T>::evaluate_scale_factor(Value eg) {
789
790     Color strongSide = eg > VALUE_DRAW ? WHITE : BLACK;
791     ScaleFactor sf = me->scale_factor(pos, strongSide);
792
793     // If we don't already have an unusual scale factor, check for certain
794     // types of endgames, and use a lower scale for those.
795     if (sf == SCALE_FACTOR_NORMAL || sf == SCALE_FACTOR_ONEPAWN)
796     {
797         if (pos.opposite_bishops())
798         {
799             // Endgame with opposite-colored bishops and no other pieces (ignoring pawns)
800             // is almost a draw, in case of KBP vs KB, it is even more a draw.
801             if (   pos.non_pawn_material(WHITE) == BishopValueMg
802                 && pos.non_pawn_material(BLACK) == BishopValueMg)
803                 return more_than_one(pos.pieces(PAWN)) ? ScaleFactor(31) : ScaleFactor(9);
804
805             // Endgame with opposite-colored bishops, but also other pieces. Still
806             // a bit drawish, but not as drawish as with only the two bishops.
807             return ScaleFactor(46);
808         }
809         // Endings where weaker side can place his king in front of the opponent's
810         // pawns are drawish.
811         else if (    abs(eg) <= BishopValueEg
812                  &&  pos.count<PAWN>(strongSide) <= 2
813                  && !pos.pawn_passed(~strongSide, pos.square<KING>(~strongSide)))
814             return ScaleFactor(37 + 7 * pos.count<PAWN>(strongSide));
815     }
816
817     return sf;
818   }
819
820
821   // value() is the main function of the class. It computes the various parts of
822   // the evaluation and returns the value of the position from the point of view
823   // of the side to move.
824
825   template<Tracing T>
826   Value Evaluation<T>::value() {
827
828     assert(!pos.checkers());
829
830     // Probe the material hash table
831     me = Material::probe(pos);
832
833     // If we have a specialized evaluation function for the current material
834     // configuration, call it and return.
835     if (me->specialized_eval_exists())
836         return me->evaluate(pos);
837
838     // Initialize score by reading the incrementally updated scores included in
839     // the position object (material + piece square tables) and the material
840     // imbalance. Score is computed internally from the white point of view.
841     Score score = pos.psq_score() + me->imbalance();
842
843     // Probe the pawn hash table
844     pe = Pawns::probe(pos);
845     score += pe->pawns_score();
846
847     // Early exit if score is high
848     Value v = (mg_value(score) + eg_value(score)) / 2;
849     if (abs(v) > LazyThreshold)
850        return pos.side_to_move() == WHITE ? v : -v;
851
852     // Main evaluation begins here
853
854     initialize<WHITE>();
855     initialize<BLACK>();
856
857     score += evaluate_pieces<WHITE, KNIGHT>() - evaluate_pieces<BLACK, KNIGHT>();
858     score += evaluate_pieces<WHITE, BISHOP>() - evaluate_pieces<BLACK, BISHOP>();
859     score += evaluate_pieces<WHITE, ROOK  >() - evaluate_pieces<BLACK, ROOK  >();
860     score += evaluate_pieces<WHITE, QUEEN >() - evaluate_pieces<BLACK, QUEEN >();
861
862     score += mobility[WHITE] - mobility[BLACK];
863
864     score +=  evaluate_king<WHITE>()
865             - evaluate_king<BLACK>();
866
867     score +=  evaluate_threats<WHITE>()
868             - evaluate_threats<BLACK>();
869
870     score +=  evaluate_passed_pawns<WHITE>()
871             - evaluate_passed_pawns<BLACK>();
872
873     if (pos.non_pawn_material() >= SpaceThreshold)
874         score +=  evaluate_space<WHITE>()
875                 - evaluate_space<BLACK>();
876
877     score += evaluate_initiative(eg_value(score));
878
879     // Interpolate between a middlegame and a (scaled by 'sf') endgame score
880     ScaleFactor sf = evaluate_scale_factor(eg_value(score));
881     v =  mg_value(score) * int(me->game_phase())
882        + eg_value(score) * int(PHASE_MIDGAME - me->game_phase()) * sf / SCALE_FACTOR_NORMAL;
883
884     v /= int(PHASE_MIDGAME);
885
886     // In case of tracing add all remaining individual evaluation terms
887     if (T)
888     {
889         Trace::add(MATERIAL, pos.psq_score());
890         Trace::add(IMBALANCE, me->imbalance());
891         Trace::add(PAWN, pe->pawns_score());
892         Trace::add(MOBILITY, mobility[WHITE], mobility[BLACK]);
893         if (pos.non_pawn_material() >= SpaceThreshold)
894             Trace::add(SPACE, evaluate_space<WHITE>()
895                             , evaluate_space<BLACK>());
896         Trace::add(TOTAL, score);
897     }
898
899     return (pos.side_to_move() == WHITE ? v : -v) + Eval::Tempo; // Side to move point of view
900   }
901
902 } // namespace
903
904
905 /// evaluate() is the evaluator for the outer world. It returns a static evaluation
906 /// of the position from the point of view of the side to move.
907
908 Value Eval::evaluate(const Position& pos)
909 {
910    return Evaluation<>(pos).value();
911 }
912
913 /// trace() is like evaluate(), but instead of returning a value, it returns
914 /// a string (suitable for outputting to stdout) that contains the detailed
915 /// descriptions and values of each evaluation term. Useful for debugging.
916
917 std::string Eval::trace(const Position& pos) {
918
919   std::memset(scores, 0, sizeof(scores));
920
921   Value v = Evaluation<TRACE>(pos).value();
922   v = pos.side_to_move() == WHITE ? v : -v; // White's point of view
923
924   std::stringstream ss;
925   ss << std::showpoint << std::noshowpos << std::fixed << std::setprecision(2)
926      << "      Eval term |    White    |    Black    |    Total    \n"
927      << "                |   MG    EG  |   MG    EG  |   MG    EG  \n"
928      << "----------------+-------------+-------------+-------------\n"
929      << "       Material | " << Term(MATERIAL)
930      << "      Imbalance | " << Term(IMBALANCE)
931      << "          Pawns | " << Term(PAWN)
932      << "        Knights | " << Term(KNIGHT)
933      << "        Bishops | " << Term(BISHOP)
934      << "          Rooks | " << Term(ROOK)
935      << "         Queens | " << Term(QUEEN)
936      << "       Mobility | " << Term(MOBILITY)
937      << "    King safety | " << Term(KING)
938      << "        Threats | " << Term(THREAT)
939      << "   Passed pawns | " << Term(PASSED)
940      << "          Space | " << Term(SPACE)
941      << "----------------+-------------+-------------+-------------\n"
942      << "          Total | " << Term(TOTAL);
943
944   ss << "\nTotal Evaluation: " << to_cp(v) << " (white side)\n";
945
946   return ss.str();
947 }