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