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