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