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