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