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