]> git.sesse.net Git - stockfish/blob - src/position.cpp
6b05c24b2a434d3ef1f41b454af877883dc0b765
[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 = make_square(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 = make_square(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 r = RANK_8; r >= RANK_1; --r)
392   {
393       for (File f = FILE_A; f <= FILE_H; ++f)
394       {
395           for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
396               ++emptyCnt;
397
398           if (emptyCnt)
399               ss << emptyCnt;
400
401           if (f <= FILE_H)
402               ss << PieceToChar[piece_on(make_square(f, r))];
403       }
404
405       if (r > 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 m) const {
437
438   std::ostringstream ss;
439
440   if (m)
441       ss << "\nMove: " << (sideToMove == BLACK ? ".." : "")
442          << move_to_san(*const_cast<Position*>(this), m);
443
444   ss << "\n +---+---+---+---+---+---+---+---+\n";
445
446   for (Rank r = RANK_8; r >= RANK_1; --r)
447   {
448       for (File f = FILE_A; f <= FILE_H; ++f)
449           ss << " | " << PieceToChar[piece_on(make_square(f, r))];
450
451       ss << " |\n +---+---+---+---+---+---+---+---+\n";
452   }
453
454   ss << "\nFen: " << fen() << "\nKey: " << std::hex << std::uppercase
455      << std::setfill('0') << std::setw(16) << st->key << "\nCheckers: ";
456
457   for (Bitboard b = checkers(); b; )
458       ss << to_string(pop_lsb(&b)) << " ";
459
460   ss << "\nLegal moves: ";
461   for (MoveList<LEGAL> it(*this); *it; ++it)
462       ss << move_to_san(*const_cast<Position*>(this), *it) << " ";
463
464   return ss.str();
465 }
466
467
468 /// Position::check_blockers() returns a bitboard of all the pieces with color
469 /// 'c' that are blocking check on the king with color 'kingColor'. A piece
470 /// blocks a check if removing that piece from the board would result in a
471 /// position where the king is in check. A check blocking piece can be either a
472 /// pinned or a discovered check piece, according if its color 'c' is the same
473 /// or the opposite of 'kingColor'.
474
475 Bitboard Position::check_blockers(Color c, Color kingColor) const {
476
477   Bitboard b, pinners, result = 0;
478   Square ksq = king_square(kingColor);
479
480   // Pinners are sliders that give check when a pinned piece is removed
481   pinners = (  (pieces(  ROOK, QUEEN) & PseudoAttacks[ROOK  ][ksq])
482              | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(~kingColor);
483
484   while (pinners)
485   {
486       b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
487
488       if (!more_than_one(b))
489           result |= b & pieces(c);
490   }
491   return result;
492 }
493
494
495 /// Position::attackers_to() computes a bitboard of all pieces which attack a
496 /// given square. Slider attacks use the occ bitboard to indicate occupancy.
497
498 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
499
500   return  (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
501         | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
502         | (attacks_from<KNIGHT>(s)      & pieces(KNIGHT))
503         | (attacks_bb<ROOK>(s, occ)     & pieces(ROOK, QUEEN))
504         | (attacks_bb<BISHOP>(s, occ)   & pieces(BISHOP, QUEEN))
505         | (attacks_from<KING>(s)        & pieces(KING));
506 }
507
508
509 /// Position::legal() tests whether a pseudo-legal move is legal
510
511 bool Position::legal(Move m, Bitboard pinned) const {
512
513   assert(is_ok(m));
514   assert(pinned == pinned_pieces(sideToMove));
515
516   Color us = sideToMove;
517   Square from = from_sq(m);
518
519   assert(color_of(moved_piece(m)) == us);
520   assert(piece_on(king_square(us)) == make_piece(us, KING));
521
522   // En passant captures are a tricky special case. Because they are rather
523   // uncommon, we do it simply by testing whether the king is attacked after
524   // the move is made.
525   if (type_of(m) == ENPASSANT)
526   {
527       Square ksq = king_square(us);
528       Square to = to_sq(m);
529       Square capsq = to - pawn_push(us);
530       Bitboard occ = (pieces() ^ from ^ capsq) | to;
531
532       assert(to == ep_square());
533       assert(moved_piece(m) == make_piece(us, PAWN));
534       assert(piece_on(capsq) == make_piece(~us, PAWN));
535       assert(piece_on(to) == NO_PIECE);
536
537       return   !(attacks_bb<  ROOK>(ksq, occ) & pieces(~us, QUEEN, ROOK))
538             && !(attacks_bb<BISHOP>(ksq, occ) & pieces(~us, QUEEN, BISHOP));
539   }
540
541   // If the moving piece is a king, check whether the destination
542   // square is attacked by the opponent. Castling moves are checked
543   // for legality during move generation.
544   if (type_of(piece_on(from)) == KING)
545       return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
546
547   // A non-king move is legal if and only if it is not pinned or it
548   // is moving along the ray towards or away from the king.
549   return   !pinned
550         || !(pinned & from)
551         ||  aligned(from, to_sq(m), king_square(us));
552 }
553
554
555 /// Position::pseudo_legal() takes a random move and tests whether the move is
556 /// pseudo legal. It is used to validate moves from TT that can be corrupted
557 /// due to SMP concurrent access or hash position key aliasing.
558
559 bool Position::pseudo_legal(const Move m) const {
560
561   Color us = sideToMove;
562   Square from = from_sq(m);
563   Square to = to_sq(m);
564   Piece pc = moved_piece(m);
565
566   // Use a slower but simpler function for uncommon cases
567   if (type_of(m) != NORMAL)
568       return MoveList<LEGAL>(*this).contains(m);
569
570   // Is not a promotion, so promotion piece must be empty
571   if (promotion_type(m) - 2 != NO_PIECE_TYPE)
572       return false;
573
574   // If the 'from' square is not occupied by a piece belonging to the side to
575   // move, the move is obviously not legal.
576   if (pc == NO_PIECE || color_of(pc) != us)
577       return false;
578
579   // The destination square cannot be occupied by a friendly piece
580   if (pieces(us) & to)
581       return false;
582
583   // Handle the special case of a pawn move
584   if (type_of(pc) == PAWN)
585   {
586       // We have already handled promotion moves, so destination
587       // cannot be on the 8th/1st rank.
588       if (rank_of(to) == relative_rank(us, RANK_8))
589           return false;
590
591       if (   !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
592
593           && !((from + pawn_push(us) == to) && empty(to))       // Not a single push
594
595           && !(   (from + 2 * pawn_push(us) == to)              // Not a double push
596                && (rank_of(from) == relative_rank(us, RANK_2))
597                && empty(to)
598                && empty(to - pawn_push(us))))
599           return false;
600   }
601   else if (!(attacks_from(pc, from) & to))
602       return false;
603
604   // Evasions generator already takes care to avoid some kind of illegal moves
605   // and legal() relies on this. We therefore have to take care that the same
606   // kind of moves are filtered out here.
607   if (checkers())
608   {
609       if (type_of(pc) != KING)
610       {
611           // Double check? In this case a king move is required
612           if (more_than_one(checkers()))
613               return false;
614
615           // Our move must be a blocking evasion or a capture of the checking piece
616           if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
617               return false;
618       }
619       // In case of king moves under check we have to remove king so as to catch
620       // invalid moves like b1a1 when opposite queen is on c1.
621       else if (attackers_to(to, pieces() ^ from) & pieces(~us))
622           return false;
623   }
624
625   return true;
626 }
627
628
629 /// Position::gives_check() tests whether a pseudo-legal move gives a check
630
631 bool Position::gives_check(Move m, const CheckInfo& ci) const {
632
633   assert(is_ok(m));
634   assert(ci.dcCandidates == discovered_check_candidates());
635   assert(color_of(moved_piece(m)) == sideToMove);
636
637   Square from = from_sq(m);
638   Square to = to_sq(m);
639   PieceType pt = type_of(piece_on(from));
640
641   // Is there a direct check?
642   if (ci.checkSq[pt] & to)
643       return true;
644
645   // Is there a discovered check?
646   if (   unlikely(ci.dcCandidates)
647       && (ci.dcCandidates & from)
648       && !aligned(from, to, ci.ksq))
649       return true;
650
651   switch (type_of(m))
652   {
653   case NORMAL:
654       return false;
655
656   case PROMOTION:
657       return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & ci.ksq;
658
659   // En passant capture with check? We have already handled the case
660   // of direct checks and ordinary discovered check, so the only case we
661   // need to handle is the unusual case of a discovered check through
662   // the captured pawn.
663   case ENPASSANT:
664   {
665       Square capsq = make_square(file_of(to), rank_of(from));
666       Bitboard b = (pieces() ^ from ^ capsq) | to;
667
668       return  (attacks_bb<  ROOK>(ci.ksq, b) & pieces(sideToMove, QUEEN, ROOK))
669             | (attacks_bb<BISHOP>(ci.ksq, b) & pieces(sideToMove, QUEEN, BISHOP));
670   }
671   case CASTLING:
672   {
673       Square kfrom = from;
674       Square rfrom = to; // Castling is encoded as 'King captures the rook'
675       Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
676       Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
677
678       return   (PseudoAttacks[ROOK][rto] & ci.ksq)
679             && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ci.ksq);
680   }
681   default:
682       assert(false);
683       return false;
684   }
685 }
686
687
688 /// Position::do_move() makes a move, and saves all information necessary
689 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
690 /// moves should be filtered out before this function is called.
691
692 void Position::do_move(Move m, StateInfo& newSt) {
693
694   CheckInfo ci(*this);
695   do_move(m, newSt, ci, gives_check(m, ci));
696 }
697
698 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
699
700   assert(is_ok(m));
701   assert(&newSt != st);
702
703   ++nodes;
704   Key k = st->key;
705
706   // Copy some fields of the old state to our new StateInfo object except the
707   // ones which are going to be recalculated from scratch anyway and then switch
708   // our state pointer to point to the new (ready to be updated) state.
709   std::memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
710
711   newSt.previous = st;
712   st = &newSt;
713
714   // Update side to move
715   k ^= Zobrist::side;
716
717   // Increment ply counters. In particular, rule50 will be reset to zero later on
718   // in case of a capture or a pawn move.
719   ++gamePly;
720   ++st->rule50;
721   ++st->pliesFromNull;
722
723   Color us = sideToMove;
724   Color them = ~us;
725   Square from = from_sq(m);
726   Square to = to_sq(m);
727   Piece pc = piece_on(from);
728   PieceType pt = type_of(pc);
729   PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
730
731   assert(color_of(pc) == us);
732   assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLING);
733   assert(captured != KING);
734
735   if (type_of(m) == CASTLING)
736   {
737       assert(pc == make_piece(us, KING));
738
739       Square rfrom, rto;
740       do_castling<true>(from, to, rfrom, rto);
741
742       captured = NO_PIECE_TYPE;
743       st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
744       k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
745   }
746
747   if (captured)
748   {
749       Square capsq = to;
750
751       // If the captured piece is a pawn, update pawn hash key, otherwise
752       // update non-pawn material.
753       if (captured == PAWN)
754       {
755           if (type_of(m) == ENPASSANT)
756           {
757               capsq += pawn_push(them);
758
759               assert(pt == PAWN);
760               assert(to == st->epSquare);
761               assert(relative_rank(us, to) == RANK_6);
762               assert(piece_on(to) == NO_PIECE);
763               assert(piece_on(capsq) == make_piece(them, PAWN));
764
765               board[capsq] = NO_PIECE;
766           }
767
768           st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
769       }
770       else
771           st->npMaterial[them] -= PieceValue[MG][captured];
772
773       // Update board and piece lists
774       remove_piece(capsq, them, captured);
775
776       // Update material hash key and prefetch access to materialTable
777       k ^= Zobrist::psq[them][captured][capsq];
778       st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]];
779       prefetch((char*)thisThread->materialTable[st->materialKey]);
780
781       // Update incremental scores
782       st->psq -= psq[them][captured][capsq];
783
784       // Reset rule 50 counter
785       st->rule50 = 0;
786   }
787
788   // Update hash key
789   k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
790
791   // Reset en passant square
792   if (st->epSquare != SQ_NONE)
793   {
794       k ^= Zobrist::enpassant[file_of(st->epSquare)];
795       st->epSquare = SQ_NONE;
796   }
797
798   // Update castling rights if needed
799   if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
800   {
801       int cr = castlingRightsMask[from] | castlingRightsMask[to];
802       k ^= Zobrist::castling[st->castlingRights & cr];
803       st->castlingRights &= ~cr;
804   }
805
806   // Prefetch TT access as soon as we know the new hash key
807   prefetch((char*)TT.first_entry(k));
808
809   // Move the piece. The tricky Chess960 castling is handled earlier
810   if (type_of(m) != CASTLING)
811       move_piece(from, to, us, pt);
812
813   // If the moving piece is a pawn do some special extra work
814   if (pt == PAWN)
815   {
816       // Set en-passant square if the moved pawn can be captured
817       if (   (int(to) ^ int(from)) == 16
818           && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
819       {
820           st->epSquare = Square((from + to) / 2);
821           k ^= Zobrist::enpassant[file_of(st->epSquare)];
822       }
823
824       else if (type_of(m) == PROMOTION)
825       {
826           PieceType promotion = promotion_type(m);
827
828           assert(relative_rank(us, to) == RANK_8);
829           assert(promotion >= KNIGHT && promotion <= QUEEN);
830
831           remove_piece(to, us, PAWN);
832           put_piece(to, us, promotion);
833
834           // Update hash keys
835           k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
836           st->pawnKey ^= Zobrist::psq[us][PAWN][to];
837           st->materialKey ^=  Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
838                             ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
839
840           // Update incremental score
841           st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
842
843           // Update material
844           st->npMaterial[us] += PieceValue[MG][promotion];
845       }
846
847       // Update pawn hash key and prefetch access to pawnsTable
848       st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
849       prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
850
851       // Reset rule 50 draw counter
852       st->rule50 = 0;
853   }
854
855   // Update incremental scores
856   st->psq += psq[us][pt][to] - psq[us][pt][from];
857
858   // Set capture piece
859   st->capturedType = captured;
860
861   // Update the key with the final value
862   st->key = k;
863
864   // Update checkers bitboard: piece must be already moved due to attacks_from()
865   st->checkersBB = 0;
866
867   if (moveIsCheck)
868   {
869       if (type_of(m) != NORMAL)
870           st->checkersBB = attackers_to(king_square(them)) & pieces(us);
871       else
872       {
873           // Direct checks
874           if (ci.checkSq[pt] & to)
875               st->checkersBB |= to;
876
877           // Discovered checks
878           if (unlikely(ci.dcCandidates) && (ci.dcCandidates & from))
879           {
880               if (pt != ROOK)
881                   st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
882
883               if (pt != BISHOP)
884                   st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
885           }
886       }
887   }
888
889   sideToMove = ~sideToMove;
890
891   assert(pos_is_ok());
892 }
893
894
895 /// Position::undo_move() unmakes a move. When it returns, the position should
896 /// be restored to exactly the same state as before the move was made.
897
898 void Position::undo_move(Move m) {
899
900   assert(is_ok(m));
901
902   sideToMove = ~sideToMove;
903
904   Color us = sideToMove;
905   Square from = from_sq(m);
906   Square to = to_sq(m);
907   PieceType pt = type_of(piece_on(to));
908
909   assert(empty(from) || type_of(m) == CASTLING);
910   assert(st->capturedType != KING);
911
912   if (type_of(m) == PROMOTION)
913   {
914       assert(pt == promotion_type(m));
915       assert(relative_rank(us, to) == RANK_8);
916       assert(promotion_type(m) >= KNIGHT && promotion_type(m) <= QUEEN);
917
918       remove_piece(to, us, promotion_type(m));
919       put_piece(to, us, PAWN);
920       pt = PAWN;
921   }
922
923   if (type_of(m) == CASTLING)
924   {
925       Square rfrom, rto;
926       do_castling<false>(from, to, rfrom, rto);
927   }
928   else
929   {
930       move_piece(to, from, us, pt); // Put the piece back at the source square
931
932       if (st->capturedType)
933       {
934           Square capsq = to;
935
936           if (type_of(m) == ENPASSANT)
937           {
938               capsq -= pawn_push(us);
939
940               assert(pt == PAWN);
941               assert(to == st->previous->epSquare);
942               assert(relative_rank(us, to) == RANK_6);
943               assert(piece_on(capsq) == NO_PIECE);
944           }
945
946           put_piece(capsq, ~us, st->capturedType); // Restore the captured piece
947       }
948   }
949
950   // Finally point our state pointer back to the previous state
951   st = st->previous;
952   --gamePly;
953
954   assert(pos_is_ok());
955 }
956
957
958 /// Position::do_castling() is a helper used to do/undo a castling move. This
959 /// is a bit tricky, especially in Chess960.
960 template<bool Do>
961 void Position::do_castling(Square from, Square& to, Square& rfrom, Square& rto) {
962
963   bool kingSide = to > from;
964   rfrom = to; // Castling is encoded as "king captures friendly rook"
965   rto = relative_square(sideToMove, kingSide ? SQ_F1 : SQ_D1);
966   to  = relative_square(sideToMove, kingSide ? SQ_G1 : SQ_C1);
967
968   // Remove both pieces first since squares could overlap in Chess960
969   remove_piece(Do ?  from :  to, sideToMove, KING);
970   remove_piece(Do ? rfrom : rto, sideToMove, ROOK);
971   board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
972   put_piece(Do ?  to :  from, sideToMove, KING);
973   put_piece(Do ? rto : rfrom, sideToMove, ROOK);
974 }
975
976
977 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
978 /// the side to move without executing any move on the board.
979
980 void Position::do_null_move(StateInfo& newSt) {
981
982   assert(!checkers());
983
984   std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
985
986   newSt.previous = st;
987   st = &newSt;
988
989   if (st->epSquare != SQ_NONE)
990   {
991       st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
992       st->epSquare = SQ_NONE;
993   }
994
995   st->key ^= Zobrist::side;
996   prefetch((char*)TT.first_entry(st->key));
997
998   ++st->rule50;
999   st->pliesFromNull = 0;
1000
1001   sideToMove = ~sideToMove;
1002
1003   assert(pos_is_ok());
1004 }
1005
1006 void Position::undo_null_move() {
1007
1008   assert(!checkers());
1009
1010   st = st->previous;
1011   sideToMove = ~sideToMove;
1012 }
1013
1014
1015 /// Position::see() is a static exchange evaluator: It tries to estimate the
1016 /// material gain or loss resulting from a move.
1017
1018 Value Position::see_sign(Move m) const {
1019
1020   assert(is_ok(m));
1021
1022   // Early return if SEE cannot be negative because captured piece value
1023   // is not less then capturing one. Note that king moves always return
1024   // here because king midgame value is set to 0.
1025   if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
1026       return VALUE_KNOWN_WIN;
1027
1028   return see(m);
1029 }
1030
1031 Value Position::see(Move m) const {
1032
1033   Square from, to;
1034   Bitboard occupied, attackers, stmAttackers;
1035   Value swapList[32];
1036   int slIndex = 1;
1037   PieceType captured;
1038   Color stm;
1039
1040   assert(is_ok(m));
1041
1042   from = from_sq(m);
1043   to = to_sq(m);
1044   swapList[0] = PieceValue[MG][piece_on(to)];
1045   stm = color_of(piece_on(from));
1046   occupied = pieces() ^ from;
1047
1048   // Castling moves are implemented as king capturing the rook so cannot be
1049   // handled correctly. Simply return 0 that is always the correct value
1050   // unless in the rare case the rook ends up under attack.
1051   if (type_of(m) == CASTLING)
1052       return VALUE_ZERO;
1053
1054   if (type_of(m) == ENPASSANT)
1055   {
1056       occupied ^= to - pawn_push(stm); // Remove the captured pawn
1057       swapList[0] = PieceValue[MG][PAWN];
1058   }
1059
1060   // Find all attackers to the destination square, with the moving piece
1061   // removed, but possibly an X-ray attacker added behind it.
1062   attackers = attackers_to(to, occupied) & occupied;
1063
1064   // If the opponent has no attackers we are finished
1065   stm = ~stm;
1066   stmAttackers = attackers & pieces(stm);
1067   if (!stmAttackers)
1068       return swapList[0];
1069
1070   // The destination square is defended, which makes things rather more
1071   // difficult to compute. We proceed by building up a "swap list" containing
1072   // the material gain or loss at each stop in a sequence of captures to the
1073   // destination square, where the sides alternately capture, and always
1074   // capture with the least valuable piece. After each capture, we look for
1075   // new X-ray attacks from behind the capturing piece.
1076   captured = type_of(piece_on(from));
1077
1078   do {
1079       assert(slIndex < 32);
1080
1081       // Add the new entry to the swap list
1082       swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1083
1084       // Locate and remove the next least valuable attacker
1085       captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1086
1087       // Stop before processing a king capture
1088       if (captured == KING)
1089       {
1090           if (stmAttackers == attackers)
1091               ++slIndex;
1092
1093           break;
1094       }
1095
1096       stm = ~stm;
1097       stmAttackers = attackers & pieces(stm);
1098       ++slIndex;
1099
1100   } while (stmAttackers);
1101
1102   // Having built the swap list, we negamax through it to find the best
1103   // achievable score from the point of view of the side to move.
1104   while (--slIndex)
1105       swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1106
1107   return swapList[0];
1108 }
1109
1110
1111 /// Position::is_draw() tests whether the position is drawn by material, 50 moves
1112 /// rule or repetition. It does not detect stalemates.
1113
1114 bool Position::is_draw() const {
1115
1116   if (   !pieces(PAWN)
1117       && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1118       return true;
1119
1120   if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1121       return true;
1122
1123   StateInfo* stp = st;
1124   for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1125   {
1126       stp = stp->previous->previous;
1127
1128       if (stp->key == st->key)
1129           return true; // Draw at first repetition
1130   }
1131
1132   return false;
1133 }
1134
1135
1136 /// Position::flip() flips position with the white and black sides reversed. This
1137 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1138
1139 static char toggle_case(char c) {
1140   return char(islower(c) ? toupper(c) : tolower(c));
1141 }
1142
1143 void Position::flip() {
1144
1145   string f, token;
1146   std::stringstream ss(fen());
1147
1148   for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1149   {
1150       std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1151       f.insert(0, token + (f.empty() ? " " : "/"));
1152   }
1153
1154   ss >> token; // Active color
1155   f += (token == "w" ? "B " : "W "); // Will be lowercased later
1156
1157   ss >> token; // Castling availability
1158   f += token + " ";
1159
1160   std::transform(f.begin(), f.end(), f.begin(), toggle_case);
1161
1162   ss >> token; // En passant square
1163   f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1164
1165   std::getline(ss, token); // Half and full moves
1166   f += token;
1167
1168   set(f, is_chess960(), this_thread());
1169
1170   assert(pos_is_ok());
1171 }
1172
1173
1174 /// Position::pos_is_ok() performs some consistency checks for the position object.
1175 /// This is meant to be helpful when debugging.
1176
1177 bool Position::pos_is_ok(int* step) const {
1178
1179   // Which parts of the position should be verified?
1180   const bool all = false;
1181
1182   const bool testBitboards       = all || false;
1183   const bool testState           = all || false;
1184   const bool testKingCount       = all || false;
1185   const bool testKingCapture     = all || false;
1186   const bool testPieceCounts     = all || false;
1187   const bool testPieceList       = all || false;
1188   const bool testCastlingSquares = all || false;
1189
1190   if (step)
1191       *step = 1;
1192
1193   if (   (sideToMove != WHITE && sideToMove != BLACK)
1194       || piece_on(king_square(WHITE)) != W_KING
1195       || piece_on(king_square(BLACK)) != B_KING
1196       || (   ep_square() != SQ_NONE
1197           && relative_rank(sideToMove, ep_square()) != RANK_6))
1198       return false;
1199
1200   if (step && ++*step, testBitboards)
1201   {
1202       // The intersection of the white and black pieces must be empty
1203       if (pieces(WHITE) & pieces(BLACK))
1204           return false;
1205
1206       // The union of the white and black pieces must be equal to all
1207       // occupied squares
1208       if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1209           return false;
1210
1211       // Separate piece type bitboards must have empty intersections
1212       for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1213           for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1214               if (p1 != p2 && (pieces(p1) & pieces(p2)))
1215                   return false;
1216   }
1217
1218   if (step && ++*step, testState)
1219   {
1220       StateInfo si;
1221       set_state(&si);
1222       if (   st->key != si.key
1223           || st->pawnKey != si.pawnKey
1224           || st->materialKey != si.materialKey
1225           || st->npMaterial[WHITE] != si.npMaterial[WHITE]
1226           || st->npMaterial[BLACK] != si.npMaterial[BLACK]
1227           || st->psq != si.psq
1228           || st->checkersBB != si.checkersBB)
1229           return false;
1230   }
1231
1232   if (step && ++*step, testKingCount)
1233       if (   std::count(board, board + SQUARE_NB, W_KING) != 1
1234           || std::count(board, board + SQUARE_NB, B_KING) != 1)
1235           return false;
1236
1237   if (step && ++*step, testKingCapture)
1238       if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1239           return false;
1240
1241   if (step && ++*step, testPieceCounts)
1242       for (Color c = WHITE; c <= BLACK; ++c)
1243           for (PieceType pt = PAWN; pt <= KING; ++pt)
1244               if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1245                   return false;
1246
1247   if (step && ++*step, testPieceList)
1248       for (Color c = WHITE; c <= BLACK; ++c)
1249           for (PieceType pt = PAWN; pt <= KING; ++pt)
1250               for (int i = 0; i < pieceCount[c][pt];  ++i)
1251                   if (   board[pieceList[c][pt][i]] != make_piece(c, pt)
1252                       || index[pieceList[c][pt][i]] != i)
1253                       return false;
1254
1255   if (step && ++*step, testCastlingSquares)
1256       for (Color c = WHITE; c <= BLACK; ++c)
1257           for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1258           {
1259               if (!can_castle(c | s))
1260                   continue;
1261
1262               if (  (castlingRightsMask[king_square(c)] & (c | s)) != (c | s)
1263                   || piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1264                   || castlingRightsMask[castlingRookSquare[c | s]] != (c | s))
1265                   return false;
1266           }
1267
1268   return true;
1269 }