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