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