Add eval cache infrastructure
[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-2012 Marco Costalba, Joona Kiiski, Tord Romstad
5
6   Stockfish is free software: you can redistribute it and/or modify
7   it under the terms of the GNU General Public License as published by
8   the Free Software Foundation, either version 3 of the License, or
9   (at your option) any later version.
10
11   Stockfish is distributed in the hope that it will be useful,
12   but WITHOUT ANY WARRANTY; without even the implied warranty of
13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   GNU General Public License for more details.
15
16   You should have received a copy of the GNU General Public License
17   along with this program.  If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include <cassert>
21 #include <iomanip>
22 #include <sstream>
23 #include <algorithm>
24
25 #include "bitcount.h"
26 #include "evaluate.h"
27 #include "material.h"
28 #include "pawns.h"
29 #include "thread.h"
30 #include "ucioption.h"
31
32 namespace {
33
34   // Struct EvalInfo contains various information computed and collected
35   // by the evaluation functions.
36   struct EvalInfo {
37
38     // Pointers to material and pawn hash table entries
39     MaterialEntry* mi;
40     PawnEntry* pi;
41
42     // attackedBy[color][piece type] is a bitboard representing all squares
43     // attacked by a given color and piece type, attackedBy[color][0] contains
44     // all squares attacked by the given color.
45     Bitboard attackedBy[COLOR_NB][PIECE_TYPE_NB];
46
47     // kingRing[color] is the zone around the king which is considered
48     // by the king safety evaluation. This consists of the squares directly
49     // adjacent to the king, and the three (or two, for a king on an edge file)
50     // squares two ranks in front of the king. For instance, if black's king
51     // is on g8, kingRing[BLACK] is a bitboard containing the squares f8, h8,
52     // f7, g7, h7, f6, g6 and h6.
53     Bitboard kingRing[COLOR_NB];
54
55     // kingAttackersCount[color] is the number of pieces of the given color
56     // which attack a square in the kingRing of the enemy king.
57     int kingAttackersCount[COLOR_NB];
58
59     // kingAttackersWeight[color] is the sum of the "weight" of the pieces of the
60     // given color which attack a square in the kingRing of the enemy king. The
61     // weights of the individual piece types are given by the variables
62     // QueenAttackWeight, RookAttackWeight, BishopAttackWeight and
63     // KnightAttackWeight in evaluate.cpp
64     int kingAttackersWeight[COLOR_NB];
65
66     // kingAdjacentZoneAttacksCount[color] is the number of attacks to squares
67     // directly adjacent to the king of the given color. Pieces which attack
68     // more than one square are counted multiple times. For instance, if black's
69     // king is on g8 and there's a white knight on g5, this knight adds
70     // 2 to kingAdjacentZoneAttacksCount[BLACK].
71     int kingAdjacentZoneAttacksCount[COLOR_NB];
72   };
73
74   // Evaluation grain size, must be a power of 2
75   const int GrainSize = 8;
76
77   // Evaluation weights, initialized from UCI options
78   enum { Mobility, PassedPawns, Space, KingDangerUs, KingDangerThem };
79   Score Weights[6];
80
81   typedef Value V;
82   #define S(mg, eg) make_score(mg, eg)
83
84   // Internal evaluation weights. These are applied on top of the evaluation
85   // weights read from UCI parameters. The purpose is to be able to change
86   // the evaluation weights while keeping the default values of the UCI
87   // parameters at 100, which looks prettier.
88   //
89   // Values modified by Joona Kiiski
90   const Score WeightsInternal[] = {
91       S(252, 344), S(216, 266), S(46, 0), S(247, 0), S(259, 0)
92   };
93
94   // MobilityBonus[PieceType][attacked] contains mobility bonuses for middle and
95   // end game, indexed by piece type and number of attacked squares not occupied
96   // by friendly pieces.
97   const Score MobilityBonus[][32] = {
98      {}, {},
99      { S(-38,-33), S(-25,-23), S(-12,-13), S( 0, -3), S(12,  7), S(25, 17), // Knights
100        S( 31, 22), S( 38, 27), S( 38, 27) },
101      { S(-25,-30), S(-11,-16), S(  3, -2), S(17, 12), S(31, 26), S(45, 40), // Bishops
102        S( 57, 52), S( 65, 60), S( 71, 65), S(74, 69), S(76, 71), S(78, 73),
103        S( 79, 74), S( 80, 75), S( 81, 76), S(81, 76) },
104      { S(-20,-36), S(-14,-19), S( -8, -3), S(-2, 13), S( 4, 29), S(10, 46), // Rooks
105        S( 14, 62), S( 19, 79), S( 23, 95), S(26,106), S(27,111), S(28,114),
106        S( 29,116), S( 30,117), S( 31,118), S(32,118) },
107      { S(-10,-18), S( -8,-13), S( -6, -7), S(-3, -2), S(-1,  3), S( 1,  8), // Queens
108        S(  3, 13), S(  5, 19), S(  8, 23), S(10, 27), S(12, 32), S(15, 34),
109        S( 16, 35), S( 17, 35), S( 18, 35), S(20, 35), S(20, 35), S(20, 35),
110        S( 20, 35), S( 20, 35), S( 20, 35), S(20, 35), S(20, 35), S(20, 35),
111        S( 20, 35), S( 20, 35), S( 20, 35), S(20, 35), S(20, 35), S(20, 35),
112        S( 20, 35), S( 20, 35) }
113   };
114
115   // OutpostBonus[PieceType][Square] contains outpost bonuses of knights and
116   // bishops, indexed by piece type and square (from white's point of view).
117   const Value OutpostBonus[][SQUARE_NB] = {
118   {
119   //  A     B     C     D     E     F     G     H
120     V(0), V(0), V(0), V(0), V(0), V(0), V(0), V(0), // Knights
121     V(0), V(0), V(0), V(0), V(0), V(0), V(0), V(0),
122     V(0), V(0), V(4), V(8), V(8), V(4), V(0), V(0),
123     V(0), V(4),V(17),V(26),V(26),V(17), V(4), V(0),
124     V(0), V(8),V(26),V(35),V(35),V(26), V(8), V(0),
125     V(0), V(4),V(17),V(17),V(17),V(17), V(4), V(0) },
126   {
127     V(0), V(0), V(0), V(0), V(0), V(0), V(0), V(0), // Bishops
128     V(0), V(0), V(0), V(0), V(0), V(0), V(0), V(0),
129     V(0), V(0), V(5), V(5), V(5), V(5), V(0), V(0),
130     V(0), V(5),V(10),V(10),V(10),V(10), V(5), V(0),
131     V(0),V(10),V(21),V(21),V(21),V(21),V(10), V(0),
132     V(0), V(5), V(8), V(8), V(8), V(8), V(5), V(0) }
133   };
134
135   // ThreatBonus[attacking][attacked] contains threat bonuses according to
136   // which piece type attacks which one.
137   const Score ThreatBonus[][PIECE_TYPE_NB] = {
138     {}, {},
139     { S(0, 0), S( 7, 39), S( 0,  0), S(24, 49), S(41,100), S(41,100) }, // KNIGHT
140     { S(0, 0), S( 7, 39), S(24, 49), S( 0,  0), S(41,100), S(41,100) }, // BISHOP
141     { S(0, 0), S( 0, 22), S(15, 49), S(15, 49), S( 0,  0), S(24, 49) }, // ROOK
142     { S(0, 0), S(15, 39), S(15, 39), S(15, 39), S(15, 39), S( 0,  0) }  // QUEEN
143   };
144
145   // ThreatenedByPawnPenalty[PieceType] contains a penalty according to which
146   // piece type is attacked by an enemy pawn.
147   const Score ThreatenedByPawnPenalty[] = {
148     S(0, 0), S(0, 0), S(56, 70), S(56, 70), S(76, 99), S(86, 118)
149   };
150
151   #undef S
152
153   // Bonus for having the side to move (modified by Joona Kiiski)
154   const Score Tempo = make_score(24, 11);
155
156   // Rooks and queens on the 7th rank
157   const Score RookOn7thBonus  = make_score(3, 20);
158   const Score QueenOn7thBonus = make_score(1,  8);
159
160   // Rooks and queens attacking pawns on the same rank
161   const Score RookOnPawnBonus  = make_score(3, 48);
162   const Score QueenOnPawnBonus = make_score(1, 40);
163
164   // Rooks on open files (modified by Joona Kiiski)
165   const Score RookOpenFileBonus     = make_score(43, 21);
166   const Score RookHalfOpenFileBonus = make_score(19, 10);
167
168   // Penalty for rooks trapped inside a friendly king which has lost the
169   // right to castle.
170   const Value TrappedRookPenalty = Value(180);
171
172   // Penalty for a bishop on a1/h1 (a8/h8 for black) which is trapped by
173   // a friendly pawn on b2/g2 (b7/g7 for black). This can obviously only
174   // happen in Chess960 games.
175   const Score TrappedBishopA1H1Penalty = make_score(100, 100);
176
177   // Penalty for an undefended bishop or knight
178   const Score UndefendedMinorPenalty = make_score(25, 10);
179
180   // The SpaceMask[Color] contains the area of the board which is considered
181   // by the space evaluation. In the middle game, each side is given a bonus
182   // based on how many squares inside this area are safe and available for
183   // friendly minor pieces.
184   const Bitboard SpaceMask[] = {
185     (1ULL << SQ_C2) | (1ULL << SQ_D2) | (1ULL << SQ_E2) | (1ULL << SQ_F2) |
186     (1ULL << SQ_C3) | (1ULL << SQ_D3) | (1ULL << SQ_E3) | (1ULL << SQ_F3) |
187     (1ULL << SQ_C4) | (1ULL << SQ_D4) | (1ULL << SQ_E4) | (1ULL << SQ_F4),
188     (1ULL << SQ_C7) | (1ULL << SQ_D7) | (1ULL << SQ_E7) | (1ULL << SQ_F7) |
189     (1ULL << SQ_C6) | (1ULL << SQ_D6) | (1ULL << SQ_E6) | (1ULL << SQ_F6) |
190     (1ULL << SQ_C5) | (1ULL << SQ_D5) | (1ULL << SQ_E5) | (1ULL << SQ_F5)
191   };
192
193   // King danger constants and variables. The king danger scores are taken
194   // from the KingDangerTable[]. Various little "meta-bonuses" measuring
195   // the strength of the enemy attack are added up into an integer, which
196   // is used as an index to KingDangerTable[].
197   //
198   // KingAttackWeights[PieceType] contains king attack weights by piece type
199   const int KingAttackWeights[] = { 0, 0, 2, 2, 3, 5 };
200
201   // Bonuses for enemy's safe checks
202   const int QueenContactCheckBonus = 6;
203   const int RookContactCheckBonus  = 4;
204   const int QueenCheckBonus        = 3;
205   const int RookCheckBonus         = 2;
206   const int BishopCheckBonus       = 1;
207   const int KnightCheckBonus       = 1;
208
209   // InitKingDanger[Square] contains penalties based on the position of the
210   // defending king, indexed by king's square (from white's point of view).
211   const int InitKingDanger[] = {
212      2,  0,  2,  5,  5,  2,  0,  2,
213      2,  2,  4,  8,  8,  4,  2,  2,
214      7, 10, 12, 12, 12, 12, 10,  7,
215     15, 15, 15, 15, 15, 15, 15, 15,
216     15, 15, 15, 15, 15, 15, 15, 15,
217     15, 15, 15, 15, 15, 15, 15, 15,
218     15, 15, 15, 15, 15, 15, 15, 15,
219     15, 15, 15, 15, 15, 15, 15, 15
220   };
221
222   // KingDangerTable[Color][attackUnits] contains the actual king danger
223   // weighted scores, indexed by color and by a calculated integer number.
224   Score KingDangerTable[COLOR_NB][128];
225
226   // TracedTerms[Color][PieceType || TracedType] contains a breakdown of the
227   // evaluation terms, used when tracing.
228   Score TracedScores[COLOR_NB][16];
229   std::stringstream TraceStream;
230
231   enum TracedType {
232     PST = 8, IMBALANCE = 9, MOBILITY = 10, THREAT = 11,
233     PASSED = 12, UNSTOPPABLE = 13, SPACE = 14, TOTAL = 15
234   };
235
236   // Function prototypes
237   template<bool Trace>
238   Value do_evaluate(const Position& pos, Value& margin);
239
240   template<Color Us>
241   void init_eval_info(const Position& pos, EvalInfo& ei);
242
243   template<Color Us, bool Trace>
244   Score evaluate_pieces_of_color(const Position& pos, EvalInfo& ei, Score& mobility);
245
246   template<Color Us, bool Trace>
247   Score evaluate_king(const Position& pos, EvalInfo& ei, int16_t margins[]);
248
249   template<Color Us>
250   Score evaluate_threats(const Position& pos, EvalInfo& ei);
251
252   template<Color Us>
253   int evaluate_space(const Position& pos, EvalInfo& ei);
254
255   template<Color Us>
256   Score evaluate_passed_pawns(const Position& pos, EvalInfo& ei);
257
258   Score evaluate_unstoppable_pawns(const Position& pos, EvalInfo& ei);
259
260   Value interpolate(const Score& v, Phase ph, ScaleFactor sf);
261   Score weight_option(const std::string& mgOpt, const std::string& egOpt, Score internalWeight);
262   double to_cp(Value v);
263   void trace_add(int idx, Score term_w, Score term_b = SCORE_ZERO);
264   void trace_row(const char* name, int idx);
265 }
266
267
268 namespace Eval {
269
270   /// evaluate() is the main evaluation function. It always computes two
271   /// values, an endgame score and a middle game score, and interpolates
272   /// between them based on the remaining material.
273
274   Value evaluate(const Position& pos, Value& margin) {
275     return do_evaluate<false>(pos, margin);
276   }
277
278
279   /// init() computes evaluation weights from the corresponding UCI parameters
280   /// and setup king tables.
281
282   void init() {
283
284     Weights[Mobility]       = weight_option("Mobility (Middle Game)", "Mobility (Endgame)", WeightsInternal[Mobility]);
285     Weights[PassedPawns]    = weight_option("Passed Pawns (Middle Game)", "Passed Pawns (Endgame)", WeightsInternal[PassedPawns]);
286     Weights[Space]          = weight_option("Space", "Space", WeightsInternal[Space]);
287     Weights[KingDangerUs]   = weight_option("Cowardice", "Cowardice", WeightsInternal[KingDangerUs]);
288     Weights[KingDangerThem] = weight_option("Aggressiveness", "Aggressiveness", WeightsInternal[KingDangerThem]);
289
290     // King safety is asymmetrical. Our king danger level is weighted by
291     // "Cowardice" UCI parameter, instead the opponent one by "Aggressiveness".
292     // If running in analysis mode, make sure we use symmetrical king safety. We
293     // do this by replacing both Weights[kingDangerUs] and Weights[kingDangerThem]
294     // by their average.
295     if (Options["UCI_AnalyseMode"])
296         Weights[KingDangerUs] = Weights[KingDangerThem] = (Weights[KingDangerUs] + Weights[KingDangerThem]) / 2;
297
298     const int MaxSlope = 30;
299     const int Peak = 1280;
300
301     for (int t = 0, i = 1; i < 100; i++)
302     {
303         t = std::min(Peak, std::min(int(0.4 * i * i), t + MaxSlope));
304
305         KingDangerTable[1][i] = apply_weight(make_score(t, 0), Weights[KingDangerUs]);
306         KingDangerTable[0][i] = apply_weight(make_score(t, 0), Weights[KingDangerThem]);
307     }
308   }
309
310
311   /// trace() is like evaluate() but instead of a value returns a string suitable
312   /// to be print on stdout with the detailed descriptions and values of each
313   /// evaluation term. Used mainly for debugging.
314
315   std::string trace(const Position& pos) {
316
317     Value margin;
318     std::string totals;
319
320     Search::RootColor = pos.side_to_move();
321
322     TraceStream.str("");
323     TraceStream << std::showpoint << std::showpos << std::fixed << std::setprecision(2);
324     memset(TracedScores, 0, 2 * 16 * sizeof(Score));
325
326     do_evaluate<true>(pos, margin);
327
328     totals = TraceStream.str();
329     TraceStream.str("");
330
331     TraceStream << std::setw(21) << "Eval term " << "|    White    |    Black    |     Total     \n"
332                 <<             "                     |   MG    EG  |   MG    EG  |   MG     EG   \n"
333                 <<             "---------------------+-------------+-------------+---------------\n";
334
335     trace_row("Material, PST, Tempo", PST);
336     trace_row("Material imbalance", IMBALANCE);
337     trace_row("Pawns", PAWN);
338     trace_row("Knights", KNIGHT);
339     trace_row("Bishops", BISHOP);
340     trace_row("Rooks", ROOK);
341     trace_row("Queens", QUEEN);
342     trace_row("Mobility", MOBILITY);
343     trace_row("King safety", KING);
344     trace_row("Threats", THREAT);
345     trace_row("Passed pawns", PASSED);
346     trace_row("Unstoppable pawns", UNSTOPPABLE);
347     trace_row("Space", SPACE);
348
349     TraceStream <<             "---------------------+-------------+-------------+---------------\n";
350     trace_row("Total", TOTAL);
351     TraceStream << totals;
352
353     return TraceStream.str();
354   }
355
356 } // namespace Eval
357
358
359 namespace {
360
361 template<bool Trace>
362 Value do_evaluate(const Position& pos, Value& margin) {
363
364   assert(!pos.in_check());
365
366   EvalInfo ei;
367   Score score, mobilityWhite, mobilityBlack;
368
369   Key key = pos.key();
370   Eval::Entry* e = pos.this_thread()->evalTable[key];
371
372   // If e->key matches the position's hash key, it means that we have analysed
373   // this node before, and we can simply return the information we found the last
374   // time instead of recomputing it.
375   if (e->key == key)
376   {
377       margin = Value(e->margins[pos.side_to_move()]);
378       return e->value;
379   }
380
381   // Otherwise we overwrite current content with this node info.
382   e->key = key;
383
384   // margins[] store the uncertainty estimation of position's evaluation
385   // that typically is used by the search for pruning decisions.
386   e->margins[WHITE] = e->margins[BLACK] = VALUE_ZERO;
387
388   // Initialize score by reading the incrementally updated scores included
389   // in the position object (material + piece square tables) and adding
390   // Tempo bonus. Score is computed from the point of view of white.
391   score = pos.psq_score() + (pos.side_to_move() == WHITE ? Tempo : -Tempo);
392
393   // Probe the material hash table
394   ei.mi = pos.this_thread()->materialTable.probe(pos);
395   score += ei.mi->material_value();
396
397   // If we have a specialized evaluation function for the current material
398   // configuration, call it and return.
399   if (ei.mi->specialized_eval_exists())
400   {
401       margin = VALUE_ZERO;
402       e->value = ei.mi->evaluate(pos);
403       return e->value;
404   }
405
406   // Probe the pawn hash table
407   ei.pi = pos.this_thread()->pawnTable.probe(pos);
408   score += ei.pi->pawns_value();
409
410   // Initialize attack and king safety bitboards
411   init_eval_info<WHITE>(pos, ei);
412   init_eval_info<BLACK>(pos, ei);
413
414   // Evaluate pieces and mobility
415   score +=  evaluate_pieces_of_color<WHITE, Trace>(pos, ei, mobilityWhite)
416           - evaluate_pieces_of_color<BLACK, Trace>(pos, ei, mobilityBlack);
417
418   score += apply_weight(mobilityWhite - mobilityBlack, Weights[Mobility]);
419
420   // Evaluate kings after all other pieces because we need complete attack
421   // information when computing the king safety evaluation.
422   score +=  evaluate_king<WHITE, Trace>(pos, ei, e->margins)
423           - evaluate_king<BLACK, Trace>(pos, ei, e->margins);
424
425   // Evaluate tactical threats, we need full attack information including king
426   score +=  evaluate_threats<WHITE>(pos, ei)
427           - evaluate_threats<BLACK>(pos, ei);
428
429   // Evaluate passed pawns, we need full attack information including king
430   score +=  evaluate_passed_pawns<WHITE>(pos, ei)
431           - evaluate_passed_pawns<BLACK>(pos, ei);
432
433   // If one side has only a king, check whether exists any unstoppable passed pawn
434   if (!pos.non_pawn_material(WHITE) || !pos.non_pawn_material(BLACK))
435       score += evaluate_unstoppable_pawns(pos, ei);
436
437   // Evaluate space for both sides, only in middle-game.
438   if (ei.mi->space_weight())
439   {
440       int s = evaluate_space<WHITE>(pos, ei) - evaluate_space<BLACK>(pos, ei);
441       score += apply_weight(make_score(s * ei.mi->space_weight(), 0), Weights[Space]);
442   }
443
444   // Scale winning side if position is more drawish that what it appears
445   ScaleFactor sf = eg_value(score) > VALUE_DRAW ? ei.mi->scale_factor(pos, WHITE)
446                                                 : ei.mi->scale_factor(pos, BLACK);
447
448   // If we don't already have an unusual scale factor, check for opposite
449   // colored bishop endgames, and use a lower scale for those.
450   if (   ei.mi->game_phase() < PHASE_MIDGAME
451       && pos.opposite_bishops()
452       && sf == SCALE_FACTOR_NORMAL)
453   {
454       // Only the two bishops ?
455       if (   pos.non_pawn_material(WHITE) == BishopValueMg
456           && pos.non_pawn_material(BLACK) == BishopValueMg)
457       {
458           // Check for KBP vs KB with only a single pawn that is almost
459           // certainly a draw or at least two pawns.
460           bool one_pawn = (pos.piece_count(WHITE, PAWN) + pos.piece_count(BLACK, PAWN) == 1);
461           sf = one_pawn ? ScaleFactor(8) : ScaleFactor(32);
462       }
463       else
464           // Endgame with opposite-colored bishops, but also other pieces. Still
465           // a bit drawish, but not as drawish as with only the two bishops.
466            sf = ScaleFactor(50);
467   }
468
469   margin = Value(e->margins[pos.side_to_move()]);
470   Value v = interpolate(score, ei.mi->game_phase(), sf);
471
472   // In case of tracing add all single evaluation contributions for both white and black
473   if (Trace)
474   {
475       trace_add(PST, pos.psq_score());
476       trace_add(IMBALANCE, ei.mi->material_value());
477       trace_add(PAWN, ei.pi->pawns_value());
478       trace_add(MOBILITY, apply_weight(mobilityWhite, Weights[Mobility]), apply_weight(mobilityBlack, Weights[Mobility]));
479       trace_add(THREAT, evaluate_threats<WHITE>(pos, ei), evaluate_threats<BLACK>(pos, ei));
480       trace_add(PASSED, evaluate_passed_pawns<WHITE>(pos, ei), evaluate_passed_pawns<BLACK>(pos, ei));
481       trace_add(UNSTOPPABLE, evaluate_unstoppable_pawns(pos, ei));
482       Score w = make_score(ei.mi->space_weight() * evaluate_space<WHITE>(pos, ei), 0);
483       Score b = make_score(ei.mi->space_weight() * evaluate_space<BLACK>(pos, ei), 0);
484       trace_add(SPACE, apply_weight(w, Weights[Space]), apply_weight(b, Weights[Space]));
485       trace_add(TOTAL, score);
486       TraceStream << "\nUncertainty margin: White: " << to_cp(Value(e->margins[WHITE]))
487                   << ", Black: " << to_cp(Value(e->margins[BLACK]))
488                   << "\nScaling: " << std::noshowpos
489                   << std::setw(6) << 100.0 * ei.mi->game_phase() / 128.0 << "% MG, "
490                   << std::setw(6) << 100.0 * (1.0 - ei.mi->game_phase() / 128.0) << "% * "
491                   << std::setw(6) << (100.0 * sf) / SCALE_FACTOR_NORMAL << "% EG.\n"
492                   << "Total evaluation: " << to_cp(v);
493   }
494
495   return e->value = pos.side_to_move() == WHITE ? v : -v;
496 }
497
498
499   // init_eval_info() initializes king bitboards for given color adding
500   // pawn attacks. To be done at the beginning of the evaluation.
501
502   template<Color Us>
503   void init_eval_info(const Position& pos, EvalInfo& ei) {
504
505     const Color Them = (Us == WHITE ? BLACK : WHITE);
506
507     Bitboard b = ei.attackedBy[Them][KING] = pos.attacks_from<KING>(pos.king_square(Them));
508     ei.attackedBy[Us][PAWN] = ei.pi->pawn_attacks(Us);
509
510     // Init king safety tables only if we are going to use them
511     if (   pos.piece_count(Us, QUEEN)
512         && pos.non_pawn_material(Us) >= QueenValueMg + RookValueMg)
513     {
514         ei.kingRing[Them] = (b | (Us == WHITE ? b >> 8 : b << 8));
515         b &= ei.attackedBy[Us][PAWN];
516         ei.kingAttackersCount[Us] = b ? popcount<Max15>(b) / 2 : 0;
517         ei.kingAdjacentZoneAttacksCount[Us] = ei.kingAttackersWeight[Us] = 0;
518     } else
519         ei.kingRing[Them] = ei.kingAttackersCount[Us] = 0;
520   }
521
522
523   // evaluate_outposts() evaluates bishop and knight outposts squares
524
525   template<PieceType Piece, Color Us>
526   Score evaluate_outposts(const Position& pos, EvalInfo& ei, Square s) {
527
528     const Color Them = (Us == WHITE ? BLACK : WHITE);
529
530     assert (Piece == BISHOP || Piece == KNIGHT);
531
532     // Initial bonus based on square
533     Value bonus = OutpostBonus[Piece == BISHOP][relative_square(Us, s)];
534
535     // Increase bonus if supported by pawn, especially if the opponent has
536     // no minor piece which can exchange the outpost piece.
537     if (bonus && (ei.attackedBy[Us][PAWN] & s))
538     {
539         if (   !pos.pieces(Them, KNIGHT)
540             && !(same_color_squares(s) & pos.pieces(Them, BISHOP)))
541             bonus += bonus + bonus / 2;
542         else
543             bonus += bonus / 2;
544     }
545     return make_score(bonus, bonus);
546   }
547
548
549   // evaluate_pieces<>() assigns bonuses and penalties to the pieces of a given color
550
551   template<PieceType Piece, Color Us, bool Trace>
552   Score evaluate_pieces(const Position& pos, EvalInfo& ei, Score& mobility, Bitboard mobilityArea) {
553
554     Bitboard b;
555     Square s, ksq;
556     int mob;
557     File f;
558     Score score = SCORE_ZERO;
559
560     const Color Them = (Us == WHITE ? BLACK : WHITE);
561     const Square* pl = pos.piece_list(Us, Piece);
562
563     ei.attackedBy[Us][Piece] = 0;
564
565     while ((s = *pl++) != SQ_NONE)
566     {
567         // Find attacked squares, including x-ray attacks for bishops and rooks
568         if (Piece == KNIGHT || Piece == QUEEN)
569             b = pos.attacks_from<Piece>(s);
570         else if (Piece == BISHOP)
571             b = attacks_bb<BISHOP>(s, pos.pieces() ^ pos.pieces(Us, QUEEN));
572         else if (Piece == ROOK)
573             b = attacks_bb<ROOK>(s, pos.pieces() ^ pos.pieces(Us, ROOK, QUEEN));
574         else
575             assert(false);
576
577         ei.attackedBy[Us][Piece] |= b;
578
579         if (b & ei.kingRing[Them])
580         {
581             ei.kingAttackersCount[Us]++;
582             ei.kingAttackersWeight[Us] += KingAttackWeights[Piece];
583             Bitboard bb = (b & ei.attackedBy[Them][KING]);
584             if (bb)
585                 ei.kingAdjacentZoneAttacksCount[Us] += popcount<Max15>(bb);
586         }
587
588         mob = (Piece != QUEEN ? popcount<Max15>(b & mobilityArea)
589                               : popcount<Full >(b & mobilityArea));
590
591         mobility += MobilityBonus[Piece][mob];
592
593         // Add a bonus if a slider is pinning an enemy piece
594         if (   (Piece == BISHOP || Piece == ROOK || Piece == QUEEN)
595             && (PseudoAttacks[Piece][pos.king_square(Them)] & s))
596         {
597             b = BetweenBB[s][pos.king_square(Them)] & pos.pieces();
598
599             assert(b);
600
601             if (!more_than_one(b) && (b & pos.pieces(Them)))
602                 score += ThreatBonus[Piece][type_of(pos.piece_on(lsb(b)))];
603         }
604
605         // Decrease score if we are attacked by an enemy pawn. Remaining part
606         // of threat evaluation must be done later when we have full attack info.
607         if (ei.attackedBy[Them][PAWN] & s)
608             score -= ThreatenedByPawnPenalty[Piece];
609
610         // Bishop and knight outposts squares
611         if (    (Piece == BISHOP || Piece == KNIGHT)
612             && !(pos.pieces(Them, PAWN) & attack_span_mask(Us, s)))
613             score += evaluate_outposts<Piece, Us>(pos, ei, s);
614
615         if ((Piece == ROOK || Piece == QUEEN) && relative_rank(Us, s) >= RANK_5)
616         {
617             // Major piece on 7th rank
618             if (   relative_rank(Us, s) == RANK_7
619                 && relative_rank(Us, pos.king_square(Them)) == RANK_8)
620                 score += (Piece == ROOK ? RookOn7thBonus : QueenOn7thBonus);
621
622             // Major piece attacking pawns on the same rank
623             Bitboard pawns = pos.pieces(Them, PAWN) & rank_bb(s);
624             if (pawns)
625                 score += (Piece == ROOK ? RookOnPawnBonus
626                                         : QueenOnPawnBonus) * popcount<Max15>(pawns);
627         }
628
629         // Special extra evaluation for bishops
630         if (Piece == BISHOP && pos.is_chess960())
631         {
632             // An important Chess960 pattern: A cornered bishop blocked by
633             // a friendly pawn diagonally in front of it is a very serious
634             // problem, especially when that pawn is also blocked.
635             if (s == relative_square(Us, SQ_A1) || s == relative_square(Us, SQ_H1))
636             {
637                 Square d = pawn_push(Us) + (file_of(s) == FILE_A ? DELTA_E : DELTA_W);
638                 if (pos.piece_on(s + d) == make_piece(Us, PAWN))
639                 {
640                     if (!pos.is_empty(s + d + pawn_push(Us)))
641                         score -= 2*TrappedBishopA1H1Penalty;
642                     else if (pos.piece_on(s + 2*d) == make_piece(Us, PAWN))
643                         score -= TrappedBishopA1H1Penalty;
644                     else
645                         score -= TrappedBishopA1H1Penalty / 2;
646                 }
647             }
648         }
649
650         // Special extra evaluation for rooks
651         if (Piece == ROOK)
652         {
653             // Open and half-open files
654             f = file_of(s);
655             if (ei.pi->file_is_half_open(Us, f))
656             {
657                 if (ei.pi->file_is_half_open(Them, f))
658                     score += RookOpenFileBonus;
659                 else
660                     score += RookHalfOpenFileBonus;
661             }
662
663             // Penalize rooks which are trapped inside a king. Penalize more if
664             // king has lost right to castle.
665             if (mob > 6 || ei.pi->file_is_half_open(Us, f))
666                 continue;
667
668             ksq = pos.king_square(Us);
669
670             if (    file_of(ksq) >= FILE_E
671                 &&  file_of(s) > file_of(ksq)
672                 && (relative_rank(Us, ksq) == RANK_1 || rank_of(ksq) == rank_of(s)))
673             {
674                 // Is there a half-open file between the king and the edge of the board?
675                 if (!ei.pi->has_open_file_to_right(Us, file_of(ksq)))
676                     score -= make_score(pos.can_castle(Us) ? (TrappedRookPenalty - mob * 16) / 2
677                                                            : (TrappedRookPenalty - mob * 16), 0);
678             }
679             else if (    file_of(ksq) <= FILE_D
680                      &&  file_of(s) < file_of(ksq)
681                      && (relative_rank(Us, ksq) == RANK_1 || rank_of(ksq) == rank_of(s)))
682             {
683                 // Is there a half-open file between the king and the edge of the board?
684                 if (!ei.pi->has_open_file_to_left(Us, file_of(ksq)))
685                     score -= make_score(pos.can_castle(Us) ? (TrappedRookPenalty - mob * 16) / 2
686                                                            : (TrappedRookPenalty - mob * 16), 0);
687             }
688         }
689     }
690
691     if (Trace)
692         TracedScores[Us][Piece] = score;
693
694     return score;
695   }
696
697
698   // evaluate_threats<>() assigns bonuses according to the type of attacking piece
699   // and the type of attacked one.
700
701   template<Color Us>
702   Score evaluate_threats(const Position& pos, EvalInfo& ei) {
703
704     const Color Them = (Us == WHITE ? BLACK : WHITE);
705
706     Bitboard b, undefendedMinors, weakEnemies;
707     Score score = SCORE_ZERO;
708
709     // Undefended minors get penalized even if not under attack
710     undefendedMinors =  pos.pieces(Them)
711                       & (pos.pieces(BISHOP) | pos.pieces(KNIGHT))
712                       & ~ei.attackedBy[Them][0];
713
714     if (undefendedMinors)
715         score += more_than_one(undefendedMinors) ? UndefendedMinorPenalty * 2
716                                                  : UndefendedMinorPenalty;
717
718     // Enemy pieces not defended by a pawn and under our attack
719     weakEnemies =  pos.pieces(Them)
720                  & ~ei.attackedBy[Them][PAWN]
721                  & ei.attackedBy[Us][0];
722
723     if (!weakEnemies)
724         return score;
725
726     // Add bonus according to type of attacked enemy piece and to the
727     // type of attacking piece, from knights to queens. Kings are not
728     // considered because are already handled in king evaluation.
729     for (PieceType pt1 = KNIGHT; pt1 < KING; pt1++)
730     {
731         b = ei.attackedBy[Us][pt1] & weakEnemies;
732         if (b)
733             for (PieceType pt2 = PAWN; pt2 < KING; pt2++)
734                 if (b & pos.pieces(pt2))
735                     score += ThreatBonus[pt1][pt2];
736     }
737     return score;
738   }
739
740
741   // evaluate_pieces_of_color<>() assigns bonuses and penalties to all the
742   // pieces of a given color.
743
744   template<Color Us, bool Trace>
745   Score evaluate_pieces_of_color(const Position& pos, EvalInfo& ei, Score& mobility) {
746
747     const Color Them = (Us == WHITE ? BLACK : WHITE);
748
749     Score score = mobility = SCORE_ZERO;
750
751     // Do not include in mobility squares protected by enemy pawns or occupied by our pieces
752     const Bitboard mobilityArea = ~(ei.attackedBy[Them][PAWN] | pos.pieces(Us));
753
754     score += evaluate_pieces<KNIGHT, Us, Trace>(pos, ei, mobility, mobilityArea);
755     score += evaluate_pieces<BISHOP, Us, Trace>(pos, ei, mobility, mobilityArea);
756     score += evaluate_pieces<ROOK,   Us, Trace>(pos, ei, mobility, mobilityArea);
757     score += evaluate_pieces<QUEEN,  Us, Trace>(pos, ei, mobility, mobilityArea);
758
759     // Sum up all attacked squares
760     ei.attackedBy[Us][0] =   ei.attackedBy[Us][PAWN]   | ei.attackedBy[Us][KNIGHT]
761                            | ei.attackedBy[Us][BISHOP] | ei.attackedBy[Us][ROOK]
762                            | ei.attackedBy[Us][QUEEN]  | ei.attackedBy[Us][KING];
763     return score;
764   }
765
766
767   // evaluate_king<>() assigns bonuses and penalties to a king of a given color
768
769   template<Color Us, bool Trace>
770   Score evaluate_king(const Position& pos, EvalInfo& ei, int16_t margins[]) {
771
772     const Color Them = (Us == WHITE ? BLACK : WHITE);
773
774     Bitboard undefended, b, b1, b2, safe;
775     int attackUnits;
776     const Square ksq = pos.king_square(Us);
777
778     // King shelter and enemy pawns storm
779     Score score = ei.pi->king_safety<Us>(pos, ksq);
780
781     // King safety. This is quite complicated, and is almost certainly far
782     // from optimally tuned.
783     if (   ei.kingAttackersCount[Them] >= 2
784         && ei.kingAdjacentZoneAttacksCount[Them])
785     {
786         // Find the attacked squares around the king which has no defenders
787         // apart from the king itself
788         undefended = ei.attackedBy[Them][0] & ei.attackedBy[Us][KING];
789         undefended &= ~(  ei.attackedBy[Us][PAWN]   | ei.attackedBy[Us][KNIGHT]
790                         | ei.attackedBy[Us][BISHOP] | ei.attackedBy[Us][ROOK]
791                         | ei.attackedBy[Us][QUEEN]);
792
793         // Initialize the 'attackUnits' variable, which is used later on as an
794         // index to the KingDangerTable[] array. The initial value is based on
795         // the number and types of the enemy's attacking pieces, the number of
796         // attacked and undefended squares around our king, the square of the
797         // king, and the quality of the pawn shelter.
798         attackUnits =  std::min(25, (ei.kingAttackersCount[Them] * ei.kingAttackersWeight[Them]) / 2)
799                      + 3 * (ei.kingAdjacentZoneAttacksCount[Them] + popcount<Max15>(undefended))
800                      + InitKingDanger[relative_square(Us, ksq)]
801                      - mg_value(score) / 32;
802
803         // Analyse enemy's safe queen contact checks. First find undefended
804         // squares around the king attacked by enemy queen...
805         b = undefended & ei.attackedBy[Them][QUEEN] & ~pos.pieces(Them);
806         if (b)
807         {
808             // ...then remove squares not supported by another enemy piece
809             b &= (  ei.attackedBy[Them][PAWN]   | ei.attackedBy[Them][KNIGHT]
810                   | ei.attackedBy[Them][BISHOP] | ei.attackedBy[Them][ROOK]);
811             if (b)
812                 attackUnits +=  QueenContactCheckBonus
813                               * popcount<Max15>(b)
814                               * (Them == pos.side_to_move() ? 2 : 1);
815         }
816
817         // Analyse enemy's safe rook contact checks. First find undefended
818         // squares around the king attacked by enemy rooks...
819         b = undefended & ei.attackedBy[Them][ROOK] & ~pos.pieces(Them);
820
821         // Consider only squares where the enemy rook gives check
822         b &= PseudoAttacks[ROOK][ksq];
823
824         if (b)
825         {
826             // ...then remove squares not supported by another enemy piece
827             b &= (  ei.attackedBy[Them][PAWN]   | ei.attackedBy[Them][KNIGHT]
828                   | ei.attackedBy[Them][BISHOP] | ei.attackedBy[Them][QUEEN]);
829             if (b)
830                 attackUnits +=  RookContactCheckBonus
831                               * popcount<Max15>(b)
832                               * (Them == pos.side_to_move() ? 2 : 1);
833         }
834
835         // Analyse enemy's safe distance checks for sliders and knights
836         safe = ~(pos.pieces(Them) | ei.attackedBy[Us][0]);
837
838         b1 = pos.attacks_from<ROOK>(ksq) & safe;
839         b2 = pos.attacks_from<BISHOP>(ksq) & safe;
840
841         // Enemy queen safe checks
842         b = (b1 | b2) & ei.attackedBy[Them][QUEEN];
843         if (b)
844             attackUnits += QueenCheckBonus * popcount<Max15>(b);
845
846         // Enemy rooks safe checks
847         b = b1 & ei.attackedBy[Them][ROOK];
848         if (b)
849             attackUnits += RookCheckBonus * popcount<Max15>(b);
850
851         // Enemy bishops safe checks
852         b = b2 & ei.attackedBy[Them][BISHOP];
853         if (b)
854             attackUnits += BishopCheckBonus * popcount<Max15>(b);
855
856         // Enemy knights safe checks
857         b = pos.attacks_from<KNIGHT>(ksq) & ei.attackedBy[Them][KNIGHT] & safe;
858         if (b)
859             attackUnits += KnightCheckBonus * popcount<Max15>(b);
860
861         // To index KingDangerTable[] attackUnits must be in [0, 99] range
862         attackUnits = std::min(99, std::max(0, attackUnits));
863
864         // Finally, extract the king danger score from the KingDangerTable[]
865         // array and subtract the score from evaluation. Set also margins[]
866         // value that will be used for pruning because this value can sometimes
867         // be very big, and so capturing a single attacking piece can therefore
868         // result in a score change far bigger than the value of the captured piece.
869         score -= KingDangerTable[Us == Search::RootColor][attackUnits];
870         margins[Us] += int16_t(mg_value(KingDangerTable[Us == Search::RootColor][attackUnits]));
871     }
872
873     if (Trace)
874         TracedScores[Us][KING] = score;
875
876     return score;
877   }
878
879
880   // evaluate_passed_pawns<>() evaluates the passed pawns of the given color
881
882   template<Color Us>
883   Score evaluate_passed_pawns(const Position& pos, EvalInfo& ei) {
884
885     const Color Them = (Us == WHITE ? BLACK : WHITE);
886
887     Bitboard b, squaresToQueen, defendedSquares, unsafeSquares, supportingPawns;
888     Score score = SCORE_ZERO;
889
890     b = ei.pi->passed_pawns(Us);
891
892     if (!b)
893         return SCORE_ZERO;
894
895     do {
896         Square s = pop_lsb(&b);
897
898         assert(pos.pawn_is_passed(Us, s));
899
900         int r = int(relative_rank(Us, s) - RANK_2);
901         int rr = r * (r - 1);
902
903         // Base bonus based on rank
904         Value mbonus = Value(20 * rr);
905         Value ebonus = Value(10 * (rr + r + 1));
906
907         if (rr)
908         {
909             Square blockSq = s + pawn_push(Us);
910
911             // Adjust bonus based on kings proximity
912             ebonus += Value(square_distance(pos.king_square(Them), blockSq) * 5 * rr);
913             ebonus -= Value(square_distance(pos.king_square(Us), blockSq) * 2 * rr);
914
915             // If blockSq is not the queening square then consider also a second push
916             if (rank_of(blockSq) != (Us == WHITE ? RANK_8 : RANK_1))
917                 ebonus -= Value(square_distance(pos.king_square(Us), blockSq + pawn_push(Us)) * rr);
918
919             // If the pawn is free to advance, increase bonus
920             if (pos.is_empty(blockSq))
921             {
922                 squaresToQueen = forward_bb(Us, s);
923                 defendedSquares = squaresToQueen & ei.attackedBy[Us][0];
924
925                 // If there is an enemy rook or queen attacking the pawn from behind,
926                 // add all X-ray attacks by the rook or queen. Otherwise consider only
927                 // the squares in the pawn's path attacked or occupied by the enemy.
928                 if (   (forward_bb(Them, s) & pos.pieces(Them, ROOK, QUEEN))
929                     && (forward_bb(Them, s) & pos.pieces(Them, ROOK, QUEEN) & pos.attacks_from<ROOK>(s)))
930                     unsafeSquares = squaresToQueen;
931                 else
932                     unsafeSquares = squaresToQueen & (ei.attackedBy[Them][0] | pos.pieces(Them));
933
934                 // If there aren't enemy attacks or pieces along the path to queen give
935                 // huge bonus. Even bigger if we protect the pawn's path.
936                 if (!unsafeSquares)
937                     ebonus += Value(rr * (squaresToQueen == defendedSquares ? 17 : 15));
938                 else
939                     // OK, there are enemy attacks or pieces (but not pawns). Are those
940                     // squares which are attacked by the enemy also attacked by us ?
941                     // If yes, big bonus (but smaller than when there are no enemy attacks),
942                     // if no, somewhat smaller bonus.
943                     ebonus += Value(rr * ((unsafeSquares & defendedSquares) == unsafeSquares ? 13 : 8));
944             }
945         } // rr != 0
946
947         // Increase the bonus if the passed pawn is supported by a friendly pawn
948         // on the same rank and a bit smaller if it's on the previous rank.
949         supportingPawns = pos.pieces(Us, PAWN) & adjacent_files_bb(file_of(s));
950         if (supportingPawns & rank_bb(s))
951             ebonus += Value(r * 20);
952
953         else if (supportingPawns & rank_bb(s - pawn_push(Us)))
954             ebonus += Value(r * 12);
955
956         // Rook pawns are a special case: They are sometimes worse, and
957         // sometimes better than other passed pawns. It is difficult to find
958         // good rules for determining whether they are good or bad. For now,
959         // we try the following: Increase the value for rook pawns if the
960         // other side has no pieces apart from a knight, and decrease the
961         // value if the other side has a rook or queen.
962         if (file_of(s) == FILE_A || file_of(s) == FILE_H)
963         {
964             if (pos.non_pawn_material(Them) <= KnightValueMg)
965                 ebonus += ebonus / 4;
966             else if (pos.pieces(Them, ROOK, QUEEN))
967                 ebonus -= ebonus / 4;
968         }
969         score += make_score(mbonus, ebonus);
970
971     } while (b);
972
973     // Add the scores to the middle game and endgame eval
974     return apply_weight(score, Weights[PassedPawns]);
975   }
976
977
978   // evaluate_unstoppable_pawns() evaluates the unstoppable passed pawns for both sides, this is quite
979   // conservative and returns a winning score only when we are very sure that the pawn is winning.
980
981   Score evaluate_unstoppable_pawns(const Position& pos, EvalInfo& ei) {
982
983     Bitboard b, b2, blockers, supporters, queeningPath, candidates;
984     Square s, blockSq, queeningSquare;
985     Color c, winnerSide, loserSide;
986     bool pathDefended, opposed;
987     int pliesToGo, movesToGo, oppMovesToGo, sacptg, blockersCount, minKingDist, kingptg, d;
988     int pliesToQueen[] = { 256, 256 };
989
990     // Step 1. Hunt for unstoppable passed pawns. If we find at least one,
991     // record how many plies are required for promotion.
992     for (c = WHITE; c <= BLACK; c++)
993     {
994         // Skip if other side has non-pawn pieces
995         if (pos.non_pawn_material(~c))
996             continue;
997
998         b = ei.pi->passed_pawns(c);
999
1000         while (b)
1001         {
1002             s = pop_lsb(&b);
1003             queeningSquare = relative_square(c, file_of(s) | RANK_8);
1004             queeningPath = forward_bb(c, s);
1005
1006             // Compute plies to queening and check direct advancement
1007             movesToGo = rank_distance(s, queeningSquare) - int(relative_rank(c, s) == RANK_2);
1008             oppMovesToGo = square_distance(pos.king_square(~c), queeningSquare) - int(c != pos.side_to_move());
1009             pathDefended = ((ei.attackedBy[c][0] & queeningPath) == queeningPath);
1010
1011             if (movesToGo >= oppMovesToGo && !pathDefended)
1012                 continue;
1013
1014             // Opponent king cannot block because path is defended and position
1015             // is not in check. So only friendly pieces can be blockers.
1016             assert(!pos.in_check());
1017             assert((queeningPath & pos.pieces()) == (queeningPath & pos.pieces(c)));
1018
1019             // Add moves needed to free the path from friendly pieces and retest condition
1020             movesToGo += popcount<Max15>(queeningPath & pos.pieces(c));
1021
1022             if (movesToGo >= oppMovesToGo && !pathDefended)
1023                 continue;
1024
1025             pliesToGo = 2 * movesToGo - int(c == pos.side_to_move());
1026             pliesToQueen[c] = std::min(pliesToQueen[c], pliesToGo);
1027         }
1028     }
1029
1030     // Step 2. If either side cannot promote at least three plies before the other side then situation
1031     // becomes too complex and we give up. Otherwise we determine the possibly "winning side"
1032     if (abs(pliesToQueen[WHITE] - pliesToQueen[BLACK]) < 3)
1033         return SCORE_ZERO;
1034
1035     winnerSide = (pliesToQueen[WHITE] < pliesToQueen[BLACK] ? WHITE : BLACK);
1036     loserSide = ~winnerSide;
1037
1038     // Step 3. Can the losing side possibly create a new passed pawn and thus prevent the loss?
1039     b = candidates = pos.pieces(loserSide, PAWN);
1040
1041     while (b)
1042     {
1043         s = pop_lsb(&b);
1044
1045         // Compute plies from queening
1046         queeningSquare = relative_square(loserSide, file_of(s) | RANK_8);
1047         movesToGo = rank_distance(s, queeningSquare) - int(relative_rank(loserSide, s) == RANK_2);
1048         pliesToGo = 2 * movesToGo - int(loserSide == pos.side_to_move());
1049
1050         // Check if (without even considering any obstacles) we're too far away or doubled
1051         if (   pliesToQueen[winnerSide] + 3 <= pliesToGo
1052             || (forward_bb(loserSide, s) & pos.pieces(loserSide, PAWN)))
1053             candidates ^= s;
1054     }
1055
1056     // If any candidate is already a passed pawn it _may_ promote in time. We give up.
1057     if (candidates & ei.pi->passed_pawns(loserSide))
1058         return SCORE_ZERO;
1059
1060     // Step 4. Check new passed pawn creation through king capturing and pawn sacrifices
1061     b = candidates;
1062
1063     while (b)
1064     {
1065         s = pop_lsb(&b);
1066         sacptg = blockersCount = 0;
1067         minKingDist = kingptg = 256;
1068
1069         // Compute plies from queening
1070         queeningSquare = relative_square(loserSide, file_of(s) | RANK_8);
1071         movesToGo = rank_distance(s, queeningSquare) - int(relative_rank(loserSide, s) == RANK_2);
1072         pliesToGo = 2 * movesToGo - int(loserSide == pos.side_to_move());
1073
1074         // Generate list of blocking pawns and supporters
1075         supporters = adjacent_files_bb(file_of(s)) & candidates;
1076         opposed = forward_bb(loserSide, s) & pos.pieces(winnerSide, PAWN);
1077         blockers = passed_pawn_mask(loserSide, s) & pos.pieces(winnerSide, PAWN);
1078
1079         assert(blockers);
1080
1081         // How many plies does it take to remove all the blocking pawns?
1082         while (blockers)
1083         {
1084             blockSq = pop_lsb(&blockers);
1085             movesToGo = 256;
1086
1087             // Check pawns that can give support to overcome obstacle, for instance
1088             // black pawns: a4, b4 white: b2 then pawn in b4 is giving support.
1089             if (!opposed)
1090             {
1091                 b2 = supporters & in_front_bb(winnerSide, blockSq + pawn_push(winnerSide));
1092
1093                 while (b2) // This while-loop could be replaced with LSB/MSB (depending on color)
1094                 {
1095                     d = square_distance(blockSq, pop_lsb(&b2)) - 2;
1096                     movesToGo = std::min(movesToGo, d);
1097                 }
1098             }
1099
1100             // Check pawns that can be sacrificed against the blocking pawn
1101             b2 = attack_span_mask(winnerSide, blockSq) & candidates & ~(1ULL << s);
1102
1103             while (b2) // This while-loop could be replaced with LSB/MSB (depending on color)
1104             {
1105                 d = square_distance(blockSq, pop_lsb(&b2)) - 2;
1106                 movesToGo = std::min(movesToGo, d);
1107             }
1108
1109             // If obstacle can be destroyed with an immediate pawn exchange / sacrifice,
1110             // it's not a real obstacle and we have nothing to add to pliesToGo.
1111             if (movesToGo <= 0)
1112                 continue;
1113
1114             // Plies needed to sacrifice against all the blocking pawns
1115             sacptg += movesToGo * 2;
1116             blockersCount++;
1117
1118             // Plies needed for the king to capture all the blocking pawns
1119             d = square_distance(pos.king_square(loserSide), blockSq);
1120             minKingDist = std::min(minKingDist, d);
1121             kingptg = (minKingDist + blockersCount) * 2;
1122         }
1123
1124         // Check if pawn sacrifice plan _may_ save the day
1125         if (pliesToQueen[winnerSide] + 3 > pliesToGo + sacptg)
1126             return SCORE_ZERO;
1127
1128         // Check if king capture plan _may_ save the day (contains some false positives)
1129         if (pliesToQueen[winnerSide] + 3 > pliesToGo + kingptg)
1130             return SCORE_ZERO;
1131     }
1132
1133     // Winning pawn is unstoppable and will promote as first, return big score
1134     Score score = make_score(0, (Value) 1280 - 32 * pliesToQueen[winnerSide]);
1135     return winnerSide == WHITE ? score : -score;
1136   }
1137
1138
1139   // evaluate_space() computes the space evaluation for a given side. The
1140   // space evaluation is a simple bonus based on the number of safe squares
1141   // available for minor pieces on the central four files on ranks 2--4. Safe
1142   // squares one, two or three squares behind a friendly pawn are counted
1143   // twice. Finally, the space bonus is scaled by a weight taken from the
1144   // material hash table. The aim is to improve play on game opening.
1145   template<Color Us>
1146   int evaluate_space(const Position& pos, EvalInfo& ei) {
1147
1148     const Color Them = (Us == WHITE ? BLACK : WHITE);
1149
1150     // Find the safe squares for our pieces inside the area defined by
1151     // SpaceMask[]. A square is unsafe if it is attacked by an enemy
1152     // pawn, or if it is undefended and attacked by an enemy piece.
1153     Bitboard safe =   SpaceMask[Us]
1154                    & ~pos.pieces(Us, PAWN)
1155                    & ~ei.attackedBy[Them][PAWN]
1156                    & (ei.attackedBy[Us][0] | ~ei.attackedBy[Them][0]);
1157
1158     // Find all squares which are at most three squares behind some friendly pawn
1159     Bitboard behind = pos.pieces(Us, PAWN);
1160     behind |= (Us == WHITE ? behind >>  8 : behind <<  8);
1161     behind |= (Us == WHITE ? behind >> 16 : behind << 16);
1162
1163     return popcount<Max15>(safe) + popcount<Max15>(behind & safe);
1164   }
1165
1166
1167   // interpolate() interpolates between a middle game and an endgame score,
1168   // based on game phase. It also scales the return value by a ScaleFactor array.
1169
1170   Value interpolate(const Score& v, Phase ph, ScaleFactor sf) {
1171
1172     assert(mg_value(v) > -VALUE_INFINITE && mg_value(v) < VALUE_INFINITE);
1173     assert(eg_value(v) > -VALUE_INFINITE && eg_value(v) < VALUE_INFINITE);
1174     assert(ph >= PHASE_ENDGAME && ph <= PHASE_MIDGAME);
1175
1176     int ev = (eg_value(v) * int(sf)) / SCALE_FACTOR_NORMAL;
1177     int result = (mg_value(v) * int(ph) + ev * int(128 - ph)) / 128;
1178     return Value((result + GrainSize / 2) & ~(GrainSize - 1));
1179   }
1180
1181
1182   // weight_option() computes the value of an evaluation weight, by combining
1183   // two UCI-configurable weights (midgame and endgame) with an internal weight.
1184
1185   Score weight_option(const std::string& mgOpt, const std::string& egOpt, Score internalWeight) {
1186
1187     // Scale option value from 100 to 256
1188     int mg = Options[mgOpt] * 256 / 100;
1189     int eg = Options[egOpt] * 256 / 100;
1190
1191     return apply_weight(make_score(mg, eg), internalWeight);
1192   }
1193
1194
1195   // A couple of little helpers used by tracing code, to_cp() converts a value to
1196   // a double in centipawns scale, trace_add() stores white and black scores.
1197
1198   double to_cp(Value v) { return double(v) / double(PawnValueMg); }
1199
1200   void trace_add(int idx, Score wScore, Score bScore) {
1201
1202     TracedScores[WHITE][idx] = wScore;
1203     TracedScores[BLACK][idx] = bScore;
1204   }
1205
1206
1207   // trace_row() is an helper function used by tracing code to register the
1208   // values of a single evaluation term.
1209
1210   void trace_row(const char* name, int idx) {
1211
1212     Score wScore = TracedScores[WHITE][idx];
1213     Score bScore = TracedScores[BLACK][idx];
1214
1215     switch (idx) {
1216     case PST: case IMBALANCE: case PAWN: case UNSTOPPABLE: case TOTAL:
1217         TraceStream << std::setw(20) << name << " |   ---   --- |   ---   --- | "
1218                     << std::setw(6)  << to_cp(mg_value(wScore)) << " "
1219                     << std::setw(6)  << to_cp(eg_value(wScore)) << " \n";
1220         break;
1221     default:
1222         TraceStream << std::setw(20) << name << " | " << std::noshowpos
1223                     << std::setw(5)  << to_cp(mg_value(wScore)) << " "
1224                     << std::setw(5)  << to_cp(eg_value(wScore)) << " | "
1225                     << std::setw(5)  << to_cp(mg_value(bScore)) << " "
1226                     << std::setw(5)  << to_cp(eg_value(bScore)) << " | "
1227                     << std::showpos
1228                     << std::setw(6)  << to_cp(mg_value(wScore - bScore)) << " "
1229                     << std::setw(6)  << to_cp(eg_value(wScore - bScore)) << " \n";
1230     }
1231   }
1232 }