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