Use templates for end game evaluation functions
[stockfish] / src / endgame.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 Marco Costalba
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
21 ////
22 //// Includes
23 ////
24
25 #include <cassert>
26
27 #include "bitbase.h"
28 #include "endgame.h"
29
30
31 ////
32 //// Constants and variables
33 ////
34
35 /// Evaluation functions
36
37 // Generic "mate lone king" eval
38 EvaluationFunction<KXK> EvaluateKXK(WHITE), EvaluateKKX(BLACK);
39
40 // K and two minors vs K and one or two minors
41 EvaluationFunction<KmmKm> EvaluateKmmKm(WHITE);
42
43 EvaluationFunction<KBNK> EvaluateKBNK(WHITE), EvaluateKKBN(BLACK); // KBN vs K
44 EvaluationFunction<KPK> EvaluateKPK(WHITE), EvaluateKKP(BLACK);    // KP vs K
45 EvaluationFunction<KRKP> EvaluateKRKP(WHITE), EvaluateKPKR(BLACK); // KR vs KP
46 EvaluationFunction<KRKB> EvaluateKRKB(WHITE), EvaluateKBKR(BLACK); // KR vs KB
47 EvaluationFunction<KRKN> EvaluateKRKN(WHITE), EvaluateKNKR(BLACK); // KR vs KN
48 EvaluationFunction<KQKR> EvaluateKQKR(WHITE), EvaluateKRKQ(BLACK); // KQ vs KR
49 EvaluationFunction<KBBKN> EvaluateKBBKN(WHITE), EvaluateKNKBB(BLACK); // KBB vs KN
50
51
52 /// Scaling functions
53
54 // KBP vs K
55 KBPKScalingFunction ScaleKBPK = KBPKScalingFunction(WHITE);
56 KBPKScalingFunction ScaleKKBP = KBPKScalingFunction(BLACK);
57
58 // KQ vs KRP
59 KQKRPScalingFunction ScaleKQKRP = KQKRPScalingFunction(WHITE);
60 KQKRPScalingFunction ScaleKRPKQ = KQKRPScalingFunction(BLACK);
61
62 // KRP vs KR
63 KRPKRScalingFunction ScaleKRPKR = KRPKRScalingFunction(WHITE);
64 KRPKRScalingFunction ScaleKRKRP = KRPKRScalingFunction(BLACK);
65
66 // KRPP vs KRP
67 KRPPKRPScalingFunction ScaleKRPPKRP = KRPPKRPScalingFunction(WHITE);
68 KRPPKRPScalingFunction ScaleKRPKRPP = KRPPKRPScalingFunction(BLACK);
69
70 // King and pawns vs king
71 KPsKScalingFunction ScaleKPsK = KPsKScalingFunction(WHITE);
72 KPsKScalingFunction ScaleKKPs = KPsKScalingFunction(BLACK);
73
74 // KBP vs KB
75 KBPKBScalingFunction ScaleKBPKB = KBPKBScalingFunction(WHITE);
76 KBPKBScalingFunction ScaleKBKBP = KBPKBScalingFunction(BLACK);
77
78 // KBP vs KN
79 KBPKNScalingFunction ScaleKBPKN = KBPKNScalingFunction(WHITE);
80 KBPKNScalingFunction ScaleKNKBP = KBPKNScalingFunction(BLACK);
81
82 // KNP vs K
83 KNPKScalingFunction ScaleKNPK = KNPKScalingFunction(WHITE);
84 KNPKScalingFunction ScaleKKNP = KNPKScalingFunction(BLACK);
85
86 // KPKP
87 KPKPScalingFunction ScaleKPKPw = KPKPScalingFunction(WHITE);
88 KPKPScalingFunction ScaleKPKPb = KPKPScalingFunction(BLACK);
89
90
91 ////
92 //// Local definitions
93 ////
94
95 namespace {
96
97   // Table used to drive the defending king towards the edge of the board
98   // in KX vs K and KQ vs KR endgames.
99   const uint8_t MateTable[64] = {
100     100, 90, 80, 70, 70, 80, 90, 100,
101      90, 70, 60, 50, 50, 60, 70,  90,
102      80, 60, 40, 30, 30, 40, 60,  80,
103      70, 50, 30, 20, 20, 30, 50,  70,
104      70, 50, 30, 20, 20, 30, 50,  70,
105      80, 60, 40, 30, 30, 40, 60,  80,
106      90, 70, 60, 50, 50, 60, 70,  90,
107     100, 90, 80, 70, 70, 80, 90, 100,
108   };
109
110   // Table used to drive the defending king towards a corner square of the
111   // right color in KBN vs K endgames.
112   const uint8_t KBNKMateTable[64] = {
113     200, 190, 180, 170, 160, 150, 140, 130,
114     190, 180, 170, 160, 150, 140, 130, 140,
115     180, 170, 155, 140, 140, 125, 140, 150,
116     170, 160, 140, 120, 110, 140, 150, 160,
117     160, 150, 140, 110, 120, 140, 160, 170,
118     150, 140, 125, 140, 140, 155, 170, 180,
119     140, 130, 140, 150, 160, 170, 180, 190,
120     130, 140, 150, 160, 170, 180, 190, 200
121   };
122
123   // The attacking side is given a descending bonus based on distance between
124   // the two kings in basic endgames.
125   const int DistanceBonus[8] = { 0, 0, 100, 80, 60, 40, 20, 10 };
126
127   // Bitbase for KP vs K
128   uint8_t KPKBitbase[24576];
129
130   // Penalty for big distance between king and knight for the defending king
131   // and knight in KR vs KN endgames.
132   const int KRKNKingKnightDistancePenalty[8] = { 0, 0, 4, 10, 20, 32, 48, 70 };
133
134   // Various inline functions for accessing the above arrays
135   inline Value mate_table(Square s) {
136     return Value(MateTable[s]);
137   }
138
139   inline Value kbnk_mate_table(Square s) {
140     return Value(KBNKMateTable[s]);
141   }
142
143   inline Value distance_bonus(int d) {
144     return Value(DistanceBonus[d]);
145   }
146
147   inline Value krkn_king_knight_distance_penalty(int d) {
148     return Value(KRKNKingKnightDistancePenalty[d]);
149   }
150
151   // Function for probing the KP vs K bitbase
152   int probe_kpk(Square wksq, Square wpsq, Square bksq, Color stm);
153
154 }
155
156
157 ////
158 //// Functions
159 ////
160
161 /// Constructors
162
163 EndgameEvaluationFunction::EndgameEvaluationFunction(Color c) : strongerSide(c) {
164   weakerSide = opposite_color(strongerSide);
165 }
166
167 ScalingFunction::ScalingFunction(Color c) : strongerSide(c) {
168   weakerSide = opposite_color(c);
169 }
170
171 KBPKScalingFunction::KBPKScalingFunction(Color c)       : ScalingFunction(c) {}
172 KQKRPScalingFunction::KQKRPScalingFunction(Color c)     : ScalingFunction(c) {}
173 KRPKRScalingFunction::KRPKRScalingFunction(Color c)     : ScalingFunction(c) {}
174 KRPPKRPScalingFunction::KRPPKRPScalingFunction(Color c) : ScalingFunction(c) {}
175 KPsKScalingFunction::KPsKScalingFunction(Color c)       : ScalingFunction(c) {}
176 KBPKBScalingFunction::KBPKBScalingFunction(Color c)     : ScalingFunction(c) {}
177 KBPKNScalingFunction::KBPKNScalingFunction(Color c)     : ScalingFunction(c) {}
178 KNPKScalingFunction::KNPKScalingFunction(Color c)       : ScalingFunction(c) {}
179 KPKPScalingFunction::KPKPScalingFunction(Color c)       : ScalingFunction(c) {}
180
181
182 /// Mate with KX vs K. This function is used to evaluate positions with
183 /// King and plenty of material vs a lone king. It simply gives the
184 /// attacking side a bonus for driving the defending king towards the edge
185 /// of the board, and for keeping the distance between the two kings small.
186 template<>
187 Value EvaluationFunction<KXK>::apply(const Position& pos) {
188
189   assert(pos.non_pawn_material(weakerSide) == Value(0));
190   assert(pos.piece_count(weakerSide, PAWN) == Value(0));
191
192   Square winnerKSq = pos.king_square(strongerSide);
193   Square loserKSq = pos.king_square(weakerSide);
194
195   Value result =   pos.non_pawn_material(strongerSide)
196                  + pos.piece_count(strongerSide, PAWN) * PawnValueEndgame
197                  + mate_table(loserKSq)
198                  + distance_bonus(square_distance(winnerKSq, loserKSq));
199
200   if (   pos.piece_count(strongerSide, QUEEN) > 0
201       || pos.piece_count(strongerSide, ROOK) > 0
202       || pos.piece_count(strongerSide, BISHOP) > 1)
203       // TODO: check for two equal-colored bishops!
204       result += VALUE_KNOWN_WIN;
205
206   return (strongerSide == pos.side_to_move() ? result : -result);
207 }
208
209
210 /// Mate with KBN vs K. This is similar to KX vs K, but we have to drive the
211 /// defending king towards a corner square of the right color.
212 template<>
213 Value EvaluationFunction<KBNK>::apply(const Position& pos) {
214
215   assert(pos.non_pawn_material(weakerSide) == Value(0));
216   assert(pos.piece_count(weakerSide, PAWN) == Value(0));
217   assert(pos.non_pawn_material(strongerSide) == KnightValueMidgame + BishopValueMidgame);
218   assert(pos.piece_count(strongerSide, BISHOP) == 1);
219   assert(pos.piece_count(strongerSide, KNIGHT) == 1);
220   assert(pos.piece_count(strongerSide, PAWN) == 0);
221
222   Square winnerKSq = pos.king_square(strongerSide);
223   Square loserKSq = pos.king_square(weakerSide);
224   Square bishopSquare = pos.piece_list(strongerSide, BISHOP, 0);
225
226   if (square_color(bishopSquare) == BLACK)
227   {
228       winnerKSq = flop_square(winnerKSq);
229       loserKSq = flop_square(loserKSq);
230   }
231
232   Value result =  VALUE_KNOWN_WIN
233                 + distance_bonus(square_distance(winnerKSq, loserKSq))
234                 + kbnk_mate_table(loserKSq);
235
236   return (strongerSide == pos.side_to_move() ? result : -result);
237 }
238
239
240 /// KP vs K. This endgame is evaluated with the help of a bitbase.
241 template<>
242 Value EvaluationFunction<KPK>::apply(const Position& pos) {
243
244   assert(pos.non_pawn_material(strongerSide) == Value(0));
245   assert(pos.non_pawn_material(weakerSide) == Value(0));
246   assert(pos.piece_count(strongerSide, PAWN) == 1);
247   assert(pos.piece_count(weakerSide, PAWN) == 0);
248
249   Square wksq, bksq, wpsq;
250   Color stm;
251
252   if (strongerSide == WHITE)
253   {
254       wksq = pos.king_square(WHITE);
255       bksq = pos.king_square(BLACK);
256       wpsq = pos.piece_list(WHITE, PAWN, 0);
257       stm = pos.side_to_move();
258   }
259   else
260   {
261       wksq = flip_square(pos.king_square(BLACK));
262       bksq = flip_square(pos.king_square(WHITE));
263       wpsq = flip_square(pos.piece_list(BLACK, PAWN, 0));
264       stm = opposite_color(pos.side_to_move());
265   }
266
267   if (square_file(wpsq) >= FILE_E)
268   {
269     wksq = flop_square(wksq);
270     bksq = flop_square(bksq);
271     wpsq = flop_square(wpsq);
272   }
273
274   if (!probe_kpk(wksq, wpsq, bksq, stm))
275       return VALUE_DRAW;
276
277   Value result =  VALUE_KNOWN_WIN
278                 + PawnValueEndgame
279                 + Value(square_rank(wpsq));
280
281   return (strongerSide == pos.side_to_move() ? result : -result);
282 }
283
284
285 /// KR vs KP. This is a somewhat tricky endgame to evaluate precisely without
286 /// a bitbase. The function below returns drawish scores when the pawn is
287 /// far advanced with support of the king, while the attacking king is far
288 /// away.
289 template<>
290 Value EvaluationFunction<KRKP>::apply(const Position& pos) {
291
292   assert(pos.non_pawn_material(strongerSide) == RookValueMidgame);
293   assert(pos.piece_count(strongerSide, PAWN) == 0);
294   assert(pos.non_pawn_material(weakerSide) == 0);
295   assert(pos.piece_count(weakerSide, PAWN) == 1);
296
297   Square wksq, wrsq, bksq, bpsq;
298   int tempo = (pos.side_to_move() == strongerSide);
299
300   wksq = pos.king_square(strongerSide);
301   wrsq = pos.piece_list(strongerSide, ROOK, 0);
302   bksq = pos.king_square(weakerSide);
303   bpsq = pos.piece_list(weakerSide, PAWN, 0);
304
305   if (strongerSide == BLACK)
306   {
307       wksq = flip_square(wksq);
308       wrsq = flip_square(wrsq);
309       bksq = flip_square(bksq);
310       bpsq = flip_square(bpsq);
311   }
312
313   Square queeningSq = make_square(square_file(bpsq), RANK_1);
314   Value result;
315
316   // If the stronger side's king is in front of the pawn, it's a win
317   if (wksq < bpsq && square_file(wksq) == square_file(bpsq))
318       result = RookValueEndgame - Value(square_distance(wksq, bpsq));
319
320   // If the weaker side's king is too far from the pawn and the rook,
321   // it's a win
322   else if (   square_distance(bksq, bpsq) - (tempo^1) >= 3
323            && square_distance(bksq, wrsq) >= 3)
324       result = RookValueEndgame - Value(square_distance(wksq, bpsq));
325
326   // If the pawn is far advanced and supported by the defending king,
327   // the position is drawish
328   else if (   square_rank(bksq) <= RANK_3
329            && square_distance(bksq, bpsq) == 1
330            && square_rank(wksq) >= RANK_4
331            && square_distance(wksq, bpsq) - tempo > 2)
332       result = Value(80 - square_distance(wksq, bpsq) * 8);
333
334   else
335       result =  Value(200)
336               - Value(square_distance(wksq, bpsq + DELTA_S) * 8)
337               + Value(square_distance(bksq, bpsq + DELTA_S) * 8)
338               + Value(square_distance(bpsq, queeningSq) * 8);
339
340   return (strongerSide == pos.side_to_move() ? result : -result);
341 }
342
343
344 /// KR vs KB. This is very simple, and always returns drawish scores.  The
345 /// score is slightly bigger when the defending king is close to the edge.
346 template<>
347 Value EvaluationFunction<KRKB>::apply(const Position& pos) {
348
349   assert(pos.non_pawn_material(strongerSide) == RookValueMidgame);
350   assert(pos.piece_count(strongerSide, PAWN) == 0);
351   assert(pos.non_pawn_material(weakerSide) == BishopValueMidgame);
352   assert(pos.piece_count(weakerSide, PAWN) == 0);
353   assert(pos.piece_count(weakerSide, BISHOP) == 1);
354
355   Value result = mate_table(pos.king_square(weakerSide));
356   return (pos.side_to_move() == strongerSide ? result : -result);
357 }
358
359
360 /// KR vs KN.  The attacking side has slightly better winning chances than
361 /// in KR vs KB, particularly if the king and the knight are far apart.
362 template<>
363 Value EvaluationFunction<KRKN>::apply(const Position& pos) {
364
365   assert(pos.non_pawn_material(strongerSide) == RookValueMidgame);
366   assert(pos.piece_count(strongerSide, PAWN) == 0);
367   assert(pos.non_pawn_material(weakerSide) == KnightValueMidgame);
368   assert(pos.piece_count(weakerSide, PAWN) == 0);
369   assert(pos.piece_count(weakerSide, KNIGHT) == 1);
370
371   Square defendingKSq = pos.king_square(weakerSide);
372   Square nSq = pos.piece_list(weakerSide, KNIGHT, 0);
373
374   Value result = Value(10) + mate_table(defendingKSq) +
375     krkn_king_knight_distance_penalty(square_distance(defendingKSq, nSq));
376
377   return (strongerSide == pos.side_to_move())? result : -result;
378 }
379
380
381 /// KQ vs KR.  This is almost identical to KX vs K:  We give the attacking
382 /// king a bonus for having the kings close together, and for forcing the
383 /// defending king towards the edge.  If we also take care to avoid null move
384 /// for the defending side in the search, this is usually sufficient to be
385 /// able to win KQ vs KR.
386 template<>
387 Value EvaluationFunction<KQKR>::apply(const Position& pos) {
388
389   assert(pos.non_pawn_material(strongerSide) == QueenValueMidgame);
390   assert(pos.piece_count(strongerSide, PAWN) == 0);
391   assert(pos.non_pawn_material(weakerSide) == RookValueMidgame);
392   assert(pos.piece_count(weakerSide, PAWN) == 0);
393
394   Square winnerKSq = pos.king_square(strongerSide);
395   Square loserKSq = pos.king_square(weakerSide);
396
397   Value result =  QueenValueEndgame
398                 - RookValueEndgame
399                 + mate_table(loserKSq)
400                 + distance_bonus(square_distance(winnerKSq, loserKSq));
401
402   return (strongerSide == pos.side_to_move())? result : -result;
403 }
404
405 template<>
406 Value EvaluationFunction<KBBKN>::apply(const Position& pos) {
407
408   assert(pos.piece_count(strongerSide, BISHOP) == 2);
409   assert(pos.non_pawn_material(strongerSide) == 2*BishopValueMidgame);
410   assert(pos.piece_count(weakerSide, KNIGHT) == 1);
411   assert(pos.non_pawn_material(weakerSide) == KnightValueMidgame);
412   assert(pos.pawns() == EmptyBoardBB);
413
414   Value result = BishopValueEndgame;
415   Square wksq = pos.king_square(strongerSide);
416   Square bksq = pos.king_square(weakerSide);
417   Square nsq = pos.piece_list(weakerSide, KNIGHT, 0);
418
419   // Bonus for attacking king close to defending king
420   result += distance_bonus(square_distance(wksq, bksq));
421
422   // Bonus for driving the defending king and knight apart
423   result += Value(square_distance(bksq, nsq) * 32);
424
425   // Bonus for restricting the knight's mobility
426   result += Value((8 - count_1s_max_15(pos.piece_attacks<KNIGHT>(nsq))) * 8);
427
428   return (strongerSide == pos.side_to_move() ? result : -result);
429 }
430
431 template<>
432 Value EvaluationFunction<KmmKm>::apply(const Position &pos) {
433   return Value(0);
434 }
435
436
437 /// KBPKScalingFunction scales endgames where the stronger side has king,
438 /// bishop and one or more pawns. It checks for draws with rook pawns and a
439 /// bishop of the wrong color. If such a draw is detected, ScaleFactor(0) is
440 /// returned. If not, the return value is SCALE_FACTOR_NONE, i.e. no scaling
441 /// will be used.
442
443 ScaleFactor KBPKScalingFunction::apply(const Position& pos) {
444
445   assert(pos.non_pawn_material(strongerSide) == BishopValueMidgame);
446   assert(pos.piece_count(strongerSide, BISHOP) == 1);
447   assert(pos.piece_count(strongerSide, PAWN) >= 1);
448
449   // No assertions about the material of weakerSide, because we want draws to
450   // be detected even when the weaker side has some pawns.
451
452   Bitboard pawns = pos.pawns(strongerSide);
453   File pawnFile = square_file(pos.piece_list(strongerSide, PAWN, 0));
454
455   // All pawns are on a single rook file ?
456   if (   (pawnFile == FILE_A || pawnFile == FILE_H)
457       && (pawns & ~file_bb(pawnFile)) == EmptyBoardBB)
458   {
459       Square bishopSq = pos.piece_list(strongerSide, BISHOP, 0);
460       Square queeningSq = relative_square(strongerSide, make_square(pawnFile, RANK_8));
461       Square kingSq = pos.king_square(weakerSide);
462
463       if (   square_color(queeningSq) != square_color(bishopSq)
464           && file_distance(square_file(kingSq), pawnFile) <= 1)
465       {
466           // The bishop has the wrong color, and the defending king is on the
467           // file of the pawn(s) or the neighboring file. Find the rank of the
468           // frontmost pawn.
469
470           Rank rank;
471           if (strongerSide == WHITE)
472           {
473               for (rank = RANK_7; (rank_bb(rank) & pawns) == EmptyBoardBB; rank--) {}
474               assert(rank >= RANK_2 && rank <= RANK_7);
475           }
476           else
477           {
478               for(rank = RANK_2; (rank_bb(rank) & pawns) == EmptyBoardBB; rank++) {}
479               rank = Rank(rank^7);  // HACK to get the relative rank
480               assert(rank >= RANK_2 && rank <= RANK_7);
481           }
482           // If the defending king has distance 1 to the promotion square or
483           // is placed somewhere in front of the pawn, it's a draw.
484           if (   square_distance(kingSq, queeningSq) <= 1
485               || relative_rank(strongerSide, kingSq) >= rank)
486               return ScaleFactor(0);
487       }
488   }
489   return SCALE_FACTOR_NONE;
490 }
491
492
493 /// KQKRPScalingFunction scales endgames where the stronger side has only
494 /// king and queen, while the weaker side has at least a rook and a pawn.
495 /// It tests for fortress draws with a rook on the third rank defended by
496 /// a pawn.
497
498 ScaleFactor KQKRPScalingFunction::apply(const Position& pos) {
499
500   assert(pos.non_pawn_material(strongerSide) == QueenValueMidgame);
501   assert(pos.piece_count(strongerSide, QUEEN) == 1);
502   assert(pos.piece_count(strongerSide, PAWN) == 0);
503   assert(pos.piece_count(weakerSide, ROOK) == 1);
504   assert(pos.piece_count(weakerSide, PAWN) >= 1);
505
506   Square kingSq = pos.king_square(weakerSide);
507   if (   relative_rank(weakerSide, kingSq) <= RANK_2
508       && relative_rank(weakerSide, pos.king_square(strongerSide)) >= RANK_4
509       && (pos.rooks(weakerSide) & relative_rank_bb(weakerSide, RANK_3))
510       && (pos.pawns(weakerSide) & relative_rank_bb(weakerSide, RANK_2))
511       && (pos.piece_attacks<KING>(kingSq) & pos.pawns(weakerSide)))
512   {
513       Square rsq = pos.piece_list(weakerSide, ROOK, 0);
514       if (pos.pawn_attacks(strongerSide, rsq) & pos.pawns(weakerSide))
515           return ScaleFactor(0);
516   }
517   return SCALE_FACTOR_NONE;
518 }
519
520
521 /// KRPKRScalingFunction scales KRP vs KR endgames. This function knows a
522 /// handful of the most important classes of drawn positions, but is far
523 /// from perfect. It would probably be a good idea to add more knowledge
524 /// in the future.
525 ///
526 /// It would also be nice to rewrite the actual code for this function,
527 /// which is mostly copied from Glaurung 1.x, and not very pretty.
528
529 ScaleFactor KRPKRScalingFunction::apply(const Position &pos) {
530
531   assert(pos.non_pawn_material(strongerSide) == RookValueMidgame);
532   assert(pos.piece_count(strongerSide, PAWN) == 1);
533   assert(pos.non_pawn_material(weakerSide) == RookValueMidgame);
534   assert(pos.piece_count(weakerSide, PAWN) == 0);
535
536   Square wksq = pos.king_square(strongerSide);
537   Square wrsq = pos.piece_list(strongerSide, ROOK, 0);
538   Square wpsq = pos.piece_list(strongerSide, PAWN, 0);
539   Square bksq = pos.king_square(weakerSide);
540   Square brsq = pos.piece_list(weakerSide, ROOK, 0);
541
542   // Orient the board in such a way that the stronger side is white, and the
543   // pawn is on the left half of the board.
544   if (strongerSide == BLACK)
545   {
546       wksq = flip_square(wksq);
547       wrsq = flip_square(wrsq);
548       wpsq = flip_square(wpsq);
549       bksq = flip_square(bksq);
550       brsq = flip_square(brsq);
551   }
552   if (square_file(wpsq) > FILE_D)
553   {
554       wksq = flop_square(wksq);
555       wrsq = flop_square(wrsq);
556       wpsq = flop_square(wpsq);
557       bksq = flop_square(bksq);
558       brsq = flop_square(brsq);
559   }
560
561   File f = square_file(wpsq);
562   Rank r = square_rank(wpsq);
563   Square queeningSq = make_square(f, RANK_8);
564   int tempo = (pos.side_to_move() == strongerSide);
565
566   // If the pawn is not too far advanced and the defending king defends the
567   // queening square, use the third-rank defence.
568   if (   r <= RANK_5
569       && square_distance(bksq, queeningSq) <= 1
570       && wksq <= SQ_H5
571       && (square_rank(brsq) == RANK_6 || (r <= RANK_3 && square_rank(wrsq) != RANK_6)))
572       return ScaleFactor(0);
573
574   // The defending side saves a draw by checking from behind in case the pawn
575   // has advanced to the 6th rank with the king behind.
576   if (   r == RANK_6
577       && square_distance(bksq, queeningSq) <= 1
578       && square_rank(wksq) + tempo <= RANK_6
579       && (square_rank(brsq) == RANK_1 || (!tempo && abs(square_file(brsq) - f) >= 3)))
580       return ScaleFactor(0);
581
582   if (   r >= RANK_6
583       && bksq == queeningSq
584       && square_rank(brsq) == RANK_1
585       && (!tempo || square_distance(wksq, wpsq) >= 2))
586       return ScaleFactor(0);
587
588   // White pawn on a7 and rook on a8 is a draw if black's king is on g7 or h7
589   // and the black rook is behind the pawn.
590   if (   wpsq == SQ_A7
591       && wrsq == SQ_A8
592       && (bksq == SQ_H7 || bksq == SQ_G7)
593       && square_file(brsq) == FILE_A
594       && (square_rank(brsq) <= RANK_3 || square_file(wksq) >= FILE_D || square_rank(wksq) <= RANK_5))
595       return ScaleFactor(0);
596
597   // If the defending king blocks the pawn and the attacking king is too far
598   // away, it's a draw.
599   if (   r <= RANK_5
600       && bksq == wpsq + DELTA_N
601       && square_distance(wksq, wpsq) - tempo >= 2
602       && square_distance(wksq, brsq) - tempo >= 2)
603       return ScaleFactor(0);
604
605   // Pawn on the 7th rank supported by the rook from behind usually wins if the
606   // attacking king is closer to the queening square than the defending king,
607   // and the defending king cannot gain tempi by threatening the attacking rook.
608   if (   r == RANK_7
609       && f != FILE_A
610       && square_file(wrsq) == f
611       && wrsq != queeningSq
612       && (square_distance(wksq, queeningSq) < square_distance(bksq, queeningSq) - 2 + tempo)
613       && (square_distance(wksq, queeningSq) < square_distance(bksq, wrsq) + tempo))
614       return ScaleFactor(SCALE_FACTOR_MAX - 2 * square_distance(wksq, queeningSq));
615
616   // Similar to the above, but with the pawn further back
617   if (   f != FILE_A
618       && square_file(wrsq) == f
619       && wrsq < wpsq
620       && (square_distance(wksq, queeningSq) < square_distance(bksq, queeningSq) - 2 + tempo)
621       && (square_distance(wksq, wpsq + DELTA_N) < square_distance(bksq, wpsq + DELTA_N) - 2 + tempo)
622       && (  square_distance(bksq, wrsq) + tempo >= 3
623           || (    square_distance(wksq, queeningSq) < square_distance(bksq, wrsq) + tempo
624               && (square_distance(wksq, wpsq + DELTA_N) < square_distance(bksq, wrsq) + tempo))))
625       return ScaleFactor(  SCALE_FACTOR_MAX
626                          - (8 * square_distance(wpsq, queeningSq)
627                          + 2 * square_distance(wksq, queeningSq)));
628
629   // If the pawn is not far advanced, and the defending king is somewhere in
630   // the pawn's path, it's probably a draw.
631   if (r <= RANK_4 && bksq > wpsq)
632   {
633       if (square_file(bksq) == square_file(wpsq))
634           return ScaleFactor(10);
635       if (   abs(square_file(bksq) - square_file(wpsq)) == 1
636           && square_distance(wksq, bksq) > 2)
637           return ScaleFactor(24 - 2 * square_distance(wksq, bksq));
638   }
639   return SCALE_FACTOR_NONE;
640 }
641
642
643 /// KRPPKRPScalingFunction scales KRPP vs KRP endgames. There is only a
644 /// single pattern: If the stronger side has no pawns and the defending king
645 /// is actively placed, the position is drawish.
646
647 ScaleFactor KRPPKRPScalingFunction::apply(const Position &pos) {
648
649   assert(pos.non_pawn_material(strongerSide) == RookValueMidgame);
650   assert(pos.piece_count(strongerSide, PAWN) == 2);
651   assert(pos.non_pawn_material(weakerSide) == RookValueMidgame);
652   assert(pos.piece_count(weakerSide, PAWN) == 1);
653
654   Square wpsq1 = pos.piece_list(strongerSide, PAWN, 0);
655   Square wpsq2 = pos.piece_list(strongerSide, PAWN, 1);
656   Square bksq = pos.king_square(weakerSide);
657
658   // Does the stronger side have a passed pawn?
659   if (   pos.pawn_is_passed(strongerSide, wpsq1)
660       || pos.pawn_is_passed(strongerSide, wpsq2))
661       return SCALE_FACTOR_NONE;
662
663   Rank r = Max(relative_rank(strongerSide, wpsq1), relative_rank(strongerSide, wpsq2));
664
665   if (   file_distance(bksq, wpsq1) <= 1
666       && file_distance(bksq, wpsq2) <= 1
667       && relative_rank(strongerSide, bksq) > r)
668   {
669       switch (r) {
670       case RANK_2: return ScaleFactor(10);
671       case RANK_3: return ScaleFactor(10);
672       case RANK_4: return ScaleFactor(15);
673       case RANK_5: return ScaleFactor(20);
674       case RANK_6: return ScaleFactor(40);
675       default: assert(false);
676       }
677   }
678   return SCALE_FACTOR_NONE;
679 }
680
681
682 /// KPsKScalingFunction scales endgames with king and two or more pawns
683 /// against king. There is just a single rule here: If all pawns are on
684 /// the same rook file and are blocked by the defending king, it's a draw.
685
686 ScaleFactor KPsKScalingFunction::apply(const Position &pos) {
687
688   assert(pos.non_pawn_material(strongerSide) == Value(0));
689   assert(pos.piece_count(strongerSide, PAWN) >= 2);
690   assert(pos.non_pawn_material(weakerSide) == Value(0));
691   assert(pos.piece_count(weakerSide, PAWN) == 0);
692
693   Bitboard pawns = pos.pawns(strongerSide);
694
695   // Are all pawns on the 'a' file?
696   if ((pawns & ~FileABB) == EmptyBoardBB)
697   {
698       // Does the defending king block the pawns?
699       Square ksq = pos.king_square(weakerSide);
700       if (square_distance(ksq, relative_square(strongerSide, SQ_A8)) <= 1)
701           return ScaleFactor(0);
702       else if(   square_file(ksq) == FILE_A
703               && (in_front_bb(strongerSide, ksq) & pawns) == EmptyBoardBB)
704           return ScaleFactor(0);
705       else
706           return SCALE_FACTOR_NONE;
707   }
708   // Are all pawns on the 'h' file?
709   else if ((pawns & ~FileHBB) == EmptyBoardBB)
710   {
711     // Does the defending king block the pawns?
712     Square ksq = pos.king_square(weakerSide);
713     if (square_distance(ksq, relative_square(strongerSide, SQ_H8)) <= 1)
714         return ScaleFactor(0);
715     else if (   square_file(ksq) == FILE_H
716              && (in_front_bb(strongerSide, ksq) & pawns) == EmptyBoardBB)
717         return ScaleFactor(0);
718     else
719         return SCALE_FACTOR_NONE;
720   }
721   else
722       return SCALE_FACTOR_NONE;
723 }
724
725
726 /// KBPKBScalingFunction scales KBP vs KB endgames. There are two rules:
727 /// If the defending king is somewhere along the path of the pawn, and the
728 /// square of the king is not of the same color as the stronger side's bishop,
729 /// it's a draw. If the two bishops have opposite color, it's almost always
730 /// a draw.
731
732 ScaleFactor KBPKBScalingFunction::apply(const Position &pos) {
733
734   assert(pos.non_pawn_material(strongerSide) == BishopValueMidgame);
735   assert(pos.piece_count(strongerSide, BISHOP) == 1);
736   assert(pos.piece_count(strongerSide, PAWN) == 1);
737   assert(pos.non_pawn_material(weakerSide) == BishopValueMidgame);
738   assert(pos.piece_count(weakerSide, BISHOP) == 1);
739   assert(pos.piece_count(weakerSide, PAWN) == 0);
740
741   Square pawnSq = pos.piece_list(strongerSide, PAWN, 0);
742   Square strongerBishopSq = pos.piece_list(strongerSide, BISHOP, 0);
743   Square weakerBishopSq = pos.piece_list(weakerSide, BISHOP, 0);
744   Square weakerKingSq = pos.king_square(weakerSide);
745
746   // Case 1: Defending king blocks the pawn, and cannot be driven away
747   if (   square_file(weakerKingSq) == square_file(pawnSq)
748       && relative_rank(strongerSide, pawnSq) < relative_rank(strongerSide, weakerKingSq)
749       && (   square_color(weakerKingSq) != square_color(strongerBishopSq)
750           || relative_rank(strongerSide, weakerKingSq) <= RANK_6))
751       return ScaleFactor(0);
752
753   // Case 2: Opposite colored bishops
754   if (square_color(strongerBishopSq) != square_color(weakerBishopSq))
755   {
756       // We assume that the position is drawn in the following three situations:
757       //
758       //   a. The pawn is on rank 5 or further back.
759       //   b. The defending king is somewhere in the pawn's path.
760       //   c. The defending bishop attacks some square along the pawn's path,
761       //      and is at least three squares away from the pawn.
762       //
763       // These rules are probably not perfect, but in practice they work
764       // reasonably well.
765
766       if (relative_rank(strongerSide, pawnSq) <= RANK_5)
767           return ScaleFactor(0);
768       else
769       {
770           Bitboard ray = ray_bb(pawnSq, (strongerSide == WHITE)? SIGNED_DIR_N : SIGNED_DIR_S);
771           if (ray & pos.kings(weakerSide))
772               return ScaleFactor(0);
773           if(  (pos.piece_attacks<BISHOP>(weakerBishopSq) & ray)
774              && square_distance(weakerBishopSq, pawnSq) >= 3)
775               return ScaleFactor(0);
776       }
777   }
778   return SCALE_FACTOR_NONE;
779 }
780
781
782 /// KBPKNScalingFunction scales KBP vs KN endgames. There is a single rule:
783 /// If the defending king is somewhere along the path of the pawn, and the
784 /// square of the king is not of the same color as the stronger side's bishop,
785 /// it's a draw.
786
787 ScaleFactor KBPKNScalingFunction::apply(const Position &pos) {
788
789   assert(pos.non_pawn_material(strongerSide) == BishopValueMidgame);
790   assert(pos.piece_count(strongerSide, BISHOP) == 1);
791   assert(pos.piece_count(strongerSide, PAWN) == 1);
792   assert(pos.non_pawn_material(weakerSide) == KnightValueMidgame);
793   assert(pos.piece_count(weakerSide, KNIGHT) == 1);
794   assert(pos.piece_count(weakerSide, PAWN) == 0);
795
796   Square pawnSq = pos.piece_list(strongerSide, PAWN, 0);
797   Square strongerBishopSq = pos.piece_list(strongerSide, BISHOP, 0);
798   Square weakerKingSq = pos.king_square(weakerSide);
799
800   if (   square_file(weakerKingSq) == square_file(pawnSq)
801       && relative_rank(strongerSide, pawnSq) < relative_rank(strongerSide, weakerKingSq)
802       && (   square_color(weakerKingSq) != square_color(strongerBishopSq)
803           || relative_rank(strongerSide, weakerKingSq) <= RANK_6))
804       return ScaleFactor(0);
805
806   return SCALE_FACTOR_NONE;
807 }
808
809
810 /// KNPKScalingFunction scales KNP vs K endgames. There is a single rule:
811 /// If the pawn is a rook pawn on the 7th rank and the defending king prevents
812 /// the pawn from advancing, the position is drawn.
813
814 ScaleFactor KNPKScalingFunction::apply(const Position &pos) {
815
816   assert(pos.non_pawn_material(strongerSide) == KnightValueMidgame);
817   assert(pos.piece_count(strongerSide, KNIGHT) == 1);
818   assert(pos.piece_count(strongerSide, PAWN) == 1);
819   assert(pos.non_pawn_material(weakerSide) == Value(0));
820   assert(pos.piece_count(weakerSide, PAWN) == 0);
821
822   Square pawnSq = pos.piece_list(strongerSide, PAWN, 0);
823   Square weakerKingSq = pos.king_square(weakerSide);
824
825   if (   pawnSq == relative_square(strongerSide, SQ_A7)
826       && square_distance(weakerKingSq, relative_square(strongerSide, SQ_A8)) <= 1)
827       return ScaleFactor(0);
828
829   if (   pawnSq == relative_square(strongerSide, SQ_H7)
830       && square_distance(weakerKingSq, relative_square(strongerSide, SQ_H8)) <= 1)
831       return ScaleFactor(0);
832
833   return SCALE_FACTOR_NONE;
834 }
835
836
837 /// KPKPScalingFunction scales KP vs KP endgames. This is done by removing
838 /// the weakest side's pawn and probing the KP vs K bitbase: If the weakest
839 /// side has a draw without the pawn, she probably has at least a draw with
840 /// the pawn as well. The exception is when the stronger side's pawn is far
841 /// advanced and not on a rook file; in this case it is often possible to win
842 /// (e.g. 8/4k3/3p4/3P4/6K1/8/8/8 w - - 0 1).
843
844 ScaleFactor KPKPScalingFunction::apply(const Position &pos) {
845
846   assert(pos.non_pawn_material(strongerSide) == Value(0));
847   assert(pos.non_pawn_material(weakerSide) == Value(0));
848   assert(pos.piece_count(WHITE, PAWN) == 1);
849   assert(pos.piece_count(BLACK, PAWN) == 1);
850
851   Square wksq, bksq, wpsq;
852   Color stm;
853
854   if (strongerSide == WHITE)
855   {
856       wksq = pos.king_square(WHITE);
857       bksq = pos.king_square(BLACK);
858       wpsq = pos.piece_list(WHITE, PAWN, 0);
859       stm = pos.side_to_move();
860   }
861   else
862   {
863       wksq = flip_square(pos.king_square(BLACK));
864       bksq = flip_square(pos.king_square(WHITE));
865       wpsq = flip_square(pos.piece_list(BLACK, PAWN, 0));
866       stm = opposite_color(pos.side_to_move());
867   }
868
869   if (square_file(wpsq) >= FILE_E)
870   {
871       wksq = flop_square(wksq);
872       bksq = flop_square(bksq);
873       wpsq = flop_square(wpsq);
874   }
875
876   // If the pawn has advanced to the fifth rank or further, and is not a
877   // rook pawn, it's too dangerous to assume that it's at least a draw.
878   if (   square_rank(wpsq) >= RANK_5
879       && square_file(wpsq) != FILE_A)
880       return SCALE_FACTOR_NONE;
881
882   // Probe the KPK bitbase with the weakest side's pawn removed. If it's a
883   // draw, it's probably at least a draw even with the pawn.
884   if (probe_kpk(wksq, wpsq, bksq, stm))
885       return SCALE_FACTOR_NONE;
886   else
887       return ScaleFactor(0);
888 }
889
890
891 /// init_bitbases() is called during program initialization, and simply loads
892 /// bitbases from disk into memory.  At the moment, there is only the bitbase
893 /// for KP vs K, but we may decide to add other bitbases later.
894
895 void init_bitbases() {
896   generate_kpk_bitbase(KPKBitbase);
897 }
898
899
900 namespace {
901
902   // Probe the KP vs K bitbase:
903
904   int probe_kpk(Square wksq, Square wpsq, Square bksq, Color stm) {
905
906     int wp = int(square_file(wpsq)) + (int(square_rank(wpsq)) - 1) * 4;
907     int index = int(stm) + 2*int(bksq) + 128*int(wksq) + 8192*wp;
908
909     assert(index >= 0 && index < 24576*8);
910     return KPKBitbase[index/8] & (1 << (index&7));
911   }
912 }