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