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