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