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