git.sesse.net Git - stockfish/blob - src/endgame.cpp

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