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