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