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
 563   assert(pos.non_pawn_material(strongerSide) == RookValueMidgame);
 564   assert(pos.piece_count(strongerSide, PAWN) == 1);
 565   assert(pos.non_pawn_material(weakerSide) == RookValueMidgame);
 566   assert(pos.piece_count(weakerSide, PAWN) == 0);
 567
 568   Square wksq = pos.king_square(strongerSide);
 569   Square wrsq = pos.piece_list(strongerSide, ROOK, 0);
 570   Square wpsq = pos.piece_list(strongerSide, PAWN, 0);
 571   Square bksq = pos.king_square(weakerSide);
 572   Square brsq = pos.piece_list(weakerSide, ROOK, 0);
 573
 574   // Orient the board in such a way that the stronger side is white, and the
 575   // pawn is on the left half of the board.
 576   if (strongerSide == BLACK)
 577   {
 578       wksq = flip_square(wksq);
 579       wrsq = flip_square(wrsq);
 580       wpsq = flip_square(wpsq);
 581       bksq = flip_square(bksq);
 582       brsq = flip_square(brsq);
 583   }
 584   if (square_file(wpsq) > FILE_D)
 585   {
 586       wksq = flop_square(wksq);
 587       wrsq = flop_square(wrsq);
 588       wpsq = flop_square(wpsq);
 589       bksq = flop_square(bksq);
 590       brsq = flop_square(brsq);
 591   }
 592
 593   File f = square_file(wpsq);
 594   Rank r = square_rank(wpsq);
 595   Square queeningSq = make_square(f, RANK_8);
 596   int tempo = (pos.side_to_move() == strongerSide);
 597
 598   // If the pawn is not too far advanced and the defending king defends the
 599   // queening square, use the third-rank defence.
 600   if (   r <= RANK_5
 601       && square_distance(bksq, queeningSq) <= 1
 602       && wksq <= SQ_H5
 603       && (square_rank(brsq) == RANK_6 || (r <= RANK_3 && square_rank(wrsq) != RANK_6)))
 604       return ScaleFactor(0);
 605
 606   // The defending side saves a draw by checking from behind in case the pawn
 607   // has advanced to the 6th rank with the king behind.
 608   if (   r == RANK_6
 609       && square_distance(bksq, queeningSq) <= 1
 610       && square_rank(wksq) + tempo <= RANK_6
 611       && (square_rank(brsq) == RANK_1 || (!tempo && abs(square_file(brsq) - f) >= 3)))
 612       return ScaleFactor(0);
 613
 614   if (   r >= RANK_6
 615       && bksq == queeningSq
 616       && square_rank(brsq) == RANK_1
 617       && (!tempo || square_distance(wksq, wpsq) >= 2))
 618       return ScaleFactor(0);
 619
 620   // White pawn on a7 and rook on a8 is a draw if black's king is on g7 or h7
 621   // and the black rook is behind the pawn.
 622   if (   wpsq == SQ_A7
 623       && wrsq == SQ_A8
 624       && (bksq == SQ_H7 || bksq == SQ_G7)
 625       && square_file(brsq) == FILE_A
 626       && (square_rank(brsq) <= RANK_3 || square_file(wksq) >= FILE_D || square_rank(wksq) <= RANK_5))
 627       return ScaleFactor(0);
 628
 629   // If the defending king blocks the pawn and the attacking king is too far
 630   // away, it's a draw.
 631   if (   r <= RANK_5
 632       && bksq == wpsq + DELTA_N
 633       && square_distance(wksq, wpsq) - tempo >= 2
 634       && square_distance(wksq, brsq) - tempo >= 2)
 635       return ScaleFactor(0);
 636
 637   // Pawn on the 7th rank supported by the rook from behind usually wins if the
 638   // attacking king is closer to the queening square than the defending king,
 639   // and the defending king cannot gain tempi by threatening the attacking rook.
 640   if (   r == RANK_7
 641       && f != FILE_A
 642       && square_file(wrsq) == f
 643       && wrsq != queeningSq
 644       && (square_distance(wksq, queeningSq) < square_distance(bksq, queeningSq) - 2 + tempo)
 645       && (square_distance(wksq, queeningSq) < square_distance(bksq, wrsq) + tempo))
 646       return ScaleFactor(SCALE_FACTOR_MAX - 2 * square_distance(wksq, queeningSq));
 647
 648   // Similar to the above, but with the pawn further back
 649   if (   f != FILE_A
 650       && square_file(wrsq) == f
 651       && wrsq < wpsq
 652       && (square_distance(wksq, queeningSq) < square_distance(bksq, queeningSq) - 2 + tempo)
 653       && (square_distance(wksq, wpsq + DELTA_N) < square_distance(bksq, wpsq + DELTA_N) - 2 + tempo)
 654       && (  square_distance(bksq, wrsq) + tempo >= 3
 655           || (    square_distance(wksq, queeningSq) < square_distance(bksq, wrsq) + tempo
 656               && (square_distance(wksq, wpsq + DELTA_N) < square_distance(bksq, wrsq) + tempo))))
 657       return ScaleFactor(  SCALE_FACTOR_MAX
 658                          - (8 * square_distance(wpsq, queeningSq)
 659                          + 2 * square_distance(wksq, queeningSq)));
 660
 661   // If the pawn is not far advanced, and the defending king is somewhere in
 662   // the pawn's path, it's probably a draw.
 663   if (r <= RANK_4 && bksq > wpsq)
 664   {
 665       if (square_file(bksq) == square_file(wpsq))
 666           return ScaleFactor(10);
 667       if (   abs(square_file(bksq) - square_file(wpsq)) == 1
 668           && square_distance(wksq, bksq) > 2)
 669           return ScaleFactor(24 - 2 * square_distance(wksq, bksq));
 670   }
 671   return SCALE_FACTOR_NONE;
 672 }
 673
 674
 675 /// KRPPKRPScalingFunction scales KRPP vs KRP endgames. There is only a
 676 /// single pattern: If the stronger side has no pawns and the defending king
 677 /// is actively placed, the position is drawish.
 678
 679 ScaleFactor KRPPKRPScalingFunction::apply(const Position &pos) {
 680
 681   assert(pos.non_pawn_material(strongerSide) == RookValueMidgame);
 682   assert(pos.piece_count(strongerSide, PAWN) == 2);
 683   assert(pos.non_pawn_material(weakerSide) == RookValueMidgame);
 684   assert(pos.piece_count(weakerSide, PAWN) == 1);
 685
 686   Square wpsq1 = pos.piece_list(strongerSide, PAWN, 0);
 687   Square wpsq2 = pos.piece_list(strongerSide, PAWN, 1);
 688   Square bksq = pos.king_square(weakerSide);
 689
 690   // Does the stronger side have a passed pawn?
 691   if (   pos.pawn_is_passed(strongerSide, wpsq1)
 692       || pos.pawn_is_passed(strongerSide, wpsq2))
 693       return SCALE_FACTOR_NONE;
 694
 695   Rank r = Max(relative_rank(strongerSide, wpsq1), relative_rank(strongerSide, wpsq2));
 696
 697   if (   file_distance(bksq, wpsq1) <= 1
 698       && file_distance(bksq, wpsq2) <= 1
 699       && relative_rank(strongerSide, bksq) > r)
 700   {
 701       switch (r) {
 702       case RANK_2: return ScaleFactor(10);
 703       case RANK_3: return ScaleFactor(10);
 704       case RANK_4: return ScaleFactor(15);
 705       case RANK_5: return ScaleFactor(20);
 706       case RANK_6: return ScaleFactor(40);
 707       default: assert(false);
 708       }
 709   }
 710   return SCALE_FACTOR_NONE;
 711 }
 712
 713
 714 /// KPsKScalingFunction scales endgames with king and two or more pawns
 715 /// against king. There is just a single rule here: If all pawns are on
 716 /// the same rook file and are blocked by the defending king, it's a draw.
 717
 718 ScaleFactor KPsKScalingFunction::apply(const Position &pos) {
 719
 720   assert(pos.non_pawn_material(strongerSide) == Value(0));
 721   assert(pos.piece_count(strongerSide, PAWN) >= 2);
 722   assert(pos.non_pawn_material(weakerSide) == Value(0));
 723   assert(pos.piece_count(weakerSide, PAWN) == 0);
 724
 725   Bitboard pawns = pos.pawns(strongerSide);
 726
 727   // Are all pawns on the 'a' file?
 728   if ((pawns & ~FileABB) == EmptyBoardBB)
 729   {
 730       // Does the defending king block the pawns?
 731       Square ksq = pos.king_square(weakerSide);
 732       if (square_distance(ksq, relative_square(strongerSide, SQ_A8)) <= 1)
 733           return ScaleFactor(0);
 734       else if(   square_file(ksq) == FILE_A
 735               && (in_front_bb(strongerSide, ksq) & pawns) == EmptyBoardBB)
 736           return ScaleFactor(0);
 737       else
 738           return SCALE_FACTOR_NONE;
 739   }
 740   // Are all pawns on the 'h' file?
 741   else if ((pawns & ~FileHBB) == EmptyBoardBB)
 742   {
 743     // Does the defending king block the pawns?
 744     Square ksq = pos.king_square(weakerSide);
 745     if (square_distance(ksq, relative_square(strongerSide, SQ_H8)) <= 1)
 746         return ScaleFactor(0);
 747     else if (   square_file(ksq) == FILE_H
 748              && (in_front_bb(strongerSide, ksq) & pawns) == EmptyBoardBB)
 749         return ScaleFactor(0);
 750     else
 751         return SCALE_FACTOR_NONE;
 752   }
 753   else
 754       return SCALE_FACTOR_NONE;
 755 }
 756
 757
 758 /// KBPKBScalingFunction scales KBP vs KB endgames. There are two rules:
 759 /// If the defending king is somewhere along the path of the pawn, and the
 760 /// square of the king is not of the same color as the stronger side's bishop,
 761 /// it's a draw. If the two bishops have opposite color, it's almost always
 762 /// a draw.
 763
 764 ScaleFactor KBPKBScalingFunction::apply(const Position &pos) {
 765
 766   assert(pos.non_pawn_material(strongerSide) == BishopValueMidgame);
 767   assert(pos.piece_count(strongerSide, BISHOP) == 1);
 768   assert(pos.piece_count(strongerSide, PAWN) == 1);
 769   assert(pos.non_pawn_material(weakerSide) == BishopValueMidgame);
 770   assert(pos.piece_count(weakerSide, BISHOP) == 1);
 771   assert(pos.piece_count(weakerSide, PAWN) == 0);
 772
 773   Square pawnSq = pos.piece_list(strongerSide, PAWN, 0);
 774   Square strongerBishopSq = pos.piece_list(strongerSide, BISHOP, 0);
 775   Square weakerBishopSq = pos.piece_list(weakerSide, BISHOP, 0);
 776   Square weakerKingSq = pos.king_square(weakerSide);
 777
 778   // Case 1: Defending king blocks the pawn, and cannot be driven away
 779   if (   square_file(weakerKingSq) == square_file(pawnSq)
 780       && relative_rank(strongerSide, pawnSq) < relative_rank(strongerSide, weakerKingSq)
 781       && (   square_color(weakerKingSq) != square_color(strongerBishopSq)
 782           || relative_rank(strongerSide, weakerKingSq) <= RANK_6))
 783       return ScaleFactor(0);
 784
 785   // Case 2: Opposite colored bishops
 786   if (square_color(strongerBishopSq) != square_color(weakerBishopSq))
 787   {
 788       // We assume that the position is drawn in the following three situations:
 789       //
 790       //   a. The pawn is on rank 5 or further back.
 791       //   b. The defending king is somewhere in the pawn's path.
 792       //   c. The defending bishop attacks some square along the pawn's path,
 793       //      and is at least three squares away from the pawn.
 794       //
 795       // These rules are probably not perfect, but in practice they work
 796       // reasonably well.
 797
 798       if (relative_rank(strongerSide, pawnSq) <= RANK_5)
 799           return ScaleFactor(0);
 800       else
 801       {
 802           Bitboard ray = ray_bb(pawnSq, (strongerSide == WHITE)? SIGNED_DIR_N : SIGNED_DIR_S);
 803           if (ray & pos.kings(weakerSide))
 804               return ScaleFactor(0);
 805           if(  (pos.piece_attacks<BISHOP>(weakerBishopSq) & ray)
 806              && square_distance(weakerBishopSq, pawnSq) >= 3)
 807               return ScaleFactor(0);
 808       }
 809   }
 810   return SCALE_FACTOR_NONE;
 811 }
 812
 813
 814 /// KBPKNScalingFunction scales KBP vs KN endgames. There is a single rule:
 815 /// If the defending king is somewhere along the path of the pawn, and the
 816 /// square of the king is not of the same color as the stronger side's bishop,
 817 /// it's a draw.
 818
 819 ScaleFactor KBPKNScalingFunction::apply(const Position &pos) {
 820
 821   assert(pos.non_pawn_material(strongerSide) == BishopValueMidgame);
 822   assert(pos.piece_count(strongerSide, BISHOP) == 1);
 823   assert(pos.piece_count(strongerSide, PAWN) == 1);
 824   assert(pos.non_pawn_material(weakerSide) == KnightValueMidgame);
 825   assert(pos.piece_count(weakerSide, KNIGHT) == 1);
 826   assert(pos.piece_count(weakerSide, PAWN) == 0);
 827
 828   Square pawnSq = pos.piece_list(strongerSide, PAWN, 0);
 829   Square strongerBishopSq = pos.piece_list(strongerSide, BISHOP, 0);
 830   Square weakerKingSq = pos.king_square(weakerSide);
 831
 832   if (   square_file(weakerKingSq) == square_file(pawnSq)
 833       && relative_rank(strongerSide, pawnSq) < relative_rank(strongerSide, weakerKingSq)
 834       && (   square_color(weakerKingSq) != square_color(strongerBishopSq)
 835           || relative_rank(strongerSide, weakerKingSq) <= RANK_6))
 836       return ScaleFactor(0);
 837
 838   return SCALE_FACTOR_NONE;
 839 }
 840
 841
 842 /// KNPKScalingFunction scales KNP vs K endgames. There is a single rule:
 843 /// If the pawn is a rook pawn on the 7th rank and the defending king prevents
 844 /// the pawn from advancing, the position is drawn.
 845
 846 ScaleFactor KNPKScalingFunction::apply(const Position &pos) {
 847
 848   assert(pos.non_pawn_material(strongerSide) == KnightValueMidgame);
 849   assert(pos.piece_count(strongerSide, KNIGHT) == 1);
 850   assert(pos.piece_count(strongerSide, PAWN) == 1);
 851   assert(pos.non_pawn_material(weakerSide) == Value(0));
 852   assert(pos.piece_count(weakerSide, PAWN) == 0);
 853
 854   Square pawnSq = pos.piece_list(strongerSide, PAWN, 0);
 855   Square weakerKingSq = pos.king_square(weakerSide);
 856
 857   if (   pawnSq == relative_square(strongerSide, SQ_A7)
 858       && square_distance(weakerKingSq, relative_square(strongerSide, SQ_A8)) <= 1)
 859       return ScaleFactor(0);
 860
 861   if (   pawnSq == relative_square(strongerSide, SQ_H7)
 862       && square_distance(weakerKingSq, relative_square(strongerSide, SQ_H8)) <= 1)
 863       return ScaleFactor(0);
 864
 865   return SCALE_FACTOR_NONE;
 866 }
 867
 868
 869 /// KPKPScalingFunction scales KP vs KP endgames. This is done by removing
 870 /// the weakest side's pawn and probing the KP vs K bitbase: If the weakest
 871 /// side has a draw without the pawn, she probably has at least a draw with
 872 /// the pawn as well. The exception is when the stronger side's pawn is far
 873 /// advanced and not on a rook file; in this case it is often possible to win
 874 /// (e.g. 8/4k3/3p4/3P4/6K1/8/8/8 w - - 0 1).
 875
 876 ScaleFactor KPKPScalingFunction::apply(const Position &pos) {
 877
 878   assert(pos.non_pawn_material(strongerSide) == Value(0));
 879   assert(pos.non_pawn_material(weakerSide) == Value(0));
 880   assert(pos.piece_count(WHITE, PAWN) == 1);
 881   assert(pos.piece_count(BLACK, PAWN) == 1);
 882
 883   Square wksq, bksq, wpsq;
 884   Color stm;
 885
 886   if (strongerSide == WHITE)
 887   {
 888       wksq = pos.king_square(WHITE);
 889       bksq = pos.king_square(BLACK);
 890       wpsq = pos.piece_list(WHITE, PAWN, 0);
 891       stm = pos.side_to_move();
 892   }
 893   else
 894   {
 895       wksq = flip_square(pos.king_square(BLACK));
 896       bksq = flip_square(pos.king_square(WHITE));
 897       wpsq = flip_square(pos.piece_list(BLACK, PAWN, 0));
 898       stm = opposite_color(pos.side_to_move());
 899   }
 900
 901   if (square_file(wpsq) >= FILE_E)
 902   {
 903       wksq = flop_square(wksq);
 904       bksq = flop_square(bksq);
 905       wpsq = flop_square(wpsq);
 906   }
 907
 908   // If the pawn has advanced to the fifth rank or further, and is not a
 909   // rook pawn, it's too dangerous to assume that it's at least a draw.
 910   if (   square_rank(wpsq) >= RANK_5
 911       && square_file(wpsq) != FILE_A)
 912       return SCALE_FACTOR_NONE;
 913
 914   // Probe the KPK bitbase with the weakest side's pawn removed. If it's a
 915   // draw, it's probably at least a draw even with the pawn.
 916   if (probe_kpk(wksq, wpsq, bksq, stm))
 917       return SCALE_FACTOR_NONE;
 918   else
 919       return ScaleFactor(0);
 920 }
 921
 922
 923 /// init_bitbases() is called during program initialization, and simply loads
 924 /// bitbases from disk into memory.  At the moment, there is only the bitbase
 925 /// for KP vs K, but we may decide to add other bitbases later.
 926
 927 void init_bitbases() {
 928   generate_kpk_bitbase(KPKBitbase);
 929 }
 930
 931
 932 namespace {
 933
 934   // Probe the KP vs K bitbase:
 935
 936   int probe_kpk(Square wksq, Square wpsq, Square bksq, Color stm) {
 937
 938     int wp = int(square_file(wpsq)) + (int(square_rank(wpsq)) - 1) * 4;
 939     int index = int(stm) + 2*int(bksq) + 128*int(wksq) + 8192*wp;
 940
 941     assert(index >= 0 && index < 24576*8);
 942     return KPKBitbase[index/8] & (1 << (index&7));
 943   }
 944 }