2cc384a31e8267a525250e9f69738314c38f0e82
[stockfish] / src / position.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-2012 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 <iostream>
23 #include <sstream>
24 #include <algorithm>
25
26 #include "bitcount.h"
27 #include "movegen.h"
28 #include "position.h"
29 #include "psqtab.h"
30 #include "rkiss.h"
31 #include "thread.h"
32 #include "tt.h"
33
34 using std::string;
35 using std::cout;
36 using std::endl;
37
38 Key Position::zobrist[2][8][64];
39 Key Position::zobEp[8];
40 Key Position::zobCastle[16];
41 Key Position::zobSideToMove;
42 Key Position::zobExclusion;
43
44 Score Position::pieceSquareTable[16][64];
45
46 // Material values arrays, indexed by Piece
47 const Value PieceValueMidgame[17] = {
48   VALUE_ZERO,
49   PawnValueMidgame, KnightValueMidgame, BishopValueMidgame,
50   RookValueMidgame, QueenValueMidgame,
51   VALUE_ZERO, VALUE_ZERO, VALUE_ZERO,
52   PawnValueMidgame, KnightValueMidgame, BishopValueMidgame,
53   RookValueMidgame, QueenValueMidgame
54 };
55
56 const Value PieceValueEndgame[17] = {
57   VALUE_ZERO,
58   PawnValueEndgame, KnightValueEndgame, BishopValueEndgame,
59   RookValueEndgame, QueenValueEndgame,
60   VALUE_ZERO, VALUE_ZERO, VALUE_ZERO,
61   PawnValueEndgame, KnightValueEndgame, BishopValueEndgame,
62   RookValueEndgame, QueenValueEndgame
63 };
64
65
66 namespace {
67
68   // Bonus for having the side to move (modified by Joona Kiiski)
69   const Score TempoValue = make_score(48, 22);
70
71   // To convert a Piece to and from a FEN char
72   const string PieceToChar(" PNBRQK  pnbrqk  .");
73 }
74
75
76 /// CheckInfo c'tor
77
78 CheckInfo::CheckInfo(const Position& pos) {
79
80   Color them = ~pos.side_to_move();
81   ksq = pos.king_square(them);
82
83   pinned = pos.pinned_pieces();
84   dcCandidates = pos.discovered_check_candidates();
85
86   checkSq[PAWN]   = pos.attacks_from<PAWN>(ksq, them);
87   checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
88   checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
89   checkSq[ROOK]   = pos.attacks_from<ROOK>(ksq);
90   checkSq[QUEEN]  = checkSq[BISHOP] | checkSq[ROOK];
91   checkSq[KING]   = 0;
92 }
93
94
95 /// Position c'tors. Here we always create a copy of the original position
96 /// or the FEN string, we want the new born Position object do not depend
97 /// on any external data so we detach state pointer from the source one.
98
99 void Position::copy(const Position& pos, int th) {
100
101   memcpy(this, &pos, sizeof(Position));
102   startState = *st;
103   st = &startState;
104   threadID = th;
105   nodes = 0;
106
107   assert(pos_is_ok());
108 }
109
110 Position::Position(const string& fen, bool isChess960, int th) {
111
112   from_fen(fen, isChess960);
113   threadID = th;
114 }
115
116
117 /// Position::from_fen() initializes the position object with the given FEN
118 /// string. This function is not very robust - make sure that input FENs are
119 /// correct (this is assumed to be the responsibility of the GUI).
120
121 void Position::from_fen(const string& fenStr, bool isChess960) {
122 /*
123    A FEN string defines a particular position using only the ASCII character set.
124
125    A FEN string contains six fields separated by a space. The fields are:
126
127    1) Piece placement (from white's perspective). Each rank is described, starting
128       with rank 8 and ending with rank 1; within each rank, the contents of each
129       square are described from file A through file H. Following the Standard
130       Algebraic Notation (SAN), each piece is identified by a single letter taken
131       from the standard English names. White pieces are designated using upper-case
132       letters ("PNBRQK") while Black take lowercase ("pnbrqk"). Blank squares are
133       noted using digits 1 through 8 (the number of blank squares), and "/"
134       separates ranks.
135
136    2) Active color. "w" means white moves next, "b" means black.
137
138    3) Castling availability. If neither side can castle, this is "-". Otherwise,
139       this has one or more letters: "K" (White can castle kingside), "Q" (White
140       can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
141       can castle queenside).
142
143    4) En passant target square (in algebraic notation). If there's no en passant
144       target square, this is "-". If a pawn has just made a 2-square move, this
145       is the position "behind" the pawn. This is recorded regardless of whether
146       there is a pawn in position to make an en passant capture.
147
148    5) Halfmove clock. This is the number of halfmoves since the last pawn advance
149       or capture. This is used to determine if a draw can be claimed under the
150       fifty-move rule.
151
152    6) Fullmove number. The number of the full move. It starts at 1, and is
153       incremented after Black's move.
154 */
155
156   char col, row, token;
157   size_t p;
158   Square sq = SQ_A8;
159   std::istringstream fen(fenStr);
160
161   clear();
162   fen >> std::noskipws;
163
164   // 1. Piece placement
165   while ((fen >> token) && !isspace(token))
166   {
167       if (isdigit(token))
168           sq += Square(token - '0'); // Advance the given number of files
169
170       else if (token == '/')
171           sq = make_square(FILE_A, rank_of(sq) - Rank(2));
172
173       else if ((p = PieceToChar.find(token)) != string::npos)
174       {
175           put_piece(Piece(p), sq);
176           sq++;
177       }
178   }
179
180   // 2. Active color
181   fen >> token;
182   sideToMove = (token == 'w' ? WHITE : BLACK);
183   fen >> token;
184
185   // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
186   // Shredder-FEN that uses the letters of the columns on which the rooks began
187   // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
188   // if an inner rook is associated with the castling right, the castling tag is
189   // replaced by the file letter of the involved rook, as for the Shredder-FEN.
190   while ((fen >> token) && !isspace(token))
191   {
192       Square rsq;
193       Color c = islower(token) ? BLACK : WHITE;
194
195       token = char(toupper(token));
196
197       if (token == 'K')
198           for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; rsq--) {}
199
200       else if (token == 'Q')
201           for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; rsq++) {}
202
203       else if (token >= 'A' && token <= 'H')
204           rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
205
206       else
207           continue;
208
209       set_castle_right(c, rsq);
210   }
211
212   // 4. En passant square. Ignore if no pawn capture is possible
213   if (   ((fen >> col) && (col >= 'a' && col <= 'h'))
214       && ((fen >> row) && (row == '3' || row == '6')))
215   {
216       st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
217
218       if (!(attackers_to(st->epSquare) & pieces(PAWN, sideToMove)))
219           st->epSquare = SQ_NONE;
220   }
221
222   // 5-6. Halfmove clock and fullmove number
223   fen >> std::skipws >> st->rule50 >> startPosPly;
224
225   // Convert from fullmove starting from 1 to ply starting from 0,
226   // handle also common incorrect FEN with fullmove = 0.
227   startPosPly = std::max(2 * (startPosPly - 1), 0) + int(sideToMove == BLACK);
228
229   st->key = compute_key();
230   st->pawnKey = compute_pawn_key();
231   st->materialKey = compute_material_key();
232   st->value = compute_value();
233   st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
234   st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
235   st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
236   chess960 = isChess960;
237
238   assert(pos_is_ok());
239 }
240
241
242 /// Position::set_castle_right() is an helper function used to set castling
243 /// rights given the corresponding color and the rook starting square.
244
245 void Position::set_castle_right(Color c, Square rsq) {
246
247   int f = (rsq < king_square(c) ? WHITE_OOO : WHITE_OO) << c;
248
249   st->castleRights |= f;
250   castleRightsMask[king_square(c)] |= f;
251   castleRightsMask[rsq] |= f;
252   castleRookSquare[f] = rsq;
253 }
254
255
256 /// Position::to_fen() returns a FEN representation of the position. In case
257 /// of Chess960 the Shredder-FEN notation is used. Mainly a debugging function.
258
259 const string Position::to_fen() const {
260
261   std::ostringstream fen;
262   Square sq;
263   int emptyCnt;
264
265   for (Rank rank = RANK_8; rank >= RANK_1; rank--)
266   {
267       emptyCnt = 0;
268
269       for (File file = FILE_A; file <= FILE_H; file++)
270       {
271           sq = make_square(file, rank);
272
273           if (square_is_empty(sq))
274               emptyCnt++;
275           else
276           {
277               if (emptyCnt > 0)
278               {
279                   fen << emptyCnt;
280                   emptyCnt = 0;
281               }
282               fen << PieceToChar[piece_on(sq)];
283           }
284       }
285
286       if (emptyCnt > 0)
287           fen << emptyCnt;
288
289       if (rank > RANK_1)
290           fen << '/';
291   }
292
293   fen << (sideToMove == WHITE ? " w " : " b ");
294
295   if (can_castle(WHITE_OO))
296       fen << (chess960 ? char(toupper(file_to_char(file_of(castle_rook_square(WHITE_OO))))) : 'K');
297
298   if (can_castle(WHITE_OOO))
299       fen << (chess960 ? char(toupper(file_to_char(file_of(castle_rook_square(WHITE_OOO))))) : 'Q');
300
301   if (can_castle(BLACK_OO))
302       fen << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK_OO))) : 'k');
303
304   if (can_castle(BLACK_OOO))
305       fen << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK_OOO))) : 'q');
306
307   if (st->castleRights == CASTLES_NONE)
308       fen << '-';
309
310   fen << (ep_square() == SQ_NONE ? " - " : " " + square_to_string(ep_square()) + " ")
311       << st->rule50 << " " << 1 + (startPosPly - int(sideToMove == BLACK)) / 2;
312
313   return fen.str();
314 }
315
316
317 /// Position::print() prints an ASCII representation of the position to
318 /// the standard output. If a move is given then also the san is printed.
319
320 void Position::print(Move move) const {
321
322   const char* dottedLine = "\n+---+---+---+---+---+---+---+---+\n";
323
324   if (move)
325   {
326       Position p(*this, thread());
327       cout << "\nMove is: " << (sideToMove == BLACK ? ".." : "") << move_to_san(p, move);
328   }
329
330   for (Rank rank = RANK_8; rank >= RANK_1; rank--)
331   {
332       cout << dottedLine << '|';
333       for (File file = FILE_A; file <= FILE_H; file++)
334       {
335           Square sq = make_square(file, rank);
336           Piece piece = piece_on(sq);
337           char c = (color_of(piece) == BLACK ? '=' : ' ');
338
339           if (piece == NO_PIECE && !opposite_colors(sq, SQ_A1))
340               piece++; // Index the dot
341
342           cout << c << PieceToChar[piece] << c << '|';
343       }
344   }
345   cout << dottedLine << "Fen is: " << to_fen() << "\nKey is: " << st->key << endl;
346 }
347
348
349 /// Position:hidden_checkers<>() returns a bitboard of all pinned (against the
350 /// king) pieces for the given color. Or, when template parameter FindPinned is
351 /// false, the function return the pieces of the given color candidate for a
352 /// discovery check against the enemy king.
353 template<bool FindPinned>
354 Bitboard Position::hidden_checkers() const {
355
356   // Pinned pieces protect our king, dicovery checks attack the enemy king
357   Bitboard b, result = 0;
358   Bitboard pinners = pieces(FindPinned ? ~sideToMove : sideToMove);
359   Square ksq = king_square(FindPinned ? sideToMove : ~sideToMove);
360
361   // Pinners are sliders, that give check when candidate pinned is removed
362   pinners &=  (pieces(ROOK, QUEEN) & PseudoAttacks[ROOK][ksq])
363             | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq]);
364
365   while (pinners)
366   {
367       b = squares_between(ksq, pop_1st_bit(&pinners)) & occupied_squares();
368
369       // Only one bit set and is an our piece?
370       if (b && !(b & (b - 1)) && (b & pieces(sideToMove)))
371           result |= b;
372   }
373   return result;
374 }
375
376 // Explicit template instantiations
377 template Bitboard Position::hidden_checkers<true>() const;
378 template Bitboard Position::hidden_checkers<false>() const;
379
380
381 /// Position::attackers_to() computes a bitboard of all pieces which attack a
382 /// given square. Slider attacks use occ bitboard as occupancy.
383
384 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
385
386   return  (attacks_from<PAWN>(s, BLACK) & pieces(PAWN, WHITE))
387         | (attacks_from<PAWN>(s, WHITE) & pieces(PAWN, BLACK))
388         | (attacks_from<KNIGHT>(s)      & pieces(KNIGHT))
389         | (attacks_bb<ROOK>(s, occ)     & pieces(ROOK, QUEEN))
390         | (attacks_bb<BISHOP>(s, occ)   & pieces(BISHOP, QUEEN))
391         | (attacks_from<KING>(s)        & pieces(KING));
392 }
393
394
395 /// Position::attacks_from() computes a bitboard of all attacks of a given piece
396 /// put in a given square. Slider attacks use occ bitboard as occupancy.
397
398 Bitboard Position::attacks_from(Piece p, Square s, Bitboard occ) {
399
400   assert(square_is_ok(s));
401
402   switch (type_of(p))
403   {
404   case BISHOP: return attacks_bb<BISHOP>(s, occ);
405   case ROOK  : return attacks_bb<ROOK>(s, occ);
406   case QUEEN : return attacks_bb<BISHOP>(s, occ) | attacks_bb<ROOK>(s, occ);
407   default    : return StepAttacksBB[p][s];
408   }
409 }
410
411
412 /// Position::move_attacks_square() tests whether a move from the current
413 /// position attacks a given square.
414
415 bool Position::move_attacks_square(Move m, Square s) const {
416
417   assert(is_ok(m));
418   assert(square_is_ok(s));
419
420   Bitboard occ, xray;
421   Square from = from_sq(m);
422   Square to = to_sq(m);
423   Piece piece = piece_moved(m);
424
425   assert(!square_is_empty(from));
426
427   // Update occupancy as if the piece is moving
428   occ = occupied_squares() ^ from ^ to;
429
430   // The piece moved in 'to' attacks the square 's' ?
431   if (attacks_from(piece, to, occ) & s)
432       return true;
433
434   // Scan for possible X-ray attackers behind the moved piece
435   xray = (attacks_bb<ROOK>(s, occ)   & pieces(ROOK, QUEEN, color_of(piece)))
436         |(attacks_bb<BISHOP>(s, occ) & pieces(BISHOP, QUEEN, color_of(piece)));
437
438   // Verify attackers are triggered by our move and not already existing
439   return xray && (xray ^ (xray & attacks_from<QUEEN>(s)));
440 }
441
442
443 /// Position::pl_move_is_legal() tests whether a pseudo-legal move is legal
444
445 bool Position::pl_move_is_legal(Move m, Bitboard pinned) const {
446
447   assert(is_ok(m));
448   assert(pinned == pinned_pieces());
449
450   Color us = sideToMove;
451   Square from = from_sq(m);
452
453   assert(color_of(piece_moved(m)) == us);
454   assert(piece_on(king_square(us)) == make_piece(us, KING));
455
456   // En passant captures are a tricky special case. Because they are rather
457   // uncommon, we do it simply by testing whether the king is attacked after
458   // the move is made.
459   if (is_enpassant(m))
460   {
461       Color them = ~us;
462       Square to = to_sq(m);
463       Square capsq = to + pawn_push(them);
464       Square ksq = king_square(us);
465       Bitboard b = (occupied_squares() ^ from ^ capsq) | to;
466
467       assert(to == ep_square());
468       assert(piece_moved(m) == make_piece(us, PAWN));
469       assert(piece_on(capsq) == make_piece(them, PAWN));
470       assert(piece_on(to) == NO_PIECE);
471
472       return   !(attacks_bb<ROOK>(ksq, b) & pieces(ROOK, QUEEN, them))
473             && !(attacks_bb<BISHOP>(ksq, b) & pieces(BISHOP, QUEEN, them));
474   }
475
476   // If the moving piece is a king, check whether the destination
477   // square is attacked by the opponent. Castling moves are checked
478   // for legality during move generation.
479   if (type_of(piece_on(from)) == KING)
480       return is_castle(m) || !(attackers_to(to_sq(m)) & pieces(~us));
481
482   // A non-king move is legal if and only if it is not pinned or it
483   // is moving along the ray towards or away from the king.
484   return   !pinned
485         || !(pinned & from)
486         ||  squares_aligned(from, to_sq(m), king_square(us));
487 }
488
489
490 /// Position::move_is_legal() takes a random move and tests whether the move
491 /// is legal. This version is not very fast and should be used only in non
492 /// time-critical paths.
493
494 bool Position::move_is_legal(const Move m) const {
495
496   for (MoveList<MV_LEGAL> ml(*this); !ml.end(); ++ml)
497       if (ml.move() == m)
498           return true;
499
500   return false;
501 }
502
503
504 /// Position::is_pseudo_legal() takes a random move and tests whether the move
505 /// is pseudo legal. It is used to validate moves from TT that can be corrupted
506 /// due to SMP concurrent access or hash position key aliasing.
507
508 bool Position::is_pseudo_legal(const Move m) const {
509
510   Color us = sideToMove;
511   Color them = ~sideToMove;
512   Square from = from_sq(m);
513   Square to = to_sq(m);
514   Piece pc = piece_moved(m);
515
516   // Use a slower but simpler function for uncommon cases
517   if (is_special(m))
518       return move_is_legal(m);
519
520   // Is not a promotion, so promotion piece must be empty
521   if (promotion_piece_type(m) - 2 != NO_PIECE_TYPE)
522       return false;
523
524   // If the from square is not occupied by a piece belonging to the side to
525   // move, the move is obviously not legal.
526   if (pc == NO_PIECE || color_of(pc) != us)
527       return false;
528
529   // The destination square cannot be occupied by a friendly piece
530   if (color_of(piece_on(to)) == us)
531       return false;
532
533   // Handle the special case of a pawn move
534   if (type_of(pc) == PAWN)
535   {
536       // Move direction must be compatible with pawn color
537       int direction = to - from;
538       if ((us == WHITE) != (direction > 0))
539           return false;
540
541       // We have already handled promotion moves, so destination
542       // cannot be on the 8/1th rank.
543       if (rank_of(to) == RANK_8 || rank_of(to) == RANK_1)
544           return false;
545
546       // Proceed according to the square delta between the origin and
547       // destination squares.
548       switch (direction)
549       {
550       case DELTA_NW:
551       case DELTA_NE:
552       case DELTA_SW:
553       case DELTA_SE:
554       // Capture. The destination square must be occupied by an enemy
555       // piece (en passant captures was handled earlier).
556       if (color_of(piece_on(to)) != them)
557           return false;
558
559       // From and to files must be one file apart, avoids a7h5
560       if (abs(file_of(from) - file_of(to)) != 1)
561           return false;
562       break;
563
564       case DELTA_N:
565       case DELTA_S:
566       // Pawn push. The destination square must be empty.
567       if (!square_is_empty(to))
568           return false;
569       break;
570
571       case DELTA_NN:
572       // Double white pawn push. The destination square must be on the fourth
573       // rank, and both the destination square and the square between the
574       // source and destination squares must be empty.
575       if (   rank_of(to) != RANK_4
576           || !square_is_empty(to)
577           || !square_is_empty(from + DELTA_N))
578           return false;
579       break;
580
581       case DELTA_SS:
582       // Double black pawn push. The destination square must be on the fifth
583       // rank, and both the destination square and the square between the
584       // source and destination squares must be empty.
585       if (   rank_of(to) != RANK_5
586           || !square_is_empty(to)
587           || !square_is_empty(from + DELTA_S))
588           return false;
589       break;
590
591       default:
592           return false;
593       }
594   }
595   else if (!(attacks_from(pc, from) & to))
596       return false;
597
598   // Evasions generator already takes care to avoid some kind of illegal moves
599   // and pl_move_is_legal() relies on this. So we have to take care that the
600   // same kind of moves are filtered out here.
601   if (in_check())
602   {
603       if (type_of(pc) != KING)
604       {
605           Bitboard b = checkers();
606           Square checksq = pop_1st_bit(&b);
607
608           if (b) // double check ? In this case a king move is required
609               return false;
610
611           // Our move must be a blocking evasion or a capture of the checking piece
612           if (!((squares_between(checksq, king_square(us)) | checkers()) & to))
613               return false;
614       }
615       // In case of king moves under check we have to remove king so to catch
616       // as invalid moves like b1a1 when opposite queen is on c1.
617       else if (attackers_to(to, occupied_squares() ^ from) & pieces(~us))
618           return false;
619   }
620
621   return true;
622 }
623
624
625 /// Position::move_gives_check() tests whether a pseudo-legal move gives a check
626
627 bool Position::move_gives_check(Move m, const CheckInfo& ci) const {
628
629   assert(is_ok(m));
630   assert(ci.dcCandidates == discovered_check_candidates());
631   assert(color_of(piece_moved(m)) == sideToMove);
632
633   Square from = from_sq(m);
634   Square to = to_sq(m);
635   PieceType pt = type_of(piece_on(from));
636
637   // Direct check ?
638   if (ci.checkSq[pt] & to)
639       return true;
640
641   // Discovery check ?
642   if (ci.dcCandidates && (ci.dcCandidates & from))
643   {
644       // For pawn and king moves we need to verify also direction
645       if (  (pt != PAWN && pt != KING)
646           || !squares_aligned(from, to, king_square(~sideToMove)))
647           return true;
648   }
649
650   // Can we skip the ugly special cases ?
651   if (!is_special(m))
652       return false;
653
654   Color us = sideToMove;
655   Square ksq = king_square(~us);
656
657   // Promotion with check ?
658   if (is_promotion(m))
659       return attacks_from(Piece(promotion_piece_type(m)), to, occupied_squares() ^ from) & ksq;
660
661   // En passant capture with check ? We have already handled the case
662   // of direct checks and ordinary discovered check, the only case we
663   // need to handle is the unusual case of a discovered check through
664   // the captured pawn.
665   if (is_enpassant(m))
666   {
667       Square capsq = make_square(file_of(to), rank_of(from));
668       Bitboard b = (occupied_squares() ^ from ^ capsq) | to;
669
670       return  (attacks_bb<  ROOK>(ksq, b) & pieces(  ROOK, QUEEN, us))
671             | (attacks_bb<BISHOP>(ksq, b) & pieces(BISHOP, QUEEN, us));
672   }
673
674   // Castling with check ?
675   if (is_castle(m))
676   {
677       Square kfrom = from;
678       Square rfrom = to; // 'King captures the rook' notation
679       Square kto = relative_square(us, rfrom > kfrom ? SQ_G1 : SQ_C1);
680       Square rto = relative_square(us, rfrom > kfrom ? SQ_F1 : SQ_D1);
681       Bitboard b = (occupied_squares() ^ kfrom ^ rfrom) | rto | kto;
682
683       return attacks_bb<ROOK>(rto, b) & ksq;
684   }
685
686   return false;
687 }
688
689
690 /// Position::do_move() makes a move, and saves all information necessary
691 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
692 /// moves should be filtered out before this function is called.
693
694 void Position::do_move(Move m, StateInfo& newSt) {
695
696   CheckInfo ci(*this);
697   do_move(m, newSt, ci, move_gives_check(m, ci));
698 }
699
700 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
701
702   assert(is_ok(m));
703   assert(&newSt != st);
704
705   nodes++;
706   Key k = st->key;
707
708   // Copy some fields of old state to our new StateInfo object except the ones
709   // which are recalculated from scratch anyway, then switch our state pointer
710   // to point to the new, ready to be updated, state.
711   struct ReducedStateInfo {
712     Key pawnKey, materialKey;
713     Value npMaterial[2];
714     int castleRights, rule50, pliesFromNull;
715     Score value;
716     Square epSquare;
717   };
718
719   memcpy(&newSt, st, sizeof(ReducedStateInfo));
720
721   newSt.previous = st;
722   st = &newSt;
723
724   // Update side to move
725   k ^= zobSideToMove;
726
727   // Increment the 50 moves rule draw counter. Resetting it to zero in the
728   // case of a capture or a pawn move is taken care of later.
729   st->rule50++;
730   st->pliesFromNull++;
731
732   if (is_castle(m))
733   {
734       st->key = k;
735       do_castle_move<true>(m);
736       return;
737   }
738
739   Color us = sideToMove;
740   Color them = ~us;
741   Square from = from_sq(m);
742   Square to = to_sq(m);
743   Piece piece = piece_on(from);
744   PieceType pt = type_of(piece);
745   PieceType capture = is_enpassant(m) ? PAWN : type_of(piece_on(to));
746
747   assert(color_of(piece) == us);
748   assert(color_of(piece_on(to)) != us);
749   assert(capture != KING);
750
751   if (capture)
752   {
753       Square capsq = to;
754
755       // If the captured piece is a pawn, update pawn hash key, otherwise
756       // update non-pawn material.
757       if (capture == PAWN)
758       {
759           if (is_enpassant(m))
760           {
761               capsq += pawn_push(them);
762
763               assert(pt == PAWN);
764               assert(to == st->epSquare);
765               assert(relative_rank(us, to) == RANK_6);
766               assert(piece_on(to) == NO_PIECE);
767               assert(piece_on(capsq) == make_piece(them, PAWN));
768
769               board[capsq] = NO_PIECE;
770           }
771
772           st->pawnKey ^= zobrist[them][PAWN][capsq];
773       }
774       else
775           st->npMaterial[them] -= PieceValueMidgame[capture];
776
777       // Remove the captured piece
778       byColorBB[them] ^= capsq;
779       byTypeBB[capture] ^= capsq;
780       occupied ^= capsq;
781
782       // Update piece list, move the last piece at index[capsq] position and
783       // shrink the list.
784       //
785       // WARNING: This is a not revresible operation. When we will reinsert the
786       // captured piece in undo_move() we will put it at the end of the list and
787       // not in its original place, it means index[] and pieceList[] are not
788       // guaranteed to be invariant to a do_move() + undo_move() sequence.
789       Square lastSquare = pieceList[them][capture][--pieceCount[them][capture]];
790       index[lastSquare] = index[capsq];
791       pieceList[them][capture][index[lastSquare]] = lastSquare;
792       pieceList[them][capture][pieceCount[them][capture]] = SQ_NONE;
793
794       // Update hash keys
795       k ^= zobrist[them][capture][capsq];
796       st->materialKey ^= zobrist[them][capture][pieceCount[them][capture]];
797
798       // Update incremental scores
799       st->value -= pst(make_piece(them, capture), capsq);
800
801       // Reset rule 50 counter
802       st->rule50 = 0;
803   }
804
805   // Update hash key
806   k ^= zobrist[us][pt][from] ^ zobrist[us][pt][to];
807
808   // Reset en passant square
809   if (st->epSquare != SQ_NONE)
810   {
811       k ^= zobEp[file_of(st->epSquare)];
812       st->epSquare = SQ_NONE;
813   }
814
815   // Update castle rights if needed
816   if (st->castleRights && (castleRightsMask[from] | castleRightsMask[to]))
817   {
818       int cr = castleRightsMask[from] | castleRightsMask[to];
819       k ^= zobCastle[st->castleRights & cr];
820       st->castleRights &= ~cr;
821   }
822
823   // Prefetch TT access as soon as we know key is updated
824   prefetch((char*)TT.first_entry(k));
825
826   // Move the piece
827   Bitboard from_to_bb = SquareBB[from] | SquareBB[to];
828   byColorBB[us] ^= from_to_bb;
829   byTypeBB[pt] ^= from_to_bb;
830   occupied ^= from_to_bb;
831
832   board[to] = board[from];
833   board[from] = NO_PIECE;
834
835   // Update piece lists, index[from] is not updated and becomes stale. This
836   // works as long as index[] is accessed just by known occupied squares.
837   index[to] = index[from];
838   pieceList[us][pt][index[to]] = to;
839
840   // If the moving piece is a pawn do some special extra work
841   if (pt == PAWN)
842   {
843       // Set en-passant square, only if moved pawn can be captured
844       if (   (int(to) ^ int(from)) == 16
845           && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(PAWN, them)))
846       {
847           st->epSquare = Square((from + to) / 2);
848           k ^= zobEp[file_of(st->epSquare)];
849       }
850
851       if (is_promotion(m))
852       {
853           PieceType promotion = promotion_piece_type(m);
854
855           assert(relative_rank(us, to) == RANK_8);
856           assert(promotion >= KNIGHT && promotion <= QUEEN);
857
858           // Replace the pawn with the promoted piece
859           byTypeBB[PAWN] ^= to;
860           byTypeBB[promotion] |= to;
861           board[to] = make_piece(us, promotion);
862
863           // Update piece lists, move the last pawn at index[to] position
864           // and shrink the list. Add a new promotion piece to the list.
865           Square lastSquare = pieceList[us][PAWN][--pieceCount[us][PAWN]];
866           index[lastSquare] = index[to];
867           pieceList[us][PAWN][index[lastSquare]] = lastSquare;
868           pieceList[us][PAWN][pieceCount[us][PAWN]] = SQ_NONE;
869           index[to] = pieceCount[us][promotion];
870           pieceList[us][promotion][index[to]] = to;
871
872           // Update hash keys
873           k ^= zobrist[us][PAWN][to] ^ zobrist[us][promotion][to];
874           st->pawnKey ^= zobrist[us][PAWN][to];
875           st->materialKey ^=  zobrist[us][promotion][pieceCount[us][promotion]++]
876                             ^ zobrist[us][PAWN][pieceCount[us][PAWN]];
877
878           // Update incremental score
879           st->value +=  pst(make_piece(us, promotion), to)
880                       - pst(make_piece(us, PAWN), to);
881
882           // Update material
883           st->npMaterial[us] += PieceValueMidgame[promotion];
884       }
885
886       // Update pawn hash key
887       st->pawnKey ^= zobrist[us][PAWN][from] ^ zobrist[us][PAWN][to];
888
889       // Reset rule 50 draw counter
890       st->rule50 = 0;
891   }
892
893   // Prefetch pawn and material hash tables
894   Threads[threadID].pawnTable.prefetch(st->pawnKey);
895   Threads[threadID].materialTable.prefetch(st->materialKey);
896
897   // Update incremental scores
898   st->value += pst_delta(piece, from, to);
899
900   // Set capture piece
901   st->capturedType = capture;
902
903   // Update the key with the final value
904   st->key = k;
905
906   // Update checkers bitboard, piece must be already moved
907   st->checkersBB = 0;
908
909   if (moveIsCheck)
910   {
911       if (is_special(m))
912           st->checkersBB = attackers_to(king_square(them)) & pieces(us);
913       else
914       {
915           // Direct checks
916           if (ci.checkSq[pt] & to)
917               st->checkersBB |= to;
918
919           // Discovery checks
920           if (ci.dcCandidates && (ci.dcCandidates & from))
921           {
922               if (pt != ROOK)
923                   st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(ROOK, QUEEN, us);
924
925               if (pt != BISHOP)
926                   st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(BISHOP, QUEEN, us);
927           }
928       }
929   }
930
931   // Finish
932   sideToMove = ~sideToMove;
933   st->value += (sideToMove == WHITE ?  TempoValue : -TempoValue);
934
935   assert(pos_is_ok());
936 }
937
938
939 /// Position::undo_move() unmakes a move. When it returns, the position should
940 /// be restored to exactly the same state as before the move was made.
941
942 void Position::undo_move(Move m) {
943
944   assert(is_ok(m));
945
946   sideToMove = ~sideToMove;
947
948   if (is_castle(m))
949   {
950       do_castle_move<false>(m);
951       return;
952   }
953
954   Color us = sideToMove;
955   Color them = ~us;
956   Square from = from_sq(m);
957   Square to = to_sq(m);
958   Piece piece = piece_on(to);
959   PieceType pt = type_of(piece);
960   PieceType capture = st->capturedType;
961
962   assert(square_is_empty(from));
963   assert(color_of(piece) == us);
964   assert(capture != KING);
965
966   if (is_promotion(m))
967   {
968       PieceType promotion = promotion_piece_type(m);
969
970       assert(promotion == pt);
971       assert(relative_rank(us, to) == RANK_8);
972       assert(promotion >= KNIGHT && promotion <= QUEEN);
973
974       // Replace the promoted piece with the pawn
975       byTypeBB[promotion] ^= to;
976       byTypeBB[PAWN] |= to;
977       board[to] = make_piece(us, PAWN);
978
979       // Update piece lists, move the last promoted piece at index[to] position
980       // and shrink the list. Add a new pawn to the list.
981       Square lastSquare = pieceList[us][promotion][--pieceCount[us][promotion]];
982       index[lastSquare] = index[to];
983       pieceList[us][promotion][index[lastSquare]] = lastSquare;
984       pieceList[us][promotion][pieceCount[us][promotion]] = SQ_NONE;
985       index[to] = pieceCount[us][PAWN]++;
986       pieceList[us][PAWN][index[to]] = to;
987
988       pt = PAWN;
989   }
990
991   // Put the piece back at the source square
992   Bitboard from_to_bb = SquareBB[from] | SquareBB[to];
993   byColorBB[us] ^= from_to_bb;
994   byTypeBB[pt] ^= from_to_bb;
995   occupied ^= from_to_bb;
996
997   board[from] = board[to];
998   board[to] = NO_PIECE;
999
1000   // Update piece lists, index[to] is not updated and becomes stale. This
1001   // works as long as index[] is accessed just by known occupied squares.
1002   index[from] = index[to];
1003   pieceList[us][pt][index[from]] = from;
1004
1005   if (capture)
1006   {
1007       Square capsq = to;
1008
1009       if (is_enpassant(m))
1010       {
1011           capsq -= pawn_push(us);
1012
1013           assert(pt == PAWN);
1014           assert(to == st->previous->epSquare);
1015           assert(relative_rank(us, to) == RANK_6);
1016           assert(piece_on(capsq) == NO_PIECE);
1017       }
1018
1019       // Restore the captured piece
1020       byColorBB[them] |= capsq;
1021       byTypeBB[capture] |= capsq;
1022       occupied |= capsq;
1023
1024       board[capsq] = make_piece(them, capture);
1025
1026       // Update piece list, add a new captured piece in capsq square
1027       index[capsq] = pieceCount[them][capture]++;
1028       pieceList[them][capture][index[capsq]] = capsq;
1029   }
1030
1031   // Finally point our state pointer back to the previous state
1032   st = st->previous;
1033
1034   assert(pos_is_ok());
1035 }
1036
1037
1038 /// Position::do_castle_move() is a private method used to do/undo a castling
1039 /// move. Note that castling moves are encoded as "king captures friendly rook"
1040 /// moves, for instance white short castling in a non-Chess960 game is encoded
1041 /// as e1h1.
1042 template<bool Do>
1043 void Position::do_castle_move(Move m) {
1044
1045   assert(is_ok(m));
1046   assert(is_castle(m));
1047
1048   Square kto, kfrom, rfrom, rto, kAfter, rAfter;
1049
1050   Color us = sideToMove;
1051   Square kBefore = from_sq(m);
1052   Square rBefore = to_sq(m);
1053
1054   // Find after-castle squares for king and rook
1055   if (rBefore > kBefore) // O-O
1056   {
1057       kAfter = relative_square(us, SQ_G1);
1058       rAfter = relative_square(us, SQ_F1);
1059   }
1060   else // O-O-O
1061   {
1062       kAfter = relative_square(us, SQ_C1);
1063       rAfter = relative_square(us, SQ_D1);
1064   }
1065
1066   kfrom = Do ? kBefore : kAfter;
1067   rfrom = Do ? rBefore : rAfter;
1068
1069   kto = Do ? kAfter : kBefore;
1070   rto = Do ? rAfter : rBefore;
1071
1072   assert(piece_on(kfrom) == make_piece(us, KING));
1073   assert(piece_on(rfrom) == make_piece(us, ROOK));
1074
1075   // Remove pieces from source squares
1076   byColorBB[us] ^= kfrom;
1077   byTypeBB[KING] ^= kfrom;
1078   occupied ^= kfrom;
1079   byColorBB[us] ^= rfrom;
1080   byTypeBB[ROOK] ^= rfrom;
1081   occupied ^= rfrom;
1082
1083   // Put pieces on destination squares
1084   byColorBB[us] |= kto;
1085   byTypeBB[KING] |= kto;
1086   occupied |= kto;
1087   byColorBB[us] |= rto;
1088   byTypeBB[ROOK] |= rto;
1089   occupied |= rto;
1090
1091   // Update board
1092   Piece king = make_piece(us, KING);
1093   Piece rook = make_piece(us, ROOK);
1094   board[kfrom] = board[rfrom] = NO_PIECE;
1095   board[kto] = king;
1096   board[rto] = rook;
1097
1098   // Update piece lists
1099   pieceList[us][KING][index[kfrom]] = kto;
1100   pieceList[us][ROOK][index[rfrom]] = rto;
1101   int tmp = index[rfrom]; // In Chess960 could be kto == rfrom
1102   index[kto] = index[kfrom];
1103   index[rto] = tmp;
1104
1105   if (Do)
1106   {
1107       // Reset capture field
1108       st->capturedType = NO_PIECE_TYPE;
1109
1110       // Update incremental scores
1111       st->value += pst_delta(king, kfrom, kto);
1112       st->value += pst_delta(rook, rfrom, rto);
1113
1114       // Update hash key
1115       st->key ^= zobrist[us][KING][kfrom] ^ zobrist[us][KING][kto];
1116       st->key ^= zobrist[us][ROOK][rfrom] ^ zobrist[us][ROOK][rto];
1117
1118       // Clear en passant square
1119       if (st->epSquare != SQ_NONE)
1120       {
1121           st->key ^= zobEp[file_of(st->epSquare)];
1122           st->epSquare = SQ_NONE;
1123       }
1124
1125       // Update castling rights
1126       st->key ^= zobCastle[st->castleRights & castleRightsMask[kfrom]];
1127       st->castleRights &= ~castleRightsMask[kfrom];
1128
1129       // Update checkers BB
1130       st->checkersBB = attackers_to(king_square(~us)) & pieces(us);
1131
1132       // Finish
1133       sideToMove = ~sideToMove;
1134       st->value += (sideToMove == WHITE ?  TempoValue : -TempoValue);
1135   }
1136   else
1137       // Undo: point our state pointer back to the previous state
1138       st = st->previous;
1139
1140   assert(pos_is_ok());
1141 }
1142
1143
1144 /// Position::do_null_move() is used to do/undo a "null move": It flips the side
1145 /// to move and updates the hash key without executing any move on the board.
1146 template<bool Do>
1147 void Position::do_null_move(StateInfo& backupSt) {
1148
1149   assert(!in_check());
1150
1151   // Back up the information necessary to undo the null move to the supplied
1152   // StateInfo object. Note that differently from normal case here backupSt
1153   // is actually used as a backup storage not as the new state. This reduces
1154   // the number of fields to be copied.
1155   StateInfo* src = Do ? st : &backupSt;
1156   StateInfo* dst = Do ? &backupSt : st;
1157
1158   dst->key      = src->key;
1159   dst->epSquare = src->epSquare;
1160   dst->value    = src->value;
1161   dst->rule50   = src->rule50;
1162   dst->pliesFromNull = src->pliesFromNull;
1163
1164   sideToMove = ~sideToMove;
1165
1166   if (Do)
1167   {
1168       if (st->epSquare != SQ_NONE)
1169           st->key ^= zobEp[file_of(st->epSquare)];
1170
1171       st->key ^= zobSideToMove;
1172       prefetch((char*)TT.first_entry(st->key));
1173
1174       st->epSquare = SQ_NONE;
1175       st->rule50++;
1176       st->pliesFromNull = 0;
1177       st->value += (sideToMove == WHITE) ?  TempoValue : -TempoValue;
1178   }
1179
1180   assert(pos_is_ok());
1181 }
1182
1183 // Explicit template instantiations
1184 template void Position::do_null_move<false>(StateInfo& backupSt);
1185 template void Position::do_null_move<true>(StateInfo& backupSt);
1186
1187
1188 /// Position::see() is a static exchange evaluator: It tries to estimate the
1189 /// material gain or loss resulting from a move. There are three versions of
1190 /// this function: One which takes a destination square as input, one takes a
1191 /// move, and one which takes a 'from' and a 'to' square. The function does
1192 /// not yet understand promotions captures.
1193
1194 int Position::see_sign(Move m) const {
1195
1196   assert(is_ok(m));
1197
1198   // Early return if SEE cannot be negative because captured piece value
1199   // is not less then capturing one. Note that king moves always return
1200   // here because king midgame value is set to 0.
1201   if (PieceValueMidgame[piece_on(to_sq(m))] >= PieceValueMidgame[piece_moved(m)])
1202       return 1;
1203
1204   return see(m);
1205 }
1206
1207 int Position::see(Move m) const {
1208
1209   Square from, to;
1210   Bitboard occ, attackers, stmAttackers, b;
1211   int swapList[32], slIndex = 1;
1212   PieceType capturedType, pt;
1213   Color stm;
1214
1215   assert(is_ok(m));
1216
1217   // As castle moves are implemented as capturing the rook, they have
1218   // SEE == RookValueMidgame most of the times (unless the rook is under
1219   // attack).
1220   if (is_castle(m))
1221       return 0;
1222
1223   from = from_sq(m);
1224   to = to_sq(m);
1225   capturedType = type_of(piece_on(to));
1226   occ = occupied_squares();
1227
1228   // Handle en passant moves
1229   if (is_enpassant(m))
1230   {
1231       Square capQq = to - pawn_push(sideToMove);
1232
1233       assert(!capturedType);
1234       assert(type_of(piece_on(capQq)) == PAWN);
1235
1236       // Remove the captured pawn
1237       occ ^= capQq;
1238       capturedType = PAWN;
1239   }
1240
1241   // Find all attackers to the destination square, with the moving piece
1242   // removed, but possibly an X-ray attacker added behind it.
1243   occ ^= from;
1244   attackers = attackers_to(to, occ);
1245
1246   // If the opponent has no attackers we are finished
1247   stm = ~color_of(piece_on(from));
1248   stmAttackers = attackers & pieces(stm);
1249   if (!stmAttackers)
1250       return PieceValueMidgame[capturedType];
1251
1252   // The destination square is defended, which makes things rather more
1253   // difficult to compute. We proceed by building up a "swap list" containing
1254   // the material gain or loss at each stop in a sequence of captures to the
1255   // destination square, where the sides alternately capture, and always
1256   // capture with the least valuable piece. After each capture, we look for
1257   // new X-ray attacks from behind the capturing piece.
1258   swapList[0] = PieceValueMidgame[capturedType];
1259   capturedType = type_of(piece_on(from));
1260
1261   do {
1262       // Locate the least valuable attacker for the side to move. The loop
1263       // below looks like it is potentially infinite, but it isn't. We know
1264       // that the side to move still has at least one attacker left.
1265       for (pt = PAWN; !(stmAttackers & pieces(pt)); pt++)
1266           assert(pt < KING);
1267
1268       // Remove the attacker we just found from the 'occupied' bitboard,
1269       // and scan for new X-ray attacks behind the attacker.
1270       b = stmAttackers & pieces(pt);
1271       occ ^= (b & (~b + 1));
1272       attackers |=  (attacks_bb<ROOK>(to, occ)   & pieces(ROOK, QUEEN))
1273                   | (attacks_bb<BISHOP>(to, occ) & pieces(BISHOP, QUEEN));
1274
1275       attackers &= occ; // Cut out pieces we've already done
1276
1277       // Add the new entry to the swap list
1278       assert(slIndex < 32);
1279       swapList[slIndex] = -swapList[slIndex - 1] + PieceValueMidgame[capturedType];
1280       slIndex++;
1281
1282       // Remember the value of the capturing piece, and change the side to
1283       // move before beginning the next iteration.
1284       capturedType = pt;
1285       stm = ~stm;
1286       stmAttackers = attackers & pieces(stm);
1287
1288       // Stop before processing a king capture
1289       if (capturedType == KING && stmAttackers)
1290       {
1291           assert(slIndex < 32);
1292           swapList[slIndex++] = QueenValueMidgame*10;
1293           break;
1294       }
1295   } while (stmAttackers);
1296
1297   // Having built the swap list, we negamax through it to find the best
1298   // achievable score from the point of view of the side to move.
1299   while (--slIndex)
1300       swapList[slIndex-1] = std::min(-swapList[slIndex], swapList[slIndex-1]);
1301
1302   return swapList[0];
1303 }
1304
1305
1306 /// Position::clear() erases the position object to a pristine state, with an
1307 /// empty board, white to move, and no castling rights.
1308
1309 void Position::clear() {
1310
1311   memset(this, 0, sizeof(Position));
1312   startState.epSquare = SQ_NONE;
1313   st = &startState;
1314
1315   for (int i = 0; i < 8; i++)
1316       for (int j = 0; j < 16; j++)
1317           pieceList[0][i][j] = pieceList[1][i][j] = SQ_NONE;
1318
1319   for (Square sq = SQ_A1; sq <= SQ_H8; sq++)
1320       board[sq] = NO_PIECE;
1321 }
1322
1323
1324 /// Position::put_piece() puts a piece on the given square of the board,
1325 /// updating the board array, pieces list, bitboards, and piece counts.
1326
1327 void Position::put_piece(Piece p, Square s) {
1328
1329   Color c = color_of(p);
1330   PieceType pt = type_of(p);
1331
1332   board[s] = p;
1333   index[s] = pieceCount[c][pt]++;
1334   pieceList[c][pt][index[s]] = s;
1335
1336   byTypeBB[pt] |= s;
1337   byColorBB[c] |= s;
1338   occupied |= s;
1339 }
1340
1341
1342 /// Position::compute_key() computes the hash key of the position. The hash
1343 /// key is usually updated incrementally as moves are made and unmade, the
1344 /// compute_key() function is only used when a new position is set up, and
1345 /// to verify the correctness of the hash key when running in debug mode.
1346
1347 Key Position::compute_key() const {
1348
1349   Key result = zobCastle[st->castleRights];
1350
1351   for (Square s = SQ_A1; s <= SQ_H8; s++)
1352       if (!square_is_empty(s))
1353           result ^= zobrist[color_of(piece_on(s))][type_of(piece_on(s))][s];
1354
1355   if (ep_square() != SQ_NONE)
1356       result ^= zobEp[file_of(ep_square())];
1357
1358   if (sideToMove == BLACK)
1359       result ^= zobSideToMove;
1360
1361   return result;
1362 }
1363
1364
1365 /// Position::compute_pawn_key() computes the hash key of the position. The
1366 /// hash key is usually updated incrementally as moves are made and unmade,
1367 /// the compute_pawn_key() function is only used when a new position is set
1368 /// up, and to verify the correctness of the pawn hash key when running in
1369 /// debug mode.
1370
1371 Key Position::compute_pawn_key() const {
1372
1373   Bitboard b;
1374   Key result = 0;
1375
1376   for (Color c = WHITE; c <= BLACK; c++)
1377   {
1378       b = pieces(PAWN, c);
1379       while (b)
1380           result ^= zobrist[c][PAWN][pop_1st_bit(&b)];
1381   }
1382   return result;
1383 }
1384
1385
1386 /// Position::compute_material_key() computes the hash key of the position.
1387 /// The hash key is usually updated incrementally as moves are made and unmade,
1388 /// the compute_material_key() function is only used when a new position is set
1389 /// up, and to verify the correctness of the material hash key when running in
1390 /// debug mode.
1391
1392 Key Position::compute_material_key() const {
1393
1394   Key result = 0;
1395
1396   for (Color c = WHITE; c <= BLACK; c++)
1397       for (PieceType pt = PAWN; pt <= QUEEN; pt++)
1398           for (int i = 0; i < piece_count(c, pt); i++)
1399               result ^= zobrist[c][pt][i];
1400
1401   return result;
1402 }
1403
1404
1405 /// Position::compute_value() compute the incremental scores for the middle
1406 /// game and the endgame. These functions are used to initialize the incremental
1407 /// scores when a new position is set up, and to verify that the scores are correctly
1408 /// updated by do_move and undo_move when the program is running in debug mode.
1409 Score Position::compute_value() const {
1410
1411   Bitboard b;
1412   Score result = SCORE_ZERO;
1413
1414   for (Color c = WHITE; c <= BLACK; c++)
1415       for (PieceType pt = PAWN; pt <= KING; pt++)
1416       {
1417           b = pieces(pt, c);
1418           while (b)
1419               result += pst(make_piece(c, pt), pop_1st_bit(&b));
1420       }
1421
1422   result += (sideToMove == WHITE ? TempoValue / 2 : -TempoValue / 2);
1423   return result;
1424 }
1425
1426
1427 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1428 /// game material value for the given side. Material values are updated
1429 /// incrementally during the search, this function is only used while
1430 /// initializing a new Position object.
1431
1432 Value Position::compute_non_pawn_material(Color c) const {
1433
1434   Value result = VALUE_ZERO;
1435
1436   for (PieceType pt = KNIGHT; pt <= QUEEN; pt++)
1437       result += piece_count(c, pt) * PieceValueMidgame[pt];
1438
1439   return result;
1440 }
1441
1442
1443 /// Position::is_draw() tests whether the position is drawn by material,
1444 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1445 /// must be done by the search.
1446 template<bool SkipRepetition>
1447 bool Position::is_draw() const {
1448
1449   // Draw by material?
1450   if (   !pieces(PAWN)
1451       && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMidgame))
1452       return true;
1453
1454   // Draw by the 50 moves rule?
1455   if (st->rule50 > 99 && (!in_check() || MoveList<MV_LEGAL>(*this).size()))
1456       return true;
1457
1458   // Draw by repetition?
1459   if (!SkipRepetition)
1460   {
1461       int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1462
1463       if (i <= e)
1464       {
1465           StateInfo* stp = st->previous->previous;
1466
1467           do {
1468               stp = stp->previous->previous;
1469
1470               if (stp->key == st->key)
1471                   return true;
1472
1473               i +=2;
1474
1475           } while (i <= e);
1476       }
1477   }
1478
1479   return false;
1480 }
1481
1482 // Explicit template instantiations
1483 template bool Position::is_draw<false>() const;
1484 template bool Position::is_draw<true>() const;
1485
1486
1487 /// Position::init() is a static member function which initializes at startup
1488 /// the various arrays used to compute hash keys and the piece square tables.
1489 /// The latter is a two-step operation: First, the white halves of the tables
1490 /// are copied from PSQT[] tables. Second, the black halves of the tables are
1491 /// initialized by flipping and changing the sign of the white scores.
1492
1493 void Position::init() {
1494
1495   RKISS rk;
1496
1497   for (Color c = WHITE; c <= BLACK; c++)
1498       for (PieceType pt = PAWN; pt <= KING; pt++)
1499           for (Square s = SQ_A1; s <= SQ_H8; s++)
1500               zobrist[c][pt][s] = rk.rand<Key>();
1501
1502   for (File f = FILE_A; f <= FILE_H; f++)
1503       zobEp[f] = rk.rand<Key>();
1504
1505   for (int cr = CASTLES_NONE; cr <= ALL_CASTLES; cr++)
1506   {
1507       Bitboard b = cr;
1508       while (b)
1509       {
1510           Key k = zobCastle[1 << pop_1st_bit(&b)];
1511           zobCastle[cr] ^= k ? k : rk.rand<Key>();
1512       }
1513   }
1514
1515   zobSideToMove = rk.rand<Key>();
1516   zobExclusion  = rk.rand<Key>();
1517
1518   for (Piece p = W_PAWN; p <= W_KING; p++)
1519   {
1520       Score ps = make_score(PieceValueMidgame[p], PieceValueEndgame[p]);
1521
1522       for (Square s = SQ_A1; s <= SQ_H8; s++)
1523       {
1524           pieceSquareTable[p][s] = ps + PSQT[p][s];
1525           pieceSquareTable[p+8][~s] = -pieceSquareTable[p][s];
1526       }
1527   }
1528 }
1529
1530
1531 /// Position::flip_me() flips position with the white and black sides reversed. This
1532 /// is only useful for debugging especially for finding evaluation symmetry bugs.
1533
1534 void Position::flip_me() {
1535
1536   // Make a copy of current position before to start changing
1537   const Position pos(*this, threadID);
1538
1539   clear();
1540   threadID = pos.thread();
1541
1542   // Board
1543   for (Square s = SQ_A1; s <= SQ_H8; s++)
1544       if (!pos.square_is_empty(s))
1545           put_piece(Piece(pos.piece_on(s) ^ 8), ~s);
1546
1547   // Side to move
1548   sideToMove = ~pos.side_to_move();
1549
1550   // Castling rights
1551   if (pos.can_castle(WHITE_OO))
1552       set_castle_right(BLACK, ~pos.castle_rook_square(WHITE_OO));
1553   if (pos.can_castle(WHITE_OOO))
1554       set_castle_right(BLACK, ~pos.castle_rook_square(WHITE_OOO));
1555   if (pos.can_castle(BLACK_OO))
1556       set_castle_right(WHITE, ~pos.castle_rook_square(BLACK_OO));
1557   if (pos.can_castle(BLACK_OOO))
1558       set_castle_right(WHITE, ~pos.castle_rook_square(BLACK_OOO));
1559
1560   // En passant square
1561   if (pos.st->epSquare != SQ_NONE)
1562       st->epSquare = ~pos.st->epSquare;
1563
1564   // Checkers
1565   st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
1566
1567   // Hash keys
1568   st->key = compute_key();
1569   st->pawnKey = compute_pawn_key();
1570   st->materialKey = compute_material_key();
1571
1572   // Incremental scores
1573   st->value = compute_value();
1574
1575   // Material
1576   st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
1577   st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
1578
1579   assert(pos_is_ok());
1580 }
1581
1582
1583 /// Position::pos_is_ok() performs some consitency checks for the position object.
1584 /// This is meant to be helpful when debugging.
1585
1586 bool Position::pos_is_ok(int* failedStep) const {
1587
1588   // What features of the position should be verified?
1589   const bool debugAll = false;
1590
1591   const bool debugBitboards       = debugAll || false;
1592   const bool debugKingCount       = debugAll || false;
1593   const bool debugKingCapture     = debugAll || false;
1594   const bool debugCheckerCount    = debugAll || false;
1595   const bool debugKey             = debugAll || false;
1596   const bool debugMaterialKey     = debugAll || false;
1597   const bool debugPawnKey         = debugAll || false;
1598   const bool debugIncrementalEval = debugAll || false;
1599   const bool debugNonPawnMaterial = debugAll || false;
1600   const bool debugPieceCounts     = debugAll || false;
1601   const bool debugPieceList       = debugAll || false;
1602   const bool debugCastleSquares   = debugAll || false;
1603
1604   if (failedStep) *failedStep = 1;
1605
1606   // Side to move OK?
1607   if (sideToMove != WHITE && sideToMove != BLACK)
1608       return false;
1609
1610   // Are the king squares in the position correct?
1611   if (failedStep) (*failedStep)++;
1612   if (piece_on(king_square(WHITE)) != W_KING)
1613       return false;
1614
1615   if (failedStep) (*failedStep)++;
1616   if (piece_on(king_square(BLACK)) != B_KING)
1617       return false;
1618
1619   // Do both sides have exactly one king?
1620   if (failedStep) (*failedStep)++;
1621   if (debugKingCount)
1622   {
1623       int kingCount[2] = {0, 0};
1624       for (Square s = SQ_A1; s <= SQ_H8; s++)
1625           if (type_of(piece_on(s)) == KING)
1626               kingCount[color_of(piece_on(s))]++;
1627
1628       if (kingCount[0] != 1 || kingCount[1] != 1)
1629           return false;
1630   }
1631
1632   // Can the side to move capture the opponent's king?
1633   if (failedStep) (*failedStep)++;
1634   if (debugKingCapture)
1635   {
1636       Color us = sideToMove;
1637       Color them = ~us;
1638       Square ksq = king_square(them);
1639       if (attackers_to(ksq) & pieces(us))
1640           return false;
1641   }
1642
1643   // Is there more than 2 checkers?
1644   if (failedStep) (*failedStep)++;
1645   if (debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1646       return false;
1647
1648   // Bitboards OK?
1649   if (failedStep) (*failedStep)++;
1650   if (debugBitboards)
1651   {
1652       // The intersection of the white and black pieces must be empty
1653       if (pieces(WHITE) & pieces(BLACK))
1654           return false;
1655
1656       // The union of the white and black pieces must be equal to all
1657       // occupied squares
1658       if ((pieces(WHITE) | pieces(BLACK)) != occupied_squares())
1659           return false;
1660
1661       // Separate piece type bitboards must have empty intersections
1662       for (PieceType p1 = PAWN; p1 <= KING; p1++)
1663           for (PieceType p2 = PAWN; p2 <= KING; p2++)
1664               if (p1 != p2 && (pieces(p1) & pieces(p2)))
1665                   return false;
1666   }
1667
1668   // En passant square OK?
1669   if (failedStep) (*failedStep)++;
1670   if (ep_square() != SQ_NONE)
1671   {
1672       // The en passant square must be on rank 6, from the point of view of the
1673       // side to move.
1674       if (relative_rank(sideToMove, ep_square()) != RANK_6)
1675           return false;
1676   }
1677
1678   // Hash key OK?
1679   if (failedStep) (*failedStep)++;
1680   if (debugKey && st->key != compute_key())
1681       return false;
1682
1683   // Pawn hash key OK?
1684   if (failedStep) (*failedStep)++;
1685   if (debugPawnKey && st->pawnKey != compute_pawn_key())
1686       return false;
1687
1688   // Material hash key OK?
1689   if (failedStep) (*failedStep)++;
1690   if (debugMaterialKey && st->materialKey != compute_material_key())
1691       return false;
1692
1693   // Incremental eval OK?
1694   if (failedStep) (*failedStep)++;
1695   if (debugIncrementalEval && st->value != compute_value())
1696       return false;
1697
1698   // Non-pawn material OK?
1699   if (failedStep) (*failedStep)++;
1700   if (debugNonPawnMaterial)
1701   {
1702       if (st->npMaterial[WHITE] != compute_non_pawn_material(WHITE))
1703           return false;
1704
1705       if (st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1706           return false;
1707   }
1708
1709   // Piece counts OK?
1710   if (failedStep) (*failedStep)++;
1711   if (debugPieceCounts)
1712       for (Color c = WHITE; c <= BLACK; c++)
1713           for (PieceType pt = PAWN; pt <= KING; pt++)
1714               if (pieceCount[c][pt] != popcount<Full>(pieces(pt, c)))
1715                   return false;
1716
1717   if (failedStep) (*failedStep)++;
1718   if (debugPieceList)
1719       for (Color c = WHITE; c <= BLACK; c++)
1720           for (PieceType pt = PAWN; pt <= KING; pt++)
1721               for (int i = 0; i < pieceCount[c][pt]; i++)
1722               {
1723                   if (piece_on(piece_list(c, pt)[i]) != make_piece(c, pt))
1724                       return false;
1725
1726                   if (index[piece_list(c, pt)[i]] != i)
1727                       return false;
1728               }
1729
1730   if (failedStep) (*failedStep)++;
1731   if (debugCastleSquares)
1732       for (CastleRight f = WHITE_OO; f <= BLACK_OOO; f = CastleRight(f << 1))
1733       {
1734           if (!can_castle(f))
1735               continue;
1736
1737           Piece rook = (f & (WHITE_OO | WHITE_OOO) ? W_ROOK : B_ROOK);
1738
1739           if (   piece_on(castleRookSquare[f]) != rook
1740               || castleRightsMask[castleRookSquare[f]] != f)
1741               return false;
1742       }
1743
1744   if (failedStep) *failedStep = 0;
1745   return true;
1746 }