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