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