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