9fe5f893c9da5f199577abeb283fa7942d4bee6e
[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() is a static exchange evaluator: It tries to estimate the
959 /// material gain or loss resulting from a move.
960
961 Value Position::see_sign(Move m) const {
962
963   assert(is_ok(m));
964
965   // Early return if SEE cannot be negative because captured piece value
966   // is not less then capturing one. Note that king moves always return
967   // here because king midgame value is set to 0.
968   if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
969       return VALUE_KNOWN_WIN;
970
971   return see(m);
972 }
973
974 Value Position::see(Move m) const {
975
976   Square from, to;
977   Bitboard occupied, attackers, stmAttackers;
978   Value swapList[32];
979   int slIndex = 1;
980   PieceType nextVictim;
981   Color stm;
982
983   assert(is_ok(m));
984
985   from = from_sq(m);
986   to = to_sq(m);
987   swapList[0] = PieceValue[MG][piece_on(to)];
988   stm = color_of(piece_on(from));
989   occupied = pieces() ^ from;
990
991   // Castling moves are implemented as king capturing the rook so cannot
992   // be handled correctly. Simply return VALUE_ZERO that is always correct
993   // unless in the rare case the rook ends up under attack.
994   if (type_of(m) == CASTLING)
995       return VALUE_ZERO;
996
997   if (type_of(m) == ENPASSANT)
998   {
999       occupied ^= to - pawn_push(stm); // Remove the captured pawn
1000       swapList[0] = PieceValue[MG][PAWN];
1001   }
1002
1003   // Find all attackers to the destination square, with the moving piece
1004   // removed, but possibly an X-ray attacker added behind it.
1005   attackers = attackers_to(to, occupied) & occupied;
1006
1007   // If the opponent has no attackers we are finished
1008   stm = ~stm;
1009   stmAttackers = attackers & pieces(stm);
1010   occupied ^= to; // For the case when captured piece is a pinner
1011
1012   // Don't allow pinned pieces to attack pieces except the king as long all
1013   // pinners are on their original square.
1014   if (!(st->pinnersForKing[stm] & ~occupied))
1015       stmAttackers &= ~st->blockersForKing[stm];
1016
1017   if (!stmAttackers)
1018         return swapList[0];
1019
1020   // The destination square is defended, which makes things rather more
1021   // difficult to compute. We proceed by building up a "swap list" containing
1022   // the material gain or loss at each stop in a sequence of captures to the
1023   // destination square, where the sides alternately capture, and always
1024   // capture with the least valuable piece. After each capture, we look for
1025   // new X-ray attacks from behind the capturing piece.
1026   nextVictim = type_of(piece_on(from));
1027
1028   do {
1029       assert(slIndex < 32);
1030
1031       // Add the new entry to the swap list
1032       swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][nextVictim];
1033
1034       // Locate and remove the next least valuable attacker
1035       nextVictim = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1036       stm = ~stm;
1037       stmAttackers = attackers & pieces(stm);
1038
1039       // Don't allow pinned pieces to attack pieces except the king
1040       if (   nextVictim != KING
1041           && !(st->pinnersForKing[stm] & ~occupied))
1042           stmAttackers &= ~st->blockersForKing[stm];
1043
1044       ++slIndex;
1045
1046   } while (stmAttackers && (nextVictim != KING || (--slIndex, false))); // Stop before a king capture
1047
1048   // Having built the swap list, we negamax through it to find the best
1049   // achievable score from the point of view of the side to move.
1050   while (--slIndex)
1051       swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1052
1053   return swapList[0];
1054 }
1055
1056
1057 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1058 /// or by repetition. It does not detect stalemates.
1059
1060 bool Position::is_draw() const {
1061
1062   if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1063       return true;
1064
1065   StateInfo* stp = st;
1066   for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1067   {
1068       stp = stp->previous->previous;
1069
1070       if (stp->key == st->key)
1071           return true; // Draw at first repetition
1072   }
1073
1074   return false;
1075 }
1076
1077
1078 /// Position::flip() flips position with the white and black sides reversed. This
1079 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1080
1081 void Position::flip() {
1082
1083   string f, token;
1084   std::stringstream ss(fen());
1085
1086   for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1087   {
1088       std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1089       f.insert(0, token + (f.empty() ? " " : "/"));
1090   }
1091
1092   ss >> token; // Active color
1093   f += (token == "w" ? "B " : "W "); // Will be lowercased later
1094
1095   ss >> token; // Castling availability
1096   f += token + " ";
1097
1098   std::transform(f.begin(), f.end(), f.begin(),
1099                  [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1100
1101   ss >> token; // En passant square
1102   f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1103
1104   std::getline(ss, token); // Half and full moves
1105   f += token;
1106
1107   set(f, is_chess960(), st, this_thread());
1108
1109   assert(pos_is_ok());
1110 }
1111
1112
1113 /// Position::pos_is_ok() performs some consistency checks for the position object.
1114 /// This is meant to be helpful when debugging.
1115
1116 bool Position::pos_is_ok(int* failedStep) const {
1117
1118   const bool Fast = true; // Quick (default) or full check?
1119
1120   enum { Default, King, Bitboards, State, Lists, Castling };
1121
1122   for (int step = Default; step <= (Fast ? Default : Castling); step++)
1123   {
1124       if (failedStep)
1125           *failedStep = step;
1126
1127       if (step == Default)
1128           if (   (sideToMove != WHITE && sideToMove != BLACK)
1129               || piece_on(square<KING>(WHITE)) != W_KING
1130               || piece_on(square<KING>(BLACK)) != B_KING
1131               || (   ep_square() != SQ_NONE
1132                   && relative_rank(sideToMove, ep_square()) != RANK_6))
1133               return false;
1134
1135       if (step == King)
1136           if (   std::count(board, board + SQUARE_NB, W_KING) != 1
1137               || std::count(board, board + SQUARE_NB, B_KING) != 1
1138               || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1139               return false;
1140
1141       if (step == Bitboards)
1142       {
1143           if (  (pieces(WHITE) & pieces(BLACK))
1144               ||(pieces(WHITE) | pieces(BLACK)) != pieces())
1145               return false;
1146
1147           for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1148               for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1149                   if (p1 != p2 && (pieces(p1) & pieces(p2)))
1150                       return false;
1151       }
1152
1153       if (step == State)
1154       {
1155           StateInfo si = *st;
1156           set_state(&si);
1157           if (std::memcmp(&si, st, sizeof(StateInfo)))
1158               return false;
1159       }
1160
1161       if (step == Lists)
1162           for (Piece pc : Pieces)
1163           {
1164               if (pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc))))
1165                   return false;
1166
1167               for (int i = 0; i < pieceCount[pc]; ++i)
1168                   if (board[pieceList[pc][i]] != pc || index[pieceList[pc][i]] != i)
1169                       return false;
1170           }
1171
1172       if (step == Castling)
1173           for (Color c = WHITE; c <= BLACK; ++c)
1174               for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1175               {
1176                   if (!can_castle(c | s))
1177                       continue;
1178
1179                   if (   piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1180                       || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1181                       ||(castlingRightsMask[square<KING>(c)] & (c | s)) != (c | s))
1182                       return false;
1183               }
1184   }
1185
1186   return true;
1187 }