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