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