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 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 #include <map>
  27
  28 #include "lock.h"
  29 #include "material.h"
  30
  31
  32 ////
  33 //// Local definitions
  34 ////
  35
  36 namespace {
  37
  38   const Value BishopPairMidgameBonus = Value(100);
  39   const Value BishopPairEndgameBonus = Value(100);
  40
  41   Key KNNKMaterialKey, KKNNMaterialKey;
  42
  43   struct ScalingInfo
  44   {
  45       Color col;
  46       ScalingFunction* fun;
  47   };
  48
  49   std::map<Key, EndgameEvaluationFunction*> EEFmap;
  50   std::map<Key, ScalingInfo> ESFmap;
  51
  52   Lock EEFmapLock;
  53   Lock ESFmapLock;
  54
  55   void add(Key k, EndgameEvaluationFunction* f) {
  56
  57       EEFmap.insert(std::pair<Key, EndgameEvaluationFunction*>(k, f));
  58   }
  59
  60   void add(Key k, Color c, ScalingFunction* f) {
  61
  62       ScalingInfo s = {c, f};
  63       ESFmap.insert(std::pair<Key, ScalingInfo>(k, s));
  64   }
  65
  66   // STL map are not guaranteed to be thread safe even
  67   // for read-access so we need this two helpers to access them.
  68   EndgameEvaluationFunction* getEEF(Key key) {
  69
  70       EndgameEvaluationFunction* f = NULL;
  71
  72       lock_grab(&EEFmapLock);
  73
  74       if (EEFmap.find(key) != EEFmap.end())
  75           f = EEFmap[key];
  76
  77       lock_release(&EEFmapLock);
  78       return f;
  79   }
  80
  81   ScalingInfo getESF(Key key) {
  82
  83       ScalingInfo si = {WHITE, NULL};
  84
  85       lock_grab(&ESFmapLock);
  86
  87       if (ESFmap.find(key) != ESFmap.end())
  88           si = ESFmap[key];
  89
  90       lock_release(&ESFmapLock);
  91       return si;
  92   }
  93
  94 }
  95
  96
  97 ////
  98 //// Functions
  99 ////
 100
 101 /// MaterialInfo::init() is called during program initialization. It
 102 /// precomputes material hash keys for a few basic endgames, in order
 103 /// to make it easy to recognize such endgames when they occur.
 104
 105 void MaterialInfo::init() {
 106
 107   // Initialize std::map access locks
 108   lock_init(&EEFmapLock, NULL);
 109   lock_init(&ESFmapLock, NULL);
 110
 111   typedef Key ZM[2][8][16];
 112   const ZM& z = Position::zobMaterial;
 113
 114   static const Color W = WHITE;
 115   static const Color B = BLACK;
 116
 117   KNNKMaterialKey = z[W][KNIGHT][1] ^ z[W][KNIGHT][2];
 118   KKNNMaterialKey = z[B][KNIGHT][1] ^ z[B][KNIGHT][2];
 119
 120   add(z[W][PAWN][1], &EvaluateKPK);
 121   add(z[B][PAWN][1], &EvaluateKKP);
 122
 123   add(z[W][BISHOP][1] ^ z[W][KNIGHT][1], &EvaluateKBNK);
 124   add(z[B][BISHOP][1] ^ z[B][KNIGHT][1], &EvaluateKKBN);
 125   add(z[W][ROOK][1]   ^ z[B][PAWN][1],   &EvaluateKRKP);
 126   add(z[W][PAWN][1]   ^ z[B][ROOK][1],   &EvaluateKPKR);
 127   add(z[W][ROOK][1]   ^ z[B][BISHOP][1], &EvaluateKRKB);
 128   add(z[W][BISHOP][1] ^ z[B][ROOK][1],   &EvaluateKBKR);
 129   add(z[W][ROOK][1]   ^ z[B][KNIGHT][1], &EvaluateKRKN);
 130   add(z[W][KNIGHT][1] ^ z[B][ROOK][1],   &EvaluateKNKR);
 131   add(z[W][QUEEN][1]  ^ z[B][ROOK][1],   &EvaluateKQKR);
 132   add(z[W][ROOK][1]   ^ z[B][QUEEN][1],  &EvaluateKRKQ);
 133
 134   add(z[W][KNIGHT][1] ^ z[W][PAWN][1], W, &ScaleKNPK);
 135   add(z[B][KNIGHT][1] ^ z[B][PAWN][1], B, &ScaleKKNP);
 136
 137   add(z[W][ROOK][1]   ^ z[W][PAWN][1]   ^ z[B][ROOK][1]  , W, &ScaleKRPKR);
 138   add(z[W][ROOK][1]   ^ z[B][ROOK][1]   ^ z[B][PAWN][1]  , B, &ScaleKRKRP);
 139   add(z[W][BISHOP][1] ^ z[W][PAWN][1]   ^ z[B][BISHOP][1], W, &ScaleKBPKB);
 140   add(z[W][BISHOP][1] ^ z[B][BISHOP][1] ^ z[B][PAWN][1]  , B, &ScaleKBKBP);
 141   add(z[W][BISHOP][1] ^ z[W][PAWN][1]   ^ z[B][KNIGHT][1], W, &ScaleKBPKN);
 142   add(z[W][KNIGHT][1] ^ z[B][BISHOP][1] ^ z[B][PAWN][1]  , B, &ScaleKNKBP);
 143
 144   add(z[W][ROOK][1] ^ z[W][PAWN][1] ^ z[W][PAWN][2] ^ z[B][ROOK][1] ^ z[B][PAWN][1], W, &ScaleKRPPKRP);
 145   add(z[W][ROOK][1] ^ z[W][PAWN][1] ^ z[B][ROOK][1] ^ z[B][PAWN][1] ^ z[B][PAWN][2], B, &ScaleKRPKRPP);
 146 }
 147
 148
 149 /// Constructor for the MaterialInfoTable class
 150
 151 MaterialInfoTable::MaterialInfoTable(unsigned int numOfEntries) {
 152
 153   size = numOfEntries;
 154   entries = new MaterialInfo[size];
 155   if (!entries)
 156   {
 157       std::cerr << "Failed to allocate " << (numOfEntries * sizeof(MaterialInfo))
 158                 << " bytes for material hash table." << std::endl;
 159       exit(EXIT_FAILURE);
 160   }
 161   clear();
 162 }
 163
 164
 165 /// Destructor for the MaterialInfoTable class
 166
 167 MaterialInfoTable::~MaterialInfoTable() {
 168
 169   delete [] entries;
 170 }
 171
 172
 173 /// MaterialInfoTable::clear() clears a material hash table by setting
 174 /// all entries to 0.
 175
 176 void MaterialInfoTable::clear() {
 177
 178   memset(entries, 0, size * sizeof(MaterialInfo));
 179 }
 180
 181
 182 /// MaterialInfoTable::get_material_info() takes a position object as input,
 183 /// computes or looks up a MaterialInfo object, and returns a pointer to it.
 184 /// If the material configuration is not already present in the table, it
 185 /// is stored there, so we don't have to recompute everything when the
 186 /// same material configuration occurs again.
 187
 188 MaterialInfo *MaterialInfoTable::get_material_info(const Position& pos) {
 189
 190   Key key = pos.get_material_key();
 191   int index = key & (size - 1);
 192   MaterialInfo* mi = entries + index;
 193
 194   // If mi->key matches the position's material hash key, it means that we
 195   // have analysed this material configuration before, and we can simply
 196   // return the information we found the last time instead of recomputing it.
 197   if (mi->key == key)
 198     return mi;
 199
 200   // Clear the MaterialInfo object, and set its key
 201   mi->clear();
 202   mi->key = key;
 203
 204   // A special case before looking for a specialized evaluation function
 205   // KNN vs K is a draw.
 206   if (key == KNNKMaterialKey || key == KKNNMaterialKey)
 207   {
 208     mi->factor[WHITE] = mi->factor[BLACK] = 0;
 209     return mi;
 210   }
 211
 212   // Let's look if we have a specialized evaluation function for this
 213   // particular material configuration.
 214   if ((mi->evaluationFunction = getEEF(key)) != NULL)
 215       return mi;
 216
 217   else if (   pos.non_pawn_material(BLACK) == Value(0)
 218            && pos.piece_count(BLACK, PAWN) == 0
 219            && pos.non_pawn_material(WHITE) >= RookValueEndgame)
 220   {
 221       mi->evaluationFunction = &EvaluateKXK;
 222       return mi;
 223   }
 224   else if (   pos.non_pawn_material(WHITE) == Value(0)
 225            && pos.piece_count(WHITE, PAWN) == 0
 226            && pos.non_pawn_material(BLACK) >= RookValueEndgame)
 227   {
 228       mi->evaluationFunction = &EvaluateKKX;
 229       return mi;
 230   }
 231
 232   // OK, we didn't find any special evaluation function for the current
 233   // material configuration. Is there a suitable scaling function?
 234   //
 235   // The code below is rather messy, and it could easily get worse later,
 236   // if we decide to add more special cases.  We face problems when there
 237   // are several conflicting applicable scaling functions and we need to
 238   // decide which one to use.
 239   ScalingInfo si = getESF(key);
 240   if (si.fun != NULL)
 241   {
 242       mi->scalingFunction[si.col] = si.fun;
 243       return mi;
 244   }
 245
 246   if (   pos.non_pawn_material(WHITE) == BishopValueMidgame
 247       && pos.piece_count(WHITE, BISHOP) == 1
 248       && pos.piece_count(WHITE, PAWN) >= 1)
 249       mi->scalingFunction[WHITE] = &ScaleKBPK;
 250
 251   if (   pos.non_pawn_material(BLACK) == BishopValueMidgame
 252       && pos.piece_count(BLACK, BISHOP) == 1
 253       && pos.piece_count(BLACK, PAWN) >= 1)
 254       mi->scalingFunction[BLACK] = &ScaleKKBP;
 255
 256   if (   pos.piece_count(WHITE, PAWN) == 0
 257       && pos.non_pawn_material(WHITE) == QueenValueMidgame
 258       && pos.piece_count(WHITE, QUEEN) == 1
 259       && pos.piece_count(BLACK, ROOK) == 1
 260       && pos.piece_count(BLACK, PAWN) >= 1)
 261       mi->scalingFunction[WHITE] = &ScaleKQKRP;
 262
 263   else if (   pos.piece_count(BLACK, PAWN) == 0
 264            && pos.non_pawn_material(BLACK) == QueenValueMidgame
 265            && pos.piece_count(BLACK, QUEEN) == 1
 266            && pos.piece_count(WHITE, ROOK) == 1
 267            && pos.piece_count(WHITE, PAWN) >= 1)
 268       mi->scalingFunction[BLACK] = &ScaleKRPKQ;
 269
 270   if (pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) == Value(0))
 271   {
 272       if (pos.piece_count(BLACK, PAWN) == 0)
 273       {
 274           assert(pos.piece_count(WHITE, PAWN) >= 2);
 275           mi->scalingFunction[WHITE] = &ScaleKPsK;
 276       }
 277       else if (pos.piece_count(WHITE, PAWN) == 0)
 278       {
 279           assert(pos.piece_count(BLACK, PAWN) >= 2);
 280           mi->scalingFunction[BLACK] = &ScaleKKPs;
 281       }
 282       else if (pos.piece_count(WHITE, PAWN) == 1 && pos.piece_count(BLACK, PAWN) == 1)
 283       {
 284           mi->scalingFunction[WHITE] = &ScaleKPKPw;
 285           mi->scalingFunction[BLACK] = &ScaleKPKPb;
 286       }
 287   }
 288
 289   // Evaluate the material balance
 290
 291   Color c;
 292   int sign;
 293   Value egValue = Value(0);
 294   Value mgValue = Value(0);
 295
 296   for (c = WHITE, sign = 1; c <= BLACK; c++, sign = -sign)
 297   {
 298     // No pawns makes it difficult to win, even with a material advantage
 299     if (   pos.piece_count(c, PAWN) == 0
 300         && pos.non_pawn_material(c) - pos.non_pawn_material(opposite_color(c)) <= BishopValueMidgame)
 301     {
 302         if (   pos.non_pawn_material(c) == pos.non_pawn_material(opposite_color(c))
 303             || pos.non_pawn_material(c) < RookValueMidgame)
 304             mi->factor[c] = 0;
 305         else
 306         {
 307             switch (pos.piece_count(c, BISHOP)) {
 308             case 2:
 309                 mi->factor[c] = 32;
 310                 break;
 311             case 1:
 312                 mi->factor[c] = 12;
 313                 break;
 314             case 0:
 315                 mi->factor[c] = 6;
 316                 break;
 317             }
 318         }
 319     }
 320
 321     // Bishop pair
 322     if (pos.piece_count(c, BISHOP) >= 2)
 323     {
 324         mgValue += sign * BishopPairMidgameBonus;
 325         egValue += sign * BishopPairEndgameBonus;
 326     }
 327
 328     // Knights are stronger when there are many pawns on the board.  The
 329     // formula is taken from Larry Kaufman's paper "The Evaluation of Material
 330     // Imbalances in Chess":
 331     // http://mywebpages.comcast.net/danheisman/Articles/evaluation_of_material_imbalance.htm
 332     mgValue += sign * Value(pos.piece_count(c, KNIGHT)*(pos.piece_count(c, PAWN)-5)*16);
 333     egValue += sign * Value(pos.piece_count(c, KNIGHT)*(pos.piece_count(c, PAWN)-5)*16);
 334
 335     // Redundancy of major pieces, again based on Kaufman's paper:
 336     if (pos.piece_count(c, ROOK) >= 1)
 337     {
 338         Value v = Value((pos.piece_count(c, ROOK) - 1) * 32 + pos.piece_count(c, QUEEN) * 16);
 339         mgValue -= sign * v;
 340         egValue -= sign * v;
 341     }
 342   }
 343
 344   mi->mgValue = int16_t(mgValue);
 345   mi->egValue = int16_t(egValue);
 346   return mi;
 347 }