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