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