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