Better check evasion move sorting
[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-2015 Marco Costalba, Joona Kiiski, Tord Romstad
5   Copyright (C) 2015-2018 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad
6
7   Stockfish is free software: you can redistribute it and/or modify
8   it under the terms of the GNU General Public License as published by
9   the Free Software Foundation, either version 3 of the License, or
10   (at your option) any later version.
11
12   Stockfish is distributed in the hope that it will be useful,
13   but WITHOUT ANY WARRANTY; without even the implied warranty of
14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15   GNU General Public License for more details.
16
17   You should have received a copy of the GNU General Public License
18   along with this program.  If not, see <http://www.gnu.org/licenses/>.
19 */
20
21 #include <algorithm>
22 #include <cassert>
23 #include <cstddef> // For offsetof()
24 #include <cstring> // For std::memset, std::memcmp
25 #include <iomanip>
26 #include <sstream>
27
28 #include "bitboard.h"
29 #include "misc.h"
30 #include "movegen.h"
31 #include "position.h"
32 #include "thread.h"
33 #include "tt.h"
34 #include "uci.h"
35 #include "syzygy/tbprobe.h"
36
37 using std::string;
38
39 namespace Zobrist {
40
41   Key psq[PIECE_NB][SQUARE_NB];
42   Key enpassant[FILE_NB];
43   Key castling[CASTLING_RIGHT_NB];
44   Key side, noPawns;
45 }
46
47 namespace {
48
49 const string PieceToChar(" PNBRQK  pnbrqk");
50
51 constexpr Piece Pieces[] = { W_PAWN, W_KNIGHT, W_BISHOP, W_ROOK, W_QUEEN, W_KING,
52                              B_PAWN, B_KNIGHT, B_BISHOP, B_ROOK, B_QUEEN, B_KING };
53
54 // min_attacker() is a helper function used by see_ge() to locate the least
55 // valuable attacker for the side to move, remove the attacker we just found
56 // from the bitboards and scan for new X-ray attacks behind it.
57
58 template<int Pt>
59 PieceType min_attacker(const Bitboard* byTypeBB, Square to, Bitboard stmAttackers,
60                        Bitboard& occupied, Bitboard& attackers) {
61
62   Bitboard b = stmAttackers & byTypeBB[Pt];
63   if (!b)
64       return min_attacker<Pt + 1>(byTypeBB, to, stmAttackers, occupied, attackers);
65
66   occupied ^= lsb(b); // Remove the attacker from occupied
67
68   // Add any X-ray attack behind the just removed piece. For instance with
69   // rooks in a8 and a7 attacking a1, after removing a7 we add rook in a8.
70   // Note that new added attackers can be of any color.
71   if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
72       attackers |= attacks_bb<BISHOP>(to, occupied) & (byTypeBB[BISHOP] | byTypeBB[QUEEN]);
73
74   if (Pt == ROOK || Pt == QUEEN)
75       attackers |= attacks_bb<ROOK>(to, occupied) & (byTypeBB[ROOK] | byTypeBB[QUEEN]);
76
77   // X-ray may add already processed pieces because byTypeBB[] is constant: in
78   // the rook example, now attackers contains _again_ rook in a7, so remove it.
79   attackers &= occupied;
80   return (PieceType)Pt;
81 }
82
83 template<>
84 PieceType min_attacker<KING>(const Bitboard*, Square, Bitboard, Bitboard&, Bitboard&) {
85   return KING; // No need to update bitboards: it is the last cycle
86 }
87
88 } // namespace
89
90
91 /// operator<<(Position) returns an ASCII representation of the position
92
93 std::ostream& operator<<(std::ostream& os, const Position& pos) {
94
95   os << "\n +---+---+---+---+---+---+---+---+\n";
96
97   for (Rank r = RANK_8; r >= RANK_1; --r)
98   {
99       for (File f = FILE_A; f <= FILE_H; ++f)
100           os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
101
102       os << " |\n +---+---+---+---+---+---+---+---+\n";
103   }
104
105   os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
106      << std::setfill('0') << std::setw(16) << pos.key()
107      << std::setfill(' ') << std::dec << "\nCheckers: ";
108
109   for (Bitboard b = pos.checkers(); b; )
110       os << UCI::square(pop_lsb(&b)) << " ";
111
112   if (    int(Tablebases::MaxCardinality) >= popcount(pos.pieces())
113       && !pos.can_castle(ANY_CASTLING))
114   {
115       StateInfo st;
116       Position p;
117       p.set(pos.fen(), pos.is_chess960(), &st, pos.this_thread());
118       Tablebases::ProbeState s1, s2;
119       Tablebases::WDLScore wdl = Tablebases::probe_wdl(p, &s1);
120       int dtz = Tablebases::probe_dtz(p, &s2);
121       os << "\nTablebases WDL: " << std::setw(4) << wdl << " (" << s1 << ")"
122          << "\nTablebases DTZ: " << std::setw(4) << dtz << " (" << s2 << ")";
123   }
124
125   return os;
126 }
127
128
129 // Marcel van Kervinck's cuckoo algorithm for fast detection of "upcoming repetition"
130 // situations. Description of the algorithm in the following paper:
131 // https://marcelk.net/2013-04-06/paper/upcoming-rep-v2.pdf
132
133 // First and second hash functions for indexing the cuckoo tables
134 inline int H1(Key h) { return h & 0x1fff; }
135 inline int H2(Key h) { return (h >> 16) & 0x1fff; }
136
137 // Cuckoo tables with Zobrist hashes of valid reversible moves, and the moves themselves
138 Key cuckoo[8192];
139 Move cuckooMove[8192];
140
141
142 /// Position::init() initializes at startup the various arrays used to compute
143 /// hash keys.
144
145 void Position::init() {
146
147   PRNG rng(1070372);
148
149   for (Piece pc : Pieces)
150       for (Square s = SQ_A1; s <= SQ_H8; ++s)
151           Zobrist::psq[pc][s] = rng.rand<Key>();
152
153   for (File f = FILE_A; f <= FILE_H; ++f)
154       Zobrist::enpassant[f] = rng.rand<Key>();
155
156   for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
157   {
158       Zobrist::castling[cr] = 0;
159       Bitboard b = cr;
160       while (b)
161       {
162           Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
163           Zobrist::castling[cr] ^= k ? k : rng.rand<Key>();
164       }
165   }
166
167   Zobrist::side = rng.rand<Key>();
168   Zobrist::noPawns = rng.rand<Key>();
169
170   // Prepare the cuckoo tables
171   std::memset(cuckoo, 0, sizeof(cuckoo));
172   std::memset(cuckooMove, 0, sizeof(cuckooMove));
173   int count = 0;
174   for (Piece pc : Pieces)
175       for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1)
176           for (Square s2 = Square(s1 + 1); s2 <= SQ_H8; ++s2)
177               if (PseudoAttacks[type_of(pc)][s1] & s2)
178               {
179                   Move move = make_move(s1, s2);
180                   Key key = Zobrist::psq[pc][s1] ^ Zobrist::psq[pc][s2] ^ Zobrist::side;
181                   int i = H1(key);
182                   while (true)
183                   {
184                       std::swap(cuckoo[i], key);
185                       std::swap(cuckooMove[i], move);
186                       if (move == 0)   // Arrived at empty slot ?
187                           break;
188                       i = (i == H1(key)) ? H2(key) : H1(key); // Push victim to alternative slot
189                   }
190                   count++;
191              }
192   assert(count == 3668);
193 }
194
195
196 /// Position::set() initializes the position object with the given FEN string.
197 /// This function is not very robust - make sure that input FENs are correct,
198 /// this is assumed to be the responsibility of the GUI.
199
200 Position& Position::set(const string& fenStr, bool isChess960, StateInfo* si, Thread* th) {
201 /*
202    A FEN string defines a particular position using only the ASCII character set.
203
204    A FEN string contains six fields separated by a space. The fields are:
205
206    1) Piece placement (from white's perspective). Each rank is described, starting
207       with rank 8 and ending with rank 1. Within each rank, the contents of each
208       square are described from file A through file H. Following the Standard
209       Algebraic Notation (SAN), each piece is identified by a single letter taken
210       from the standard English names. White pieces are designated using upper-case
211       letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
212       noted using digits 1 through 8 (the number of blank squares), and "/"
213       separates ranks.
214
215    2) Active color. "w" means white moves next, "b" means black.
216
217    3) Castling availability. If neither side can castle, this is "-". Otherwise,
218       this has one or more letters: "K" (White can castle kingside), "Q" (White
219       can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
220       can castle queenside).
221
222    4) En passant target square (in algebraic notation). If there's no en passant
223       target square, this is "-". If a pawn has just made a 2-square move, this
224       is the position "behind" the pawn. This is recorded only if there is a pawn
225       in position to make an en passant capture, and if there really is a pawn
226       that might have advanced two squares.
227
228    5) Halfmove clock. This is the number of halfmoves since the last pawn advance
229       or capture. This is used to determine if a draw can be claimed under the
230       fifty-move rule.
231
232    6) Fullmove number. The number of the full move. It starts at 1, and is
233       incremented after Black's move.
234 */
235
236   unsigned char col, row, token;
237   size_t idx;
238   Square sq = SQ_A8;
239   std::istringstream ss(fenStr);
240
241   std::memset(this, 0, sizeof(Position));
242   std::memset(si, 0, sizeof(StateInfo));
243   std::fill_n(&pieceList[0][0], sizeof(pieceList) / sizeof(Square), SQ_NONE);
244   st = si;
245
246   ss >> std::noskipws;
247
248   // 1. Piece placement
249   while ((ss >> token) && !isspace(token))
250   {
251       if (isdigit(token))
252           sq += (token - '0') * EAST; // Advance the given number of files
253
254       else if (token == '/')
255           sq += 2 * SOUTH;
256
257       else if ((idx = PieceToChar.find(token)) != string::npos)
258       {
259           put_piece(Piece(idx), sq);
260           ++sq;
261       }
262   }
263
264   // 2. Active color
265   ss >> token;
266   sideToMove = (token == 'w' ? WHITE : BLACK);
267   ss >> token;
268
269   // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
270   // Shredder-FEN that uses the letters of the columns on which the rooks began
271   // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
272   // if an inner rook is associated with the castling right, the castling tag is
273   // replaced by the file letter of the involved rook, as for the Shredder-FEN.
274   while ((ss >> token) && !isspace(token))
275   {
276       Square rsq;
277       Color c = islower(token) ? BLACK : WHITE;
278       Piece rook = make_piece(c, ROOK);
279
280       token = char(toupper(token));
281
282       if (token == 'K')
283           for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) {}
284
285       else if (token == 'Q')
286           for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) {}
287
288       else if (token >= 'A' && token <= 'H')
289           rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
290
291       else
292           continue;
293
294       set_castling_right(c, rsq);
295   }
296
297   // 4. En passant square. Ignore if no pawn capture is possible
298   if (   ((ss >> col) && (col >= 'a' && col <= 'h'))
299       && ((ss >> row) && (row == '3' || row == '6')))
300   {
301       st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
302
303       if (   !(attackers_to(st->epSquare) & pieces(sideToMove, PAWN))
304           || !(pieces(~sideToMove, PAWN) & (st->epSquare + pawn_push(~sideToMove))))
305           st->epSquare = SQ_NONE;
306   }
307   else
308       st->epSquare = SQ_NONE;
309
310   // 5-6. Halfmove clock and fullmove number
311   ss >> std::skipws >> st->rule50 >> gamePly;
312
313   // Convert from fullmove starting from 1 to gamePly starting from 0,
314   // handle also common incorrect FEN with fullmove = 0.
315   gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
316
317   chess960 = isChess960;
318   thisThread = th;
319   set_state(st);
320
321   assert(pos_is_ok());
322
323   return *this;
324 }
325
326
327 /// Position::set_castling_right() is a helper function used to set castling
328 /// rights given the corresponding color and the rook starting square.
329
330 void Position::set_castling_right(Color c, Square rfrom) {
331
332   Square kfrom = square<KING>(c);
333   CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
334   CastlingRight cr = (c | cs);
335
336   st->castlingRights |= cr;
337   castlingRightsMask[kfrom] |= cr;
338   castlingRightsMask[rfrom] |= cr;
339   castlingRookSquare[cr] = rfrom;
340
341   Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
342   Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
343
344   for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
345       if (s != kfrom && s != rfrom)
346           castlingPath[cr] |= s;
347
348   for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
349       if (s != kfrom && s != rfrom)
350           castlingPath[cr] |= s;
351 }
352
353
354 /// Position::set_check_info() sets king attacks to detect if a move gives check
355
356 void Position::set_check_info(StateInfo* si) const {
357
358   si->blockersForKing[WHITE] = slider_blockers(pieces(BLACK), square<KING>(WHITE), si->pinners[BLACK]);
359   si->blockersForKing[BLACK] = slider_blockers(pieces(WHITE), square<KING>(BLACK), si->pinners[WHITE]);
360
361   Square ksq = square<KING>(~sideToMove);
362
363   si->checkSquares[PAWN]   = attacks_from<PAWN>(ksq, ~sideToMove);
364   si->checkSquares[KNIGHT] = attacks_from<KNIGHT>(ksq);
365   si->checkSquares[BISHOP] = attacks_from<BISHOP>(ksq);
366   si->checkSquares[ROOK]   = attacks_from<ROOK>(ksq);
367   si->checkSquares[QUEEN]  = si->checkSquares[BISHOP] | si->checkSquares[ROOK];
368   si->checkSquares[KING]   = 0;
369 }
370
371
372 /// Position::set_state() computes the hash keys of the position, and other
373 /// data that once computed is updated incrementally as moves are made.
374 /// The function is only used when a new position is set up, and to verify
375 /// the correctness of the StateInfo data when running in debug mode.
376
377 void Position::set_state(StateInfo* si) const {
378
379   si->key = si->materialKey = 0;
380   si->pawnKey = Zobrist::noPawns;
381   si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
382   si->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
383
384   set_check_info(si);
385
386   for (Bitboard b = pieces(); b; )
387   {
388       Square s = pop_lsb(&b);
389       Piece pc = piece_on(s);
390       si->key ^= Zobrist::psq[pc][s];
391   }
392
393   if (si->epSquare != SQ_NONE)
394       si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
395
396   if (sideToMove == BLACK)
397       si->key ^= Zobrist::side;
398
399   si->key ^= Zobrist::castling[si->castlingRights];
400
401   for (Bitboard b = pieces(PAWN); b; )
402   {
403       Square s = pop_lsb(&b);
404       si->pawnKey ^= Zobrist::psq[piece_on(s)][s];
405   }
406
407   for (Piece pc : Pieces)
408   {
409       if (type_of(pc) != PAWN && type_of(pc) != KING)
410           si->nonPawnMaterial[color_of(pc)] += pieceCount[pc] * PieceValue[MG][pc];
411
412       for (int cnt = 0; cnt < pieceCount[pc]; ++cnt)
413           si->materialKey ^= Zobrist::psq[pc][cnt];
414   }
415 }
416
417
418 /// Position::set() is an overload to initialize the position object with
419 /// the given endgame code string like "KBPKN". It is mainly a helper to
420 /// get the material key out of an endgame code.
421
422 Position& Position::set(const string& code, Color c, StateInfo* si) {
423
424   assert(code.length() > 0 && code.length() < 8);
425   assert(code[0] == 'K');
426
427   string sides[] = { code.substr(code.find('K', 1)),      // Weak
428                      code.substr(0, code.find('K', 1)) }; // Strong
429
430   std::transform(sides[c].begin(), sides[c].end(), sides[c].begin(), tolower);
431
432   string fenStr = "8/" + sides[0] + char(8 - sides[0].length() + '0') + "/8/8/8/8/"
433                        + sides[1] + char(8 - sides[1].length() + '0') + "/8 w - - 0 10";
434
435   return set(fenStr, false, si, nullptr);
436 }
437
438
439 /// Position::fen() returns a FEN representation of the position. In case of
440 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
441
442 const string Position::fen() const {
443
444   int emptyCnt;
445   std::ostringstream ss;
446
447   for (Rank r = RANK_8; r >= RANK_1; --r)
448   {
449       for (File f = FILE_A; f <= FILE_H; ++f)
450       {
451           for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
452               ++emptyCnt;
453
454           if (emptyCnt)
455               ss << emptyCnt;
456
457           if (f <= FILE_H)
458               ss << PieceToChar[piece_on(make_square(f, r))];
459       }
460
461       if (r > RANK_1)
462           ss << '/';
463   }
464
465   ss << (sideToMove == WHITE ? " w " : " b ");
466
467   if (can_castle(WHITE_OO))
468       ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE |  KING_SIDE))) : 'K');
469
470   if (can_castle(WHITE_OOO))
471       ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE))) : 'Q');
472
473   if (can_castle(BLACK_OO))
474       ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK |  KING_SIDE))) : 'k');
475
476   if (can_castle(BLACK_OOO))
477       ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE))) : 'q');
478
479   if (!can_castle(WHITE) && !can_castle(BLACK))
480       ss << '-';
481
482   ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
483      << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
484
485   return ss.str();
486 }
487
488
489 /// Position::slider_blockers() returns a bitboard of all the pieces (both colors)
490 /// that are blocking attacks on the square 's' from 'sliders'. A piece blocks a
491 /// slider if removing that piece from the board would result in a position where
492 /// square 's' is attacked. For example, a king-attack blocking piece can be either
493 /// a pinned or a discovered check piece, according if its color is the opposite
494 /// or the same of the color of the slider.
495
496 Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const {
497
498   Bitboard blockers = 0;
499   pinners = 0;
500
501   // Snipers are sliders that attack 's' when a piece is removed
502   Bitboard snipers = (  (PseudoAttacks[  ROOK][s] & pieces(QUEEN, ROOK))
503                       | (PseudoAttacks[BISHOP][s] & pieces(QUEEN, BISHOP))) & sliders;
504
505   while (snipers)
506   {
507     Square sniperSq = pop_lsb(&snipers);
508     Bitboard b = between_bb(s, sniperSq) & pieces();
509
510     if (b && !more_than_one(b))
511     {
512         blockers |= b;
513         if (b & pieces(color_of(piece_on(s))))
514             pinners |= sniperSq;
515     }
516   }
517   return blockers;
518 }
519
520
521 /// Position::attackers_to() computes a bitboard of all pieces which attack a
522 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
523
524 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
525
526   return  (attacks_from<PAWN>(s, BLACK)    & pieces(WHITE, PAWN))
527         | (attacks_from<PAWN>(s, WHITE)    & pieces(BLACK, PAWN))
528         | (attacks_from<KNIGHT>(s)         & pieces(KNIGHT))
529         | (attacks_bb<  ROOK>(s, occupied) & pieces(  ROOK, QUEEN))
530         | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
531         | (attacks_from<KING>(s)           & pieces(KING));
532 }
533
534
535 /// Position::legal() tests whether a pseudo-legal move is legal
536
537 bool Position::legal(Move m) const {
538
539   assert(is_ok(m));
540
541   Color us = sideToMove;
542   Square from = from_sq(m);
543
544   assert(color_of(moved_piece(m)) == us);
545   assert(piece_on(square<KING>(us)) == make_piece(us, KING));
546
547   // En passant captures are a tricky special case. Because they are rather
548   // uncommon, we do it simply by testing whether the king is attacked after
549   // the move is made.
550   if (type_of(m) == ENPASSANT)
551   {
552       Square ksq = square<KING>(us);
553       Square to = to_sq(m);
554       Square capsq = to - pawn_push(us);
555       Bitboard occupied = (pieces() ^ from ^ capsq) | to;
556
557       assert(to == ep_square());
558       assert(moved_piece(m) == make_piece(us, PAWN));
559       assert(piece_on(capsq) == make_piece(~us, PAWN));
560       assert(piece_on(to) == NO_PIECE);
561
562       return   !(attacks_bb<  ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
563             && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
564   }
565
566   // If the moving piece is a king, check whether the destination
567   // square is attacked by the opponent. Castling moves are checked
568   // for legality during move generation.
569   if (type_of(piece_on(from)) == KING)
570       return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
571
572   // A non-king move is legal if and only if it is not pinned or it
573   // is moving along the ray towards or away from the king.
574   return   !(blockers_for_king(us) & from)
575         ||  aligned(from, to_sq(m), square<KING>(us));
576 }
577
578
579 /// Position::pseudo_legal() takes a random move and tests whether the move is
580 /// pseudo legal. It is used to validate moves from TT that can be corrupted
581 /// due to SMP concurrent access or hash position key aliasing.
582
583 bool Position::pseudo_legal(const Move m) const {
584
585   Color us = sideToMove;
586   Square from = from_sq(m);
587   Square to = to_sq(m);
588   Piece pc = moved_piece(m);
589
590   // Use a slower but simpler function for uncommon cases
591   if (type_of(m) != NORMAL)
592       return MoveList<LEGAL>(*this).contains(m);
593
594   // Is not a promotion, so promotion piece must be empty
595   if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
596       return false;
597
598   // If the 'from' square is not occupied by a piece belonging to the side to
599   // move, the move is obviously not legal.
600   if (pc == NO_PIECE || color_of(pc) != us)
601       return false;
602
603   // The destination square cannot be occupied by a friendly piece
604   if (pieces(us) & to)
605       return false;
606
607   // Handle the special case of a pawn move
608   if (type_of(pc) == PAWN)
609   {
610       // We have already handled promotion moves, so destination
611       // cannot be on the 8th/1st rank.
612       if (rank_of(to) == relative_rank(us, RANK_8))
613           return false;
614
615       if (   !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
616           && !((from + pawn_push(us) == to) && empty(to))       // Not a single push
617           && !(   (from + 2 * pawn_push(us) == to)              // Not a double push
618                && (rank_of(from) == relative_rank(us, RANK_2))
619                && empty(to)
620                && empty(to - pawn_push(us))))
621           return false;
622   }
623   else if (!(attacks_from(type_of(pc), from) & to))
624       return false;
625
626   // Evasions generator already takes care to avoid some kind of illegal moves
627   // and legal() relies on this. We therefore have to take care that the same
628   // kind of moves are filtered out here.
629   if (checkers())
630   {
631       if (type_of(pc) != KING)
632       {
633           // Double check? In this case a king move is required
634           if (more_than_one(checkers()))
635               return false;
636
637           // Our move must be a blocking evasion or a capture of the checking piece
638           if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
639               return false;
640       }
641       // In case of king moves under check we have to remove king so as to catch
642       // invalid moves like b1a1 when opposite queen is on c1.
643       else if (attackers_to(to, pieces() ^ from) & pieces(~us))
644           return false;
645   }
646
647   return true;
648 }
649
650
651 /// Position::gives_check() tests whether a pseudo-legal move gives a check
652
653 bool Position::gives_check(Move m) const {
654
655   assert(is_ok(m));
656   assert(color_of(moved_piece(m)) == sideToMove);
657
658   Square from = from_sq(m);
659   Square to = to_sq(m);
660
661   // Is there a direct check?
662   if (st->checkSquares[type_of(piece_on(from))] & to)
663       return true;
664
665   // Is there a discovered check?
666   if (   (st->blockersForKing[~sideToMove] & from)
667       && !aligned(from, to, square<KING>(~sideToMove)))
668       return true;
669
670   switch (type_of(m))
671   {
672   case NORMAL:
673       return false;
674
675   case PROMOTION:
676       return attacks_bb(promotion_type(m), to, pieces() ^ from) & square<KING>(~sideToMove);
677
678   // En passant capture with check? We have already handled the case
679   // of direct checks and ordinary discovered check, so the only case we
680   // need to handle is the unusual case of a discovered check through
681   // the captured pawn.
682   case ENPASSANT:
683   {
684       Square capsq = make_square(file_of(to), rank_of(from));
685       Bitboard b = (pieces() ^ from ^ capsq) | to;
686
687       return  (attacks_bb<  ROOK>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))
688             | (attacks_bb<BISHOP>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, BISHOP));
689   }
690   case CASTLING:
691   {
692       Square kfrom = from;
693       Square rfrom = to; // Castling is encoded as 'King captures the rook'
694       Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
695       Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
696
697       return   (PseudoAttacks[ROOK][rto] & square<KING>(~sideToMove))
698             && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & square<KING>(~sideToMove));
699   }
700   default:
701       assert(false);
702       return false;
703   }
704 }
705
706
707 /// Position::do_move() makes a move, and saves all information necessary
708 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
709 /// moves should be filtered out before this function is called.
710
711 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
712
713   assert(is_ok(m));
714   assert(&newSt != st);
715
716   thisThread->nodes.fetch_add(1, std::memory_order_relaxed);
717   Key k = st->key ^ Zobrist::side;
718
719   // Copy some fields of the old state to our new StateInfo object except the
720   // ones which are going to be recalculated from scratch anyway and then switch
721   // our state pointer to point to the new (ready to be updated) state.
722   std::memcpy(&newSt, st, offsetof(StateInfo, key));
723   newSt.previous = st;
724   st = &newSt;
725
726   // Increment ply counters. In particular, rule50 will be reset to zero later on
727   // in case of a capture or a pawn move.
728   ++gamePly;
729   ++st->rule50;
730   ++st->pliesFromNull;
731
732   Color us = sideToMove;
733   Color them = ~us;
734   Square from = from_sq(m);
735   Square to = to_sq(m);
736   Piece pc = piece_on(from);
737   Piece captured = type_of(m) == ENPASSANT ? make_piece(them, PAWN) : piece_on(to);
738
739   assert(color_of(pc) == us);
740   assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us));
741   assert(type_of(captured) != KING);
742
743   if (type_of(m) == CASTLING)
744   {
745       assert(pc == make_piece(us, KING));
746       assert(captured == make_piece(us, ROOK));
747
748       Square rfrom, rto;
749       do_castling<true>(us, from, to, rfrom, rto);
750
751       k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
752       captured = NO_PIECE;
753   }
754
755   if (captured)
756   {
757       Square capsq = to;
758
759       // If the captured piece is a pawn, update pawn hash key, otherwise
760       // update non-pawn material.
761       if (type_of(captured) == PAWN)
762       {
763           if (type_of(m) == ENPASSANT)
764           {
765               capsq -= pawn_push(us);
766
767               assert(pc == make_piece(us, PAWN));
768               assert(to == st->epSquare);
769               assert(relative_rank(us, to) == RANK_6);
770               assert(piece_on(to) == NO_PIECE);
771               assert(piece_on(capsq) == make_piece(them, PAWN));
772
773               board[capsq] = NO_PIECE; // Not done by remove_piece()
774           }
775
776           st->pawnKey ^= Zobrist::psq[captured][capsq];
777       }
778       else
779           st->nonPawnMaterial[them] -= PieceValue[MG][captured];
780
781       // Update board and piece lists
782       remove_piece(captured, capsq);
783
784       // Update material hash key and prefetch access to materialTable
785       k ^= Zobrist::psq[captured][capsq];
786       st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];
787       prefetch(thisThread->materialTable[st->materialKey]);
788
789       // Reset rule 50 counter
790       st->rule50 = 0;
791   }
792
793   // Update hash key
794   k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
795
796   // Reset en passant square
797   if (st->epSquare != SQ_NONE)
798   {
799       k ^= Zobrist::enpassant[file_of(st->epSquare)];
800       st->epSquare = SQ_NONE;
801   }
802
803   // Update castling rights if needed
804   if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
805   {
806       int cr = castlingRightsMask[from] | castlingRightsMask[to];
807       k ^= Zobrist::castling[st->castlingRights & cr];
808       st->castlingRights &= ~cr;
809   }
810
811   // Move the piece. The tricky Chess960 castling is handled earlier
812   if (type_of(m) != CASTLING)
813       move_piece(pc, from, to);
814
815   // If the moving piece is a pawn do some special extra work
816   if (type_of(pc) == PAWN)
817   {
818       // Set en-passant square if the moved pawn can be captured
819       if (   (int(to) ^ int(from)) == 16
820           && (attacks_from<PAWN>(to - pawn_push(us), us) & pieces(them, PAWN)))
821       {
822           st->epSquare = to - pawn_push(us);
823           k ^= Zobrist::enpassant[file_of(st->epSquare)];
824       }
825
826       else if (type_of(m) == PROMOTION)
827       {
828           Piece promotion = make_piece(us, promotion_type(m));
829
830           assert(relative_rank(us, to) == RANK_8);
831           assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);
832
833           remove_piece(pc, to);
834           put_piece(promotion, to);
835
836           // Update hash keys
837           k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
838           st->pawnKey ^= Zobrist::psq[pc][to];
839           st->materialKey ^=  Zobrist::psq[promotion][pieceCount[promotion]-1]
840                             ^ Zobrist::psq[pc][pieceCount[pc]];
841
842           // Update material
843           st->nonPawnMaterial[us] += PieceValue[MG][promotion];
844       }
845
846       // Update pawn hash key and prefetch access to pawnsTable
847       st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
848       prefetch2(thisThread->pawnsTable[st->pawnKey]);
849
850       // Reset rule 50 draw counter
851       st->rule50 = 0;
852   }
853
854   // Set capture piece
855   st->capturedPiece = captured;
856
857   // Update the key with the final value
858   st->key = k;
859
860   // Calculate checkers bitboard (if move gives check)
861   st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
862
863   sideToMove = ~sideToMove;
864
865   // Update king attacks used for fast check detection
866   set_check_info(st);
867
868   assert(pos_is_ok());
869 }
870
871
872 /// Position::undo_move() unmakes a move. When it returns, the position should
873 /// be restored to exactly the same state as before the move was made.
874
875 void Position::undo_move(Move m) {
876
877   assert(is_ok(m));
878
879   sideToMove = ~sideToMove;
880
881   Color us = sideToMove;
882   Square from = from_sq(m);
883   Square to = to_sq(m);
884   Piece pc = piece_on(to);
885
886   assert(empty(from) || type_of(m) == CASTLING);
887   assert(type_of(st->capturedPiece) != KING);
888
889   if (type_of(m) == PROMOTION)
890   {
891       assert(relative_rank(us, to) == RANK_8);
892       assert(type_of(pc) == promotion_type(m));
893       assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);
894
895       remove_piece(pc, to);
896       pc = make_piece(us, PAWN);
897       put_piece(pc, to);
898   }
899
900   if (type_of(m) == CASTLING)
901   {
902       Square rfrom, rto;
903       do_castling<false>(us, from, to, rfrom, rto);
904   }
905   else
906   {
907       move_piece(pc, to, from); // Put the piece back at the source square
908
909       if (st->capturedPiece)
910       {
911           Square capsq = to;
912
913           if (type_of(m) == ENPASSANT)
914           {
915               capsq -= pawn_push(us);
916
917               assert(type_of(pc) == PAWN);
918               assert(to == st->previous->epSquare);
919               assert(relative_rank(us, to) == RANK_6);
920               assert(piece_on(capsq) == NO_PIECE);
921               assert(st->capturedPiece == make_piece(~us, PAWN));
922           }
923
924           put_piece(st->capturedPiece, capsq); // Restore the captured piece
925       }
926   }
927
928   // Finally point our state pointer back to the previous state
929   st = st->previous;
930   --gamePly;
931
932   assert(pos_is_ok());
933 }
934
935
936 /// Position::do_castling() is a helper used to do/undo a castling move. This
937 /// is a bit tricky in Chess960 where from/to squares can overlap.
938 template<bool Do>
939 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
940
941   bool kingSide = to > from;
942   rfrom = to; // Castling is encoded as "king captures friendly rook"
943   rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
944   to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
945
946   // Remove both pieces first since squares could overlap in Chess960
947   remove_piece(make_piece(us, KING), Do ? from : to);
948   remove_piece(make_piece(us, ROOK), Do ? rfrom : rto);
949   board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
950   put_piece(make_piece(us, KING), Do ? to : from);
951   put_piece(make_piece(us, ROOK), Do ? rto : rfrom);
952 }
953
954
955 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
956 /// the side to move without executing any move on the board.
957
958 void Position::do_null_move(StateInfo& newSt) {
959
960   assert(!checkers());
961   assert(&newSt != st);
962
963   std::memcpy(&newSt, st, sizeof(StateInfo));
964   newSt.previous = st;
965   st = &newSt;
966
967   if (st->epSquare != SQ_NONE)
968   {
969       st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
970       st->epSquare = SQ_NONE;
971   }
972
973   st->key ^= Zobrist::side;
974   prefetch(TT.first_entry(st->key));
975
976   ++st->rule50;
977   st->pliesFromNull = 0;
978
979   sideToMove = ~sideToMove;
980
981   set_check_info(st);
982
983   assert(pos_is_ok());
984 }
985
986 void Position::undo_null_move() {
987
988   assert(!checkers());
989
990   st = st->previous;
991   sideToMove = ~sideToMove;
992 }
993
994
995 /// Position::key_after() computes the new hash key after the given move. Needed
996 /// for speculative prefetch. It doesn't recognize special moves like castling,
997 /// en-passant and promotions.
998
999 Key Position::key_after(Move m) const {
1000
1001   Square from = from_sq(m);
1002   Square to = to_sq(m);
1003   Piece pc = piece_on(from);
1004   Piece captured = piece_on(to);
1005   Key k = st->key ^ Zobrist::side;
1006
1007   if (captured)
1008       k ^= Zobrist::psq[captured][to];
1009
1010   return k ^ Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from];
1011 }
1012
1013
1014 /// Position::see_ge (Static Exchange Evaluation Greater or Equal) tests if the
1015 /// SEE value of move is greater or equal to the given threshold. We'll use an
1016 /// algorithm similar to alpha-beta pruning with a null window.
1017
1018 bool Position::see_ge(Move m, Value threshold) const {
1019
1020   assert(is_ok(m));
1021
1022   // Only deal with normal moves, assume others pass a simple see
1023   if (type_of(m) != NORMAL)
1024       return VALUE_ZERO >= threshold;
1025
1026   Bitboard stmAttackers;
1027   Square from = from_sq(m), to = to_sq(m);
1028   PieceType nextVictim = type_of(piece_on(from));
1029   Color us = color_of(piece_on(from));
1030   Color stm = ~us; // First consider opponent's move
1031   Value balance;   // Values of the pieces taken by us minus opponent's ones
1032
1033   // The opponent may be able to recapture so this is the best result
1034   // we can hope for.
1035   balance = PieceValue[MG][piece_on(to)] - threshold;
1036
1037   if (balance < VALUE_ZERO)
1038       return false;
1039
1040   // Now assume the worst possible result: that the opponent can
1041   // capture our piece for free.
1042   balance -= PieceValue[MG][nextVictim];
1043
1044   // If it is enough (like in PxQ) then return immediately. Note that
1045   // in case nextVictim == KING we always return here, this is ok
1046   // if the given move is legal.
1047   if (balance >= VALUE_ZERO)
1048       return true;
1049
1050   // Find all attackers to the destination square, with the moving piece
1051   // removed, but possibly an X-ray attacker added behind it.
1052   Bitboard occupied = pieces() ^ from ^ to;
1053   Bitboard attackers = attackers_to(to, occupied) & occupied;
1054
1055   while (true)
1056   {
1057       stmAttackers = attackers & pieces(stm);
1058
1059       // Don't allow pinned pieces to attack (except the king) as long as
1060       // all pinners are on their original square.
1061       if (!(st->pinners[~stm] & ~occupied))
1062           stmAttackers &= ~st->blockersForKing[stm];
1063
1064       // If stm has no more attackers then give up: stm loses
1065       if (!stmAttackers)
1066           break;
1067
1068       // Locate and remove the next least valuable attacker, and add to
1069       // the bitboard 'attackers' the possibly X-ray attackers behind it.
1070       nextVictim = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1071
1072       stm = ~stm; // Switch side to move
1073
1074       // Negamax the balance with alpha = balance, beta = balance+1 and
1075       // add nextVictim's value.
1076       //
1077       //      (balance, balance+1) -> (-balance-1, -balance)
1078       //
1079       assert(balance < VALUE_ZERO);
1080
1081       balance = -balance - 1 - PieceValue[MG][nextVictim];
1082
1083       // If balance is still non-negative after giving away nextVictim then we
1084       // win. The only thing to be careful about it is that we should revert
1085       // stm if we captured with the king when the opponent still has attackers.
1086       if (balance >= VALUE_ZERO)
1087       {
1088           if (nextVictim == KING && (attackers & pieces(stm)))
1089               stm = ~stm;
1090           break;
1091       }
1092       assert(nextVictim != KING);
1093   }
1094   return us != stm; // We break the above loop when stm loses
1095 }
1096
1097
1098 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1099 /// or by repetition. It does not detect stalemates.
1100
1101 bool Position::is_draw(int ply) const {
1102
1103   if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1104       return true;
1105
1106   int end = std::min(st->rule50, st->pliesFromNull);
1107
1108   if (end < 4)
1109     return false;
1110
1111   StateInfo* stp = st->previous->previous;
1112   int cnt = 0;
1113
1114   for (int i = 4; i <= end; i += 2)
1115   {
1116       stp = stp->previous->previous;
1117
1118       // Return a draw score if a position repeats once earlier but strictly
1119       // after the root, or repeats twice before or at the root.
1120       if (   stp->key == st->key
1121           && ++cnt + (ply > i) == 2)
1122           return true;
1123   }
1124
1125   return false;
1126 }
1127
1128
1129 // Position::has_repeated() tests whether there has been at least one repetition
1130 // of positions since the last capture or pawn move.
1131
1132 bool Position::has_repeated() const {
1133
1134     StateInfo* stc = st;
1135     while (true)
1136     {
1137         int i = 4, end = std::min(stc->rule50, stc->pliesFromNull);
1138
1139         if (end < i)
1140             return false;
1141
1142         StateInfo* stp = stc->previous->previous;
1143
1144         do {
1145             stp = stp->previous->previous;
1146
1147             if (stp->key == stc->key)
1148                 return true;
1149
1150             i += 2;
1151         } while (i <= end);
1152
1153         stc = stc->previous;
1154     }
1155 }
1156
1157
1158 /// Position::has_game_cycle() tests if the position has a move which draws by repetition,
1159 /// or an earlier position has a move that directly reaches the current position.
1160
1161 bool Position::has_game_cycle(int ply) const {
1162
1163   int j;
1164
1165   int end = std::min(st->rule50, st->pliesFromNull);
1166
1167   if (end < 3)
1168     return false;
1169
1170   Key originalKey = st->key;
1171   StateInfo* stp = st->previous;
1172
1173   for (int i = 3; i <= end; i += 2)
1174   {
1175       stp = stp->previous->previous;
1176
1177       Key moveKey = originalKey ^ stp->key;
1178       if (   (j = H1(moveKey), cuckoo[j] == moveKey)
1179           || (j = H2(moveKey), cuckoo[j] == moveKey))
1180       {
1181           Move move = cuckooMove[j];
1182           Square s1 = from_sq(move);
1183           Square s2 = to_sq(move);
1184
1185           if (!(between_bb(s1, s2) & pieces()))
1186           {
1187               // In the cuckoo table, both moves Rc1c5 and Rc5c1 are stored in the same
1188               // location. We select the legal one by reversing the move variable if necessary.
1189               if (empty(s1))
1190                   move = make_move(s2, s1);
1191
1192               if (ply > i)
1193                   return true;
1194
1195               // For repetitions before or at the root, require one more
1196               StateInfo* next_stp = stp;
1197               for (int k = i + 2; k <= end; k += 2)
1198               {
1199                   next_stp = next_stp->previous->previous;
1200                   if (next_stp->key == stp->key)
1201                      return true;
1202               }
1203           }
1204       }
1205   }
1206   return false;
1207 }
1208
1209
1210 /// Position::flip() flips position with the white and black sides reversed. This
1211 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1212
1213 void Position::flip() {
1214
1215   string f, token;
1216   std::stringstream ss(fen());
1217
1218   for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1219   {
1220       std::getline(ss, token, r > 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(),
1231                  [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1232
1233   ss >> token; // En passant square
1234   f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1235
1236   std::getline(ss, token); // Half and full moves
1237   f += token;
1238
1239   set(f, is_chess960(), st, this_thread());
1240
1241   assert(pos_is_ok());
1242 }
1243
1244
1245 /// Position::pos_is_ok() performs some consistency checks for the
1246 /// position object and raises an asserts if something wrong is detected.
1247 /// This is meant to be helpful when debugging.
1248
1249 bool Position::pos_is_ok() const {
1250
1251   constexpr bool Fast = true; // Quick (default) or full check?
1252
1253   if (   (sideToMove != WHITE && sideToMove != BLACK)
1254       || piece_on(square<KING>(WHITE)) != W_KING
1255       || piece_on(square<KING>(BLACK)) != B_KING
1256       || (   ep_square() != SQ_NONE
1257           && relative_rank(sideToMove, ep_square()) != RANK_6))
1258       assert(0 && "pos_is_ok: Default");
1259
1260   if (Fast)
1261       return true;
1262
1263   if (   pieceCount[W_KING] != 1
1264       || pieceCount[B_KING] != 1
1265       || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1266       assert(0 && "pos_is_ok: Kings");
1267
1268   if (   (pieces(PAWN) & (Rank1BB | Rank8BB))
1269       || pieceCount[W_PAWN] > 8
1270       || pieceCount[B_PAWN] > 8)
1271       assert(0 && "pos_is_ok: Pawns");
1272
1273   if (   (pieces(WHITE) & pieces(BLACK))
1274       || (pieces(WHITE) | pieces(BLACK)) != pieces()
1275       || popcount(pieces(WHITE)) > 16
1276       || popcount(pieces(BLACK)) > 16)
1277       assert(0 && "pos_is_ok: Bitboards");
1278
1279   for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1280       for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1281           if (p1 != p2 && (pieces(p1) & pieces(p2)))
1282               assert(0 && "pos_is_ok: Bitboards");
1283
1284   StateInfo si = *st;
1285   set_state(&si);
1286   if (std::memcmp(&si, st, sizeof(StateInfo)))
1287       assert(0 && "pos_is_ok: State");
1288
1289   for (Piece pc : Pieces)
1290   {
1291       if (   pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc)))
1292           || pieceCount[pc] != std::count(board, board + SQUARE_NB, pc))
1293           assert(0 && "pos_is_ok: Pieces");
1294
1295       for (int i = 0; i < pieceCount[pc]; ++i)
1296           if (board[pieceList[pc][i]] != pc || index[pieceList[pc][i]] != i)
1297               assert(0 && "pos_is_ok: Index");
1298   }
1299
1300   for (Color c = WHITE; c <= BLACK; ++c)
1301       for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1302       {
1303           if (!can_castle(c | s))
1304               continue;
1305
1306           if (   piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1307               || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1308               || (castlingRightsMask[square<KING>(c)] & (c | s)) != (c | s))
1309               assert(0 && "pos_is_ok: Castling");
1310       }
1311
1312   return true;
1313 }