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