Use FMHs to assist with LMR formula.
[stockfish] / src / evaluate.cpp
1 /*
2   Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3   Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
4   Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad
5   Copyright (C) 2015-2016 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad
6
7   Stockfish is free software: you can redistribute it and/or modify
8   it under the terms of the GNU General Public License as published by
9   the Free Software Foundation, either version 3 of the License, or
10   (at your option) any later version.
11
12   Stockfish is distributed in the hope that it will be useful,
13   but WITHOUT ANY WARRANTY; without even the implied warranty of
14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15   GNU General Public License for more details.
16
17   You should have received a copy of the GNU General Public License
18   along with this program.  If not, see <http://www.gnu.org/licenses/>.
19 */
20
21 #include <algorithm>
22 #include <cassert>
23 #include <cstring>   // For std::memset
24 #include <iomanip>
25 #include <sstream>
26
27 #include "bitboard.h"
28 #include "evaluate.h"
29 #include "material.h"
30 #include "pawns.h"
31
32 namespace {
33
34   namespace Trace {
35
36     enum Term { // The first 8 entries are for PieceType
37       MATERIAL = 8, IMBALANCE, MOBILITY, THREAT, PASSED, SPACE, TOTAL, TERM_NB
38     };
39
40     double scores[TERM_NB][COLOR_NB][PHASE_NB];
41
42     double to_cp(Value v) { return double(v) / PawnValueEg; }
43
44     void add(int idx, Color c, Score s) {
45       scores[idx][c][MG] = to_cp(mg_value(s));
46       scores[idx][c][EG] = to_cp(eg_value(s));
47     }
48
49     void add(int idx, Score w, Score b = SCORE_ZERO) {
50       add(idx, WHITE, w); add(idx, BLACK, b);
51     }
52
53     std::ostream& operator<<(std::ostream& os, Term t) {
54
55       if (t == MATERIAL || t == IMBALANCE || t == Term(PAWN) || t == TOTAL)
56           os << "  ---   --- |   ---   --- | ";
57       else
58           os << std::setw(5) << scores[t][WHITE][MG] << " "
59              << std::setw(5) << scores[t][WHITE][EG] << " | "
60              << std::setw(5) << scores[t][BLACK][MG] << " "
61              << std::setw(5) << scores[t][BLACK][EG] << " | ";
62
63       os << std::setw(5) << scores[t][WHITE][MG] - scores[t][BLACK][MG] << " "
64          << std::setw(5) << scores[t][WHITE][EG] - scores[t][BLACK][EG] << " \n";
65
66       return os;
67     }
68   }
69
70   using namespace Trace;
71
72   // Struct EvalInfo contains various information computed and collected
73   // by the evaluation functions.
74   struct EvalInfo {
75
76     // attackedBy[color][piece type] is a bitboard representing all squares
77     // attacked by a given color and piece type (can be also ALL_PIECES).
78     Bitboard attackedBy[COLOR_NB][PIECE_TYPE_NB];
79
80     // kingRing[color] is the zone around the king which is considered
81     // by the king safety evaluation. This consists of the squares directly
82     // adjacent to the king, and the three (or two, for a king on an edge file)
83     // squares two ranks in front of the king. For instance, if black's king
84     // is on g8, kingRing[BLACK] is a bitboard containing the squares f8, h8,
85     // f7, g7, h7, f6, g6 and h6.
86     Bitboard kingRing[COLOR_NB];
87
88     // kingAttackersCount[color] is the number of pieces of the given color
89     // which attack a square in the kingRing of the enemy king.
90     int kingAttackersCount[COLOR_NB];
91
92     // kingAttackersWeight[color] is the sum of the "weights" of the pieces of the
93     // given color which attack a square in the kingRing of the enemy king. The
94     // weights of the individual piece types are given by the elements in the
95     // KingAttackWeights array.
96     int kingAttackersWeight[COLOR_NB];
97
98     // kingAdjacentZoneAttacksCount[color] is the number of attacks by the given
99     // color to squares directly adjacent to the enemy king. Pieces which attack
100     // more than one square are counted multiple times. For instance, if there is
101     // a white knight on g5 and black's king is on g8, this white knight adds 2
102     // to kingAdjacentZoneAttacksCount[WHITE].
103     int kingAdjacentZoneAttacksCount[COLOR_NB];
104
105     Bitboard pinnedPieces[COLOR_NB];
106     Material::Entry* me;
107     Pawns::Entry* pi;
108   };
109
110   #define V(v) Value(v)
111   #define S(mg, eg) make_score(mg, eg)
112
113   // MobilityBonus[PieceType][attacked] contains bonuses for middle and end
114   // game, indexed by piece type and number of attacked squares in the MobilityArea.
115   const Score MobilityBonus[][32] = {
116     {}, {},
117     { S(-75,-76), S(-56,-54), S(- 9,-26), S( -2,-10), S(  6,  5), S( 15, 11), // Knights
118       S( 22, 26), S( 30, 28), S( 36, 29) },
119     { S(-48,-58), S(-21,-19), S( 16, -2), S( 26, 12), S( 37, 22), S( 51, 42), // Bishops
120       S( 54, 54), S( 63, 58), S( 65, 63), S( 71, 70), S( 79, 74), S( 81, 86),
121       S( 92, 90), S( 97, 94) },
122     { S(-56,-78), S(-25,-18), S(-11, 26), S( -5, 55), S( -4, 70), S( -1, 81), // Rooks
123       S(  8,109), S( 14,120), S( 21,128), S( 23,143), S( 31,154), S( 32,160),
124       S( 43,165), S( 49,168), S( 59,169) },
125     { S(-40,-35), S(-25,-12), S(  2,  7), S(  4, 19), S( 14, 37), S( 24, 55), // Queens
126       S( 25, 62), S( 40, 76), S( 43, 79), S( 47, 87), S( 54, 94), S( 56,102),
127       S( 60,111), S( 70,116), S( 72,118), S( 73,122), S( 75,128), S( 77,130),
128       S( 85,133), S( 94,136), S( 99,140), S(108,157), S(112,158), S(113,161),
129       S(118,174), S(119,177), S(123,191), S(128,199) }
130   };
131
132   // Outpost[knight/bishop][supported by pawn] contains bonuses for knights and
133   // bishops outposts, bigger if outpost piece is supported by a pawn.
134   const Score Outpost[][2] = {
135     { S(43,11), S(65,20) }, // Knights
136     { S(20, 3), S(29, 8) }  // Bishops
137   };
138
139   // ReachableOutpost[knight/bishop][supported by pawn] contains bonuses for
140   // knights and bishops which can reach an outpost square in one move, bigger
141   // if outpost square is supported by a pawn.
142   const Score ReachableOutpost[][2] = {
143     { S(21, 5), S(35, 8) }, // Knights
144     { S( 8, 0), S(14, 4) }  // Bishops
145   };
146
147   // RookOnFile[semiopen/open] contains bonuses for each rook when there is no
148   // friendly pawn on the rook file.
149   const Score RookOnFile[2] = { S(20, 7), S(45, 20) };
150
151   // ThreatBySafePawn[PieceType] contains bonuses according to which piece
152   // type is attacked by a pawn which is protected or is not attacked.
153   const Score ThreatBySafePawn[PIECE_TYPE_NB] = {
154     S(0, 0), S(0, 0), S(176, 139), S(131, 127), S(217, 218), S(203, 215) };
155
156   // Threat[by minor/by rook][attacked PieceType] contains
157   // bonuses according to which piece type attacks which one.
158   // Attacks on lesser pieces which are pawn-defended are not considered.
159   const Score Threat[][PIECE_TYPE_NB] = {
160     { S(0, 0), S(0, 33), S(45, 43), S(46, 47), S(72,107), S(48,118) }, // by Minor
161     { S(0, 0), S(0, 25), S(40, 62), S(40, 59), S( 0, 34), S(35, 48) }  // by Rook
162   };
163
164   // ThreatByKing[on one/on many] contains bonuses for King attacks on
165   // pawns or pieces which are not pawn-defended.
166   const Score ThreatByKing[2] = { S(3, 62), S(9, 138) };
167
168   // Passed[mg/eg][Rank] contains midgame and endgame bonuses for passed pawns.
169   // We don't use a Score because we process the two components independently.
170   const Value Passed[][RANK_NB] = {
171     { V(5), V( 5), V(31), V(73), V(166), V(252) },
172     { V(7), V(14), V(38), V(73), V(166), V(252) }
173   };
174
175   // PassedFile[File] contains a bonus according to the file of a passed pawn
176   const Score PassedFile[FILE_NB] = {
177     S(  9, 10), S( 2, 10), S( 1, -8), S(-20,-12),
178     S(-20,-12), S( 1, -8), S( 2, 10), S( 9, 10)
179   };
180
181   // Assorted bonuses and penalties used by evaluation
182   const Score MinorBehindPawn     = S(16,  0);
183   const Score BishopPawns         = S( 8, 12);
184   const Score RookOnPawn          = S( 8, 24);
185   const Score TrappedRook         = S(92,  0);
186   const Score Checked             = S(20, 20);
187   const Score ThreatByHangingPawn = S(71, 61);
188   const Score LooseEnemies        = S( 0, 25);
189   const Score Hanging             = S(48, 27);
190   const Score ThreatByPawnPush    = S(38, 22);
191   const Score Unstoppable         = S( 0, 20);
192
193   // Penalty for a bishop on a1/h1 (a8/h8 for black) which is trapped by
194   // a friendly pawn on b2/g2 (b7/g7 for black). This can obviously only
195   // happen in Chess960 games.
196   const Score TrappedBishopA1H1 = S(50, 50);
197
198   #undef S
199   #undef V
200
201   // King danger constants and variables. The king danger scores are looked-up
202   // in KingDanger[]. Various little "meta-bonuses" measuring the strength
203   // of the enemy attack are added up into an integer, which is used as an
204   // index to KingDanger[].
205   Score KingDanger[512];
206
207   // KingAttackWeights[PieceType] contains king attack weights by piece type
208   const int KingAttackWeights[PIECE_TYPE_NB] = { 0, 0, 7, 5, 4, 1 };
209
210   // Penalties for enemy's safe checks
211   const int QueenContactCheck = 89;
212   const int QueenCheck        = 52;
213   const int RookCheck         = 45;
214   const int BishopCheck       = 5;
215   const int KnightCheck       = 17;
216
217
218   // eval_init() initializes king and attack bitboards for a given color
219   // adding pawn attacks. To be done at the beginning of the evaluation.
220
221   template<Color Us>
222   void eval_init(const Position& pos, EvalInfo& ei) {
223
224     const Color  Them = (Us == WHITE ? BLACK   : WHITE);
225     const Square Down = (Us == WHITE ? DELTA_S : DELTA_N);
226
227     ei.pinnedPieces[Us] = pos.pinned_pieces(Us);
228     Bitboard b = ei.attackedBy[Them][KING] = pos.attacks_from<KING>(pos.square<KING>(Them));
229     ei.attackedBy[Them][ALL_PIECES] |= b;
230     ei.attackedBy[Us][ALL_PIECES] |= ei.attackedBy[Us][PAWN] = ei.pi->pawn_attacks(Us);
231
232     // Init king safety tables only if we are going to use them
233     if (pos.non_pawn_material(Us) >= QueenValueMg)
234     {
235         ei.kingRing[Them] = b | shift_bb<Down>(b);
236         b &= ei.attackedBy[Us][PAWN];
237         ei.kingAttackersCount[Us] = popcount(b);
238         ei.kingAdjacentZoneAttacksCount[Us] = ei.kingAttackersWeight[Us] = 0;
239     }
240     else
241         ei.kingRing[Them] = ei.kingAttackersCount[Us] = 0;
242   }
243
244
245   // evaluate_pieces() assigns bonuses and penalties to the pieces of a given
246   // color and type.
247
248   template<bool DoTrace, Color Us = WHITE, PieceType Pt = KNIGHT>
249   Score evaluate_pieces(const Position& pos, EvalInfo& ei, Score* mobility,
250                         const Bitboard* mobilityArea) {
251     Bitboard b, bb;
252     Square s;
253     Score score = SCORE_ZERO;
254
255     const PieceType NextPt = (Us == WHITE ? Pt : PieceType(Pt + 1));
256     const Color Them = (Us == WHITE ? BLACK : WHITE);
257     const Bitboard OutpostRanks = (Us == WHITE ? Rank4BB | Rank5BB | Rank6BB
258                                                : Rank5BB | Rank4BB | Rank3BB);
259     const Square* pl = pos.squares<Pt>(Us);
260
261     ei.attackedBy[Us][Pt] = 0;
262
263     while ((s = *pl++) != SQ_NONE)
264     {
265         // Find attacked squares, including x-ray attacks for bishops and rooks
266         b = Pt == BISHOP ? attacks_bb<BISHOP>(s, pos.pieces() ^ pos.pieces(Us, QUEEN))
267           : Pt ==   ROOK ? attacks_bb<  ROOK>(s, pos.pieces() ^ pos.pieces(Us, ROOK, QUEEN))
268                          : pos.attacks_from<Pt>(s);
269
270         if (ei.pinnedPieces[Us] & s)
271             b &= LineBB[pos.square<KING>(Us)][s];
272
273         ei.attackedBy[Us][ALL_PIECES] |= ei.attackedBy[Us][Pt] |= b;
274
275         if (b & ei.kingRing[Them])
276         {
277             ei.kingAttackersCount[Us]++;
278             ei.kingAttackersWeight[Us] += KingAttackWeights[Pt];
279             ei.kingAdjacentZoneAttacksCount[Us] += popcount(b & ei.attackedBy[Them][KING]);
280         }
281
282         if (Pt == QUEEN)
283             b &= ~(  ei.attackedBy[Them][KNIGHT]
284                    | ei.attackedBy[Them][BISHOP]
285                    | ei.attackedBy[Them][ROOK]);
286
287         int mob = popcount(b & mobilityArea[Us]);
288
289         mobility[Us] += MobilityBonus[Pt][mob];
290
291         if (Pt == BISHOP || Pt == KNIGHT)
292         {
293             // Bonus for outpost squares
294             bb = OutpostRanks & ~ei.pi->pawn_attacks_span(Them);
295             if (bb & s)
296                 score += Outpost[Pt == BISHOP][!!(ei.attackedBy[Us][PAWN] & s)];
297             else
298             {
299                 bb &= b & ~pos.pieces(Us);
300                 if (bb)
301                    score += ReachableOutpost[Pt == BISHOP][!!(ei.attackedBy[Us][PAWN] & bb)];
302             }
303
304             // Bonus when behind a pawn
305             if (    relative_rank(Us, s) < RANK_5
306                 && (pos.pieces(PAWN) & (s + pawn_push(Us))))
307                 score += MinorBehindPawn;
308
309             // Penalty for pawns on the same color square as the bishop
310             if (Pt == BISHOP)
311                 score -= BishopPawns * ei.pi->pawns_on_same_color_squares(Us, s);
312
313             // An important Chess960 pattern: A cornered bishop blocked by a friendly
314             // pawn diagonally in front of it is a very serious problem, especially
315             // when that pawn is also blocked.
316             if (   Pt == BISHOP
317                 && pos.is_chess960()
318                 && (s == relative_square(Us, SQ_A1) || s == relative_square(Us, SQ_H1)))
319             {
320                 Square d = pawn_push(Us) + (file_of(s) == FILE_A ? DELTA_E : DELTA_W);
321                 if (pos.piece_on(s + d) == make_piece(Us, PAWN))
322                     score -= !pos.empty(s + d + pawn_push(Us))                ? TrappedBishopA1H1 * 4
323                             : pos.piece_on(s + d + d) == make_piece(Us, PAWN) ? TrappedBishopA1H1 * 2
324                                                                               : TrappedBishopA1H1;
325             }
326         }
327
328         if (Pt == ROOK)
329         {
330             // Bonus for aligning with enemy pawns on the same rank/file
331             if (relative_rank(Us, s) >= RANK_5)
332                 score += RookOnPawn * popcount(pos.pieces(Them, PAWN) & PseudoAttacks[ROOK][s]);
333
334             // Bonus when on an open or semi-open file
335             if (ei.pi->semiopen_file(Us, file_of(s)))
336                 score += RookOnFile[!!ei.pi->semiopen_file(Them, file_of(s))];
337
338             // Penalize when trapped by the king, even more if the king cannot castle
339             else if (mob <= 3)
340             {
341                 Square ksq = pos.square<KING>(Us);
342
343                 if (   ((file_of(ksq) < FILE_E) == (file_of(s) < file_of(ksq)))
344                     && (rank_of(ksq) == rank_of(s) || relative_rank(Us, ksq) == RANK_1)
345                     && !ei.pi->semiopen_side(Us, file_of(ksq), file_of(s) < file_of(ksq)))
346                     score -= (TrappedRook - make_score(mob * 22, 0)) * (1 + !pos.can_castle(Us));
347             }
348         }
349     }
350
351     if (DoTrace)
352         Trace::add(Pt, Us, score);
353
354     // Recursively call evaluate_pieces() of next piece type until KING is excluded
355     return score - evaluate_pieces<DoTrace, Them, NextPt>(pos, ei, mobility, mobilityArea);
356   }
357
358   template<>
359   Score evaluate_pieces<false, WHITE, KING>(const Position&, EvalInfo&, Score*, const Bitboard*) { return SCORE_ZERO; }
360   template<>
361   Score evaluate_pieces< true, WHITE, KING>(const Position&, EvalInfo&, Score*, const Bitboard*) { return SCORE_ZERO; }
362
363
364   // evaluate_king() assigns bonuses and penalties to a king of a given color
365
366   template<Color Us, bool DoTrace>
367   Score evaluate_king(const Position& pos, const EvalInfo& ei) {
368
369     const Color Them = (Us == WHITE ? BLACK : WHITE);
370
371     Bitboard undefended, b, b1, b2, safe;
372     int attackUnits;
373     const Square ksq = pos.square<KING>(Us);
374
375     // King shelter and enemy pawns storm
376     Score score = ei.pi->king_safety<Us>(pos, ksq);
377
378     // Main king safety evaluation
379     if (ei.kingAttackersCount[Them])
380     {
381         // Find the attacked squares which are defended only by the king...
382         undefended =  ei.attackedBy[Them][ALL_PIECES]
383                     & ei.attackedBy[Us][KING]
384                     & ~(  ei.attackedBy[Us][PAWN]   | ei.attackedBy[Us][KNIGHT]
385                         | ei.attackedBy[Us][BISHOP] | ei.attackedBy[Us][ROOK]
386                         | ei.attackedBy[Us][QUEEN]);
387
388         // ... and those which are not defended at all in the larger king ring
389         b =  ei.attackedBy[Them][ALL_PIECES] & ~ei.attackedBy[Us][ALL_PIECES]
390            & ei.kingRing[Us] & ~pos.pieces(Them);
391
392         // Initialize the 'attackUnits' variable, which is used later on as an
393         // index into the KingDanger[] array. The initial value is based on the
394         // number and types of the enemy's attacking pieces, the number of
395         // attacked and undefended squares around our king and the quality of
396         // the pawn shelter (current 'score' value).
397         attackUnits =  std::min(72, ei.kingAttackersCount[Them] * ei.kingAttackersWeight[Them])
398                      +  9 * ei.kingAdjacentZoneAttacksCount[Them]
399                      + 27 * popcount(undefended)
400                      + 11 * (popcount(b) + !!ei.pinnedPieces[Us])
401                      - 64 * !pos.count<QUEEN>(Them)
402                      - mg_value(score) / 8;
403
404         // Analyse the enemy's safe queen contact checks. Firstly, find the
405         // undefended squares around the king reachable by the enemy queen...
406         b = undefended & ei.attackedBy[Them][QUEEN] & ~pos.pieces(Them);
407         if (b)
408         {
409             // ...and then remove squares not supported by another enemy piece
410             b &=  ei.attackedBy[Them][PAWN]   | ei.attackedBy[Them][KNIGHT]
411                 | ei.attackedBy[Them][BISHOP] | ei.attackedBy[Them][ROOK]
412                 | ei.attackedBy[Them][KING];
413
414             attackUnits += QueenContactCheck * popcount(b);
415         }
416
417         // Analyse the enemy's safe distance checks for sliders and knights
418         safe = ~(ei.attackedBy[Us][ALL_PIECES] | pos.pieces(Them));
419
420         b1 = pos.attacks_from<ROOK  >(ksq) & safe;
421         b2 = pos.attacks_from<BISHOP>(ksq) & safe;
422
423         // Enemy queen safe checks
424         if ((b1 | b2) & ei.attackedBy[Them][QUEEN])
425             attackUnits += QueenCheck, score -= Checked;
426
427         // Enemy rooks safe checks
428         if (b1 & ei.attackedBy[Them][ROOK])
429             attackUnits += RookCheck, score -= Checked;
430
431         // Enemy bishops safe checks
432         if (b2 & ei.attackedBy[Them][BISHOP])
433             attackUnits += BishopCheck, score -= Checked;
434
435         // Enemy knights safe checks
436         if (pos.attacks_from<KNIGHT>(ksq) & ei.attackedBy[Them][KNIGHT] & safe)
437             attackUnits += KnightCheck, score -= Checked;
438
439         // Finally, extract the king danger score from the KingDanger[]
440         // array and subtract the score from the evaluation.
441         score -= KingDanger[std::max(std::min(attackUnits, 399), 0)];
442     }
443
444     if (DoTrace)
445         Trace::add(KING, Us, score);
446
447     return score;
448   }
449
450
451   // evaluate_threats() assigns bonuses according to the types of the attacking
452   // and the attacked pieces.
453
454   template<Color Us, bool DoTrace>
455   Score evaluate_threats(const Position& pos, const EvalInfo& ei) {
456
457     const Color Them        = (Us == WHITE ? BLACK    : WHITE);
458     const Square Up         = (Us == WHITE ? DELTA_N  : DELTA_S);
459     const Square Left       = (Us == WHITE ? DELTA_NW : DELTA_SE);
460     const Square Right      = (Us == WHITE ? DELTA_NE : DELTA_SW);
461     const Bitboard TRank2BB = (Us == WHITE ? Rank2BB  : Rank7BB);
462     const Bitboard TRank7BB = (Us == WHITE ? Rank7BB  : Rank2BB);
463
464     enum { Minor, Rook };
465
466     Bitboard b, weak, defended, safeThreats;
467     Score score = SCORE_ZERO;
468
469     // Small bonus if the opponent has loose pawns or pieces
470     if (   (pos.pieces(Them) ^ pos.pieces(Them, QUEEN, KING))
471         & ~(ei.attackedBy[Us][ALL_PIECES] | ei.attackedBy[Them][ALL_PIECES]))
472         score += LooseEnemies;
473
474     // Non-pawn enemies attacked by a pawn
475     weak = (pos.pieces(Them) ^ pos.pieces(Them, PAWN)) & ei.attackedBy[Us][PAWN];
476
477     if (weak)
478     {
479         b = pos.pieces(Us, PAWN) & ( ~ei.attackedBy[Them][ALL_PIECES]
480                                     | ei.attackedBy[Us][ALL_PIECES]);
481
482         safeThreats = (shift_bb<Right>(b) | shift_bb<Left>(b)) & weak;
483
484         if (weak ^ safeThreats)
485             score += ThreatByHangingPawn;
486
487         while (safeThreats)
488             score += ThreatBySafePawn[type_of(pos.piece_on(pop_lsb(&safeThreats)))];
489     }
490
491     // Non-pawn enemies defended by a pawn
492     defended = (pos.pieces(Them) ^ pos.pieces(Them, PAWN)) & ei.attackedBy[Them][PAWN];
493
494     // Enemies not defended by a pawn and under our attack
495     weak =   pos.pieces(Them)
496           & ~ei.attackedBy[Them][PAWN]
497           &  ei.attackedBy[Us][ALL_PIECES];
498
499     // Add a bonus according to the kind of attacking pieces
500     if (defended | weak)
501     {
502         b = (defended | weak) & (ei.attackedBy[Us][KNIGHT] | ei.attackedBy[Us][BISHOP]);
503         while (b)
504             score += Threat[Minor][type_of(pos.piece_on(pop_lsb(&b)))];
505
506         b = (pos.pieces(Them, QUEEN) | weak) & ei.attackedBy[Us][ROOK];
507         while (b)
508             score += Threat[Rook ][type_of(pos.piece_on(pop_lsb(&b)))];
509
510         score += Hanging * popcount(weak & ~ei.attackedBy[Them][ALL_PIECES]);
511
512         b = weak & ei.attackedBy[Us][KING];
513         if (b)
514             score += ThreatByKing[more_than_one(b)];
515     }
516
517     // Bonus if some pawns can safely push and attack an enemy piece
518     b = pos.pieces(Us, PAWN) & ~TRank7BB;
519     b = shift_bb<Up>(b | (shift_bb<Up>(b & TRank2BB) & ~pos.pieces()));
520
521     b &=  ~pos.pieces()
522         & ~ei.attackedBy[Them][PAWN]
523         & (ei.attackedBy[Us][ALL_PIECES] | ~ei.attackedBy[Them][ALL_PIECES]);
524
525     b =  (shift_bb<Left>(b) | shift_bb<Right>(b))
526        &  pos.pieces(Them)
527        & ~ei.attackedBy[Us][PAWN];
528
529     score += ThreatByPawnPush * popcount(b);
530
531     if (DoTrace)
532         Trace::add(THREAT, Us, score);
533
534     return score;
535   }
536
537
538   // evaluate_passed_pawns() evaluates the passed pawns of the given color
539
540   template<Color Us, bool DoTrace>
541   Score evaluate_passed_pawns(const Position& pos, const EvalInfo& ei) {
542
543     const Color Them = (Us == WHITE ? BLACK : WHITE);
544
545     Bitboard b, squaresToQueen, defendedSquares, unsafeSquares;
546     Score score = SCORE_ZERO;
547
548     b = ei.pi->passed_pawns(Us);
549
550     while (b)
551     {
552         Square s = pop_lsb(&b);
553
554         assert(pos.pawn_passed(Us, s));
555
556         int r = relative_rank(Us, s) - RANK_2;
557         int rr = r * (r - 1);
558
559         Value mbonus = Passed[MG][r], ebonus = Passed[EG][r];
560
561         if (rr)
562         {
563             Square blockSq = s + pawn_push(Us);
564
565             // Adjust bonus based on the king's proximity
566             ebonus +=  distance(pos.square<KING>(Them), blockSq) * 5 * rr
567                      - distance(pos.square<KING>(Us  ), blockSq) * 2 * rr;
568
569             // If blockSq is not the queening square then consider also a second push
570             if (relative_rank(Us, blockSq) != RANK_8)
571                 ebonus -= distance(pos.square<KING>(Us), blockSq + pawn_push(Us)) * rr;
572
573             // If the pawn is free to advance, then increase the bonus
574             if (pos.empty(blockSq))
575             {
576                 // If there is a rook or queen attacking/defending the pawn from behind,
577                 // consider all the squaresToQueen. Otherwise consider only the squares
578                 // in the pawn's path attacked or occupied by the enemy.
579                 defendedSquares = unsafeSquares = squaresToQueen = forward_bb(Us, s);
580
581                 Bitboard bb = forward_bb(Them, s) & pos.pieces(ROOK, QUEEN) & pos.attacks_from<ROOK>(s);
582
583                 if (!(pos.pieces(Us) & bb))
584                     defendedSquares &= ei.attackedBy[Us][ALL_PIECES];
585
586                 if (!(pos.pieces(Them) & bb))
587                     unsafeSquares &= ei.attackedBy[Them][ALL_PIECES] | pos.pieces(Them);
588
589                 // If there aren't any enemy attacks, assign a big bonus. Otherwise
590                 // assign a smaller bonus if the block square isn't attacked.
591                 int k = !unsafeSquares ? 18 : !(unsafeSquares & blockSq) ? 8 : 0;
592
593                 // If the path to the queen is fully defended, assign a big bonus.
594                 // Otherwise assign a smaller bonus if the block square is defended.
595                 if (defendedSquares == squaresToQueen)
596                     k += 6;
597
598                 else if (defendedSquares & blockSq)
599                     k += 4;
600
601                 mbonus += k * rr, ebonus += k * rr;
602             }
603             else if (pos.pieces(Us) & blockSq)
604                 mbonus += rr + r * 2, ebonus += rr + r * 2;
605         } // rr != 0
606
607         score += make_score(mbonus, ebonus) + PassedFile[file_of(s)];
608     }
609
610     if (DoTrace)
611         Trace::add(PASSED, Us, score);
612
613     // Add the scores to the middlegame and endgame eval
614     return score;
615   }
616
617
618   // evaluate_space() computes the space evaluation for a given side. The
619   // space evaluation is a simple bonus based on the number of safe squares
620   // available for minor pieces on the central four files on ranks 2--4. Safe
621   // squares one, two or three squares behind a friendly pawn are counted
622   // twice. Finally, the space bonus is multiplied by a weight. The aim is to
623   // improve play on game opening.
624   template<Color Us>
625   Score evaluate_space(const Position& pos, const EvalInfo& ei) {
626
627     const Color Them = (Us == WHITE ? BLACK : WHITE);
628     const Bitboard SpaceMask =
629       Us == WHITE ? (FileCBB | FileDBB | FileEBB | FileFBB) & (Rank2BB | Rank3BB | Rank4BB)
630                   : (FileCBB | FileDBB | FileEBB | FileFBB) & (Rank7BB | Rank6BB | Rank5BB);
631
632     // Find the safe squares for our pieces inside the area defined by
633     // SpaceMask. A square is unsafe if it is attacked by an enemy
634     // pawn, or if it is undefended and attacked by an enemy piece.
635     Bitboard safe =   SpaceMask
636                    & ~pos.pieces(Us, PAWN)
637                    & ~ei.attackedBy[Them][PAWN]
638                    & (ei.attackedBy[Us][ALL_PIECES] | ~ei.attackedBy[Them][ALL_PIECES]);
639
640     // Find all squares which are at most three squares behind some friendly pawn
641     Bitboard behind = pos.pieces(Us, PAWN);
642     behind |= (Us == WHITE ? behind >>  8 : behind <<  8);
643     behind |= (Us == WHITE ? behind >> 16 : behind << 16);
644
645     // Since SpaceMask[Us] is fully on our half of the board...
646     assert(unsigned(safe >> (Us == WHITE ? 32 : 0)) == 0);
647
648     // ...count safe + (behind & safe) with a single popcount
649     int bonus = popcount((Us == WHITE ? safe << 32 : safe >> 32) | (behind & safe));
650     int weight =  pos.count<KNIGHT>(Us) + pos.count<BISHOP>(Us)
651                 + pos.count<KNIGHT>(Them) + pos.count<BISHOP>(Them);
652
653     return make_score(bonus * weight * weight * 2 / 11, 0);
654   }
655
656
657   // evaluate_initiative() computes the initiative correction value for the
658   // position, i.e., second order bonus/malus based on the known attacking/defending
659   // status of the players.
660   Score evaluate_initiative(const Position& pos, int asymmetry, Value eg) {
661
662     int kingDistance =  distance<File>(pos.square<KING>(WHITE), pos.square<KING>(BLACK))
663                       - distance<Rank>(pos.square<KING>(WHITE), pos.square<KING>(BLACK));
664     int pawns = pos.count<PAWN>(WHITE) + pos.count<PAWN>(BLACK);
665
666     // Compute the initiative bonus for the attacking side
667     int initiative = 8 * (asymmetry + kingDistance - 15) + 12 * pawns;
668
669     // Now apply the bonus: note that we find the attacking side by extracting
670     // the sign of the endgame value, and that we carefully cap the bonus so
671     // that the endgame score will never be divided by more than two.
672     int value = ((eg > 0) - (eg < 0)) * std::max(initiative, -abs(eg / 2));
673
674     return make_score(0, value);
675   }
676
677
678   // evaluate_scale_factor() computes the scale factor for the winning side
679   ScaleFactor evaluate_scale_factor(const Position& pos, const EvalInfo& ei, Value eg) {
680
681     Color strongSide = eg > VALUE_DRAW ? WHITE : BLACK;
682     ScaleFactor sf = ei.me->scale_factor(pos, strongSide);
683
684     // If we don't already have an unusual scale factor, check for certain
685     // types of endgames, and use a lower scale for those.
686     if (    ei.me->game_phase() < PHASE_MIDGAME
687         && (sf == SCALE_FACTOR_NORMAL || sf == SCALE_FACTOR_ONEPAWN))
688     {
689         if (pos.opposite_bishops())
690         {
691             // Endgame with opposite-colored bishops and no other pieces (ignoring pawns)
692             // is almost a draw, in case of KBP vs KB, it is even more a draw.
693             if (   pos.non_pawn_material(WHITE) == BishopValueMg
694                 && pos.non_pawn_material(BLACK) == BishopValueMg)
695                 sf = more_than_one(pos.pieces(PAWN)) ? ScaleFactor(31) : ScaleFactor(9);
696
697             // Endgame with opposite-colored bishops, but also other pieces. Still
698             // a bit drawish, but not as drawish as with only the two bishops.
699             else
700                 sf = ScaleFactor(46 * sf / SCALE_FACTOR_NORMAL);
701         }
702         // Endings where weaker side can place his king in front of the opponent's
703         // pawns are drawish.
704         else if (    abs(eg) <= BishopValueEg
705                  &&  ei.pi->pawn_span(strongSide) <= 1
706                  && !pos.pawn_passed(~strongSide, pos.square<KING>(~strongSide)))
707             sf = ei.pi->pawn_span(strongSide) ? ScaleFactor(51) : ScaleFactor(37);
708     }
709
710     return sf;
711   }
712
713 } // namespace
714
715
716 /// evaluate() is the main evaluation function. It returns a static evaluation
717 /// of the position from the point of view of the side to move.
718
719 template<bool DoTrace>
720 Value Eval::evaluate(const Position& pos) {
721
722   assert(!pos.checkers());
723
724   EvalInfo ei;
725   Score score, mobility[COLOR_NB] = { SCORE_ZERO, SCORE_ZERO };
726
727   // Initialize score by reading the incrementally updated scores included in
728   // the position object (material + piece square tables). Score is computed
729   // internally from the white point of view.
730   score = pos.psq_score();
731
732   // Probe the material hash table
733   ei.me = Material::probe(pos);
734   score += ei.me->imbalance();
735
736   // If we have a specialized evaluation function for the current material
737   // configuration, call it and return.
738   if (ei.me->specialized_eval_exists())
739       return ei.me->evaluate(pos);
740
741   // Probe the pawn hash table
742   ei.pi = Pawns::probe(pos);
743   score += ei.pi->pawns_score();
744
745   // Initialize attack and king safety bitboards
746   ei.attackedBy[WHITE][ALL_PIECES] = ei.attackedBy[BLACK][ALL_PIECES] = 0;
747   eval_init<WHITE>(pos, ei);
748   eval_init<BLACK>(pos, ei);
749
750   // Pawns blocked or on ranks 2 and 3 will be excluded from the mobility area
751   Bitboard blockedPawns[] = {
752     pos.pieces(WHITE, PAWN) & (shift_bb<DELTA_S>(pos.pieces()) | Rank2BB | Rank3BB),
753     pos.pieces(BLACK, PAWN) & (shift_bb<DELTA_N>(pos.pieces()) | Rank7BB | Rank6BB)
754   };
755
756   // Do not include in mobility area squares protected by enemy pawns, or occupied
757   // by our blocked pawns or king.
758   Bitboard mobilityArea[] = {
759     ~(ei.attackedBy[BLACK][PAWN] | blockedPawns[WHITE] | pos.square<KING>(WHITE)),
760     ~(ei.attackedBy[WHITE][PAWN] | blockedPawns[BLACK] | pos.square<KING>(BLACK))
761   };
762
763   // Evaluate all pieces but king and pawns
764   score += evaluate_pieces<DoTrace>(pos, ei, mobility, mobilityArea);
765   score += mobility[WHITE] - mobility[BLACK];
766
767   // Evaluate kings after all other pieces because we need full attack
768   // information when computing the king safety evaluation.
769   score +=  evaluate_king<WHITE, DoTrace>(pos, ei)
770           - evaluate_king<BLACK, DoTrace>(pos, ei);
771
772   // Evaluate tactical threats, we need full attack information including king
773   score +=  evaluate_threats<WHITE, DoTrace>(pos, ei)
774           - evaluate_threats<BLACK, DoTrace>(pos, ei);
775
776   // Evaluate passed pawns, we need full attack information including king
777   score +=  evaluate_passed_pawns<WHITE, DoTrace>(pos, ei)
778           - evaluate_passed_pawns<BLACK, DoTrace>(pos, ei);
779
780   // If both sides have only pawns, score for potential unstoppable pawns
781   if (!pos.non_pawn_material(WHITE) && !pos.non_pawn_material(BLACK))
782   {
783       Bitboard b;
784       if ((b = ei.pi->passed_pawns(WHITE)) != 0)
785           score += Unstoppable * int(relative_rank(WHITE, frontmost_sq(WHITE, b)));
786
787       if ((b = ei.pi->passed_pawns(BLACK)) != 0)
788           score -= Unstoppable * int(relative_rank(BLACK, frontmost_sq(BLACK, b)));
789   }
790
791   // Evaluate space for both sides, only during opening
792   if (pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) >= 12222)
793       score +=  evaluate_space<WHITE>(pos, ei)
794               - evaluate_space<BLACK>(pos, ei);
795
796   // Evaluate position potential for the winning side
797   score += evaluate_initiative(pos, ei.pi->pawn_asymmetry(), eg_value(score));
798
799   // Evaluate scale factor for the winning side
800   ScaleFactor sf = evaluate_scale_factor(pos, ei, eg_value(score));
801
802   // Interpolate between a middlegame and a (scaled by 'sf') endgame score
803   Value v =  mg_value(score) * int(ei.me->game_phase())
804            + eg_value(score) * int(PHASE_MIDGAME - ei.me->game_phase()) * sf / SCALE_FACTOR_NORMAL;
805
806   v /= int(PHASE_MIDGAME);
807
808   // In case of tracing add all remaining individual evaluation terms
809   if (DoTrace)
810   {
811       Trace::add(MATERIAL, pos.psq_score());
812       Trace::add(IMBALANCE, ei.me->imbalance());
813       Trace::add(PAWN, ei.pi->pawns_score());
814       Trace::add(MOBILITY, mobility[WHITE], mobility[BLACK]);
815       Trace::add(SPACE, evaluate_space<WHITE>(pos, ei)
816                       , evaluate_space<BLACK>(pos, ei));
817       Trace::add(TOTAL, score);
818   }
819
820   return (pos.side_to_move() == WHITE ? v : -v) + Eval::Tempo; // Side to move point of view
821 }
822
823 // Explicit template instantiations
824 template Value Eval::evaluate<true >(const Position&);
825 template Value Eval::evaluate<false>(const Position&);
826
827
828 /// trace() is like evaluate(), but instead of returning a value, it returns
829 /// a string (suitable for outputting to stdout) that contains the detailed
830 /// descriptions and values of each evaluation term. Useful for debugging.
831
832 std::string Eval::trace(const Position& pos) {
833
834   std::memset(scores, 0, sizeof(scores));
835
836   Value v = evaluate<true>(pos);
837   v = pos.side_to_move() == WHITE ? v : -v; // White's point of view
838
839   std::stringstream ss;
840   ss << std::showpoint << std::noshowpos << std::fixed << std::setprecision(2)
841      << "      Eval term |    White    |    Black    |    Total    \n"
842      << "                |   MG    EG  |   MG    EG  |   MG    EG  \n"
843      << "----------------+-------------+-------------+-------------\n"
844      << "       Material | " << Term(MATERIAL)
845      << "      Imbalance | " << Term(IMBALANCE)
846      << "          Pawns | " << Term(PAWN)
847      << "        Knights | " << Term(KNIGHT)
848      << "         Bishop | " << Term(BISHOP)
849      << "          Rooks | " << Term(ROOK)
850      << "         Queens | " << Term(QUEEN)
851      << "       Mobility | " << Term(MOBILITY)
852      << "    King safety | " << Term(KING)
853      << "        Threats | " << Term(THREAT)
854      << "   Passed pawns | " << Term(PASSED)
855      << "          Space | " << Term(SPACE)
856      << "----------------+-------------+-------------+-------------\n"
857      << "          Total | " << Term(TOTAL);
858
859   ss << "\nTotal Evaluation: " << to_cp(v) << " (white side)\n";
860
861   return ss.str();
862 }
863
864
865 /// init() computes evaluation weights, usually at startup
866
867 void Eval::init() {
868
869   const int MaxSlope = 322;
870   const int Peak = 47410;
871   int t = 0;
872
873   for (int i = 0; i < 400; ++i)
874   {
875       t = std::min(Peak, std::min(i * i - 16, t + MaxSlope));
876       KingDanger[i] = make_score(t * 268 / 7700, 0);
877   }
878 }