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