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