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