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