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