b89c645f9768b77e5974e7a40aef0517f871d0ad
[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 due to attacks_from()
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 (unlikely(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   Square from = from_sq(m);
908   Square to = to_sq(m);
909   PieceType pt = type_of(piece_on(to));
910
911   assert(empty(from) || type_of(m) == CASTLING);
912   assert(st->capturedType != KING);
913
914   if (type_of(m) == PROMOTION)
915   {
916       assert(pt == promotion_type(m));
917       assert(relative_rank(us, to) == RANK_8);
918       assert(promotion_type(m) >= KNIGHT && promotion_type(m) <= QUEEN);
919
920       remove_piece(to, us, promotion_type(m));
921       put_piece(to, us, PAWN);
922       pt = PAWN;
923   }
924
925   if (type_of(m) == CASTLING)
926   {
927       Square rfrom, rto;
928       do_castling<false>(from, to, rfrom, rto);
929   }
930   else
931   {
932       move_piece(to, from, us, pt); // Put the piece back at the source square
933
934       if (st->capturedType)
935       {
936           Square capsq = to;
937
938           if (type_of(m) == ENPASSANT)
939           {
940               capsq -= pawn_push(us);
941
942               assert(pt == PAWN);
943               assert(to == st->previous->epSquare);
944               assert(relative_rank(us, to) == RANK_6);
945               assert(piece_on(capsq) == NO_PIECE);
946           }
947
948           put_piece(capsq, ~us, st->capturedType); // Restore the captured piece
949       }
950   }
951
952   // Finally point our state pointer back to the previous state
953   st = st->previous;
954   --gamePly;
955
956   assert(pos_is_ok());
957 }
958
959
960 /// Position::do_castling() is a helper used to do/undo a castling move. This
961 /// is a bit tricky, especially in Chess960.
962 template<bool Do>
963 void Position::do_castling(Square from, Square& to, Square& rfrom, Square& rto) {
964
965   bool kingSide = to > from;
966   rfrom = to; // Castling is encoded as "king captures friendly rook"
967   rto = relative_square(sideToMove, kingSide ? SQ_F1 : SQ_D1);
968   to  = relative_square(sideToMove, kingSide ? SQ_G1 : SQ_C1);
969
970   // Remove both pieces first since squares could overlap in Chess960
971   remove_piece(Do ?  from :  to, sideToMove, KING);
972   remove_piece(Do ? rfrom : rto, sideToMove, ROOK);
973   board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
974   put_piece(Do ?  to :  from, sideToMove, KING);
975   put_piece(Do ? rto : rfrom, sideToMove, ROOK);
976 }
977
978
979 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
980 /// the side to move without executing any move on the board.
981
982 void Position::do_null_move(StateInfo& newSt) {
983
984   assert(!checkers());
985
986   std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
987
988   newSt.previous = st;
989   st = &newSt;
990
991   if (st->epSquare != SQ_NONE)
992   {
993       st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
994       st->epSquare = SQ_NONE;
995   }
996
997   st->key ^= Zobrist::side;
998   prefetch((char*)TT.first_entry(st->key));
999
1000   ++st->rule50;
1001   st->pliesFromNull = 0;
1002
1003   sideToMove = ~sideToMove;
1004
1005   assert(pos_is_ok());
1006 }
1007
1008 void Position::undo_null_move() {
1009
1010   assert(!checkers());
1011
1012   st = st->previous;
1013   sideToMove = ~sideToMove;
1014 }
1015
1016
1017 /// Position::see() is a static exchange evaluator: It tries to estimate the
1018 /// material gain or loss resulting from a move.
1019
1020 Value Position::see_sign(Move m) const {
1021
1022   assert(is_ok(m));
1023
1024   // Early return if SEE cannot be negative because captured piece value
1025   // is not less then capturing one. Note that king moves always return
1026   // here because king midgame value is set to 0.
1027   if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
1028       return VALUE_KNOWN_WIN;
1029
1030   return see(m);
1031 }
1032
1033 Value Position::see(Move m) const {
1034
1035   Square from, to;
1036   Bitboard occupied, attackers, stmAttackers;
1037   Value swapList[32];
1038   int slIndex = 1;
1039   PieceType captured;
1040   Color stm;
1041
1042   assert(is_ok(m));
1043
1044   from = from_sq(m);
1045   to = to_sq(m);
1046   swapList[0] = PieceValue[MG][piece_on(to)];
1047   stm = color_of(piece_on(from));
1048   occupied = pieces() ^ from;
1049
1050   // Castling moves are implemented as king capturing the rook so cannot be
1051   // handled correctly. Simply return 0 that is always the correct value
1052   // unless in the rare case the rook ends up under attack.
1053   if (type_of(m) == CASTLING)
1054       return VALUE_ZERO;
1055
1056   if (type_of(m) == ENPASSANT)
1057   {
1058       occupied ^= to - pawn_push(stm); // Remove the captured pawn
1059       swapList[0] = PieceValue[MG][PAWN];
1060   }
1061
1062   // Find all attackers to the destination square, with the moving piece
1063   // removed, but possibly an X-ray attacker added behind it.
1064   attackers = attackers_to(to, occupied) & occupied;
1065
1066   // If the opponent has no attackers we are finished
1067   stm = ~stm;
1068   stmAttackers = attackers & pieces(stm);
1069   if (!stmAttackers)
1070       return swapList[0];
1071
1072   // The destination square is defended, which makes things rather more
1073   // difficult to compute. We proceed by building up a "swap list" containing
1074   // the material gain or loss at each stop in a sequence of captures to the
1075   // destination square, where the sides alternately capture, and always
1076   // capture with the least valuable piece. After each capture, we look for
1077   // new X-ray attacks from behind the capturing piece.
1078   captured = type_of(piece_on(from));
1079
1080   do {
1081       assert(slIndex < 32);
1082
1083       // Add the new entry to the swap list
1084       swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1085
1086       // Locate and remove the next least valuable attacker
1087       captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1088
1089       // Stop before processing a king capture
1090       if (captured == KING)
1091       {
1092           if (stmAttackers == attackers)
1093               ++slIndex;
1094
1095           break;
1096       }
1097
1098       stm = ~stm;
1099       stmAttackers = attackers & pieces(stm);
1100       ++slIndex;
1101
1102   } while (stmAttackers);
1103
1104   // Having built the swap list, we negamax through it to find the best
1105   // achievable score from the point of view of the side to move.
1106   while (--slIndex)
1107       swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1108
1109   return swapList[0];
1110 }
1111
1112
1113 /// Position::is_draw() tests whether the position is drawn by material, 50 moves
1114 /// rule or repetition. It does not detect stalemates.
1115
1116 bool Position::is_draw() const {
1117
1118   if (   !pieces(PAWN)
1119       && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1120       return true;
1121
1122   if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1123       return true;
1124
1125   StateInfo* stp = st;
1126   for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1127   {
1128       stp = stp->previous->previous;
1129
1130       if (stp->key == st->key)
1131           return true; // Draw at first repetition
1132   }
1133
1134   return false;
1135 }
1136
1137
1138 /// Position::flip() flips position with the white and black sides reversed. This
1139 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1140
1141 static char toggle_case(char c) {
1142   return char(islower(c) ? toupper(c) : tolower(c));
1143 }
1144
1145 void Position::flip() {
1146
1147   string f, token;
1148   std::stringstream ss(fen());
1149
1150   for (Rank rank = RANK_8; rank >= RANK_1; --rank) // Piece placement
1151   {
1152       std::getline(ss, token, rank > RANK_1 ? '/' : ' ');
1153       f.insert(0, token + (f.empty() ? " " : "/"));
1154   }
1155
1156   ss >> token; // Active color
1157   f += (token == "w" ? "B " : "W "); // Will be lowercased later
1158
1159   ss >> token; // Castling availability
1160   f += token + " ";
1161
1162   std::transform(f.begin(), f.end(), f.begin(), toggle_case);
1163
1164   ss >> token; // En passant square
1165   f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1166
1167   std::getline(ss, token); // Half and full moves
1168   f += token;
1169
1170   set(f, is_chess960(), this_thread());
1171
1172   assert(pos_is_ok());
1173 }
1174
1175
1176 /// Position::pos_is_ok() performs some consistency checks for the position object.
1177 /// This is meant to be helpful when debugging.
1178
1179 bool Position::pos_is_ok(int* step) const {
1180
1181   // Which parts of the position should be verified?
1182   const bool all = false;
1183
1184   const bool testBitboards       = all || false;
1185   const bool testState           = all || false;
1186   const bool testKingCount       = all || false;
1187   const bool testKingCapture     = all || false;
1188   const bool testPieceCounts     = all || false;
1189   const bool testPieceList       = all || false;
1190   const bool testCastlingSquares = all || false;
1191
1192   if (step)
1193       *step = 1;
1194
1195   if (   (sideToMove != WHITE && sideToMove != BLACK)
1196       || piece_on(king_square(WHITE)) != W_KING
1197       || piece_on(king_square(BLACK)) != B_KING
1198       || (   ep_square() != SQ_NONE
1199           && relative_rank(sideToMove, ep_square()) != RANK_6))
1200       return false;
1201
1202   if (step && ++*step, testBitboards)
1203   {
1204       // The intersection of the white and black pieces must be empty
1205       if (pieces(WHITE) & pieces(BLACK))
1206           return false;
1207
1208       // The union of the white and black pieces must be equal to all
1209       // occupied squares
1210       if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1211           return false;
1212
1213       // Separate piece type bitboards must have empty intersections
1214       for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1215           for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1216               if (p1 != p2 && (pieces(p1) & pieces(p2)))
1217                   return false;
1218   }
1219
1220   if (step && ++*step, testState)
1221   {
1222       StateInfo si;
1223       set_state(&si);
1224       if (   st->key != si.key
1225           || st->pawnKey != si.pawnKey
1226           || st->materialKey != si.materialKey
1227           || st->npMaterial[WHITE] != si.npMaterial[WHITE]
1228           || st->npMaterial[BLACK] != si.npMaterial[BLACK]
1229           || st->psq != si.psq
1230           || st->checkersBB != si.checkersBB)
1231           return false;
1232   }
1233
1234   if (step && ++*step, testKingCount)
1235       if (   std::count(board, board + SQUARE_NB, W_KING) != 1
1236           || std::count(board, board + SQUARE_NB, B_KING) != 1)
1237           return false;
1238
1239   if (step && ++*step, testKingCapture)
1240       if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1241           return false;
1242
1243   if (step && ++*step, testPieceCounts)
1244       for (Color c = WHITE; c <= BLACK; ++c)
1245           for (PieceType pt = PAWN; pt <= KING; ++pt)
1246               if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1247                   return false;
1248
1249   if (step && ++*step, testPieceList)
1250       for (Color c = WHITE; c <= BLACK; ++c)
1251           for (PieceType pt = PAWN; pt <= KING; ++pt)
1252               for (int i = 0; i < pieceCount[c][pt];  ++i)
1253                   if (   board[pieceList[c][pt][i]] != make_piece(c, pt)
1254                       || index[pieceList[c][pt][i]] != i)
1255                       return false;
1256
1257   if (step && ++*step, testCastlingSquares)
1258       for (Color c = WHITE; c <= BLACK; ++c)
1259           for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1260           {
1261               if (!can_castle(c | s))
1262                   continue;
1263
1264               if (  (castlingRightsMask[king_square(c)] & (c | s)) != (c | s)
1265                   || piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1266                   || castlingRightsMask[castlingRookSquare[c | s]] != (c | s))
1267                   return false;
1268           }
1269
1270   return true;
1271 }