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