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