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