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