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