Simplify endgame functions handling
[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-2009 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 <sstream>
27 #include <map>
28
29 #include "material.h"
30
31 using std::string;
32
33 ////
34 //// Local definitions
35 ////
36
37 namespace {
38
39   // Values modified by Joona Kiiski
40   const Value BishopPairMidgameBonus = Value(109);
41   const Value BishopPairEndgameBonus = Value(97);
42
43   Key KNNKMaterialKey, KKNNMaterialKey;
44
45   // Unmapped endgame evaluation and scaling functions, these
46   // are accessed direcly and not through the function maps.
47   EvaluationFunction<KmmKm> EvaluateKmmKm(WHITE);
48   EvaluationFunction<KXK>   EvaluateKXK(WHITE), EvaluateKKX(BLACK);
49   ScalingFunction<KBPK>     ScaleKBPK(WHITE),   ScaleKKBP(BLACK);
50   ScalingFunction<KQKRP>    ScaleKQKRP(WHITE),  ScaleKRPKQ(BLACK);
51   ScalingFunction<KPsK>     ScaleKPsK(WHITE),   ScaleKKPs(BLACK);
52   ScalingFunction<KPKP>     ScaleKPKPw(WHITE),  ScaleKPKPb(BLACK);
53 }
54
55
56 ////
57 //// Classes
58 ////
59
60
61 /// See header for a class description. It is declared here to avoid
62 /// to include <map> in the header file.
63
64 class EndgameFunctions {
65
66   typedef EndgameEvaluationFunctionBase EF;
67   typedef EndgameScalingFunctionBase SF;
68
69 public:
70   EndgameFunctions();
71   ~EndgameFunctions();
72   EF* getEEF(Key key) const;
73   SF* getESF(Key key, Color* c) const;
74
75 private:
76   Key buildKey(const string& keyCode);
77   const string swapColors(const string& keyCode);
78   template<EndgameType> void add_ef(const string& keyCode);
79   template<EndgameType> void add_sf(const string& keyCode);
80
81   struct ScalingInfo
82   {
83       Color col;
84       SF* fun;
85   };
86
87   std::map<Key, EF*> EEFmap;
88   std::map<Key, ScalingInfo> ESFmap;
89 };
90
91
92 ////
93 //// Functions
94 ////
95
96
97 /// Constructor for the MaterialInfoTable class
98
99 MaterialInfoTable::MaterialInfoTable(unsigned int numOfEntries) {
100
101   size = numOfEntries;
102   entries = new MaterialInfo[size];
103   funcs = new EndgameFunctions();
104   if (!entries || !funcs)
105   {
106       std::cerr << "Failed to allocate " << (numOfEntries * sizeof(MaterialInfo))
107                 << " bytes for material hash table." << std::endl;
108       Application::exit_with_failure();
109   }
110 }
111
112
113 /// Destructor for the MaterialInfoTable class
114
115 MaterialInfoTable::~MaterialInfoTable() {
116
117   delete funcs;
118   delete [] entries;
119 }
120
121
122 /// MaterialInfoTable::get_material_info() takes a position object as input,
123 /// computes or looks up a MaterialInfo object, and returns a pointer to it.
124 /// If the material configuration is not already present in the table, it
125 /// is stored there, so we don't have to recompute everything when the
126 /// same material configuration occurs again.
127
128 MaterialInfo* MaterialInfoTable::get_material_info(const Position& pos) {
129
130   Key key = pos.get_material_key();
131   int index = key & (size - 1);
132   MaterialInfo* mi = entries + index;
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   // Clear the MaterialInfo object, and set its key
141   mi->clear();
142   mi->key = key;
143
144   // A special case before looking for a specialized evaluation function
145   // KNN vs K is a draw.
146   if (key == KNNKMaterialKey || key == KKNNMaterialKey)
147   {
148       mi->factor[WHITE] = mi->factor[BLACK] = 0;
149       return mi;
150   }
151
152   // Let's look if we have a specialized evaluation function for this
153   // particular material configuration. First we look for a fixed
154   // configuration one, then a generic one if previous search failed.
155   if ((mi->evaluationFunction = funcs->getEEF(key)) != NULL)
156       return mi;
157
158   else if (   pos.non_pawn_material(BLACK) == Value(0)
159            && pos.piece_count(BLACK, PAWN) == 0
160            && pos.non_pawn_material(WHITE) >= RookValueMidgame)
161   {
162       mi->evaluationFunction = &EvaluateKXK;
163       return mi;
164   }
165   else if (   pos.non_pawn_material(WHITE) == Value(0)
166            && pos.piece_count(WHITE, PAWN) == 0
167            && pos.non_pawn_material(BLACK) >= RookValueMidgame)
168   {
169       mi->evaluationFunction = &EvaluateKKX;
170       return mi;
171   }
172   else if (   pos.pawns() == EmptyBoardBB
173            && pos.rooks() == EmptyBoardBB
174            && pos.queens() == EmptyBoardBB)
175   {
176       // Minor piece endgame with at least one minor piece per side,
177       // and no pawns.
178       assert(pos.knights(WHITE) | pos.bishops(WHITE));
179       assert(pos.knights(BLACK) | pos.bishops(BLACK));
180
181       if (   pos.piece_count(WHITE, BISHOP) + pos.piece_count(WHITE, KNIGHT) <= 2
182           && pos.piece_count(BLACK, BISHOP) + pos.piece_count(BLACK, KNIGHT) <= 2)
183       {
184           mi->evaluationFunction = &EvaluateKmmKm;
185           return mi;
186       }
187   }
188
189   // OK, we didn't find any special evaluation function for the current
190   // material configuration. Is there a suitable scaling function?
191   //
192   // The code below is rather messy, and it could easily get worse later,
193   // if we decide to add more special cases. We face problems when there
194   // are several conflicting applicable scaling functions and we need to
195   // decide which one to use.
196   Color c;
197   EndgameScalingFunctionBase* sf;
198
199   if ((sf = funcs->getESF(key, &c)) != NULL)
200   {
201       mi->scalingFunction[c] = sf;
202       return mi;
203   }
204
205   if (   pos.non_pawn_material(WHITE) == BishopValueMidgame
206       && pos.piece_count(WHITE, BISHOP) == 1
207       && pos.piece_count(WHITE, PAWN) >= 1)
208       mi->scalingFunction[WHITE] = &ScaleKBPK;
209
210   if (   pos.non_pawn_material(BLACK) == BishopValueMidgame
211       && pos.piece_count(BLACK, BISHOP) == 1
212       && pos.piece_count(BLACK, PAWN) >= 1)
213       mi->scalingFunction[BLACK] = &ScaleKKBP;
214
215   if (   pos.piece_count(WHITE, PAWN) == 0
216       && pos.non_pawn_material(WHITE) == QueenValueMidgame
217       && pos.piece_count(WHITE, QUEEN) == 1
218       && pos.piece_count(BLACK, ROOK) == 1
219       && pos.piece_count(BLACK, PAWN) >= 1)
220       mi->scalingFunction[WHITE] = &ScaleKQKRP;
221
222   else if (   pos.piece_count(BLACK, PAWN) == 0
223            && pos.non_pawn_material(BLACK) == QueenValueMidgame
224            && pos.piece_count(BLACK, QUEEN) == 1
225            && pos.piece_count(WHITE, ROOK) == 1
226            && pos.piece_count(WHITE, PAWN) >= 1)
227       mi->scalingFunction[BLACK] = &ScaleKRPKQ;
228
229   if (pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) == Value(0))
230   {
231       if (pos.piece_count(BLACK, PAWN) == 0)
232       {
233           assert(pos.piece_count(WHITE, PAWN) >= 2);
234           mi->scalingFunction[WHITE] = &ScaleKPsK;
235       }
236       else if (pos.piece_count(WHITE, PAWN) == 0)
237       {
238           assert(pos.piece_count(BLACK, PAWN) >= 2);
239           mi->scalingFunction[BLACK] = &ScaleKKPs;
240       }
241       else if (pos.piece_count(WHITE, PAWN) == 1 && pos.piece_count(BLACK, PAWN) == 1)
242       {
243           mi->scalingFunction[WHITE] = &ScaleKPKPw;
244           mi->scalingFunction[BLACK] = &ScaleKPKPb;
245       }
246   }
247
248   // Compute the space weight
249   if (pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) >=
250       2*QueenValueMidgame + 4*RookValueMidgame + 2*KnightValueMidgame)
251   {
252       int minorPieceCount =  pos.piece_count(WHITE, KNIGHT)
253                            + pos.piece_count(BLACK, KNIGHT)
254                            + pos.piece_count(WHITE, BISHOP)
255                            + pos.piece_count(BLACK, BISHOP);
256
257       mi->spaceWeight = minorPieceCount * minorPieceCount;
258   }
259
260   // Evaluate the material balance
261
262   int sign;
263   Value egValue = Value(0);
264   Value mgValue = Value(0);
265
266   for (c = WHITE, sign = 1; c <= BLACK; c++, sign = -sign)
267   {
268     // No pawns makes it difficult to win, even with a material advantage
269     if (   pos.piece_count(c, PAWN) == 0
270         && pos.non_pawn_material(c) - pos.non_pawn_material(opposite_color(c)) <= BishopValueMidgame)
271     {
272         if (   pos.non_pawn_material(c) == pos.non_pawn_material(opposite_color(c))
273             || pos.non_pawn_material(c) < RookValueMidgame)
274             mi->factor[c] = 0;
275         else
276         {
277             switch (pos.piece_count(c, BISHOP)) {
278             case 2:
279                 mi->factor[c] = 32;
280                 break;
281             case 1:
282                 mi->factor[c] = 12;
283                 break;
284             case 0:
285                 mi->factor[c] = 6;
286                 break;
287             }
288         }
289     }
290
291     // Bishop pair
292     if (pos.piece_count(c, BISHOP) >= 2)
293     {
294         mgValue += sign * BishopPairMidgameBonus;
295         egValue += sign * BishopPairEndgameBonus;
296     }
297
298     // Knights are stronger when there are many pawns on the board.  The
299     // formula is taken from Larry Kaufman's paper "The Evaluation of Material
300     // Imbalances in Chess":
301     // http://mywebpages.comcast.net/danheisman/Articles/evaluation_of_material_imbalance.htm
302     mgValue += sign * Value(pos.piece_count(c, KNIGHT)*(pos.piece_count(c, PAWN)-5)*16);
303     egValue += sign * Value(pos.piece_count(c, KNIGHT)*(pos.piece_count(c, PAWN)-5)*16);
304
305     // Redundancy of major pieces, again based on Kaufman's paper:
306     if (pos.piece_count(c, ROOK) >= 1)
307     {
308         Value v = Value((pos.piece_count(c, ROOK) - 1) * 32 + pos.piece_count(c, QUEEN) * 16);
309         mgValue -= sign * v;
310         egValue -= sign * v;
311     }
312   }
313   mi->mgValue = int16_t(mgValue);
314   mi->egValue = int16_t(egValue);
315   return mi;
316 }
317
318
319 /// EndgameFunctions member definitions. This class is used to store the maps
320 /// of end game and scaling functions that MaterialInfoTable will query for
321 /// each key. The maps are constant and are populated only at construction,
322 /// but are per-thread instead of globals to avoid expensive locks needed
323 /// because std::map is not guaranteed to be thread-safe even if accessed
324 /// only for a lookup.
325
326 EndgameFunctions::EndgameFunctions() {
327
328   KNNKMaterialKey = buildKey("KNNK");
329   KKNNMaterialKey = buildKey("KKNN");
330
331   add_ef<KPK>("KPK");
332   add_ef<KBNK>("KBNK");
333   add_ef<KRKP>("KRKP");
334   add_ef<KRKB>("KRKB");
335   add_ef<KRKN>("KRKN");
336   add_ef<KQKR>("KQKR");
337   add_ef<KBBKN>("KBBKN");
338
339   add_sf<KNPK>("KNPK");
340   add_sf<KRPKR>("KRPKR");
341   add_sf<KBPKB>("KBPKB");
342   add_sf<KBPPKB>("KBPPKB");
343   add_sf<KBPKN>("KBPKN");
344   add_sf<KRPPKRP>("KRPPKRP");
345   add_sf<KRPPKRP>("KRPPKRP");
346 }
347
348 EndgameFunctions::~EndgameFunctions() {
349
350     for (std::map<Key, EF*>::iterator it = EEFmap.begin(); it != EEFmap.end(); ++it)
351         delete (*it).second;
352
353     for (std::map<Key, ScalingInfo>::iterator it = ESFmap.begin(); it != ESFmap.end(); ++it)
354         delete (*it).second.fun;
355 }
356
357 Key EndgameFunctions::buildKey(const string& keyCode) {
358
359     assert(keyCode.length() > 0 && keyCode[0] == 'K');
360     assert(keyCode.length() < 8);
361
362     std::stringstream s;
363     bool upcase = false;
364
365     // Build up a fen substring with the given pieces, note
366     // that the fen string could be of an illegal position.
367     for (size_t i = 0; i < keyCode.length(); i++)
368     {
369         if (keyCode[i] == 'K')
370             upcase = !upcase;
371
372         s << char(upcase? toupper(keyCode[i]) : tolower(keyCode[i]));
373     }
374     s << 8 - keyCode.length() << "/8/8/8/8/8/8/8 w -";
375     return Position(s.str()).get_material_key();
376 }
377
378 const string EndgameFunctions::swapColors(const string& keyCode) {
379
380     // Build corresponding key for the opposite color: "KBPKN" -> "KNKBP"
381     size_t idx = keyCode.find("K", 1);
382     return keyCode.substr(idx) + keyCode.substr(0, idx);
383 }
384
385 template<EndgameType et>
386 void EndgameFunctions::add_ef(const string& keyCode) {
387
388   EEFmap.insert(std::pair<Key, EF*>(buildKey(keyCode), new EvaluationFunction<et>(WHITE)));
389   EEFmap.insert(std::pair<Key, EF*>(buildKey(swapColors(keyCode)), new EvaluationFunction<et>(BLACK)));
390 }
391
392 template<EndgameType et>
393 void EndgameFunctions::add_sf(const string& keyCode) {
394
395   ScalingInfo s1 = {WHITE, new ScalingFunction<et>(WHITE)};
396   ScalingInfo s2 = {BLACK, new ScalingFunction<et>(BLACK)};
397
398   ESFmap.insert(std::pair<Key, ScalingInfo>(buildKey(keyCode), s1));
399   ESFmap.insert(std::pair<Key, ScalingInfo>(buildKey(swapColors(keyCode)), s2));
400 }
401
402 EndgameEvaluationFunctionBase* EndgameFunctions::getEEF(Key key) const {
403
404   std::map<Key, EF*>::const_iterator it(EEFmap.find(key));
405   return (it != EEFmap.end() ? it->second : NULL);
406 }
407
408 EndgameScalingFunctionBase* EndgameFunctions::getESF(Key key, Color* c) const {
409
410   std::map<Key, ScalingInfo>::const_iterator it(ESFmap.find(key));
411   if (it == ESFmap.end())
412       return NULL;
413
414   *c = it->second.col;
415   return it->second.fun;
416 }