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