Adjust history threshold for quiet moves futility pruning
[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-2020 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 #include "thread.h"
32
33 namespace Trace {
34
35   enum Tracing { NO_TRACE, TRACE };
36
37   enum Term { // The first 8 entries are reserved for PieceType
38     MATERIAL = 8, IMBALANCE, MOBILITY, THREAT, PASSED, SPACE, WINNABLE, TOTAL, TERM_NB
39   };
40
41   Score scores[TERM_NB][COLOR_NB];
42
43   double to_cp(Value v) { return double(v) / PawnValueEg; }
44
45   void add(int idx, Color c, Score s) {
46     scores[idx][c] = s;
47   }
48
49   void add(int idx, Score w, Score b = SCORE_ZERO) {
50     scores[idx][WHITE] = w;
51     scores[idx][BLACK] = b;
52   }
53
54   std::ostream& operator<<(std::ostream& os, Score s) {
55     os << std::setw(5) << to_cp(mg_value(s)) << " "
56        << std::setw(5) << to_cp(eg_value(s));
57     return os;
58   }
59
60   std::ostream& operator<<(std::ostream& os, Term t) {
61
62     if (t == MATERIAL || t == IMBALANCE || t == WINNABLE || t == TOTAL)
63         os << " ----  ----"    << " | " << " ----  ----";
64     else
65         os << scores[t][WHITE] << " | " << scores[t][BLACK];
66
67     os << " | " << scores[t][WHITE] - scores[t][BLACK] << "\n";
68     return os;
69   }
70 }
71
72 using namespace Trace;
73
74 namespace {
75
76   // Threshold for lazy and space evaluation
77   constexpr Value LazyThreshold  = Value(1400);
78   constexpr Value SpaceThreshold = Value(12222);
79
80   // KingAttackWeights[PieceType] contains king attack weights by piece type
81   constexpr int KingAttackWeights[PIECE_TYPE_NB] = { 0, 0, 81, 52, 44, 10 };
82
83   // Penalties for enemy's safe checks
84   constexpr int QueenSafeCheck  = 772;
85   constexpr int RookSafeCheck   = 1084;
86   constexpr int BishopSafeCheck = 645;
87   constexpr int KnightSafeCheck = 792;
88
89 #define S(mg, eg) make_score(mg, eg)
90
91   // MobilityBonus[PieceType-2][attacked] contains bonuses for middle and end game,
92   // indexed by piece type and number of attacked squares in the mobility area.
93   constexpr Score MobilityBonus[][32] = {
94     { S(-62,-81), S(-53,-56), S(-12,-31), S( -4,-16), S(  3,  5), S( 13, 11), // Knight
95       S( 22, 17), S( 28, 20), S( 33, 25) },
96     { S(-48,-59), S(-20,-23), S( 16, -3), S( 26, 13), S( 38, 24), S( 51, 42), // Bishop
97       S( 55, 54), S( 63, 57), S( 63, 65), S( 68, 73), S( 81, 78), S( 81, 86),
98       S( 91, 88), S( 98, 97) },
99     { S(-60,-78), S(-20,-17), S(  2, 23), S(  3, 39), S(  3, 70), S( 11, 99), // Rook
100       S( 22,103), S( 31,121), S( 40,134), S( 40,139), S( 41,158), S( 48,164),
101       S( 57,168), S( 57,169), S( 62,172) },
102     { S(-30,-48), S(-12,-30), S( -8, -7), S( -9, 19), S( 20, 40), S( 23, 55), // Queen
103       S( 23, 59), S( 35, 75), S( 38, 78), S( 53, 96), S( 64, 96), S( 65,100),
104       S( 65,121), S( 66,127), S( 67,131), S( 67,133), S( 72,136), S( 72,141),
105       S( 77,147), S( 79,150), S( 93,151), S(108,168), S(108,168), S(108,171),
106       S(110,182), S(114,182), S(114,192), S(116,219) }
107   };
108
109   // RookOnFile[semiopen/open] contains bonuses for each rook when there is
110   // no (friendly) pawn on the rook file.
111   constexpr Score RookOnFile[] = { S(19, 7), S(48, 29) };
112
113   // ThreatByMinor/ByRook[attacked PieceType] contains bonuses according to
114   // which piece type attacks which one. Attacks on lesser pieces which are
115   // pawn-defended are not considered.
116   constexpr Score ThreatByMinor[PIECE_TYPE_NB] = {
117     S(0, 0), S(5, 32), S(57, 41), S(77, 56), S(88, 119), S(79, 161)
118   };
119
120   constexpr Score ThreatByRook[PIECE_TYPE_NB] = {
121     S(0, 0), S(3, 46), S(37, 68), S(42, 60), S(0, 38), S(58, 41)
122   };
123
124   // PassedRank[Rank] contains a bonus according to the rank of a passed pawn
125   constexpr Score PassedRank[RANK_NB] = {
126     S(0, 0), S(10, 28), S(17, 33), S(15, 41), S(62, 72), S(168, 177), S(276, 260)
127   };
128
129   // Assorted bonuses and penalties
130   constexpr Score BishopPawns         = S(  3,  7);
131   constexpr Score BishopOnKingRing    = S( 24,  0);
132   constexpr Score BishopXRayPawns     = S(  4,  5);
133   constexpr Score CorneredBishop      = S( 50, 50);
134   constexpr Score FlankAttacks        = S(  8,  0);
135   constexpr Score Hanging             = S( 69, 36);
136   constexpr Score BishopKingProtector = S(  6,  9);
137   constexpr Score KnightKingProtector = S(  8,  9);
138   constexpr Score KnightOnQueen       = S( 16, 11);
139   constexpr Score LongDiagonalBishop  = S( 45,  0);
140   constexpr Score MinorBehindPawn     = S( 18,  3);
141   constexpr Score KnightOutpost       = S( 56, 36);
142   constexpr Score BishopOutpost       = S( 30, 23);
143   constexpr Score ReachableOutpost    = S( 31, 22);
144   constexpr Score PassedFile          = S( 11,  8);
145   constexpr Score PawnlessFlank       = S( 17, 95);
146   constexpr Score RestrictedPiece     = S(  7,  7);
147   constexpr Score RookOnKingRing      = S( 16,  0);
148   constexpr Score RookOnQueenFile     = S(  5,  9);
149   constexpr Score SliderOnQueen       = S( 59, 18);
150   constexpr Score ThreatByKing        = S( 24, 89);
151   constexpr Score ThreatByPawnPush    = S( 48, 39);
152   constexpr Score ThreatBySafePawn    = S(173, 94);
153   constexpr Score TrappedRook         = S( 55, 13);
154   constexpr Score WeakQueen           = S( 51, 14);
155   constexpr Score WeakQueenProtection = S( 15,  0);
156
157 #undef S
158
159   // Evaluation class computes and stores attacks tables and other working data
160   template<Tracing T>
161   class Evaluation {
162
163   public:
164     Evaluation() = delete;
165     explicit Evaluation(const Position& p) : pos(p) {}
166     Evaluation& operator=(const Evaluation&) = delete;
167     Value value();
168
169   private:
170     template<Color Us> void initialize();
171     template<Color Us, PieceType Pt> Score pieces();
172     template<Color Us> Score king() const;
173     template<Color Us> Score threats() const;
174     template<Color Us> Score passed() const;
175     template<Color Us> Score space() const;
176     Value winnable(Score score) const;
177
178     const Position& pos;
179     Material::Entry* me;
180     Pawns::Entry* pe;
181     Bitboard mobilityArea[COLOR_NB];
182     Score mobility[COLOR_NB] = { SCORE_ZERO, SCORE_ZERO };
183
184     // attackedBy[color][piece type] is a bitboard representing all squares
185     // attacked by a given color and piece type. Special "piece types" which
186     // is also calculated is ALL_PIECES.
187     Bitboard attackedBy[COLOR_NB][PIECE_TYPE_NB];
188
189     // attackedBy2[color] are the squares attacked by at least 2 units of a given
190     // color, including x-rays. But diagonal x-rays through pawns are not computed.
191     Bitboard attackedBy2[COLOR_NB];
192
193     // kingRing[color] are the squares adjacent to the king plus some other
194     // very near squares, depending on king position.
195     Bitboard kingRing[COLOR_NB];
196
197     // kingAttackersCount[color] is the number of pieces of the given color
198     // which attack a square in the kingRing of the enemy king.
199     int kingAttackersCount[COLOR_NB];
200
201     // kingAttackersWeight[color] is the sum of the "weights" of the pieces of
202     // the given color which attack a square in the kingRing of the enemy king.
203     // The weights of the individual piece types are given by the elements in
204     // the KingAttackWeights array.
205     int kingAttackersWeight[COLOR_NB];
206
207     // kingAttacksCount[color] is the number of attacks by the given color to
208     // squares directly adjacent to the enemy king. Pieces which attack more
209     // than one square are counted multiple times. For instance, if there is
210     // a white knight on g5 and black's king is on g8, this white knight adds 2
211     // to kingAttacksCount[WHITE].
212     int kingAttacksCount[COLOR_NB];
213   };
214
215
216   // Evaluation::initialize() computes king and pawn attacks, and the king ring
217   // bitboard for a given color. This is done at the beginning of the evaluation.
218   template<Tracing T> template<Color Us>
219   void Evaluation<T>::initialize() {
220
221     constexpr Color     Them = ~Us;
222     constexpr Direction Up   = pawn_push(Us);
223     constexpr Direction Down = -Up;
224     constexpr Bitboard LowRanks = (Us == WHITE ? Rank2BB | Rank3BB : Rank7BB | Rank6BB);
225
226     const Square ksq = pos.square<KING>(Us);
227
228     Bitboard dblAttackByPawn = pawn_double_attacks_bb<Us>(pos.pieces(Us, PAWN));
229
230     // Find our pawns that are blocked or on the first two ranks
231     Bitboard b = pos.pieces(Us, PAWN) & (shift<Down>(pos.pieces()) | LowRanks);
232
233     // Squares occupied by those pawns, by our king or queen, by blockers to attacks on our king
234     // or controlled by enemy pawns are excluded from the mobility area.
235     mobilityArea[Us] = ~(b | pos.pieces(Us, KING, QUEEN) | pos.blockers_for_king(Us) | pe->pawn_attacks(Them));
236
237     // Initialize attackedBy[] for king and pawns
238     attackedBy[Us][KING] = attacks_bb<KING>(ksq);
239     attackedBy[Us][PAWN] = pe->pawn_attacks(Us);
240     attackedBy[Us][ALL_PIECES] = attackedBy[Us][KING] | attackedBy[Us][PAWN];
241     attackedBy2[Us] = dblAttackByPawn | (attackedBy[Us][KING] & attackedBy[Us][PAWN]);
242
243     // Init our king safety tables
244     Square s = make_square(Utility::clamp(file_of(ksq), FILE_B, FILE_G),
245                            Utility::clamp(rank_of(ksq), RANK_2, RANK_7));
246     kingRing[Us] = attacks_bb<KING>(s) | s;
247
248     kingAttackersCount[Them] = popcount(kingRing[Us] & pe->pawn_attacks(Them));
249     kingAttacksCount[Them] = kingAttackersWeight[Them] = 0;
250
251     // Remove from kingRing[] the squares defended by two pawns
252     kingRing[Us] &= ~dblAttackByPawn;
253   }
254
255
256   // Evaluation::pieces() scores pieces of a given color and type
257   template<Tracing T> template<Color Us, PieceType Pt>
258   Score Evaluation<T>::pieces() {
259
260     constexpr Color     Them = ~Us;
261     constexpr Direction Down = -pawn_push(Us);
262     constexpr Bitboard OutpostRanks = (Us == WHITE ? Rank4BB | Rank5BB | Rank6BB
263                                                    : Rank5BB | Rank4BB | Rank3BB);
264     const Square* pl = pos.squares<Pt>(Us);
265
266     Bitboard b, bb;
267     Score score = SCORE_ZERO;
268
269     attackedBy[Us][Pt] = 0;
270
271     for (Square s = *pl; s != SQ_NONE; s = *++pl)
272     {
273         // Find attacked squares, including x-ray attacks for bishops and rooks
274         b = Pt == BISHOP ? attacks_bb<BISHOP>(s, pos.pieces() ^ pos.pieces(QUEEN))
275           : Pt ==   ROOK ? attacks_bb<  ROOK>(s, pos.pieces() ^ pos.pieces(QUEEN) ^ pos.pieces(Us, ROOK))
276                          : attacks_bb<Pt>(s, pos.pieces());
277
278         if (pos.blockers_for_king(Us) & s)
279             b &= line_bb(pos.square<KING>(Us), s);
280
281         attackedBy2[Us] |= attackedBy[Us][ALL_PIECES] & b;
282         attackedBy[Us][Pt] |= b;
283         attackedBy[Us][ALL_PIECES] |= b;
284
285         if (b & kingRing[Them])
286         {
287             kingAttackersCount[Us]++;
288             kingAttackersWeight[Us] += KingAttackWeights[Pt];
289             kingAttacksCount[Us] += popcount(b & attackedBy[Them][KING]);
290         }
291
292         else if (Pt == ROOK && (file_bb(s) & kingRing[Them]))
293             score += RookOnKingRing;
294
295         else if (Pt == BISHOP && (attacks_bb<BISHOP>(s, pos.pieces(PAWN)) & kingRing[Them]))
296             score += BishopOnKingRing;
297
298         int mob = popcount(b & mobilityArea[Us]);
299
300         mobility[Us] += MobilityBonus[Pt - 2][mob];
301
302         if (Pt == BISHOP || Pt == KNIGHT)
303         {
304             // Bonus if piece is on an outpost square or can reach one
305             bb = OutpostRanks & attackedBy[Us][PAWN] & ~pe->pawn_attacks_span(Them);
306             if (bb & s)
307                 score += (Pt == KNIGHT) ? KnightOutpost : BishopOutpost;
308             else if (Pt == KNIGHT && bb & b & ~pos.pieces(Us))
309                 score += ReachableOutpost;
310
311             // Bonus for a knight or bishop shielded by pawn
312             if (shift<Down>(pos.pieces(PAWN)) & s)
313                 score += MinorBehindPawn;
314
315             // Penalty if the piece is far from the king
316             score -= (Pt == KNIGHT ? KnightKingProtector
317                                    : BishopKingProtector) * distance(pos.square<KING>(Us), s);
318
319             if (Pt == BISHOP)
320             {
321                 // Penalty according to the number of our pawns on the same color square as the
322                 // bishop, bigger when the center files are blocked with pawns and smaller
323                 // when the bishop is outside the pawn chain.
324                 Bitboard blocked = pos.pieces(Us, PAWN) & shift<Down>(pos.pieces());
325
326                 score -= BishopPawns * pos.pawns_on_same_color_squares(Us, s)
327                                      * (!(attackedBy[Us][PAWN] & s) + popcount(blocked & CenterFiles));
328
329                 // Penalty for all enemy pawns x-rayed
330                 score -= BishopXRayPawns * popcount(attacks_bb<BISHOP>(s) & pos.pieces(Them, PAWN));
331
332                 // Bonus for bishop on a long diagonal which can "see" both center squares
333                 if (more_than_one(attacks_bb<BISHOP>(s, pos.pieces(PAWN)) & Center))
334                     score += LongDiagonalBishop;
335
336                 // An important Chess960 pattern: a cornered bishop blocked by a friendly
337                 // pawn diagonally in front of it is a very serious problem, especially
338                 // when that pawn is also blocked.
339                 if (   pos.is_chess960()
340                     && (s == relative_square(Us, SQ_A1) || s == relative_square(Us, SQ_H1)))
341                 {
342                     Direction d = pawn_push(Us) + (file_of(s) == FILE_A ? EAST : WEST);
343                     if (pos.piece_on(s + d) == make_piece(Us, PAWN))
344                         score -= !pos.empty(s + d + pawn_push(Us))                ? CorneredBishop * 4
345                                 : pos.piece_on(s + d + d) == make_piece(Us, PAWN) ? CorneredBishop * 2
346                                                                                   : CorneredBishop;
347                 }
348             }
349         }
350
351         if (Pt == ROOK)
352         {
353             // Bonus for rook on the same file as a queen
354             if (file_bb(s) & pos.pieces(QUEEN))
355                 score += RookOnQueenFile;
356
357             // Bonus for rook on an open or semi-open file
358             if (pos.is_on_semiopen_file(Us, s))
359                 score += RookOnFile[pos.is_on_semiopen_file(Them, s)];
360
361             // Penalty when trapped by the king, even more if the king cannot castle
362             else if (mob <= 3)
363             {
364                 File kf = file_of(pos.square<KING>(Us));
365                 if ((kf < FILE_E) == (file_of(s) < kf))
366                     score -= TrappedRook * (1 + !pos.castling_rights(Us));
367             }
368         }
369
370         if (Pt == QUEEN)
371         {
372             // Penalty if any relative pin or discovered attack against the queen
373             Bitboard queenPinners;
374             if (pos.slider_blockers(pos.pieces(Them, ROOK, BISHOP), s, queenPinners))
375                 score -= WeakQueen;
376         }
377     }
378     if (T)
379         Trace::add(Pt, Us, score);
380
381     return score;
382   }
383
384
385   // Evaluation::king() assigns bonuses and penalties to a king of a given color
386   template<Tracing T> template<Color Us>
387   Score Evaluation<T>::king() const {
388
389     constexpr Color    Them = ~Us;
390     constexpr Bitboard Camp = (Us == WHITE ? AllSquares ^ Rank6BB ^ Rank7BB ^ Rank8BB
391                                            : AllSquares ^ Rank1BB ^ Rank2BB ^ Rank3BB);
392
393     Bitboard weak, b1, b2, b3, safe, unsafeChecks = 0;
394     Bitboard rookChecks, queenChecks, bishopChecks, knightChecks;
395     int kingDanger = 0;
396     const Square ksq = pos.square<KING>(Us);
397
398     // Init the score with king shelter and enemy pawns storm
399     Score score = pe->king_safety<Us>(pos);
400
401     // Attacked squares defended at most once by our queen or king
402     weak =  attackedBy[Them][ALL_PIECES]
403           & ~attackedBy2[Us]
404           & (~attackedBy[Us][ALL_PIECES] | attackedBy[Us][KING] | attackedBy[Us][QUEEN]);
405
406     // Analyse the safe enemy's checks which are possible on next move
407     safe  = ~pos.pieces(Them);
408     safe &= ~attackedBy[Us][ALL_PIECES] | (weak & attackedBy2[Them]);
409
410     b1 = attacks_bb<ROOK  >(ksq, pos.pieces() ^ pos.pieces(Us, QUEEN));
411     b2 = attacks_bb<BISHOP>(ksq, pos.pieces() ^ pos.pieces(Us, QUEEN));
412
413     // Enemy rooks checks
414     rookChecks = b1 & safe & attackedBy[Them][ROOK];
415     if (rookChecks)
416         kingDanger += more_than_one(rookChecks) ? RookSafeCheck * 175/100
417                                                 : RookSafeCheck;
418     else
419         unsafeChecks |= b1 & attackedBy[Them][ROOK];
420
421     // Enemy queen safe checks: we count them only if they are from squares from
422     // which we can't give a rook check, because rook checks are more valuable.
423     queenChecks =  (b1 | b2)
424                  & attackedBy[Them][QUEEN]
425                  & safe
426                  & ~attackedBy[Us][QUEEN]
427                  & ~rookChecks;
428     if (queenChecks)
429         kingDanger += more_than_one(queenChecks) ? QueenSafeCheck * 145/100
430                                                  : QueenSafeCheck;
431
432     // Enemy bishops checks: we count them only if they are from squares from
433     // which we can't give a queen check, because queen checks are more valuable.
434     bishopChecks =  b2
435                   & attackedBy[Them][BISHOP]
436                   & safe
437                   & ~queenChecks;
438     if (bishopChecks)
439         kingDanger += more_than_one(bishopChecks) ? BishopSafeCheck * 3/2
440                                                   : BishopSafeCheck;
441     else
442         unsafeChecks |= b2 & attackedBy[Them][BISHOP];
443
444     // Enemy knights checks
445     knightChecks = attacks_bb<KNIGHT>(ksq) & attackedBy[Them][KNIGHT];
446     if (knightChecks & safe)
447         kingDanger += more_than_one(knightChecks & safe) ? KnightSafeCheck * 162/100
448                                                          : KnightSafeCheck;
449     else
450         unsafeChecks |= knightChecks;
451
452     // Find the squares that opponent attacks in our king flank, the squares
453     // which they attack twice in that flank, and the squares that we defend.
454     b1 = attackedBy[Them][ALL_PIECES] & KingFlank[file_of(ksq)] & Camp;
455     b2 = b1 & attackedBy2[Them];
456     b3 = attackedBy[Us][ALL_PIECES] & KingFlank[file_of(ksq)] & Camp;
457
458     int kingFlankAttack = popcount(b1) + popcount(b2);
459     int kingFlankDefense = popcount(b3);
460
461     kingDanger +=        kingAttackersCount[Them] * kingAttackersWeight[Them]
462                  + 185 * popcount(kingRing[Us] & weak)
463                  + 148 * popcount(unsafeChecks)
464                  +  98 * popcount(pos.blockers_for_king(Us))
465                  +  69 * kingAttacksCount[Them]
466                  +   3 * kingFlankAttack * kingFlankAttack / 8
467                  +       mg_value(mobility[Them] - mobility[Us])
468                  - 873 * !pos.count<QUEEN>(Them)
469                  - 100 * bool(attackedBy[Us][KNIGHT] & attackedBy[Us][KING])
470                  -   6 * mg_value(score) / 8
471                  -   4 * kingFlankDefense
472                  +  37;
473
474     // Transform the kingDanger units into a Score, and subtract it from the evaluation
475     if (kingDanger > 100)
476         score -= make_score(kingDanger * kingDanger / 4096, kingDanger / 16);
477
478     // Penalty when our king is on a pawnless flank
479     if (!(pos.pieces(PAWN) & KingFlank[file_of(ksq)]))
480         score -= PawnlessFlank;
481
482     // Penalty if king flank is under attack, potentially moving toward the king
483     score -= FlankAttacks * kingFlankAttack;
484
485     if (T)
486         Trace::add(KING, Us, score);
487
488     return score;
489   }
490
491
492   // Evaluation::threats() assigns bonuses according to the types of the
493   // attacking and the attacked pieces.
494   template<Tracing T> template<Color Us>
495   Score Evaluation<T>::threats() const {
496
497     constexpr Color     Them     = ~Us;
498     constexpr Direction Up       = pawn_push(Us);
499     constexpr Bitboard  TRank3BB = (Us == WHITE ? Rank3BB : Rank6BB);
500
501     Bitboard b, weak, defended, nonPawnEnemies, stronglyProtected, safe;
502     Score score = SCORE_ZERO;
503
504     // Non-pawn enemies
505     nonPawnEnemies = pos.pieces(Them) & ~pos.pieces(PAWN);
506
507     // Squares strongly protected by the enemy, either because they defend the
508     // square with a pawn, or because they defend the square twice and we don't.
509     stronglyProtected =  attackedBy[Them][PAWN]
510                        | (attackedBy2[Them] & ~attackedBy2[Us]);
511
512     // Non-pawn enemies, strongly protected
513     defended = nonPawnEnemies & stronglyProtected;
514
515     // Enemies not strongly protected and under our attack
516     weak = pos.pieces(Them) & ~stronglyProtected & attackedBy[Us][ALL_PIECES];
517
518     // Bonus according to the kind of attacking pieces
519     if (defended | weak)
520     {
521         b = (defended | weak) & (attackedBy[Us][KNIGHT] | attackedBy[Us][BISHOP]);
522         while (b)
523             score += ThreatByMinor[type_of(pos.piece_on(pop_lsb(&b)))];
524
525         b = weak & attackedBy[Us][ROOK];
526         while (b)
527             score += ThreatByRook[type_of(pos.piece_on(pop_lsb(&b)))];
528
529         if (weak & attackedBy[Us][KING])
530             score += ThreatByKing;
531
532         b =  ~attackedBy[Them][ALL_PIECES]
533            | (nonPawnEnemies & attackedBy2[Us]);
534         score += Hanging * popcount(weak & b);
535
536         // Additional bonus if weak piece is only protected by a queen
537         score += WeakQueenProtection * popcount(weak & attackedBy[Them][QUEEN]);
538     }
539
540     // Bonus for restricting their piece moves
541     b =   attackedBy[Them][ALL_PIECES]
542        & ~stronglyProtected
543        &  attackedBy[Us][ALL_PIECES];
544     score += RestrictedPiece * popcount(b);
545
546     // Protected or unattacked squares
547     safe = ~attackedBy[Them][ALL_PIECES] | attackedBy[Us][ALL_PIECES];
548
549     // Bonus for attacking enemy pieces with our relatively safe pawns
550     b = pos.pieces(Us, PAWN) & safe;
551     b = pawn_attacks_bb<Us>(b) & nonPawnEnemies;
552     score += ThreatBySafePawn * popcount(b);
553
554     // Find squares where our pawns can push on the next move
555     b  = shift<Up>(pos.pieces(Us, PAWN)) & ~pos.pieces();
556     b |= shift<Up>(b & TRank3BB) & ~pos.pieces();
557
558     // Keep only the squares which are relatively safe
559     b &= ~attackedBy[Them][PAWN] & safe;
560
561     // Bonus for safe pawn threats on the next move
562     b = pawn_attacks_bb<Us>(b) & nonPawnEnemies;
563     score += ThreatByPawnPush * popcount(b);
564
565     // Bonus for threats on the next moves against enemy queen
566     if (pos.count<QUEEN>(Them) == 1)
567     {
568         Square s = pos.square<QUEEN>(Them);
569         safe = mobilityArea[Us] & ~stronglyProtected;
570
571         b = attackedBy[Us][KNIGHT] & attacks_bb<KNIGHT>(s);
572
573         score += KnightOnQueen * popcount(b & safe);
574
575         b =  (attackedBy[Us][BISHOP] & attacks_bb<BISHOP>(s, pos.pieces()))
576            | (attackedBy[Us][ROOK  ] & attacks_bb<ROOK  >(s, pos.pieces()));
577
578         score += SliderOnQueen * popcount(b & safe & attackedBy2[Us]);
579     }
580
581     if (T)
582         Trace::add(THREAT, Us, score);
583
584     return score;
585   }
586
587   // Evaluation::passed() evaluates the passed pawns and candidate passed
588   // pawns of the given color.
589
590   template<Tracing T> template<Color Us>
591   Score Evaluation<T>::passed() const {
592
593     constexpr Color     Them = ~Us;
594     constexpr Direction Up   = pawn_push(Us);
595     constexpr Direction Down = -Up;
596
597     auto king_proximity = [&](Color c, Square s) {
598       return std::min(distance(pos.square<KING>(c), s), 5);
599     };
600
601     Bitboard b, bb, squaresToQueen, unsafeSquares, blockedPassers, helpers;
602     Score score = SCORE_ZERO;
603
604     b = pe->passed_pawns(Us);
605
606     blockedPassers = b & shift<Down>(pos.pieces(Them, PAWN));
607     if (blockedPassers)
608     {
609         helpers =  shift<Up>(pos.pieces(Us, PAWN))
610                  & ~pos.pieces(Them)
611                  & (~attackedBy2[Them] | attackedBy[Us][ALL_PIECES]);
612
613         // Remove blocked candidate passers that don't have help to pass
614         b &=  ~blockedPassers
615             | shift<WEST>(helpers)
616             | shift<EAST>(helpers);
617     }
618
619     while (b)
620     {
621         Square s = pop_lsb(&b);
622
623         assert(!(pos.pieces(Them, PAWN) & forward_file_bb(Us, s + Up)));
624
625         int r = relative_rank(Us, s);
626
627         Score bonus = PassedRank[r];
628
629         if (r > RANK_3)
630         {
631             int w = 5 * r - 13;
632             Square blockSq = s + Up;
633
634             // Adjust bonus based on the king's proximity
635             bonus += make_score(0, (  (king_proximity(Them, blockSq) * 19) / 4
636                                      - king_proximity(Us,   blockSq) *  2) * w);
637
638             // If blockSq is not the queening square then consider also a second push
639             if (r != RANK_7)
640                 bonus -= make_score(0, king_proximity(Us, blockSq + Up) * w);
641
642             // If the pawn is free to advance, then increase the bonus
643             if (pos.empty(blockSq))
644             {
645                 squaresToQueen = forward_file_bb(Us, s);
646                 unsafeSquares = passed_pawn_span(Us, s);
647
648                 bb = forward_file_bb(Them, s) & pos.pieces(ROOK, QUEEN);
649
650                 if (!(pos.pieces(Them) & bb))
651                     unsafeSquares &= attackedBy[Them][ALL_PIECES];
652
653                 // If there are no enemy attacks on passed pawn span, assign a big bonus.
654                 // Otherwise assign a smaller bonus if the path to queen is not attacked
655                 // and even smaller bonus if it is attacked but block square is not.
656                 int k = !unsafeSquares                    ? 35 :
657                         !(unsafeSquares & squaresToQueen) ? 20 :
658                         !(unsafeSquares & blockSq)        ?  9 :
659                                                              0 ;
660
661                 // Assign a larger bonus if the block square is defended
662                 if ((pos.pieces(Us) & bb) || (attackedBy[Us][ALL_PIECES] & blockSq))
663                     k += 5;
664
665                 bonus += make_score(k * w, k * w);
666             }
667         } // r > RANK_3
668
669         score += bonus - PassedFile * edge_distance(file_of(s));
670     }
671
672     if (T)
673         Trace::add(PASSED, Us, score);
674
675     return score;
676   }
677
678
679   // Evaluation::space() computes the space evaluation for a given side. The
680   // space evaluation is a simple bonus based on the number of safe squares
681   // available for minor pieces on the central four files on ranks 2--4. Safe
682   // squares one, two or three squares behind a friendly pawn are counted
683   // twice. Finally, the space bonus is multiplied by a weight. The aim is to
684   // improve play on game opening.
685
686   template<Tracing T> template<Color Us>
687   Score Evaluation<T>::space() const {
688
689     if (pos.non_pawn_material() < SpaceThreshold)
690         return SCORE_ZERO;
691
692     constexpr Color Them     = ~Us;
693     constexpr Direction Down = -pawn_push(Us);
694     constexpr Bitboard SpaceMask =
695       Us == WHITE ? CenterFiles & (Rank2BB | Rank3BB | Rank4BB)
696                   : CenterFiles & (Rank7BB | Rank6BB | Rank5BB);
697
698     // Find the available squares for our pieces inside the area defined by SpaceMask
699     Bitboard safe =   SpaceMask
700                    & ~pos.pieces(Us, PAWN)
701                    & ~attackedBy[Them][PAWN];
702
703     // Find all squares which are at most three squares behind some friendly pawn
704     Bitboard behind = pos.pieces(Us, PAWN);
705     behind |= shift<Down>(behind);
706     behind |= shift<Down+Down>(behind);
707
708     int bonus = popcount(safe) + popcount(behind & safe & ~attackedBy[Them][ALL_PIECES]);
709     int weight = pos.count<ALL_PIECES>(Us) - 3 + std::min(pe->blocked_count(), 9);
710     Score score = make_score(bonus * weight * weight / 16, 0);
711
712     if (T)
713         Trace::add(SPACE, Us, score);
714
715     return score;
716   }
717
718
719   // Evaluation::winnable() adjusts the mg and eg score components based on the
720   // known attacking/defending status of the players.
721   // A single value is derived from the mg and eg values and returned.
722
723   template<Tracing T>
724   Value Evaluation<T>::winnable(Score score) const {
725
726     int outflanking =  distance<File>(pos.square<KING>(WHITE), pos.square<KING>(BLACK))
727                      - distance<Rank>(pos.square<KING>(WHITE), pos.square<KING>(BLACK));
728
729     bool pawnsOnBothFlanks =   (pos.pieces(PAWN) & QueenSide)
730                             && (pos.pieces(PAWN) & KingSide);
731
732     bool almostUnwinnable =   outflanking < 0
733                            && !pawnsOnBothFlanks;
734
735     bool infiltration = rank_of(pos.square<KING>(WHITE)) > RANK_4
736                      || rank_of(pos.square<KING>(BLACK)) < RANK_5;
737
738     // Compute the initiative bonus for the attacking side
739     int complexity =   9 * pe->passed_count()
740                     + 12 * pos.count<PAWN>()
741                     +  9 * outflanking
742                     + 21 * pawnsOnBothFlanks
743                     + 24 * infiltration
744                     + 51 * !pos.non_pawn_material()
745                     - 43 * almostUnwinnable
746                     -110 ;
747
748     Value mg = mg_value(score);
749     Value eg = eg_value(score);
750
751     // Now apply the bonus: note that we find the attacking side by extracting the
752     // sign of the midgame or endgame values, and that we carefully cap the bonus
753     // so that the midgame and endgame scores do not change sign after the bonus.
754     int u = ((mg > 0) - (mg < 0)) * Utility::clamp(complexity + 50, -abs(mg), 0);
755     int v = ((eg > 0) - (eg < 0)) * std::max(complexity, -abs(eg));
756
757     mg += u;
758     eg += v;
759
760     // Compute the scale factor for the winning side
761
762     Color strongSide = eg > VALUE_DRAW ? WHITE : BLACK;
763     int sf = me->scale_factor(pos, strongSide);
764
765     // If scale is not already specific, scale down the endgame via general heuristics
766     if (sf == SCALE_FACTOR_NORMAL)
767     {
768         if (pos.opposite_bishops())
769         {
770             if (   pos.non_pawn_material(WHITE) == BishopValueMg
771                 && pos.non_pawn_material(BLACK) == BishopValueMg)
772                 sf = 18 + 4 * popcount(pe->passed_pawns(strongSide));
773             else
774                 sf = 22 + 3 * pos.count<ALL_PIECES>(strongSide);
775         }
776         else
777             sf = std::min(sf, 36 + 7 * pos.count<PAWN>(strongSide));
778     }
779
780     // Interpolate between the middlegame and (scaled by 'sf') endgame score
781     v =  mg * int(me->game_phase())
782        + eg * int(PHASE_MIDGAME - me->game_phase()) * ScaleFactor(sf) / SCALE_FACTOR_NORMAL;
783     v /= PHASE_MIDGAME;
784
785     if (T)
786     {
787         Trace::add(WINNABLE, make_score(u, eg * ScaleFactor(sf) / SCALE_FACTOR_NORMAL - eg_value(score)));
788         Trace::add(TOTAL, make_score(mg, eg * ScaleFactor(sf) / SCALE_FACTOR_NORMAL));
789     }
790
791     return Value(v);
792   }
793
794
795   // Evaluation::value() is the main function of the class. It computes the various
796   // parts of the evaluation and returns the value of the position from the point
797   // of view of the side to move.
798
799   template<Tracing T>
800   Value Evaluation<T>::value() {
801
802     assert(!pos.checkers());
803
804     // Probe the material hash table
805     me = Material::probe(pos);
806
807     // If we have a specialized evaluation function for the current material
808     // configuration, call it and return.
809     if (me->specialized_eval_exists())
810         return me->evaluate(pos);
811
812     // Initialize score by reading the incrementally updated scores included in
813     // the position object (material + piece square tables) and the material
814     // imbalance. Score is computed internally from the white point of view.
815     Score score = pos.psq_score() + me->imbalance() + pos.this_thread()->contempt;
816
817     // Probe the pawn hash table
818     pe = Pawns::probe(pos);
819     score += pe->pawn_score(WHITE) - pe->pawn_score(BLACK);
820
821     // Early exit if score is high
822     Value v = (mg_value(score) + eg_value(score)) / 2;
823     if (abs(v) > LazyThreshold + pos.non_pawn_material() / 64)
824        return pos.side_to_move() == WHITE ? v : -v;
825
826     // Main evaluation begins here
827
828     initialize<WHITE>();
829     initialize<BLACK>();
830
831     // Pieces evaluated first (also populates attackedBy, attackedBy2).
832     // Note that the order of evaluation of the terms is left unspecified
833     score +=  pieces<WHITE, KNIGHT>() - pieces<BLACK, KNIGHT>()
834             + pieces<WHITE, BISHOP>() - pieces<BLACK, BISHOP>()
835             + pieces<WHITE, ROOK  >() - pieces<BLACK, ROOK  >()
836             + pieces<WHITE, QUEEN >() - pieces<BLACK, QUEEN >();
837
838     score += mobility[WHITE] - mobility[BLACK];
839
840     // More complex interactions that require fully populated attack bitboards
841     score +=  king<   WHITE>() - king<   BLACK>()
842             + threats<WHITE>() - threats<BLACK>()
843             + passed< WHITE>() - passed< BLACK>()
844             + space<  WHITE>() - space<  BLACK>();
845
846     // Derive single value from mg and eg parts of score
847     v = winnable(score);
848
849     // In case of tracing add all remaining individual evaluation terms
850     if (T)
851     {
852         Trace::add(MATERIAL, pos.psq_score());
853         Trace::add(IMBALANCE, me->imbalance());
854         Trace::add(PAWN, pe->pawn_score(WHITE), pe->pawn_score(BLACK));
855         Trace::add(MOBILITY, mobility[WHITE], mobility[BLACK]);
856     }
857
858     // Side to move point of view
859     v = (pos.side_to_move() == WHITE ? v : -v) + Tempo;
860
861     // Damp down the evaluation linearly when shuffling
862     v = v * (100 - pos.rule50_count()) / 100;
863
864     return v;
865   }
866
867 } // namespace
868
869
870 /// evaluate() is the evaluator for the outer world. It returns a static
871 /// evaluation of the position from the point of view of the side to move.
872
873 Value Eval::evaluate(const Position& pos) {
874   return Evaluation<NO_TRACE>(pos).value();
875 }
876
877
878 /// trace() is like evaluate(), but instead of returning a value, it returns
879 /// a string (suitable for outputting to stdout) that contains the detailed
880 /// descriptions and values of each evaluation term. Useful for debugging.
881
882 std::string Eval::trace(const Position& pos) {
883
884   if (pos.checkers())
885       return "Total evaluation: none (in check)";
886
887   std::memset(scores, 0, sizeof(scores));
888
889   pos.this_thread()->contempt = SCORE_ZERO; // Reset any dynamic contempt
890
891   Value v = Evaluation<TRACE>(pos).value();
892
893   v = pos.side_to_move() == WHITE ? v : -v; // Trace scores are from white's point of view
894
895   std::stringstream ss;
896   ss << std::showpoint << std::noshowpos << std::fixed << std::setprecision(2)
897      << "     Term    |    White    |    Black    |    Total   \n"
898      << "             |   MG    EG  |   MG    EG  |   MG    EG \n"
899      << " ------------+-------------+-------------+------------\n"
900      << "    Material | " << Term(MATERIAL)
901      << "   Imbalance | " << Term(IMBALANCE)
902      << "       Pawns | " << Term(PAWN)
903      << "     Knights | " << Term(KNIGHT)
904      << "     Bishops | " << Term(BISHOP)
905      << "       Rooks | " << Term(ROOK)
906      << "      Queens | " << Term(QUEEN)
907      << "    Mobility | " << Term(MOBILITY)
908      << " King safety | " << Term(KING)
909      << "     Threats | " << Term(THREAT)
910      << "      Passed | " << Term(PASSED)
911      << "       Space | " << Term(SPACE)
912      << "    Winnable | " << Term(WINNABLE)
913      << " ------------+-------------+-------------+------------\n"
914      << "       Total | " << Term(TOTAL);
915
916   ss << "\nFinal evaluation: " << to_cp(v) << " (white side)\n";
917
918   return ss.str();
919 }