1ff2dea7744c520daff7073c2bc315f0778648af
[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-2013 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   enum ExtendedPieceType { // Used for tracing
35     PST = 8, IMBALANCE, MOBILITY, THREAT, PASSED, SPACE, TOTAL
36   };
37
38   namespace Tracing {
39
40     Score scores[COLOR_NB][TOTAL + 1];
41     std::stringstream stream;
42
43     void add(int idx, Score term_w, Score term_b = SCORE_ZERO);
44     void row(const char* name, int idx);
45     std::string do_trace(const Position& pos);
46   }
47
48   // Struct EvalInfo contains various information computed and collected
49   // by the evaluation functions.
50   struct EvalInfo {
51
52     // Pointers to material and pawn hash table entries
53     Material::Entry* mi;
54     Pawns::Entry* pi;
55
56     // attackedBy[color][piece type] is a bitboard representing all squares
57     // attacked by a given color and piece type, attackedBy[color][ALL_PIECES]
58     // contains all squares attacked by the given color.
59     Bitboard attackedBy[COLOR_NB][PIECE_TYPE_NB];
60
61     // kingRing[color] is the zone around the king which is considered
62     // by the king safety evaluation. This consists of the squares directly
63     // adjacent to the king, and the three (or two, for a king on an edge file)
64     // squares two ranks in front of the king. For instance, if black's king
65     // is on g8, kingRing[BLACK] is a bitboard containing the squares f8, h8,
66     // f7, g7, h7, f6, g6 and h6.
67     Bitboard kingRing[COLOR_NB];
68
69     // kingAttackersCount[color] is the number of pieces of the given color
70     // which attack a square in the kingRing of the enemy king.
71     int kingAttackersCount[COLOR_NB];
72
73     // kingAttackersWeight[color] is the sum of the "weight" of the pieces of the
74     // given color which attack a square in the kingRing of the enemy king. The
75     // weights of the individual piece types are given by the variables
76     // QueenAttackWeight, RookAttackWeight, BishopAttackWeight and
77     // KnightAttackWeight in evaluate.cpp
78     int kingAttackersWeight[COLOR_NB];
79
80     // kingAdjacentZoneAttacksCount[color] is the number of attacks to squares
81     // directly adjacent to the king of the given color. Pieces which attack
82     // more than one square are counted multiple times. For instance, if black's
83     // king is on g8 and there's a white knight on g5, this knight adds
84     // 2 to kingAdjacentZoneAttacksCount[BLACK].
85     int kingAdjacentZoneAttacksCount[COLOR_NB];
86   };
87
88   // Evaluation grain size, must be a power of 2
89   const int GrainSize = 4;
90
91   // Evaluation weights, initialized from UCI options
92   enum { Mobility, PawnStructure, PassedPawns, Space, KingDangerUs, KingDangerThem };
93   Score Weights[6];
94
95   typedef Value V;
96   #define S(mg, eg) make_score(mg, eg)
97
98   // Internal evaluation weights. These are applied on top of the evaluation
99   // weights read from UCI parameters. The purpose is to be able to change
100   // the evaluation weights while keeping the default values of the UCI
101   // parameters at 100, which looks prettier.
102   //
103   // Values modified by Joona Kiiski
104   const Score WeightsInternal[] = {
105       S(289, 344), S(233, 201), S(221, 273), S(46, 0), S(271, 0), S(307, 0)
106   };
107
108   // MobilityBonus[PieceType][attacked] contains bonuses for middle and end
109   // game, indexed by piece type and number of attacked squares not occupied by
110   // friendly pieces.
111   const Score MobilityBonus[][32] = {
112      {}, {},
113      { S(-35,-30), S(-22,-20), S(-9,-10), S( 3,  0), S(15, 10), S(27, 20), // Knights
114        S( 37, 28), S( 42, 31), S(44, 33) },
115      { S(-22,-27), S( -8,-13), S( 6,  1), S(20, 15), S(34, 29), S(48, 43), // Bishops
116        S( 60, 55), S( 68, 63), S(74, 68), S(77, 72), S(80, 75), S(82, 77),
117        S( 84, 79), S( 86, 81) },
118      { S(-17,-33), S(-11,-16), S(-5,  0), S( 1, 16), S( 7, 32), S(13, 48), // Rooks
119        S( 18, 64), S( 22, 80), S(26, 96), S(29,109), S(31,115), S(33,119),
120        S( 35,122), S( 36,123), S(37,124) },
121      { S(-12,-20), S( -8,-13), S(-5, -7), S(-2, -1), S( 1,  5), S( 4, 11), // Queens
122        S(  7, 17), S( 10, 23), S(13, 29), S(16, 34), S(18, 38), S(20, 40),
123        S( 22, 41), S( 23, 41), S(24, 41), S(25, 41), S(25, 41), S(25, 41),
124        S( 25, 41), S( 25, 41), S(25, 41), S(25, 41), S(25, 41), S(25, 41),
125        S( 25, 41), S( 25, 41), S(25, 41), S(25, 41) }
126   };
127
128   // Outpost[PieceType][Square] contains bonuses of knights and bishops, indexed
129   // by piece type and square (from white's point of view).
130   const Value Outpost[][SQUARE_NB] = {
131   {
132   //  A     B     C     D     E     F     G     H
133     V(0), V(0), V(0), V(0), V(0), V(0), V(0), V(0), // Knights
134     V(0), V(0), V(0), V(0), V(0), V(0), V(0), V(0),
135     V(0), V(0), V(4), V(8), V(8), V(4), V(0), V(0),
136     V(0), V(4),V(17),V(26),V(26),V(17), V(4), V(0),
137     V(0), V(8),V(26),V(35),V(35),V(26), V(8), V(0),
138     V(0), V(4),V(17),V(17),V(17),V(17), V(4), V(0) },
139   {
140     V(0), V(0), V(0), V(0), V(0), V(0), V(0), V(0), // Bishops
141     V(0), V(0), V(0), V(0), V(0), V(0), V(0), V(0),
142     V(0), V(0), V(5), V(5), V(5), V(5), V(0), V(0),
143     V(0), V(5),V(10),V(10),V(10),V(10), V(5), V(0),
144     V(0),V(10),V(21),V(21),V(21),V(21),V(10), V(0),
145     V(0), V(5), V(8), V(8), V(8), V(8), V(5), V(0) }
146   };
147
148   // Threat[attacking][attacked] contains bonuses according to which piece
149   // type attacks which one.
150   const Score Threat[][PIECE_TYPE_NB] = {
151     {}, {},
152     { S(0, 0), S( 7, 39), S( 0,  0), S(24, 49), S(41,100), S(41,100) }, // KNIGHT
153     { S(0, 0), S( 7, 39), S(24, 49), S( 0,  0), S(41,100), S(41,100) }, // BISHOP
154     { S(0, 0), S( 0, 22), S(15, 49), S(15, 49), S( 0,  0), S(24, 49) }, // ROOK
155     { S(0, 0), S(15, 39), S(15, 39), S(15, 39), S(15, 39), S( 0,  0) }  // QUEEN
156   };
157
158   // ThreatenedByPawn[PieceType] contains a penalty according to which piece
159   // type is attacked by an enemy pawn.
160   const Score ThreatenedByPawn[] = {
161     S(0, 0), S(0, 0), S(56, 70), S(56, 70), S(76, 99), S(86, 118)
162   };
163
164   #undef S
165
166   const Score Tempo            = make_score(24, 11);
167   const Score BishopPin        = make_score(66, 11);
168   const Score RookOn7th        = make_score(11, 20);
169   const Score QueenOn7th       = make_score( 3,  8);
170   const Score RookOnPawn       = make_score(10, 28);
171   const Score QueenOnPawn      = make_score( 4, 20);
172   const Score RookOpenFile     = make_score(43, 21);
173   const Score RookSemiopenFile = make_score(19, 10);
174   const Score BishopPawns      = make_score( 8, 12);
175   const Score KnightPawns      = make_score( 8,  4);
176   const Score MinorBehindPawn  = make_score(16,  0);
177   const Score UndefendedMinor  = make_score(25, 10);
178   const Score TrappedRook      = make_score(90,  0);
179   const Score Unstoppable      = make_score( 0, 20);
180
181   // Penalty for a bishop on a1/h1 (a8/h8 for black) which is trapped by
182   // a friendly pawn on b2/g2 (b7/g7 for black). This can obviously only
183   // happen in Chess960 games.
184   const Score TrappedBishopA1H1 = make_score(50, 50);
185
186   // The SpaceMask[Color] contains the area of the board which is considered
187   // by the space evaluation. In the middle game, each side is given a bonus
188   // based on how many squares inside this area are safe and available for
189   // friendly minor pieces.
190   const Bitboard SpaceMask[] = {
191     (FileCBB | FileDBB | FileEBB | FileFBB) & (Rank2BB | Rank3BB | Rank4BB),
192     (FileCBB | FileDBB | FileEBB | FileFBB) & (Rank7BB | Rank6BB | Rank5BB)
193   };
194
195   // King danger constants and variables. The king danger scores are taken
196   // from the KingDanger[]. Various little "meta-bonuses" measuring
197   // the strength of the enemy attack are added up into an integer, which
198   // is used as an index to KingDanger[].
199   //
200   // KingAttackWeights[PieceType] contains king attack weights by piece type
201   const int KingAttackWeights[] = { 0, 0, 2, 2, 3, 5 };
202
203   // Bonuses for enemy's safe checks
204   const int QueenContactCheck = 24;
205   const int RookContactCheck  = 16;
206   const int QueenCheck        = 12;
207   const int RookCheck         = 8;
208   const int BishopCheck       = 2;
209   const int KnightCheck       = 3;
210
211   // KingExposed[Square] contains penalties based on the position of the
212   // defending king, indexed by king's square (from white's point of view).
213   const int KingExposed[] = {
214      2,  0,  2,  5,  5,  2,  0,  2,
215      2,  2,  4,  8,  8,  4,  2,  2,
216      7, 10, 12, 12, 12, 12, 10,  7,
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     15, 15, 15, 15, 15, 15, 15, 15,
221     15, 15, 15, 15, 15, 15, 15, 15
222   };
223
224   // KingDanger[Color][attackUnits] contains the actual king danger weighted
225   // scores, indexed by color and by a calculated integer number.
226   Score KingDanger[COLOR_NB][128];
227
228   // Function prototypes
229   template<bool Trace>
230   Value do_evaluate(const Position& pos, Value& margin);
231
232   template<Color Us>
233   void init_eval_info(const Position& pos, EvalInfo& ei);
234
235   template<Color Us, bool Trace>
236   Score evaluate_pieces_of_color(const Position& pos, EvalInfo& ei, Score* mobility);
237
238   template<Color Us, bool Trace>
239   Score evaluate_king(const Position& pos, const EvalInfo& ei, Value margins[]);
240
241   template<Color Us, bool Trace>
242   Score evaluate_threats(const Position& pos, const EvalInfo& ei);
243
244   template<Color Us, bool Trace>
245   Score evaluate_passed_pawns(const Position& pos, const EvalInfo& ei);
246
247   template<Color Us>
248   int evaluate_space(const Position& pos, const EvalInfo& ei);
249
250   Score evaluate_unstoppable_pawns(const Position& pos, Color us, const EvalInfo& ei);
251
252   Value interpolate(const Score& v, Phase ph, ScaleFactor sf);
253   Score apply_weight(Score v, Score w);
254   Score weight_option(const std::string& mgOpt, const std::string& egOpt, Score internalWeight);
255   double to_cp(Value v);
256 }
257
258
259 namespace Eval {
260
261   /// evaluate() is the main evaluation function. It always computes two
262   /// values, an endgame score and a middle game score, and interpolates
263   /// between them based on the remaining material.
264
265   Value evaluate(const Position& pos, Value& margin) {
266     return do_evaluate<false>(pos, margin);
267   }
268
269
270   /// trace() is like evaluate() but instead of a value returns a string suitable
271   /// to be print on stdout with the detailed descriptions and values of each
272   /// evaluation term. Used mainly for debugging.
273   std::string trace(const Position& pos) {
274     return Tracing::do_trace(pos);
275   }
276
277
278   /// init() computes evaluation weights from the corresponding UCI parameters
279   /// and setup king tables.
280
281   void init() {
282
283     Weights[Mobility]       = weight_option("Mobility (Midgame)", "Mobility (Endgame)", WeightsInternal[Mobility]);
284     Weights[PawnStructure]  = weight_option("Pawn Structure (Midgame)", "Pawn Structure (Endgame)", WeightsInternal[PawnStructure]);
285     Weights[PassedPawns]    = weight_option("Passed Pawns (Midgame)", "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     const int MaxSlope = 30;
291     const int Peak = 1280;
292
293     for (int t = 0, i = 1; i < 100; ++i)
294     {
295         t = std::min(Peak, std::min(int(0.4 * i * i), t + MaxSlope));
296
297         KingDanger[1][i] = apply_weight(make_score(t, 0), Weights[KingDangerUs]);
298         KingDanger[0][i] = apply_weight(make_score(t, 0), Weights[KingDangerThem]);
299     }
300   }
301
302 } // namespace Eval
303
304
305 namespace {
306
307 template<bool Trace>
308 Value do_evaluate(const Position& pos, Value& margin) {
309
310   assert(!pos.checkers());
311
312   EvalInfo ei;
313   Value margins[COLOR_NB];
314   Score score, mobility[2] = { SCORE_ZERO, SCORE_ZERO };
315   Thread* th = pos.this_thread();
316
317   // margins[] store the uncertainty estimation of position's evaluation
318   // that typically is used by the search for pruning decisions.
319   margins[WHITE] = margins[BLACK] = VALUE_ZERO;
320
321   // Initialize score by reading the incrementally updated scores included
322   // in the position object (material + piece square tables) and adding
323   // Tempo bonus. Score is computed from the point of view of white.
324   score = pos.psq_score() + (pos.side_to_move() == WHITE ? Tempo : -Tempo);
325
326   // Probe the material hash table
327   ei.mi = Material::probe(pos, th->materialTable, th->endgames);
328   score += ei.mi->material_value();
329
330   // If we have a specialized evaluation function for the current material
331   // configuration, call it and return.
332   if (ei.mi->specialized_eval_exists())
333   {
334       margin = VALUE_ZERO;
335       return ei.mi->evaluate(pos);
336   }
337
338   // Probe the pawn hash table
339   ei.pi = Pawns::probe(pos, th->pawnsTable);
340   score += apply_weight(ei.pi->pawns_value(), Weights[PawnStructure]);
341
342   // Initialize attack and king safety bitboards
343   init_eval_info<WHITE>(pos, ei);
344   init_eval_info<BLACK>(pos, ei);
345
346   // Evaluate pieces and mobility
347   score +=  evaluate_pieces_of_color<WHITE, Trace>(pos, ei, mobility)
348           - evaluate_pieces_of_color<BLACK, Trace>(pos, ei, mobility);
349
350   score += apply_weight(mobility[WHITE] - mobility[BLACK], Weights[Mobility]);
351
352   // Evaluate kings after all other pieces because we need complete attack
353   // information when computing the king safety evaluation.
354   score +=  evaluate_king<WHITE, Trace>(pos, ei, margins)
355           - evaluate_king<BLACK, Trace>(pos, ei, margins);
356
357   // Evaluate tactical threats, we need full attack information including king
358   score +=  evaluate_threats<WHITE, Trace>(pos, ei)
359           - evaluate_threats<BLACK, Trace>(pos, ei);
360
361   // Evaluate passed pawns, we need full attack information including king
362   score +=  evaluate_passed_pawns<WHITE, Trace>(pos, ei)
363           - evaluate_passed_pawns<BLACK, Trace>(pos, ei);
364
365   // If one side has only a king, score for potential unstoppable pawns
366   if (!pos.non_pawn_material(WHITE) || !pos.non_pawn_material(BLACK))
367       score +=  evaluate_unstoppable_pawns(pos, WHITE, ei)
368               - evaluate_unstoppable_pawns(pos, BLACK, ei);
369
370   // Evaluate space for both sides, only in middle-game.
371   if (ei.mi->space_weight())
372   {
373       int s = evaluate_space<WHITE>(pos, ei) - evaluate_space<BLACK>(pos, ei);
374       score += apply_weight(s * ei.mi->space_weight(), Weights[Space]);
375   }
376
377   // Scale winning side if position is more drawish that what it appears
378   ScaleFactor sf = eg_value(score) > VALUE_DRAW ? ei.mi->scale_factor(pos, WHITE)
379                                                 : ei.mi->scale_factor(pos, BLACK);
380
381   // If we don't already have an unusual scale factor, check for opposite
382   // colored bishop endgames, and use a lower scale for those.
383   if (   ei.mi->game_phase() < PHASE_MIDGAME
384       && pos.opposite_bishops()
385       && sf == SCALE_FACTOR_NORMAL)
386   {
387       // Only the two bishops ?
388       if (   pos.non_pawn_material(WHITE) == BishopValueMg
389           && pos.non_pawn_material(BLACK) == BishopValueMg)
390       {
391           // Check for KBP vs KB with only a single pawn that is almost
392           // certainly a draw or at least two pawns.
393           bool one_pawn = (pos.count<PAWN>(WHITE) + pos.count<PAWN>(BLACK) == 1);
394           sf = one_pawn ? ScaleFactor(8) : ScaleFactor(32);
395       }
396       else
397           // Endgame with opposite-colored bishops, but also other pieces. Still
398           // a bit drawish, but not as drawish as with only the two bishops.
399            sf = ScaleFactor(50);
400   }
401
402   margin = margins[pos.side_to_move()];
403   Value v = interpolate(score, ei.mi->game_phase(), sf);
404
405   // In case of tracing add all single evaluation contributions for both white and black
406   if (Trace)
407   {
408       Tracing::add(PST, pos.psq_score());
409       Tracing::add(IMBALANCE, ei.mi->material_value());
410       Tracing::add(PAWN, ei.pi->pawns_value());
411       Score w = ei.mi->space_weight() * evaluate_space<WHITE>(pos, ei);
412       Score b = ei.mi->space_weight() * evaluate_space<BLACK>(pos, ei);
413       Tracing::add(SPACE, apply_weight(w, Weights[Space]), apply_weight(b, Weights[Space]));
414       Tracing::add(TOTAL, score);
415       Tracing::stream << "\nUncertainty margin: White: " << to_cp(margins[WHITE])
416                       << ", Black: " << to_cp(margins[BLACK])
417                       << "\nScaling: " << std::noshowpos
418                       << std::setw(6) << 100.0 * ei.mi->game_phase() / 128.0 << "% MG, "
419                       << std::setw(6) << 100.0 * (1.0 - ei.mi->game_phase() / 128.0) << "% * "
420                       << std::setw(6) << (100.0 * sf) / SCALE_FACTOR_NORMAL << "% EG.\n"
421                       << "Total evaluation: " << to_cp(v);
422   }
423
424   return pos.side_to_move() == WHITE ? v : -v;
425 }
426
427
428   // init_eval_info() initializes king bitboards for given color adding
429   // pawn attacks. To be done at the beginning of the evaluation.
430
431   template<Color Us>
432   void init_eval_info(const Position& pos, EvalInfo& ei) {
433
434     const Color  Them = (Us == WHITE ? BLACK : WHITE);
435     const Square Down = (Us == WHITE ? DELTA_S : DELTA_N);
436
437     Bitboard b = ei.attackedBy[Them][KING] = pos.attacks_from<KING>(pos.king_square(Them));
438     ei.attackedBy[Us][PAWN] = ei.pi->pawn_attacks(Us);
439
440     // Init king safety tables only if we are going to use them
441     if (pos.count<QUEEN>(Us) && pos.non_pawn_material(Us) > QueenValueMg + PawnValueMg)
442     {
443         ei.kingRing[Them] = b | shift_bb<Down>(b);
444         b &= ei.attackedBy[Us][PAWN];
445         ei.kingAttackersCount[Us] = b ? popcount<Max15>(b) / 2 : 0;
446         ei.kingAdjacentZoneAttacksCount[Us] = ei.kingAttackersWeight[Us] = 0;
447     }
448     else
449         ei.kingRing[Them] = ei.kingAttackersCount[Us] = 0;
450   }
451
452
453   // evaluate_outposts() evaluates bishop and knight outposts squares
454
455   template<PieceType Piece, Color Us>
456   Score evaluate_outposts(const Position& pos, EvalInfo& ei, Square s) {
457
458     const Color Them = (Us == WHITE ? BLACK : WHITE);
459
460     assert (Piece == BISHOP || Piece == KNIGHT);
461
462     // Initial bonus based on square
463     Value bonus = Outpost[Piece == BISHOP][relative_square(Us, s)];
464
465     // Increase bonus if supported by pawn, especially if the opponent has
466     // no minor piece which can exchange the outpost piece.
467     if (bonus && (ei.attackedBy[Us][PAWN] & s))
468     {
469         if (   !pos.pieces(Them, KNIGHT)
470             && !(squares_of_color(s) & pos.pieces(Them, BISHOP)))
471             bonus += bonus + bonus / 2;
472         else
473             bonus += bonus / 2;
474     }
475
476     return make_score(bonus, bonus);
477   }
478
479
480   // evaluate_pieces() assigns bonuses and penalties to the pieces of a given color
481
482   template<PieceType Piece, Color Us, bool Trace>
483   Score evaluate_pieces(const Position& pos, EvalInfo& ei, Score* mobility, Bitboard mobilityArea) {
484
485     Bitboard b;
486     Square s;
487     Score score = SCORE_ZERO;
488
489     const Color Them = (Us == WHITE ? BLACK : WHITE);
490     const Square* pl = pos.list<Piece>(Us);
491
492     ei.attackedBy[Us][Piece] = 0;
493
494     while ((s = *pl++) != SQ_NONE)
495     {
496         // Find attacked squares, including x-ray attacks for bishops and rooks
497         b = Piece == BISHOP ? attacks_bb<BISHOP>(s, pos.pieces() ^ pos.pieces(Us, QUEEN))
498           : Piece ==   ROOK ? attacks_bb<  ROOK>(s, pos.pieces() ^ pos.pieces(Us, ROOK, QUEEN))
499                             : pos.attacks_from<Piece>(s);
500
501         ei.attackedBy[Us][Piece] |= b;
502
503         if (b & ei.kingRing[Them])
504         {
505             ei.kingAttackersCount[Us]++;
506             ei.kingAttackersWeight[Us] += KingAttackWeights[Piece];
507             Bitboard bb = b & ei.attackedBy[Them][KING];
508             if (bb)
509                 ei.kingAdjacentZoneAttacksCount[Us] += popcount<Max15>(bb);
510         }
511
512         int mob = Piece != QUEEN ? popcount<Max15>(b & mobilityArea)
513                                  : popcount<Full >(b & mobilityArea);
514
515         mobility[Us] += MobilityBonus[Piece][mob];
516
517         // Decrease score if we are attacked by an enemy pawn. Remaining part
518         // of threat evaluation must be done later when we have full attack info.
519         if (ei.attackedBy[Them][PAWN] & s)
520             score -= ThreatenedByPawn[Piece];
521
522         // Otherwise give a bonus if we are a bishop and can pin a piece or can
523         // give a discovered check through an x-ray attack.
524         else if (    Piece == BISHOP
525                  && (PseudoAttacks[Piece][pos.king_square(Them)] & s)
526                  && !more_than_one(BetweenBB[s][pos.king_square(Them)] & pos.pieces()))
527                  score += BishopPin;
528
529         // Penalty for bishop with same coloured pawns
530         if (Piece == BISHOP)
531             score -= BishopPawns * ei.pi->pawns_on_same_color_squares(Us, s);
532
533         // Penalty for knight when there are few enemy pawns
534         if (Piece == KNIGHT)
535             score -= KnightPawns * std::max(5 - pos.count<PAWN>(Them), 0);
536
537         if (Piece == BISHOP || Piece == KNIGHT)
538         {
539             // Bishop and knight outposts squares
540             if (!(pos.pieces(Them, PAWN) & pawn_attack_span(Us, s)))
541                 score += evaluate_outposts<Piece, Us>(pos, ei, s);
542
543             // Bishop or knight behind a pawn
544             if (    relative_rank(Us, s) < RANK_5
545                 && (pos.pieces(PAWN) & (s + pawn_push(Us))))
546                 score += MinorBehindPawn;
547         }
548
549         if (  (Piece == ROOK || Piece == QUEEN)
550             && relative_rank(Us, s) >= RANK_5)
551         {
552             // Major piece on 7th rank and enemy king trapped on 8th
553             if (   relative_rank(Us, s) == RANK_7
554                 && relative_rank(Us, pos.king_square(Them)) == RANK_8)
555                 score += Piece == ROOK ? RookOn7th : QueenOn7th;
556
557             // Major piece attacking enemy pawns on the same rank/file
558             Bitboard pawns = pos.pieces(Them, PAWN) & PseudoAttacks[ROOK][s];
559             if (pawns)
560                 score += popcount<Max15>(pawns) * (Piece == ROOK ? RookOnPawn : QueenOnPawn);
561         }
562
563         // Special extra evaluation for rooks
564         if (Piece == ROOK)
565         {
566             // Give a bonus for a rook on a open or semi-open file
567             if (ei.pi->semiopen(Us, file_of(s)))
568                 score += ei.pi->semiopen(Them, file_of(s)) ? RookOpenFile : RookSemiopenFile;
569
570             if (mob > 3 || ei.pi->semiopen(Us, file_of(s)))
571                 continue;
572
573             Square ksq = pos.king_square(Us);
574
575             // Penalize rooks which are trapped inside a king. Penalize more if
576             // king has lost right to castle.
577             if (   ((file_of(ksq) < FILE_E) == (file_of(s) < file_of(ksq)))
578                 && (rank_of(ksq) == rank_of(s) || relative_rank(Us, ksq) == RANK_1)
579                 && !ei.pi->semiopen_on_side(Us, file_of(ksq), file_of(ksq) < FILE_E))
580                 score -= (TrappedRook - make_score(mob * 8, 0)) * (pos.can_castle(Us) ? 1 : 2);
581         }
582
583         // An important Chess960 pattern: A cornered bishop blocked by a friendly
584         // pawn diagonally in front of it is a very serious problem, especially
585         // when that pawn is also blocked.
586         if (   Piece == BISHOP
587             && pos.is_chess960()
588             && (s == relative_square(Us, SQ_A1) || s == relative_square(Us, SQ_H1)))
589         {
590             const enum Piece P = make_piece(Us, PAWN);
591             Square d = pawn_push(Us) + (file_of(s) == FILE_A ? DELTA_E : DELTA_W);
592             if (pos.piece_on(s + d) == P)
593                 score -= !pos.empty(s + d + pawn_push(Us)) ? TrappedBishopA1H1 * 4
594                         : pos.piece_on(s + d + d) == P     ? TrappedBishopA1H1 * 2
595                                                            : TrappedBishopA1H1;
596         }
597     }
598
599     if (Trace)
600         Tracing::scores[Us][Piece] = score;
601
602     return score;
603   }
604
605
606   // evaluate_pieces_of_color() assigns bonuses and penalties to all the
607   // pieces of a given color.
608
609   template<Color Us, bool Trace>
610   Score evaluate_pieces_of_color(const Position& pos, EvalInfo& ei, Score* mobility) {
611
612     const Color Them = (Us == WHITE ? BLACK : WHITE);
613
614     // Do not include in mobility squares protected by enemy pawns or occupied by our pieces
615     const Bitboard mobilityArea = ~(ei.attackedBy[Them][PAWN] | pos.pieces(Us, PAWN, KING));
616
617     Score score =  evaluate_pieces<KNIGHT, Us, Trace>(pos, ei, mobility, mobilityArea)
618                  + evaluate_pieces<BISHOP, Us, Trace>(pos, ei, mobility, mobilityArea)
619                  + evaluate_pieces<ROOK,   Us, Trace>(pos, ei, mobility, mobilityArea)
620                  + evaluate_pieces<QUEEN,  Us, Trace>(pos, ei, mobility, mobilityArea);
621
622     // Sum up all attacked squares (updated in evaluate_pieces)
623     ei.attackedBy[Us][ALL_PIECES] =  ei.attackedBy[Us][PAWN]   | ei.attackedBy[Us][KNIGHT]
624                                    | ei.attackedBy[Us][BISHOP] | ei.attackedBy[Us][ROOK]
625                                    | ei.attackedBy[Us][QUEEN]  | ei.attackedBy[Us][KING];
626     if (Trace)
627         Tracing::scores[Us][MOBILITY] = apply_weight(mobility[Us], Weights[Mobility]);
628
629     return score;
630   }
631
632
633   // evaluate_king() assigns bonuses and penalties to a king of a given color
634
635   template<Color Us, bool Trace>
636   Score evaluate_king(const Position& pos, const EvalInfo& ei, Value margins[]) {
637
638     const Color Them = (Us == WHITE ? BLACK : WHITE);
639
640     Bitboard undefended, b, b1, b2, safe;
641     int attackUnits;
642     const Square ksq = pos.king_square(Us);
643
644     // King shelter and enemy pawns storm
645     Score score = ei.pi->king_safety<Us>(pos, ksq);
646
647     // Main king safety evaluation
648     if (   ei.kingAttackersCount[Them] >= 2
649         && ei.kingAdjacentZoneAttacksCount[Them])
650     {
651         // Find the attacked squares around the king which has no defenders
652         // apart from the king itself
653         undefended =  ei.attackedBy[Them][ALL_PIECES]
654                     & ei.attackedBy[Us][KING]
655                     & ~(  ei.attackedBy[Us][PAWN]   | ei.attackedBy[Us][KNIGHT]
656                         | ei.attackedBy[Us][BISHOP] | ei.attackedBy[Us][ROOK]
657                         | ei.attackedBy[Us][QUEEN]);
658
659         // Initialize the 'attackUnits' variable, which is used later on as an
660         // index to the KingDanger[] array. The initial value is based on the
661         // number and types of the enemy's attacking pieces, the number of
662         // attacked and undefended squares around our king, the square of the
663         // king, and the quality of the pawn shelter.
664         attackUnits =  std::min(20, (ei.kingAttackersCount[Them] * ei.kingAttackersWeight[Them]) / 2)
665                      + 3 * (ei.kingAdjacentZoneAttacksCount[Them] + popcount<Max15>(undefended))
666                      + KingExposed[relative_square(Us, ksq)]
667                      - mg_value(score) / 32;
668
669         // Analyse enemy's safe queen contact checks. First find undefended
670         // squares around the king attacked by enemy queen...
671         b = undefended & ei.attackedBy[Them][QUEEN] & ~pos.pieces(Them);
672         if (b)
673         {
674             // ...then remove squares not supported by another enemy piece
675             b &= (  ei.attackedBy[Them][PAWN]   | ei.attackedBy[Them][KNIGHT]
676                   | ei.attackedBy[Them][BISHOP] | ei.attackedBy[Them][ROOK]);
677             if (b)
678                 attackUnits +=  QueenContactCheck
679                               * popcount<Max15>(b)
680                               * (Them == pos.side_to_move() ? 2 : 1);
681         }
682
683         // Analyse enemy's safe rook contact checks. First find undefended
684         // squares around the king attacked by enemy rooks...
685         b = undefended & ei.attackedBy[Them][ROOK] & ~pos.pieces(Them);
686
687         // Consider only squares where the enemy rook gives check
688         b &= PseudoAttacks[ROOK][ksq];
689
690         if (b)
691         {
692             // ...then remove squares not supported by another enemy piece
693             b &= (  ei.attackedBy[Them][PAWN]   | ei.attackedBy[Them][KNIGHT]
694                   | ei.attackedBy[Them][BISHOP] | ei.attackedBy[Them][QUEEN]);
695             if (b)
696                 attackUnits +=  RookContactCheck
697                               * popcount<Max15>(b)
698                               * (Them == pos.side_to_move() ? 2 : 1);
699         }
700
701         // Analyse enemy's safe distance checks for sliders and knights
702         safe = ~(pos.pieces(Them) | ei.attackedBy[Us][ALL_PIECES]);
703
704         b1 = pos.attacks_from<ROOK>(ksq) & safe;
705         b2 = pos.attacks_from<BISHOP>(ksq) & safe;
706
707         // Enemy queen safe checks
708         b = (b1 | b2) & ei.attackedBy[Them][QUEEN];
709         if (b)
710             attackUnits += QueenCheck * popcount<Max15>(b);
711
712         // Enemy rooks safe checks
713         b = b1 & ei.attackedBy[Them][ROOK];
714         if (b)
715             attackUnits += RookCheck * popcount<Max15>(b);
716
717         // Enemy bishops safe checks
718         b = b2 & ei.attackedBy[Them][BISHOP];
719         if (b)
720             attackUnits += BishopCheck * popcount<Max15>(b);
721
722         // Enemy knights safe checks
723         b = pos.attacks_from<KNIGHT>(ksq) & ei.attackedBy[Them][KNIGHT] & safe;
724         if (b)
725             attackUnits += KnightCheck * popcount<Max15>(b);
726
727         // To index KingDanger[] attackUnits must be in [0, 99] range
728         attackUnits = std::min(99, std::max(0, attackUnits));
729
730         // Finally, extract the king danger score from the KingDanger[]
731         // array and subtract the score from evaluation. Set also margins[]
732         // value that will be used for pruning because this value can sometimes
733         // be very big, and so capturing a single attacking piece can therefore
734         // result in a score change far bigger than the value of the captured piece.
735         score -= KingDanger[Us == Search::RootColor][attackUnits];
736         margins[Us] += mg_value(KingDanger[Us == Search::RootColor][attackUnits]);
737     }
738
739     if (Trace)
740         Tracing::scores[Us][KING] = score;
741
742     return score;
743   }
744
745
746   // evaluate_threats() assigns bonuses according to the type of attacking piece
747   // and the type of attacked one.
748
749   template<Color Us, bool Trace>
750   Score evaluate_threats(const Position& pos, const EvalInfo& ei) {
751
752     const Color Them = (Us == WHITE ? BLACK : WHITE);
753
754     Bitboard b, undefendedMinors, weakEnemies;
755     Score score = SCORE_ZERO;
756
757     // Undefended minors get penalized even if not under attack
758     undefendedMinors =  pos.pieces(Them, BISHOP, KNIGHT)
759                       & ~ei.attackedBy[Them][ALL_PIECES];
760
761     if (undefendedMinors)
762         score += UndefendedMinor;
763
764     // Enemy pieces not defended by a pawn and under our attack
765     weakEnemies =  pos.pieces(Them)
766                  & ~ei.attackedBy[Them][PAWN]
767                  & ei.attackedBy[Us][ALL_PIECES];
768
769     // Add bonus according to type of attacked enemy piece and to the
770     // type of attacking piece, from knights to queens. Kings are not
771     // considered because are already handled in king evaluation.
772     if (weakEnemies)
773         for (PieceType pt1 = KNIGHT; pt1 < KING; ++pt1)
774         {
775             b = ei.attackedBy[Us][pt1] & weakEnemies;
776             if (b)
777                 for (PieceType pt2 = PAWN; pt2 < KING; ++pt2)
778                     if (b & pos.pieces(pt2))
779                         score += Threat[pt1][pt2];
780         }
781
782     if (Trace)
783         Tracing::scores[Us][THREAT] = score;
784
785     return score;
786   }
787
788
789   // evaluate_passed_pawns() evaluates the passed pawns of the given color
790
791   template<Color Us, bool Trace>
792   Score evaluate_passed_pawns(const Position& pos, const EvalInfo& ei) {
793
794     const Color Them = (Us == WHITE ? BLACK : WHITE);
795
796     Bitboard b, squaresToQueen, defendedSquares, unsafeSquares, supportingPawns;
797     Score score = SCORE_ZERO;
798
799     b = ei.pi->passed_pawns(Us);
800
801     while (b)
802     {
803         Square s = pop_lsb(&b);
804
805         assert(pos.pawn_passed(Us, s));
806
807         int r = int(relative_rank(Us, s) - RANK_2);
808         int rr = r * (r - 1);
809
810         // Base bonus based on rank
811         Value mbonus = Value(17 * rr);
812         Value ebonus = Value(7 * (rr + r + 1));
813
814         if (rr)
815         {
816             Square blockSq = s + pawn_push(Us);
817
818             // Adjust bonus based on kings proximity
819             ebonus +=  Value(square_distance(pos.king_square(Them), blockSq) * 5 * rr)
820                      - Value(square_distance(pos.king_square(Us  ), blockSq) * 2 * rr);
821
822             // If blockSq is not the queening square then consider also a second push
823             if (relative_rank(Us, blockSq) != RANK_8)
824                 ebonus -= Value(square_distance(pos.king_square(Us), blockSq + pawn_push(Us)) * rr);
825
826             // If the pawn is free to advance, increase bonus
827             if (pos.empty(blockSq))
828             {
829                 squaresToQueen = forward_bb(Us, s);
830
831                 // If there is an enemy rook or queen attacking the pawn from behind,
832                 // add all X-ray attacks by the rook or queen. Otherwise consider only
833                 // the squares in the pawn's path attacked or occupied by the enemy.
834                 if (    unlikely(forward_bb(Them, s) & pos.pieces(Them, ROOK, QUEEN))
835                     && (forward_bb(Them, s) & pos.pieces(Them, ROOK, QUEEN) & pos.attacks_from<ROOK>(s)))
836                     unsafeSquares = squaresToQueen;
837                 else
838                     unsafeSquares = squaresToQueen & (ei.attackedBy[Them][ALL_PIECES] | pos.pieces(Them));
839
840                 if (    unlikely(forward_bb(Them, s) & pos.pieces(Us, ROOK, QUEEN))
841                     && (forward_bb(Them, s) & pos.pieces(Us, ROOK, QUEEN) & pos.attacks_from<ROOK>(s)))
842                     defendedSquares = squaresToQueen;
843                 else
844                     defendedSquares = squaresToQueen & ei.attackedBy[Us][ALL_PIECES];
845
846                 // If there aren't enemy attacks huge bonus, a bit smaller if at
847                 // least block square is not attacked, otherwise smallest bonus.
848                 int k = !unsafeSquares ? 15 : !(unsafeSquares & blockSq) ? 9 : 3;
849
850                 // Big bonus if the path to queen is fully defended, a bit less
851                 // if at least block square is defended.
852                 if (defendedSquares == squaresToQueen)
853                     k += 6;
854
855                 else if (defendedSquares & blockSq)
856                     k += (unsafeSquares & defendedSquares) == unsafeSquares ? 4 : 2;
857
858                 mbonus += Value(k * rr), ebonus += Value(k * rr);
859             }
860         } // rr != 0
861
862         // Increase the bonus if the passed pawn is supported by a friendly pawn
863         // on the same rank and a bit smaller if it's on the previous rank.
864         supportingPawns = pos.pieces(Us, PAWN) & adjacent_files_bb(file_of(s));
865         if (supportingPawns & rank_bb(s))
866             ebonus += Value(r * 20);
867
868         else if (supportingPawns & rank_bb(s - pawn_push(Us)))
869             ebonus += Value(r * 12);
870
871         // Rook pawns are a special case: They are sometimes worse, and
872         // sometimes better than other passed pawns. It is difficult to find
873         // good rules for determining whether they are good or bad. For now,
874         // we try the following: Increase the value for rook pawns if the
875         // other side has no pieces apart from a knight, and decrease the
876         // value if the other side has a rook or queen.
877         if (file_of(s) == FILE_A || file_of(s) == FILE_H)
878         {
879             if (pos.non_pawn_material(Them) <= KnightValueMg)
880                 ebonus += ebonus / 4;
881
882             else if (pos.pieces(Them, ROOK, QUEEN))
883                 ebonus -= ebonus / 4;
884         }
885
886         if (pos.count<PAWN>(Us) < pos.count<PAWN>(Them))
887             ebonus += ebonus / 4;
888
889         score += make_score(mbonus, ebonus);
890
891     }
892
893     if (Trace)
894         Tracing::scores[Us][PASSED] = apply_weight(score, Weights[PassedPawns]);
895
896     // Add the scores to the middle game and endgame eval
897     return apply_weight(score, Weights[PassedPawns]);
898   }
899
900
901   // evaluate_unstoppable_pawns() scores the most advanced among the passed and
902   // candidate pawns. In case opponent has no pieces but pawns, this is somewhat
903   // related to the possibility pawns are unstoppable.
904
905   Score evaluate_unstoppable_pawns(const Position& pos, Color us, const EvalInfo& ei) {
906
907     Bitboard b = ei.pi->passed_pawns(us) | ei.pi->candidate_pawns(us);
908
909     if (!b || pos.non_pawn_material(~us))
910         return SCORE_ZERO;
911
912     return Unstoppable * int(relative_rank(us, frontmost_sq(us, b)));
913   }
914
915
916   // evaluate_space() computes the space evaluation for a given side. The
917   // space evaluation is a simple bonus based on the number of safe squares
918   // available for minor pieces on the central four files on ranks 2--4. Safe
919   // squares one, two or three squares behind a friendly pawn are counted
920   // twice. Finally, the space bonus is scaled by a weight taken from the
921   // material hash table. The aim is to improve play on game opening.
922   template<Color Us>
923   int evaluate_space(const Position& pos, const EvalInfo& ei) {
924
925     const Color Them = (Us == WHITE ? BLACK : WHITE);
926
927     // Find the safe squares for our pieces inside the area defined by
928     // SpaceMask[]. A square is unsafe if it is attacked by an enemy
929     // pawn, or if it is undefended and attacked by an enemy piece.
930     Bitboard safe =   SpaceMask[Us]
931                    & ~pos.pieces(Us, PAWN)
932                    & ~ei.attackedBy[Them][PAWN]
933                    & (ei.attackedBy[Us][ALL_PIECES] | ~ei.attackedBy[Them][ALL_PIECES]);
934
935     // Find all squares which are at most three squares behind some friendly pawn
936     Bitboard behind = pos.pieces(Us, PAWN);
937     behind |= (Us == WHITE ? behind >>  8 : behind <<  8);
938     behind |= (Us == WHITE ? behind >> 16 : behind << 16);
939
940     // Since SpaceMask[Us] is fully on our half of the board
941     assert(unsigned(safe >> (Us == WHITE ? 32 : 0)) == 0);
942
943     // Count safe + (behind & safe) with a single popcount
944     return popcount<Full>((Us == WHITE ? safe << 32 : safe >> 32) | (behind & safe));
945   }
946
947
948   // interpolate() interpolates between a middle game and an endgame score,
949   // based on game phase. It also scales the return value by a ScaleFactor array.
950
951   Value interpolate(const Score& v, Phase ph, ScaleFactor sf) {
952
953     assert(mg_value(v) > -VALUE_INFINITE && mg_value(v) < VALUE_INFINITE);
954     assert(eg_value(v) > -VALUE_INFINITE && eg_value(v) < VALUE_INFINITE);
955     assert(ph >= PHASE_ENDGAME && ph <= PHASE_MIDGAME);
956
957     int e = (eg_value(v) * int(sf)) / SCALE_FACTOR_NORMAL;
958     int r = (mg_value(v) * int(ph) + e * int(PHASE_MIDGAME - ph)) / PHASE_MIDGAME;
959     return Value((r / GrainSize) * GrainSize); // Sign independent
960   }
961
962   // apply_weight() weights score v by score w trying to prevent overflow
963   Score apply_weight(Score v, Score w) {
964     return make_score((int(mg_value(v)) * mg_value(w)) / 0x100,
965                       (int(eg_value(v)) * eg_value(w)) / 0x100);
966   }
967
968   // weight_option() computes the value of an evaluation weight, by combining
969   // two UCI-configurable weights (midgame and endgame) with an internal weight.
970
971   Score weight_option(const std::string& mgOpt, const std::string& egOpt, Score internalWeight) {
972
973     // Scale option value from 100 to 256
974     int mg = Options[mgOpt] * 256 / 100;
975     int eg = Options[egOpt] * 256 / 100;
976
977     return apply_weight(make_score(mg, eg), internalWeight);
978   }
979
980
981   // Tracing functions definitions
982
983   double to_cp(Value v) { return double(v) / double(PawnValueMg); }
984
985   void Tracing::add(int idx, Score wScore, Score bScore) {
986
987     scores[WHITE][idx] = wScore;
988     scores[BLACK][idx] = bScore;
989   }
990
991   void Tracing::row(const char* name, int idx) {
992
993     Score wScore = scores[WHITE][idx];
994     Score bScore = scores[BLACK][idx];
995
996     switch (idx) {
997     case PST: case IMBALANCE: case PAWN: case TOTAL:
998         stream << std::setw(20) << name << " |   ---   --- |   ---   --- | "
999                << std::setw(6)  << to_cp(mg_value(wScore)) << " "
1000                << std::setw(6)  << to_cp(eg_value(wScore)) << " \n";
1001         break;
1002     default:
1003         stream << std::setw(20) << name << " | " << std::noshowpos
1004                << std::setw(5)  << to_cp(mg_value(wScore)) << " "
1005                << std::setw(5)  << to_cp(eg_value(wScore)) << " | "
1006                << std::setw(5)  << to_cp(mg_value(bScore)) << " "
1007                << std::setw(5)  << to_cp(eg_value(bScore)) << " | "
1008                << std::showpos
1009                << std::setw(6)  << to_cp(mg_value(wScore - bScore)) << " "
1010                << std::setw(6)  << to_cp(eg_value(wScore - bScore)) << " \n";
1011     }
1012   }
1013
1014   std::string Tracing::do_trace(const Position& pos) {
1015
1016     stream.str("");
1017     stream << std::showpoint << std::showpos << std::fixed << std::setprecision(2);
1018     std::memset(scores, 0, 2 * (TOTAL + 1) * sizeof(Score));
1019
1020     Value margin;
1021     do_evaluate<true>(pos, margin);
1022
1023     std::string totals = stream.str();
1024     stream.str("");
1025
1026     stream << std::setw(21) << "Eval term " << "|    White    |    Black    |     Total     \n"
1027                     <<             "                     |   MG    EG  |   MG    EG  |   MG     EG   \n"
1028                     <<             "---------------------+-------------+-------------+---------------\n";
1029
1030     row("Material, PST, Tempo", PST);
1031     row("Material imbalance", IMBALANCE);
1032     row("Pawns", PAWN);
1033     row("Knights", KNIGHT);
1034     row("Bishops", BISHOP);
1035     row("Rooks", ROOK);
1036     row("Queens", QUEEN);
1037     row("Mobility", MOBILITY);
1038     row("King safety", KING);
1039     row("Threats", THREAT);
1040     row("Passed pawns", PASSED);
1041     row("Space", SPACE);
1042
1043     stream <<             "---------------------+-------------+-------------+---------------\n";
1044     row("Total", TOTAL);
1045     stream << totals;
1046
1047     return stream.str();
1048   }
1049 }