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