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