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