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