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