Improved King Safety values
[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 to squares
65     // directly adjacent to the king of the given color. Pieces which attack
66     // more than one square are counted multiple times. For instance, if black's
67     // king is on g8 and there's a white knight on g5, this knight adds
68     // 2 to kingAdjacentZoneAttacksCount[BLACK].
69     int kingAdjacentZoneAttacksCount[COLOR_NB];
70
71     Bitboard pinnedPieces[COLOR_NB];
72   };
73
74   namespace Tracing {
75
76     enum Terms { // 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     EvalInfo ei;
82     ScaleFactor sf;
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     void print(std::stringstream& ss, const char* name, int idx);
88     std::string do_trace(const Position& pos);
89   }
90
91   // Evaluation weights, indexed by evaluation term
92   enum { Mobility, PawnStructure, PassedPawns, Space, KingSafety };
93   const struct Weight { int mg, eg; } Weights[] = {
94     {289, 344}, {233, 201}, {221, 273}, {46, 0}, {322, 0}
95   };
96
97   #define V(v) Value(v)
98   #define S(mg, eg) make_score(mg, eg)
99
100   // MobilityBonus[PieceType][attacked] contains bonuses for middle and end
101   // game, indexed by piece type and number of attacked squares not occupied by
102   // friendly pieces.
103   const Score MobilityBonus[][32] = {
104     {}, {},
105     { S(-65,-50), S(-42,-30), S(-9,-10), S( 3,  0), S(15, 10), S(27, 20), // Knights
106       S( 37, 28), S( 42, 31), S(44, 33) },
107     { S(-52,-47), S(-28,-23), S( 6,  1), S(20, 15), S(34, 29), S(48, 43), // Bishops
108       S( 60, 55), S( 68, 63), S(74, 68), S(77, 72), S(80, 75), S(82, 77),
109       S( 84, 79), S( 86, 81) },
110     { S(-47,-53), S(-31,-26), S(-5,  0), S( 1, 16), S( 7, 32), S(13, 48), // Rooks
111       S( 18, 64), S( 22, 80), S(26, 96), S(29,109), S(31,115), S(33,119),
112       S( 35,122), S( 36,123), S(37,124) },
113     { S(-42,-40), S(-28,-23), S(-5, -7), S( 0,  0), S( 6, 10), S(11, 19), // Queens
114       S( 13, 29), S( 18, 38), S(20, 40), S(21, 41), S(22, 41), S(22, 41),
115       S( 22, 41), S( 23, 41), S(24, 41), S(25, 41), S(25, 41), S(25, 41),
116       S( 25, 41), S( 25, 41), S(25, 41), S(25, 41), S(25, 41), S(25, 41),
117       S( 25, 41), S( 25, 41), S(25, 41), S(25, 41) }
118   };
119
120   // Outpost[PieceType][Square] contains bonuses for knights and bishops outposts,
121   // indexed by piece type and square (from white's point of view).
122   const Value Outpost[][SQUARE_NB] = {
123   {// A     B     C     D     E     F     G     H
124     V(0), V(0), V(0), V(0), V(0), V(0), V(0), V(0), // Knights
125     V(0), V(0), V(0), V(0), V(0), V(0), V(0), V(0),
126     V(0), V(0), V(4), V(8), V(8), V(4), V(0), V(0),
127     V(0), V(4),V(17),V(26),V(26),V(17), V(4), V(0),
128     V(0), V(8),V(26),V(35),V(35),V(26), V(8), V(0),
129     V(0), V(4),V(17),V(17),V(17),V(17), V(4), V(0) },
130   {
131     V(0), V(0), V(0), V(0), V(0), V(0), V(0), V(0), // Bishops
132     V(0), V(0), V(0), V(0), V(0), V(0), V(0), V(0),
133     V(0), V(0), V(5), V(5), V(5), V(5), V(0), V(0),
134     V(0), V(5),V(10),V(10),V(10),V(10), V(5), V(0),
135     V(0),V(10),V(21),V(21),V(21),V(21),V(10), V(0),
136     V(0), V(5), V(8), V(8), V(8), V(8), V(5), V(0) }
137   };
138
139   // Threat[defended/weak][minor/major attacking][attacked PieceType] contains
140   // bonuses according to which piece type attacks which one.
141   const Score Threat[][2][PIECE_TYPE_NB] = {
142   { { S(0, 0), S( 0, 0), S(19, 37), S(24, 37), S(44, 97), S(35,106) },   // Defended Minor
143     { S(0, 0), S( 0, 0), S( 9, 14), S( 9, 14), S( 7, 14), S(24, 48) } }, // Defended Major
144   { { S(0, 0), S( 0,32), S(33, 41), S(31, 50), S(41,100), S(35,104) },   // Weak Minor
145     { S(0, 0), S( 0,27), S(26, 57), S(26, 57), S(0 , 43), S(23, 51) } }  // Weak Major
146   };
147
148   // ThreatenedByPawn[PieceType] contains a penalty according to which piece
149   // type is attacked by an enemy pawn.
150   const Score ThreatenedByPawn[] = {
151     S(0, 0), S(0, 0), S(87, 118), S(84, 122), S(114, 203), S(121, 217)
152   };
153
154   // Assorted bonuses and penalties used by evaluation
155   const Score KingOnOne          = S( 2, 58);
156   const Score KingOnMany         = S( 6,125);
157   const Score RookOnPawn         = S( 7, 27);
158   const Score RookOnOpenFile     = S(43, 21);
159   const Score RookOnSemiOpenFile = S(19, 10);
160   const Score BishopPawns        = S( 8, 12);
161   const Score MinorBehindPawn    = S(16,  0);
162   const Score TrappedRook        = S(92,  0);
163   const Score Unstoppable        = S( 0, 20);
164   const Score Hanging            = S(31, 26);
165
166   // Penalty for a bishop on a1/h1 (a8/h8 for black) which is trapped by
167   // a friendly pawn on b2/g2 (b7/g7 for black). This can obviously only
168   // happen in Chess960 games.
169   const Score TrappedBishopA1H1 = S(50, 50);
170
171   #undef S
172   #undef V
173
174   // SpaceMask[Color] contains the area of the board which is considered
175   // by the space evaluation. In the middlegame, each side is given a bonus
176   // based on how many squares inside this area are safe and available for
177   // friendly minor pieces.
178   const Bitboard SpaceMask[] = {
179     (FileCBB | FileDBB | FileEBB | FileFBB) & (Rank2BB | Rank3BB | Rank4BB),
180     (FileCBB | FileDBB | FileEBB | FileFBB) & (Rank7BB | Rank6BB | Rank5BB)
181   };
182
183   // King danger constants and variables. The king danger scores are looked-up
184   // in KingDanger[]. Various little "meta-bonuses" measuring the strength
185   // of the enemy attack are added up into an integer, which is used as an
186   // index to KingDanger[].
187   //
188   // KingAttackWeights[PieceType] contains king attack weights by piece type
189   const int KingAttackWeights[] = { 0, 0, 7, 5, 4, 1 };
190
191   // Bonuses for enemy's safe checks
192   const int QueenContactCheck = 89;
193   const int RookContactCheck  = 71;
194   const int QueenCheck        = 50;
195   const int RookCheck         = 37;
196   const int BishopCheck       = 6;
197   const int KnightCheck       = 14;
198
199   // KingDanger[attackUnits] contains the actual king danger weighted
200   // scores, indexed by a calculated integer number.
201   Score KingDanger[512];
202
203   // apply_weight() weighs score 's' by weight 'w' trying to prevent overflow
204   Score apply_weight(Score s, const Weight& w) {
205     return make_score(mg_value(s) * w.mg / 256, eg_value(s) * w.eg / 256);
206   }
207
208
209   // init_eval_info() initializes king bitboards for given color adding
210   // pawn attacks. To be done at the beginning of the evaluation.
211
212   template<Color Us>
213   void init_eval_info(const Position& pos, EvalInfo& ei) {
214
215     const Color  Them = (Us == WHITE ? BLACK : WHITE);
216     const Square Down = (Us == WHITE ? DELTA_S : DELTA_N);
217
218     ei.pinnedPieces[Us] = pos.pinned_pieces(Us);
219
220     Bitboard b = ei.attackedBy[Them][KING] = pos.attacks_from<KING>(pos.king_square(Them));
221     ei.attackedBy[Us][ALL_PIECES] = ei.attackedBy[Us][PAWN] = ei.pi->pawn_attacks(Us);
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) * 31 / 256
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
497     enum { Defended, Weak };
498     enum { Minor, Major };
499
500     Bitboard b, weak, defended;
501     Score score = SCORE_ZERO;
502
503     // Non-pawn enemies defended by a pawn
504     defended =  (pos.pieces(Them) ^ pos.pieces(Them, PAWN))
505               &  ei.attackedBy[Them][PAWN];
506
507     // Add a bonus according to the kind of attacking pieces
508     if (defended)
509     {
510         b = defended & (ei.attackedBy[Us][KNIGHT] | ei.attackedBy[Us][BISHOP]);
511         while (b)
512             score += Threat[Defended][Minor][type_of(pos.piece_on(pop_lsb(&b)))];
513
514         b = defended & (ei.attackedBy[Us][ROOK]);
515         while (b)
516             score += Threat[Defended][Major][type_of(pos.piece_on(pop_lsb(&b)))];
517     }
518
519     // Enemies not defended by a pawn and under our attack
520     weak =   pos.pieces(Them)
521           & ~ei.attackedBy[Them][PAWN]
522           &  ei.attackedBy[Us][ALL_PIECES];
523
524     // Add a bonus according to the kind of attacking pieces
525     if (weak)
526     {
527         b = weak & (ei.attackedBy[Us][KNIGHT] | ei.attackedBy[Us][BISHOP]);
528         while (b)
529             score += Threat[Weak][Minor][type_of(pos.piece_on(pop_lsb(&b)))];
530
531         b = weak & (ei.attackedBy[Us][ROOK] | ei.attackedBy[Us][QUEEN]);
532         while (b)
533             score += Threat[Weak][Major][type_of(pos.piece_on(pop_lsb(&b)))];
534
535         b = weak & ~ei.attackedBy[Them][ALL_PIECES];
536         if (b)
537             score += Hanging * popcount<Max15>(b);
538
539         b = weak & ei.attackedBy[Us][KING];
540         if (b)
541             score += more_than_one(b) ? KingOnMany : KingOnOne;
542     }
543
544     if (Trace)
545         Tracing::write(Tracing::THREAT, Us, score);
546
547     return score;
548   }
549
550
551   // evaluate_passed_pawns() evaluates the passed pawns of the given color
552
553   template<Color Us, bool Trace>
554   Score evaluate_passed_pawns(const Position& pos, const EvalInfo& ei) {
555
556     const Color Them = (Us == WHITE ? BLACK : WHITE);
557
558     Bitboard b, squaresToQueen, defendedSquares, unsafeSquares;
559     Score score = SCORE_ZERO;
560
561     b = ei.pi->passed_pawns(Us);
562
563     while (b)
564     {
565         Square s = pop_lsb(&b);
566
567         assert(pos.pawn_passed(Us, s));
568
569         int r = relative_rank(Us, s) - RANK_2;
570         int rr = r * (r - 1);
571
572         // Base bonus based on rank
573         Value mbonus = Value(17 * rr), ebonus = Value(7 * (rr + r + 1));
574
575         if (rr)
576         {
577             Square blockSq = s + pawn_push(Us);
578
579             // Adjust bonus based on the king's proximity
580             ebonus +=  distance(pos.king_square(Them), blockSq) * 5 * rr
581                      - distance(pos.king_square(Us  ), blockSq) * 2 * rr;
582
583             // If blockSq is not the queening square then consider also a second push
584             if (relative_rank(Us, blockSq) != RANK_8)
585                 ebonus -= distance(pos.king_square(Us), blockSq + pawn_push(Us)) * rr;
586
587             // If the pawn is free to advance, then increase the bonus
588             if (pos.empty(blockSq))
589             {
590                 // If there is a rook or queen attacking/defending the pawn from behind,
591                 // consider all the squaresToQueen. Otherwise consider only the squares
592                 // in the pawn's path attacked or occupied by the enemy.
593                 defendedSquares = unsafeSquares = squaresToQueen = forward_bb(Us, s);
594
595                 Bitboard bb = forward_bb(Them, s) & pos.pieces(ROOK, QUEEN) & pos.attacks_from<ROOK>(s);
596
597                 if (!(pos.pieces(Us) & bb))
598                     defendedSquares &= ei.attackedBy[Us][ALL_PIECES];
599
600                 if (!(pos.pieces(Them) & bb))
601                     unsafeSquares &= ei.attackedBy[Them][ALL_PIECES] | pos.pieces(Them);
602
603                 // If there aren't any enemy attacks, assign a big bonus. Otherwise
604                 // assign a smaller bonus if the block square isn't attacked.
605                 int k = !unsafeSquares ? 15 : !(unsafeSquares & blockSq) ? 9 : 0;
606
607                 // If the path to queen is fully defended, assign a big bonus.
608                 // Otherwise assign a smaller bonus if the block square is defended.
609                 if (defendedSquares == squaresToQueen)
610                     k += 6;
611
612                 else if (defendedSquares & blockSq)
613                     k += 4;
614
615                 mbonus += k * rr, ebonus += k * rr;
616             }
617             else if (pos.pieces(Us) & blockSq)
618                 mbonus += rr * 3 + r * 2 + 3, ebonus += rr + r * 2;
619         } // rr != 0
620
621         if (pos.count<PAWN>(Us) < pos.count<PAWN>(Them))
622             ebonus += ebonus / 4;
623
624         score += make_score(mbonus, ebonus);
625     }
626
627     if (Trace)
628         Tracing::write(Tracing::PASSED, Us, apply_weight(score, Weights[PassedPawns]));
629
630     // Add the scores to the middlegame and endgame eval
631     return apply_weight(score, Weights[PassedPawns]);
632   }
633
634
635   // evaluate_space() computes the space evaluation for a given side. The
636   // space evaluation is a simple bonus based on the number of safe squares
637   // available for minor pieces on the central four files on ranks 2--4. Safe
638   // squares one, two or three squares behind a friendly pawn are counted
639   // twice. Finally, the space bonus is multiplied by a weight. The aim is to
640   // improve play on game opening.
641   template<Color Us>
642   Score evaluate_space(const Position& pos, const EvalInfo& ei) {
643
644     const Color Them = (Us == WHITE ? BLACK : WHITE);
645
646     // Find the safe squares for our pieces inside the area defined by
647     // SpaceMask[]. A square is unsafe if it is attacked by an enemy
648     // pawn, or if it is undefended and attacked by an enemy piece.
649     Bitboard safe =   SpaceMask[Us]
650                    & ~pos.pieces(Us, PAWN)
651                    & ~ei.attackedBy[Them][PAWN]
652                    & (ei.attackedBy[Us][ALL_PIECES] | ~ei.attackedBy[Them][ALL_PIECES]);
653
654     // Find all squares which are at most three squares behind some friendly pawn
655     Bitboard behind = pos.pieces(Us, PAWN);
656     behind |= (Us == WHITE ? behind >>  8 : behind <<  8);
657     behind |= (Us == WHITE ? behind >> 16 : behind << 16);
658
659     // Since SpaceMask[Us] is fully on our half of the board
660     assert(unsigned(safe >> (Us == WHITE ? 32 : 0)) == 0);
661
662     // Count safe + (behind & safe) with a single popcount
663     int bonus = popcount<Full>((Us == WHITE ? safe << 32 : safe >> 32) | (behind & safe));
664     int weight =  pos.count<KNIGHT>(Us) + pos.count<BISHOP>(Us)
665                 + pos.count<KNIGHT>(Them) + pos.count<BISHOP>(Them);
666
667     return make_score(bonus * weight * weight, 0);
668   }
669
670
671   // do_evaluate() is the evaluation entry point, called directly from evaluate()
672
673   template<bool Trace>
674   Value do_evaluate(const Position& pos) {
675
676     assert(!pos.checkers());
677
678     EvalInfo ei;
679     Score score, mobility[2] = { SCORE_ZERO, SCORE_ZERO };
680
681     // Initialize score by reading the incrementally updated scores included
682     // in the position object (material + piece square tables).
683     // Score is computed from the point of view of white.
684     score = pos.psq_score();
685
686     // Probe the material hash table
687     ei.mi = Material::probe(pos);
688     score += ei.mi->imbalance();
689
690     // If we have a specialized evaluation function for the current material
691     // configuration, call it and return.
692     if (ei.mi->specialized_eval_exists())
693         return ei.mi->evaluate(pos);
694
695     // Probe the pawn hash table
696     ei.pi = Pawns::probe(pos);
697     score += apply_weight(ei.pi->pawns_score(), Weights[PawnStructure]);
698
699     // Initialize attack and king safety bitboards
700     init_eval_info<WHITE>(pos, ei);
701     init_eval_info<BLACK>(pos, ei);
702
703     ei.attackedBy[WHITE][ALL_PIECES] |= ei.attackedBy[WHITE][KING];
704     ei.attackedBy[BLACK][ALL_PIECES] |= ei.attackedBy[BLACK][KING];
705
706     // Do not include in mobility squares protected by enemy pawns or occupied by our pawns or king
707     Bitboard mobilityArea[] = { ~(ei.attackedBy[BLACK][PAWN] | pos.pieces(WHITE, PAWN, KING)),
708                                 ~(ei.attackedBy[WHITE][PAWN] | pos.pieces(BLACK, PAWN, KING)) };
709
710     // Evaluate pieces and mobility
711     score += evaluate_pieces<KNIGHT, WHITE, Trace>(pos, ei, mobility, mobilityArea);
712     score += apply_weight(mobility[WHITE] - mobility[BLACK], Weights[Mobility]);
713
714     // Evaluate kings after all other pieces because we need complete attack
715     // information when computing the king safety evaluation.
716     score +=  evaluate_king<WHITE, Trace>(pos, ei)
717             - evaluate_king<BLACK, Trace>(pos, ei);
718
719     // Evaluate tactical threats, we need full attack information including king
720     score +=  evaluate_threats<WHITE, Trace>(pos, ei)
721             - evaluate_threats<BLACK, Trace>(pos, ei);
722
723     // Evaluate passed pawns, we need full attack information including king
724     score +=  evaluate_passed_pawns<WHITE, Trace>(pos, ei)
725             - evaluate_passed_pawns<BLACK, Trace>(pos, ei);
726
727     // If both sides have only pawns, score for potential unstoppable pawns
728     if (!pos.non_pawn_material(WHITE) && !pos.non_pawn_material(BLACK))
729     {
730         Bitboard b;
731         if ((b = ei.pi->passed_pawns(WHITE)) != 0)
732             score += int(relative_rank(WHITE, frontmost_sq(WHITE, b))) * Unstoppable;
733
734         if ((b = ei.pi->passed_pawns(BLACK)) != 0)
735             score -= int(relative_rank(BLACK, frontmost_sq(BLACK, b))) * Unstoppable;
736     }
737
738     // Evaluate space for both sides, only during opening
739     if (pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) >= 2 * QueenValueMg + 4 * RookValueMg + 2 * KnightValueMg)
740     {
741         Score s = evaluate_space<WHITE>(pos, ei) - evaluate_space<BLACK>(pos, ei);
742         score += apply_weight(s, Weights[Space]);
743     }
744
745     // Scale winning side if position is more drawish than it appears
746     Color strongSide = eg_value(score) > VALUE_DRAW ? WHITE : BLACK;
747     ScaleFactor sf = ei.mi->scale_factor(pos, strongSide);
748
749     // If we don't already have an unusual scale factor, check for certain
750     // types of endgames, and use a lower scale for those.
751     if (    ei.mi->game_phase() < PHASE_MIDGAME
752         && (sf == SCALE_FACTOR_NORMAL || sf == SCALE_FACTOR_ONEPAWN))
753     {
754         if (pos.opposite_bishops())
755         {
756             // Endgame with opposite-colored bishops and no other pieces (ignoring pawns)
757             // is almost a draw, in case of KBP vs KB is even more a draw.
758             if (   pos.non_pawn_material(WHITE) == BishopValueMg
759                 && pos.non_pawn_material(BLACK) == BishopValueMg)
760                 sf = more_than_one(pos.pieces(PAWN)) ? ScaleFactor(32) : ScaleFactor(8);
761
762             // Endgame with opposite-colored bishops, but also other pieces. Still
763             // a bit drawish, but not as drawish as with only the two bishops.
764             else
765                  sf = ScaleFactor(50 * sf / SCALE_FACTOR_NORMAL);
766         }
767         // Endings where weaker side can place his king in front of the opponent's
768         // pawns are drawish.
769         else if (    abs(eg_value(score)) <= BishopValueEg
770                  &&  ei.pi->pawn_span(strongSide) <= 1
771                  && !pos.pawn_passed(~strongSide, pos.king_square(~strongSide)))
772                  sf = ei.pi->pawn_span(strongSide) ? ScaleFactor(56) : ScaleFactor(38);
773     }
774
775     // Interpolate between a middlegame and a (scaled by 'sf') endgame score
776     Value v =  mg_value(score) * int(ei.mi->game_phase())
777              + eg_value(score) * int(PHASE_MIDGAME - ei.mi->game_phase()) * sf / SCALE_FACTOR_NORMAL;
778
779     v /= int(PHASE_MIDGAME);
780
781     // In case of tracing add all single evaluation contributions for both white and black
782     if (Trace)
783     {
784         Tracing::write(Tracing::MATERIAL, pos.psq_score());
785         Tracing::write(Tracing::IMBALANCE, ei.mi->imbalance());
786         Tracing::write(PAWN, ei.pi->pawns_score());
787         Tracing::write(Tracing::MOBILITY, apply_weight(mobility[WHITE], Weights[Mobility])
788                                         , apply_weight(mobility[BLACK], Weights[Mobility]));
789         Tracing::write(Tracing::SPACE, apply_weight(evaluate_space<WHITE>(pos, ei), Weights[Space])
790                                      , apply_weight(evaluate_space<BLACK>(pos, ei), Weights[Space]));
791         Tracing::write(Tracing::TOTAL, score);
792         Tracing::ei = ei;
793         Tracing::sf = sf;
794     }
795
796     return (pos.side_to_move() == WHITE ? v : -v) + Eval::Tempo;
797   }
798
799
800   // Tracing function definitions
801
802   double Tracing::to_cp(Value v) { return double(v) / PawnValueEg; }
803
804   void Tracing::write(int idx, Color c, Score s) { scores[c][idx] = s; }
805
806   void Tracing::write(int idx, Score w, Score b) {
807
808     write(idx, WHITE, w);
809     write(idx, BLACK, b);
810   }
811
812   void Tracing::print(std::stringstream& ss, const char* name, int idx) {
813
814     Score wScore = scores[WHITE][idx];
815     Score bScore = scores[BLACK][idx];
816
817     switch (idx) {
818     case MATERIAL: case IMBALANCE: case PAWN: case TOTAL:
819         ss << std::setw(15) << name << " |   ---   --- |   ---   --- | "
820            << std::setw(5)  << to_cp(mg_value(wScore - bScore)) << " "
821            << std::setw(5)  << to_cp(eg_value(wScore - bScore)) << " \n";
822         break;
823     default:
824         ss << std::setw(15) << name << " | " << std::noshowpos
825            << std::setw(5)  << to_cp(mg_value(wScore)) << " "
826            << std::setw(5)  << to_cp(eg_value(wScore)) << " | "
827            << std::setw(5)  << to_cp(mg_value(bScore)) << " "
828            << std::setw(5)  << to_cp(eg_value(bScore)) << " | "
829            << std::setw(5)  << to_cp(mg_value(wScore - bScore)) << " "
830            << std::setw(5)  << to_cp(eg_value(wScore - bScore)) << " \n";
831     }
832   }
833
834   std::string Tracing::do_trace(const Position& pos) {
835
836     std::memset(scores, 0, sizeof(scores));
837
838     Value v = do_evaluate<true>(pos);
839     v = pos.side_to_move() == WHITE ? v : -v; // White's point of view
840
841     std::stringstream ss;
842     ss << std::showpoint << std::noshowpos << std::fixed << std::setprecision(2)
843        << "      Eval term |    White    |    Black    |    Total    \n"
844        << "                |   MG    EG  |   MG    EG  |   MG    EG  \n"
845        << "----------------+-------------+-------------+-------------\n";
846
847     print(ss, "Material", MATERIAL);
848     print(ss, "Imbalance", IMBALANCE);
849     print(ss, "Pawns", PAWN);
850     print(ss, "Knights", KNIGHT);
851     print(ss, "Bishops", BISHOP);
852     print(ss, "Rooks", ROOK);
853     print(ss, "Queens", QUEEN);
854     print(ss, "Mobility", MOBILITY);
855     print(ss, "King safety", KING);
856     print(ss, "Threats", THREAT);
857     print(ss, "Passed pawns", PASSED);
858     print(ss, "Space", SPACE);
859
860     ss << "----------------+-------------+-------------+-------------\n";
861     print(ss, "Total", TOTAL);
862
863     ss << "\nTotal Evaluation: " << to_cp(v) << " (white side)\n";
864
865     return ss.str();
866   }
867
868 } // namespace
869
870
871 namespace Eval {
872
873   /// evaluate() is the main evaluation function. It returns a static evaluation
874   /// of the position always from the point of view of the side to move.
875
876   Value evaluate(const Position& pos) {
877     return do_evaluate<false>(pos);
878   }
879
880
881   /// trace() is like evaluate(), but instead of returning a value, it returns
882   /// a string (suitable for outputting to stdout) that contains the detailed
883   /// descriptions and values of each evaluation term. It's mainly used for
884   /// debugging.
885   std::string trace(const Position& pos) {
886     return Tracing::do_trace(pos);
887   }
888
889
890   /// init() computes evaluation weights, usually at startup
891
892   void init() {
893
894     const double MaxSlope = 8.7;
895     const double Peak = 1280;
896     double t = 0.0;
897
898     for (int i = 1; i < 400; ++i)
899     {
900         t = std::min(Peak, std::min(0.027 * i * i, t + MaxSlope));
901         KingDanger[i] = apply_weight(make_score(int(t), 0), Weights[KingSafety]);
902     }
903   }
904
905 } // namespace Eval