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