git.sesse.net Git - stockfish/blob - src/material.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-2010 Marco Costalba, Joona Kiiski, Tord Romstad
   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 #include <cassert>
  21 #include <cstring>
  22 #include <map>
  23
  24 #include "material.h"
  25
  26 using namespace std;
  27
  28 namespace {
  29
  30   // Values modified by Joona Kiiski
  31   const Value MidgameLimit = Value(15581);
  32   const Value EndgameLimit = Value(3998);
  33
  34   // Polynomial material balance parameters
  35   const Value RedundantQueenPenalty = Value(320);
  36   const Value RedundantRookPenalty  = Value(554);
  37
  38   const int LinearCoefficients[6] = { 1617, -162, -1172, -190, 105, 26 };
  39
  40   const int QuadraticCoefficientsSameColor[][8] = {
  41   { 7, 7, 7, 7, 7, 7 }, { 39, 2, 7, 7, 7, 7 }, { 35, 271, -4, 7, 7, 7 },
  42   { 7, 25, 4, 7, 7, 7 }, { -27, -2, 46, 100, 56, 7 }, { 58, 29, 83, 148, -3, -25 } };
  43
  44   const int QuadraticCoefficientsOppositeColor[][8] = {
  45   { 41, 41, 41, 41, 41, 41 }, { 37, 41, 41, 41, 41, 41 }, { 10, 62, 41, 41, 41, 41 },
  46   { 57, 64, 39, 41, 41, 41 }, { 50, 40, 23, -22, 41, 41 }, { 106, 101, 3, 151, 171, 41 } };
  47
  48   typedef EndgameEvaluationFunctionBase EF;
  49   typedef EndgameScalingFunctionBase SF;
  50   typedef map<Key, EF*> EFMap;
  51   typedef map<Key, SF*> SFMap;
  52
  53   // Endgame evaluation and scaling functions accessed direcly and not through
  54   // the function maps because correspond to more then one material hash key.
  55   EvaluationFunction<KmmKm> EvaluateKmmKm[] = { EvaluationFunction<KmmKm>(WHITE), EvaluationFunction<KmmKm>(BLACK) };
  56   EvaluationFunction<KXK>   EvaluateKXK[]   = { EvaluationFunction<KXK>(WHITE),   EvaluationFunction<KXK>(BLACK) };
  57   ScalingFunction<KBPsK>    ScaleKBPsK[]    = { ScalingFunction<KBPsK>(WHITE),    ScalingFunction<KBPsK>(BLACK) };
  58   ScalingFunction<KQKRPs>   ScaleKQKRPs[]   = { ScalingFunction<KQKRPs>(WHITE),   ScalingFunction<KQKRPs>(BLACK) };
  59   ScalingFunction<KPsK>     ScaleKPsK[]     = { ScalingFunction<KPsK>(WHITE),     ScalingFunction<KPsK>(BLACK) };
  60   ScalingFunction<KPKP>     ScaleKPKP[]     = { ScalingFunction<KPKP>(WHITE),     ScalingFunction<KPKP>(BLACK) };
  61
  62   // Helper templates used to detect a given material distribution
  63   template<Color Us> bool is_KXK(const Position& pos) {
  64     const Color Them = (Us == WHITE ? BLACK : WHITE);
  65     return   pos.non_pawn_material(Them) == VALUE_ZERO
  66           && pos.piece_count(Them, PAWN) == 0
  67           && pos.non_pawn_material(Us)   >= RookValueMidgame;
  68   }
  69
  70   template<Color Us> bool is_KBPsKs(const Position& pos) {
  71     return   pos.non_pawn_material(Us)   == BishopValueMidgame
  72           && pos.piece_count(Us, BISHOP) == 1
  73           && pos.piece_count(Us, PAWN)   >= 1;
  74   }
  75
  76   template<Color Us> bool is_KQKRPs(const Position& pos) {
  77     const Color Them = (Us == WHITE ? BLACK : WHITE);
  78     return   pos.piece_count(Us, PAWN)    == 0
  79           && pos.non_pawn_material(Us)    == QueenValueMidgame
  80           && pos.piece_count(Us, QUEEN)   == 1
  81           && pos.piece_count(Them, ROOK)  == 1
  82           && pos.piece_count(Them, PAWN)  >= 1;
  83   }
  84 }
  85
  86
  87 /// EndgameFunctions class stores endgame evaluation and scaling functions
  88 /// in two std::map. Because STL library is not guaranteed to be thread
  89 /// safe even for read access, the maps, although with identical content,
  90 /// are replicated for each thread. This is faster then using locks.
  91
  92 class EndgameFunctions {
  93 public:
  94   EndgameFunctions();
  95   ~EndgameFunctions();
  96   template<class T> T* get(Key key) const;
  97
  98 private:
  99   template<class T> void add(const string& keyCode);
 100
 101   static Key buildKey(const string& keyCode);
 102   static const string swapColors(const string& keyCode);
 103
 104   // Here we store two maps, for evaluate and scaling functions...
 105   pair<EFMap, SFMap> maps;
 106
 107   // ...and here is the accessing template function
 108   template<typename T> const map<Key, T*>& get() const;
 109 };
 110
 111 // Explicit specializations of a member function shall be declared in
 112 // the namespace of which the class template is a member.
 113 template<> const EFMap& EndgameFunctions::get<EF>() const { return maps.first; }
 114 template<> const SFMap& EndgameFunctions::get<SF>() const { return maps.second; }
 115
 116
 117 /// MaterialInfoTable c'tor and d'tor allocate and free the space for EndgameFunctions
 118
 119 MaterialInfoTable::MaterialInfoTable() { funcs = new EndgameFunctions(); }
 120 MaterialInfoTable::~MaterialInfoTable() { delete funcs; }
 121
 122
 123 /// MaterialInfoTable::get_material_info() takes a position object as input,
 124 /// computes or looks up a MaterialInfo object, and returns a pointer to it.
 125 /// If the material configuration is not already present in the table, it
 126 /// is stored there, so we don't have to recompute everything when the
 127 /// same material configuration occurs again.
 128
 129 MaterialInfo* MaterialInfoTable::get_material_info(const Position& pos) const {
 130
 131   Key key = pos.get_material_key();
 132   MaterialInfo* mi = find(key);
 133
 134   // If mi->key matches the position's material hash key, it means that we
 135   // have analysed this material configuration before, and we can simply
 136   // return the information we found the last time instead of recomputing it.
 137   if (mi->key == key)
 138       return mi;
 139
 140   // Initialize MaterialInfo entry
 141   memset(mi, 0, sizeof(MaterialInfo));
 142   mi->key = key;
 143   mi->factor[WHITE] = mi->factor[BLACK] = (uint8_t)SCALE_FACTOR_NORMAL;
 144
 145   // Store game phase
 146   mi->gamePhase = MaterialInfoTable::game_phase(pos);
 147
 148   // Let's look if we have a specialized evaluation function for this
 149   // particular material configuration. First we look for a fixed
 150   // configuration one, then a generic one if previous search failed.
 151   if ((mi->evaluationFunction = funcs->get<EF>(key)) != NULL)
 152       return mi;
 153
 154   if (is_KXK<WHITE>(pos))
 155   {
 156       mi->evaluationFunction = &EvaluateKXK[WHITE];
 157       return mi;
 158   }
 159
 160   if (is_KXK<BLACK>(pos))
 161   {
 162       mi->evaluationFunction = &EvaluateKXK[BLACK];
 163       return mi;
 164   }
 165
 166   if (!pos.pieces(PAWN) && !pos.pieces(ROOK) && !pos.pieces(QUEEN))
 167   {
 168       // Minor piece endgame with at least one minor piece per side and
 169       // no pawns. Note that the case KmmK is already handled by KXK.
 170       assert((pos.pieces(KNIGHT, WHITE) | pos.pieces(BISHOP, WHITE)));
 171       assert((pos.pieces(KNIGHT, BLACK) | pos.pieces(BISHOP, BLACK)));
 172
 173       if (   pos.piece_count(WHITE, BISHOP) + pos.piece_count(WHITE, KNIGHT) <= 2
 174           && pos.piece_count(BLACK, BISHOP) + pos.piece_count(BLACK, KNIGHT) <= 2)
 175       {
 176           mi->evaluationFunction = &EvaluateKmmKm[WHITE];
 177           return mi;
 178       }
 179   }
 180
 181   // OK, we didn't find any special evaluation function for the current
 182   // material configuration. Is there a suitable scaling function?
 183   //
 184   // We face problems when there are several conflicting applicable
 185   // scaling functions and we need to decide which one to use.
 186   SF* sf;
 187
 188   if ((sf = funcs->get<SF>(key)) != NULL)
 189   {
 190       mi->scalingFunction[sf->color()] = sf;
 191       return mi;
 192   }
 193
 194   // Generic scaling functions that refer to more then one material
 195   // distribution. Should be probed after the specialized ones.
 196   // Note that these ones don't return after setting the function.
 197   if (is_KBPsKs<WHITE>(pos))
 198       mi->scalingFunction[WHITE] = &ScaleKBPsK[WHITE];
 199
 200   if (is_KBPsKs<BLACK>(pos))
 201       mi->scalingFunction[BLACK] = &ScaleKBPsK[BLACK];
 202
 203   if (is_KQKRPs<WHITE>(pos))
 204       mi->scalingFunction[WHITE] = &ScaleKQKRPs[WHITE];
 205
 206   else if (is_KQKRPs<BLACK>(pos))
 207       mi->scalingFunction[BLACK] = &ScaleKQKRPs[BLACK];
 208
 209   if (pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) == VALUE_ZERO)
 210   {
 211       if (pos.piece_count(BLACK, PAWN) == 0)
 212       {
 213           assert(pos.piece_count(WHITE, PAWN) >= 2);
 214           mi->scalingFunction[WHITE] = &ScaleKPsK[WHITE];
 215       }
 216       else if (pos.piece_count(WHITE, PAWN) == 0)
 217       {
 218           assert(pos.piece_count(BLACK, PAWN) >= 2);
 219           mi->scalingFunction[BLACK] = &ScaleKPsK[BLACK];
 220       }
 221       else if (pos.piece_count(WHITE, PAWN) == 1 && pos.piece_count(BLACK, PAWN) == 1)
 222       {
 223           // This is a special case because we set scaling functions
 224           // for both colors instead of only one.
 225           mi->scalingFunction[WHITE] = &ScaleKPKP[WHITE];
 226           mi->scalingFunction[BLACK] = &ScaleKPKP[BLACK];
 227       }
 228   }
 229
 230   // No pawns makes it difficult to win, even with a material advantage
 231   for (Color c = WHITE; c <= BLACK; c++)
 232       if (   pos.piece_count(c, PAWN) == 0
 233           && pos.non_pawn_material(c) - pos.non_pawn_material(opposite_color(c)) <= BishopValueMidgame)
 234       {
 235           if (   pos.non_pawn_material(c) == pos.non_pawn_material(opposite_color(c))
 236               || pos.non_pawn_material(c) < RookValueMidgame)
 237               mi->factor[c] = 0;
 238           else
 239           {
 240               switch (pos.piece_count(c, BISHOP)) {
 241               case 2:
 242                   mi->factor[c] = 32;
 243                   break;
 244               case 1:
 245                   mi->factor[c] = 12;
 246                   break;
 247               case 0:
 248                   mi->factor[c] = 6;
 249                   break;
 250               }
 251           }
 252       }
 253
 254   // Compute the space weight
 255   if (pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) >=
 256       2*QueenValueMidgame + 4*RookValueMidgame + 2*KnightValueMidgame)
 257   {
 258       int minorPieceCount =  pos.piece_count(WHITE, KNIGHT)
 259                            + pos.piece_count(WHITE, BISHOP)
 260                            + pos.piece_count(BLACK, KNIGHT)
 261                            + pos.piece_count(BLACK, BISHOP);
 262
 263       mi->spaceWeight = minorPieceCount * minorPieceCount;
 264   }
 265
 266   // Evaluate the material imbalance. We use PIECE_TYPE_NONE as a place holder
 267   // for the bishop pair "extended piece", this allow us to be more flexible
 268   // in defining bishop pair bonuses.
 269   const int pieceCount[2][8] = {
 270   { pos.piece_count(WHITE, BISHOP) > 1, pos.piece_count(WHITE, PAWN), pos.piece_count(WHITE, KNIGHT),
 271     pos.piece_count(WHITE, BISHOP), pos.piece_count(WHITE, ROOK), pos.piece_count(WHITE, QUEEN) },
 272   { pos.piece_count(BLACK, BISHOP) > 1, pos.piece_count(BLACK, PAWN), pos.piece_count(BLACK, KNIGHT),
 273     pos.piece_count(BLACK, BISHOP), pos.piece_count(BLACK, ROOK), pos.piece_count(BLACK, QUEEN) } };
 274
 275   mi->value = (int16_t)(imbalance<WHITE>(pieceCount) - imbalance<BLACK>(pieceCount)) / 16;
 276   return mi;
 277 }
 278
 279
 280 /// MaterialInfoTable::imbalance() calculates imbalance comparing piece count of each
 281 /// piece type for both colors.
 282
 283 template<Color Us>
 284 int MaterialInfoTable::imbalance(const int pieceCount[][8]) {
 285
 286   const Color Them = (Us == WHITE ? BLACK : WHITE);
 287
 288   int pt1, pt2, pc, vv;
 289   int value = 0;
 290
 291   // Redundancy of major pieces, formula based on Kaufman's paper
 292   // "The Evaluation of Material Imbalances in Chess"
 293   if (pieceCount[Us][ROOK] > 0)
 294       value -=  RedundantRookPenalty * (pieceCount[Us][ROOK] - 1)
 295               + RedundantQueenPenalty * pieceCount[Us][QUEEN];
 296
 297   // Second-degree polynomial material imbalance by Tord Romstad
 298   for (pt1 = PIECE_TYPE_NONE; pt1 <= QUEEN; pt1++)
 299   {
 300       pc = pieceCount[Us][pt1];
 301       if (!pc)
 302           continue;
 303
 304       vv = LinearCoefficients[pt1];
 305
 306       for (pt2 = PIECE_TYPE_NONE; pt2 <= pt1; pt2++)
 307           vv +=  QuadraticCoefficientsSameColor[pt1][pt2] * pieceCount[Us][pt2]
 308                + QuadraticCoefficientsOppositeColor[pt1][pt2] * pieceCount[Them][pt2];
 309
 310       value += pc * vv;
 311   }
 312   return value;
 313 }
 314
 315
 316 /// MaterialInfoTable::game_phase() calculates the phase given the current
 317 /// position. Because the phase is strictly a function of the material, it
 318 /// is stored in MaterialInfo.
 319
 320 Phase MaterialInfoTable::game_phase(const Position& pos) {
 321
 322   Value npm = pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK);
 323
 324   if (npm >= MidgameLimit)
 325       return PHASE_MIDGAME;
 326
 327   if (npm <= EndgameLimit)
 328       return PHASE_ENDGAME;
 329
 330   return Phase(((npm - EndgameLimit) * 128) / (MidgameLimit - EndgameLimit));
 331 }
 332
 333
 334 /// EndgameFunctions member definitions
 335
 336 EndgameFunctions::EndgameFunctions() {
 337
 338   add<EvaluationFunction<KNNK>  >("KNNK");
 339   add<EvaluationFunction<KPK>   >("KPK");
 340   add<EvaluationFunction<KBNK>  >("KBNK");
 341   add<EvaluationFunction<KRKP>  >("KRKP");
 342   add<EvaluationFunction<KRKB>  >("KRKB");
 343   add<EvaluationFunction<KRKN>  >("KRKN");
 344   add<EvaluationFunction<KQKR>  >("KQKR");
 345   add<EvaluationFunction<KBBKN> >("KBBKN");
 346
 347   add<ScalingFunction<KNPK>    >("KNPK");
 348   add<ScalingFunction<KRPKR>   >("KRPKR");
 349   add<ScalingFunction<KBPKB>   >("KBPKB");
 350   add<ScalingFunction<KBPPKB>  >("KBPPKB");
 351   add<ScalingFunction<KBPKN>   >("KBPKN");
 352   add<ScalingFunction<KRPPKRP> >("KRPPKRP");
 353 }
 354
 355 EndgameFunctions::~EndgameFunctions() {
 356
 357     for (EFMap::const_iterator it = maps.first.begin(); it != maps.first.end(); ++it)
 358         delete it->second;
 359
 360     for (SFMap::const_iterator it = maps.second.begin(); it != maps.second.end(); ++it)
 361         delete it->second;
 362 }
 363
 364 Key EndgameFunctions::buildKey(const string& keyCode) {
 365
 366     assert(keyCode.length() > 0 && keyCode.length() < 8);
 367     assert(keyCode[0] == 'K');
 368
 369     string fen;
 370     bool upcase = false;
 371
 372     // Build up a fen string with the given pieces, note that
 373     // the fen string could be of an illegal position.
 374     for (size_t i = 0; i < keyCode.length(); i++)
 375     {
 376         if (keyCode[i] == 'K')
 377             upcase = !upcase;
 378
 379         fen += char(upcase ? toupper(keyCode[i]) : tolower(keyCode[i]));
 380     }
 381     fen += char(8 - keyCode.length() + '0');
 382     fen += "/8/8/8/8/8/8/8 w - -";
 383     return Position(fen, false, 0).get_material_key();
 384 }
 385
 386 const string EndgameFunctions::swapColors(const string& keyCode) {
 387
 388     // Build corresponding key for the opposite color: "KBPKN" -> "KNKBP"
 389     size_t idx = keyCode.find('K', 1);
 390     return keyCode.substr(idx) + keyCode.substr(0, idx);
 391 }
 392
 393 template<class T>
 394 void EndgameFunctions::add(const string& keyCode) {
 395
 396   typedef typename T::Base F;
 397   typedef map<Key, F*> M;
 398
 399   const_cast<M&>(get<F>()).insert(pair<Key, F*>(buildKey(keyCode), new T(WHITE)));
 400   const_cast<M&>(get<F>()).insert(pair<Key, F*>(buildKey(swapColors(keyCode)), new T(BLACK)));
 401 }
 402
 403 template<class T>
 404 T* EndgameFunctions::get(Key key) const {
 405
 406   typename map<Key, T*>::const_iterator it = get<T>().find(key);
 407   return it != get<T>().end() ? it->second : NULL;
 408 }