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