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