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

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