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