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