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