1 /* pawn.cpp
2 
3    GNU Chess engine
4 
5    Copyright (C) 2001-2011 Free Software Foundation, Inc.
6 
7    This program is free software: you can redistribute it and/or modify
8    it under the terms of the GNU General Public License as published by
9    the Free Software Foundation, either version 3 of the License, or
10    (at your option) any later version.
11 
12    This program is distributed in the hope that it will be useful,
13    but WITHOUT ANY WARRANTY; without even the implied warranty of
14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15    GNU General Public License for more details.
16 
17    You should have received a copy of the GNU General Public License
18    along with this program.  If not, see <http://www.gnu.org/licenses/>.
19 */
20 
21 
22 // pawn.cpp
23 
24 // includes
25 
26 #include <cstring>
27 
28 #include "board.h"
29 #include "colour.h"
30 #include "hash.h"
31 #include "option.h"
32 #include "pawn.h"
33 #include "piece.h"
34 #include "protocol.h"
35 #include "square.h"
36 #include "util.h"
37 
38 namespace engine {
39 
40 // constants
41 
42 static const bool UseTable = true;
43 static const uint32 TableSize = 16384; // 256kB
44 
45 // types
46 
47 typedef pawn_info_t entry_t;
48 
49 struct pawn_t {
50    entry_t * table;
51    uint32 size;
52    uint32 mask;
53    uint32 used;
54    sint64 read_nb;
55    sint64 read_hit;
56    sint64 write_nb;
57    sint64 write_collision;
58 };
59 
60 // constants and variables
61 
62 static /* const */ int PawnStructureWeight = 256; // 100%
63 
64 static const int DoubledOpening = 10;
65 static const int DoubledEndgame = 20;
66 
67 static const int IsolatedOpening = 10;
68 static const int IsolatedOpeningOpen = 20;
69 static const int IsolatedEndgame = 20;
70 
71 static const int BackwardOpening = 8;
72 static const int BackwardOpeningOpen = 16;
73 static const int BackwardEndgame = 10;
74 
75 static const int CandidateOpeningMin = 5;
76 static const int CandidateOpeningMax = 55;
77 static const int CandidateEndgameMin = 10;
78 static const int CandidateEndgameMax = 110;
79 
80 // this was moved to eval.cpp
81 
82 /*
83 static const int PassedOpeningMin = 10;
84 static const int PassedOpeningMax = 70;
85 static const int PassedEndgameMin = 20;
86 static const int PassedEndgameMax = 140;
87 */
88 
89 static /* const */ int Bonus[RankNb];
90 
91 // variables
92 
93 int BitEQ[16];
94 int BitLT[16];
95 int BitLE[16];
96 int BitGT[16];
97 int BitGE[16];
98 
99 int BitFirst[0x100];
100 int BitLast[0x100];
101 int BitCount[0x100];
102 int BitRev[0x100];
103 
104 static pawn_t Pawn[1];
105 
106 static int BitRank1[RankNb];
107 static int BitRank2[RankNb];
108 static int BitRank3[RankNb];
109 
110 // prototypes
111 
112 static void pawn_comp_info (pawn_info_t * info, const board_t * board);
113 
114 // functions
115 
116 // pawn_init_bit()
117 
pawn_init_bit()118 void pawn_init_bit() {
119 
120    int rank;
121    int first, last, count;
122    int b, rev;
123 
124    // rank-indexed Bit*[]
125 
126    for (rank = 0; rank < RankNb; rank++) {
127 
128       BitEQ[rank] = 0;
129       BitLT[rank] = 0;
130       BitLE[rank] = 0;
131       BitGT[rank] = 0;
132       BitGE[rank] = 0;
133 
134       BitRank1[rank] = 0;
135       BitRank2[rank] = 0;
136       BitRank3[rank] = 0;
137    }
138 
139    for (rank = Rank1; rank <= Rank8; rank++) {
140       BitEQ[rank] = 1 << (rank - Rank1);
141       BitLT[rank] = BitEQ[rank] - 1;
142       BitLE[rank] = BitLT[rank] | BitEQ[rank];
143       BitGT[rank] = BitLE[rank] ^ 0xFF;
144       BitGE[rank] = BitGT[rank] | BitEQ[rank];
145    }
146 
147    for (rank = Rank1; rank <= Rank8; rank++) {
148       BitRank1[rank] = BitEQ[rank+1];
149       BitRank2[rank] = BitEQ[rank+1] | BitEQ[rank+2];
150       BitRank3[rank] = BitEQ[rank+1] | BitEQ[rank+2] | BitEQ[rank+3];
151    }
152 
153    // bit-indexed Bit*[]
154 
155    for (b = 0; b < 0x100; b++) {
156 
157       first = Rank8; // HACK for pawn shelter
158       last = Rank1; // HACK
159       count = 0;
160       rev = 0;
161 
162       for (rank = Rank1; rank <= Rank8; rank++) {
163          if ((b & BitEQ[rank]) != 0) {
164             if (rank < first) first = rank;
165             if (rank > last) last = rank;
166             count++;
167             rev |= BitEQ[RANK_OPP(rank)];
168          }
169       }
170 
171       BitFirst[b] = first;
172       BitLast[b] = last;
173       BitCount[b] = count;
174       BitRev[b] = rev;
175    }
176 }
177 
178 // pawn_init()
179 
pawn_init()180 void pawn_init() {
181 
182    int rank;
183 
184    // UCI options
185 
186    PawnStructureWeight = (option_get_int("Pawn Structure") * 256 + 50) / 100;
187 
188    // bonus
189 
190    for (rank = 0; rank < RankNb; rank++) Bonus[rank] = 0;
191 
192    Bonus[Rank4] = 26;
193    Bonus[Rank5] = 77;
194    Bonus[Rank6] = 154;
195    Bonus[Rank7] = 256;
196 
197    // pawn hash-table
198 
199    Pawn->size = 0;
200    Pawn->mask = 0;
201    Pawn->table = NULL;
202 }
203 
204 // pawn_alloc()
205 
pawn_alloc()206 void pawn_alloc() {
207 
208    ASSERT(sizeof(entry_t)==16);
209 
210    if (UseTable) {
211 
212       Pawn->size = TableSize;
213       Pawn->mask = TableSize - 1;
214       Pawn->table = (entry_t *) my_malloc(Pawn->size*sizeof(entry_t));
215 
216       pawn_clear();
217    }
218 }
219 
220 // pawn_clear()
221 
pawn_clear()222 void pawn_clear() {
223 
224    if (Pawn->table != NULL) {
225       memset(Pawn->table,0,Pawn->size*sizeof(entry_t));
226    }
227 
228    Pawn->used = 0;
229    Pawn->read_nb = 0;
230    Pawn->read_hit = 0;
231    Pawn->write_nb = 0;
232    Pawn->write_collision = 0;
233 }
234 
235 // pawn_get_info()
236 
pawn_get_info(pawn_info_t * info,const board_t * board)237 void pawn_get_info(pawn_info_t * info, const board_t * board) {
238 
239    uint64 key;
240    entry_t * entry;
241 
242    ASSERT(info!=NULL);
243    ASSERT(board!=NULL);
244 
245    // probe
246 
247    if (UseTable) {
248 
249       Pawn->read_nb++;
250 
251       key = board->pawn_key;
252       entry = &Pawn->table[KEY_INDEX(key)&Pawn->mask];
253 
254       if (entry->lock == KEY_LOCK(key)) {
255 
256          // found
257 
258          Pawn->read_hit++;
259 
260          *info = *entry;
261 
262          return;
263       }
264    }
265 
266    // calculation
267 
268    pawn_comp_info(info,board);
269 
270    // store
271 
272    if (UseTable) {
273 
274       Pawn->write_nb++;
275 
276       if (entry->lock == 0) { // HACK: assume free entry
277          Pawn->used++;
278       } else {
279          Pawn->write_collision++;
280       }
281 
282       *entry = *info;
283       entry->lock = KEY_LOCK(key);
284    }
285 }
286 
287 // pawn_comp_info()
288 
pawn_comp_info(pawn_info_t * info,const board_t * board)289 static void pawn_comp_info(pawn_info_t * info, const board_t * board) {
290 
291    int colour;
292    int file, rank;
293    int me, opp;
294    const sq_t * ptr;
295    int sq;
296    bool backward, candidate, doubled, isolated, open, passed;
297    int t1, t2;
298    int n;
299    int bits;
300    int opening[ColourNb], endgame[ColourNb];
301    int flags[ColourNb];
302    int file_bits[ColourNb];
303    int passed_bits[ColourNb];
304    int single_file[ColourNb];
305 
306    ASSERT(info!=NULL);
307    ASSERT(board!=NULL);
308 
309    // pawn_file[]
310 
311 #if DEBUG
312    for (colour = 0; colour < ColourNb; colour++) {
313 
314       int pawn_file[FileNb];
315 
316       me = colour;
317 
318       for (file = 0; file < FileNb; file++) {
319          pawn_file[file] = 0;
320       }
321 
322       for (ptr = &board->pawn[me][0]; (sq=*ptr) != SquareNone; ptr++) {
323 
324          file = SQUARE_FILE(sq);
325          rank = PAWN_RANK(sq,me);
326 
327          ASSERT(file>=FileA&&file<=FileH);
328          ASSERT(rank>=Rank2&&rank<=Rank7);
329 
330          pawn_file[file] |= BIT(rank);
331       }
332 
333       for (file = 0; file < FileNb; file++) {
334          if (board->pawn_file[colour][file] != pawn_file[file]) my_fatal("board->pawn_file[][]\n");
335       }
336    }
337 #endif
338 
339    // init
340 
341    for (colour = 0; colour < ColourNb; colour++) {
342 
343       opening[colour] = 0;
344       endgame[colour] = 0;
345 
346       flags[colour] = 0;
347       file_bits[colour] = 0;
348       passed_bits[colour] = 0;
349       single_file[colour] = SquareNone;
350    }
351 
352    // features and scoring
353 
354    for (colour = 0; colour < ColourNb; colour++) {
355 
356       me = colour;
357       opp = COLOUR_OPP(me);
358 
359       for (ptr = &board->pawn[me][0]; (sq=*ptr) != SquareNone; ptr++) {
360 
361          // init
362 
363          file = SQUARE_FILE(sq);
364          rank = PAWN_RANK(sq,me);
365 
366          ASSERT(file>=FileA&&file<=FileH);
367          ASSERT(rank>=Rank2&&rank<=Rank7);
368 
369          // flags
370 
371          file_bits[me] |= BIT(file);
372          if (rank == Rank2) flags[me] |= BackRankFlag;
373 
374          // features
375 
376          backward = false;
377          candidate = false;
378          doubled = false;
379          isolated = false;
380          open = false;
381          passed = false;
382 
383          t1 = board->pawn_file[me][file-1] | board->pawn_file[me][file+1];
384          t2 = board->pawn_file[me][file] | BitRev[board->pawn_file[opp][file]];
385 
386          // doubled
387 
388          if ((board->pawn_file[me][file] & BitLT[rank]) != 0) {
389             doubled = true;
390          }
391 
392          // isolated and backward
393 
394          if (t1 == 0) {
395 
396             isolated = true;
397 
398          } else if ((t1 & BitLE[rank]) == 0) {
399 
400             backward = true;
401 
402             // really backward?
403 
404             if ((t1 & BitRank1[rank]) != 0) {
405 
406                ASSERT(rank+2<=Rank8);
407 
408                if (((t2 & BitRank1[rank])
409                   | ((BitRev[board->pawn_file[opp][file-1]] | BitRev[board->pawn_file[opp][file+1]]) & BitRank2[rank])) == 0) {
410 
411                   backward = false;
412                }
413 
414             } else if (rank == Rank2 && ((t1 & BitEQ[rank+2]) != 0)) {
415 
416                ASSERT(rank+3<=Rank8);
417 
418                if (((t2 & BitRank2[rank])
419                   | ((BitRev[board->pawn_file[opp][file-1]] | BitRev[board->pawn_file[opp][file+1]]) & BitRank3[rank])) == 0) {
420 
421                   backward = false;
422                }
423             }
424          }
425 
426          // open, candidate and passed
427 
428          if ((t2 & BitGT[rank]) == 0) {
429 
430             open = true;
431 
432             if (((BitRev[board->pawn_file[opp][file-1]] | BitRev[board->pawn_file[opp][file+1]]) & BitGT[rank]) == 0) {
433 
434                passed = true;
435                passed_bits[me] |= BIT(file);
436 
437             } else {
438 
439                // candidate?
440 
441                n = 0;
442 
443                n += BIT_COUNT(board->pawn_file[me][file-1]&BitLE[rank]);
444                n += BIT_COUNT(board->pawn_file[me][file+1]&BitLE[rank]);
445 
446                n -= BIT_COUNT(BitRev[board->pawn_file[opp][file-1]]&BitGT[rank]);
447                n -= BIT_COUNT(BitRev[board->pawn_file[opp][file+1]]&BitGT[rank]);
448 
449                if (n >= 0) {
450 
451                   // safe?
452 
453                   n = 0;
454 
455                   n += BIT_COUNT(board->pawn_file[me][file-1]&BitEQ[rank-1]);
456                   n += BIT_COUNT(board->pawn_file[me][file+1]&BitEQ[rank-1]);
457 
458                   n -= BIT_COUNT(BitRev[board->pawn_file[opp][file-1]]&BitEQ[rank+1]);
459                   n -= BIT_COUNT(BitRev[board->pawn_file[opp][file+1]]&BitEQ[rank+1]);
460 
461                   if (n >= 0) candidate = true;
462                }
463             }
464          }
465 
466          // score
467 
468          if (doubled) {
469             opening[me] -= DoubledOpening;
470             endgame[me] -= DoubledEndgame;
471          }
472 
473          if (isolated) {
474             if (open) {
475                opening[me] -= IsolatedOpeningOpen;
476                endgame[me] -= IsolatedEndgame;
477             } else {
478                opening[me] -= IsolatedOpening;
479                endgame[me] -= IsolatedEndgame;
480             }
481          }
482 
483          if (backward) {
484             if (open) {
485                opening[me] -= BackwardOpeningOpen;
486                endgame[me] -= BackwardEndgame;
487             } else {
488                opening[me] -= BackwardOpening;
489                endgame[me] -= BackwardEndgame;
490             }
491          }
492 
493          if (candidate) {
494             opening[me] += quad(CandidateOpeningMin,CandidateOpeningMax,rank);
495             endgame[me] += quad(CandidateEndgameMin,CandidateEndgameMax,rank);
496          }
497 
498          // this was moved to the dynamic evaluation
499 
500 /*
501          if (passed) {
502             opening[me] += quad(PassedOpeningMin,PassedOpeningMax,rank);
503             endgame[me] += quad(PassedEndgameMin,PassedEndgameMax,rank);
504          }
505 */
506       }
507    }
508 
509    // store info
510 
511    info->opening = ((opening[White] - opening[Black]) * PawnStructureWeight) / 256;
512    info->endgame = ((endgame[White] - endgame[Black]) * PawnStructureWeight) / 256;
513 
514    for (colour = 0; colour < ColourNb; colour++) {
515 
516       me = colour;
517       opp = COLOUR_OPP(me);
518 
519       // draw flags
520 
521       bits = file_bits[me];
522 
523       if (bits != 0 && (bits & (bits-1)) == 0) { // one set bit
524 
525          file = BIT_FIRST(bits);
526          rank = BIT_FIRST(board->pawn_file[me][file]);
527          ASSERT(rank>=Rank2);
528 
529          if (((BitRev[board->pawn_file[opp][file-1]] | BitRev[board->pawn_file[opp][file+1]]) & BitGT[rank]) == 0) {
530             rank = BIT_LAST(board->pawn_file[me][file]);
531             single_file[me] = SQUARE_MAKE(file,rank);
532          }
533       }
534 
535       info->flags[colour] = flags[colour];
536       info->passed_bits[colour] = passed_bits[colour];
537       info->single_file[colour] = single_file[colour];
538    }
539 }
540 
541 // quad()
542 
quad(int y_min,int y_max,int x)543 int quad(int y_min, int y_max, int x) {
544 
545    int y;
546 
547    ASSERT(y_min>=0&&y_min<=y_max&&y_max<=+32767);
548    ASSERT(x>=Rank2&&x<=Rank7);
549 
550    y = y_min + ((y_max - y_min) * Bonus[x] + 128) / 256;
551    ASSERT(y>=y_min&&y<=y_max);
552 
553    return y;
554 }
555 
556 }  // namespace engine
557 
558 // end of pawn.cpp
559 
560