Raise penalty for knight attacked by pawn
[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, gives_check(m, ci));
694 }
695
696 void Position::do_move(Move m, StateInfo& newSt, 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((char*)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((char*)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   // Calculate checkers bitboard (if move is check)
860   st->checkersBB = moveIsCheck ? attackers_to(king_square(them)) & pieces(us) : 0;
861
862   sideToMove = ~sideToMove;
863
864   assert(pos_is_ok());
865 }
866
867
868 /// Position::undo_move() unmakes a move. When it returns, the position should
869 /// be restored to exactly the same state as before the move was made.
870
871 void Position::undo_move(Move m) {
872
873   assert(is_ok(m));
874
875   sideToMove = ~sideToMove;
876
877   Color us = sideToMove;
878   Square from = from_sq(m);
879   Square to = to_sq(m);
880   PieceType pt = type_of(piece_on(to));
881
882   assert(empty(from) || type_of(m) == CASTLING);
883   assert(st->capturedType != KING);
884
885   if (type_of(m) == PROMOTION)
886   {
887       assert(pt == promotion_type(m));
888       assert(relative_rank(us, to) == RANK_8);
889       assert(promotion_type(m) >= KNIGHT && promotion_type(m) <= QUEEN);
890
891       remove_piece(to, us, promotion_type(m));
892       put_piece(to, us, PAWN);
893       pt = PAWN;
894   }
895
896   if (type_of(m) == CASTLING)
897   {
898       Square rfrom, rto;
899       do_castling<false>(from, to, rfrom, rto);
900   }
901   else
902   {
903       move_piece(to, from, us, pt); // Put the piece back at the source square
904
905       if (st->capturedType)
906       {
907           Square capsq = to;
908
909           if (type_of(m) == ENPASSANT)
910           {
911               capsq -= pawn_push(us);
912
913               assert(pt == PAWN);
914               assert(to == st->previous->epSquare);
915               assert(relative_rank(us, to) == RANK_6);
916               assert(piece_on(capsq) == NO_PIECE);
917           }
918
919           put_piece(capsq, ~us, st->capturedType); // Restore the captured piece
920       }
921   }
922
923   // Finally point our state pointer back to the previous state
924   st = st->previous;
925   --gamePly;
926
927   assert(pos_is_ok());
928 }
929
930
931 /// Position::do_castling() is a helper used to do/undo a castling move. This
932 /// is a bit tricky, especially in Chess960.
933 template<bool Do>
934 void Position::do_castling(Square from, Square& to, Square& rfrom, Square& rto) {
935
936   bool kingSide = to > from;
937   rfrom = to; // Castling is encoded as "king captures friendly rook"
938   rto = relative_square(sideToMove, kingSide ? SQ_F1 : SQ_D1);
939   to  = relative_square(sideToMove, kingSide ? SQ_G1 : SQ_C1);
940
941   // Remove both pieces first since squares could overlap in Chess960
942   remove_piece(Do ?  from :  to, sideToMove, KING);
943   remove_piece(Do ? rfrom : rto, sideToMove, ROOK);
944   board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
945   put_piece(Do ?  to :  from, sideToMove, KING);
946   put_piece(Do ? rto : rfrom, sideToMove, ROOK);
947 }
948
949
950 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
951 /// the side to move without executing any move on the board.
952
953 void Position::do_null_move(StateInfo& newSt) {
954
955   assert(!checkers());
956
957   std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
958
959   newSt.previous = st;
960   st = &newSt;
961
962   if (st->epSquare != SQ_NONE)
963   {
964       st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
965       st->epSquare = SQ_NONE;
966   }
967
968   st->key ^= Zobrist::side;
969   prefetch((char*)TT.first_entry(st->key));
970
971   ++st->rule50;
972   st->pliesFromNull = 0;
973
974   sideToMove = ~sideToMove;
975
976   assert(pos_is_ok());
977 }
978
979 void Position::undo_null_move() {
980
981   assert(!checkers());
982
983   st = st->previous;
984   sideToMove = ~sideToMove;
985 }
986
987
988 /// Position::key_after() computes the new hash key after the given move. Needed
989 /// for speculative prefetch. It doesn't recognize special moves like castling,
990 /// en-passant and promotions.
991
992 Key Position::key_after(Move m) const {
993
994   Color us = sideToMove;
995   Square from = from_sq(m);
996   Square to = to_sq(m);
997   PieceType pt = type_of(piece_on(from));
998   PieceType captured = type_of(piece_on(to));
999   Key k = st->key ^ Zobrist::side;
1000
1001   if (captured)
1002       k ^= Zobrist::psq[~us][captured][to];
1003
1004   return k ^ Zobrist::psq[us][pt][to] ^ Zobrist::psq[us][pt][from];
1005 }
1006
1007
1008 /// Position::see() is a static exchange evaluator: It tries to estimate the
1009 /// material gain or loss resulting from a move.
1010
1011 Value Position::see_sign(Move m) const {
1012
1013   assert(is_ok(m));
1014
1015   // Early return if SEE cannot be negative because captured piece value
1016   // is not less then capturing one. Note that king moves always return
1017   // here because king midgame value is set to 0.
1018   if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
1019       return VALUE_KNOWN_WIN;
1020
1021   return see(m);
1022 }
1023
1024 Value Position::see(Move m) const {
1025
1026   Square from, to;
1027   Bitboard occupied, attackers, stmAttackers;
1028   Value swapList[32];
1029   int slIndex = 1;
1030   PieceType captured;
1031   Color stm;
1032
1033   assert(is_ok(m));
1034
1035   from = from_sq(m);
1036   to = to_sq(m);
1037   swapList[0] = PieceValue[MG][piece_on(to)];
1038   stm = color_of(piece_on(from));
1039   occupied = pieces() ^ from;
1040
1041   // Castling moves are implemented as king capturing the rook so cannot
1042   // be handled correctly. Simply return VALUE_ZERO that is always correct
1043   // unless in the rare case the rook ends up under attack.
1044   if (type_of(m) == CASTLING)
1045       return VALUE_ZERO;
1046
1047   if (type_of(m) == ENPASSANT)
1048   {
1049       occupied ^= to - pawn_push(stm); // Remove the captured pawn
1050       swapList[0] = PieceValue[MG][PAWN];
1051   }
1052
1053   // Find all attackers to the destination square, with the moving piece
1054   // removed, but possibly an X-ray attacker added behind it.
1055   attackers = attackers_to(to, occupied) & occupied;
1056
1057   // If the opponent has no attackers we are finished
1058   stm = ~stm;
1059   stmAttackers = attackers & pieces(stm);
1060   if (!stmAttackers)
1061       return swapList[0];
1062
1063   // The destination square is defended, which makes things rather more
1064   // difficult to compute. We proceed by building up a "swap list" containing
1065   // the material gain or loss at each stop in a sequence of captures to the
1066   // destination square, where the sides alternately capture, and always
1067   // capture with the least valuable piece. After each capture, we look for
1068   // new X-ray attacks from behind the capturing piece.
1069   captured = type_of(piece_on(from));
1070
1071   do {
1072       assert(slIndex < 32);
1073
1074       // Add the new entry to the swap list
1075       swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1076
1077       // Locate and remove the next least valuable attacker
1078       captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1079
1080       // Stop before processing a king capture
1081       if (captured == KING)
1082       {
1083           if (stmAttackers == attackers)
1084               ++slIndex;
1085
1086           break;
1087       }
1088
1089       stm = ~stm;
1090       stmAttackers = attackers & pieces(stm);
1091       ++slIndex;
1092
1093   } while (stmAttackers);
1094
1095   // Having built the swap list, we negamax through it to find the best
1096   // achievable score from the point of view of the side to move.
1097   while (--slIndex)
1098       swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1099
1100   return swapList[0];
1101 }
1102
1103
1104 /// Position::is_draw() tests whether the position is drawn by material, 50 moves
1105 /// rule or repetition. It does not detect stalemates.
1106
1107 bool Position::is_draw() const {
1108
1109   if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1110       return true;
1111
1112   StateInfo* stp = st;
1113   for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1114   {
1115       stp = stp->previous->previous;
1116
1117       if (stp->key == st->key)
1118           return true; // Draw at first repetition
1119   }
1120
1121   return false;
1122 }
1123
1124
1125 /// Position::flip() flips position with the white and black sides reversed. This
1126 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1127
1128 static char toggle_case(char c) {
1129   return char(islower(c) ? toupper(c) : tolower(c));
1130 }
1131
1132 void Position::flip() {
1133
1134   string f, token;
1135   std::stringstream ss(fen());
1136
1137   for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1138   {
1139       std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1140       f.insert(0, token + (f.empty() ? " " : "/"));
1141   }
1142
1143   ss >> token; // Active color
1144   f += (token == "w" ? "B " : "W "); // Will be lowercased later
1145
1146   ss >> token; // Castling availability
1147   f += token + " ";
1148
1149   std::transform(f.begin(), f.end(), f.begin(), toggle_case);
1150
1151   ss >> token; // En passant square
1152   f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1153
1154   std::getline(ss, token); // Half and full moves
1155   f += token;
1156
1157   set(f, is_chess960(), this_thread());
1158
1159   assert(pos_is_ok());
1160 }
1161
1162
1163 /// Position::pos_is_ok() performs some consistency checks for the position object.
1164 /// This is meant to be helpful when debugging.
1165
1166 bool Position::pos_is_ok(int* step) const {
1167
1168   // Which parts of the position should be verified?
1169   const bool all = false;
1170
1171   const bool testBitboards       = all || false;
1172   const bool testState           = all || false;
1173   const bool testKingCount       = all || false;
1174   const bool testKingCapture     = all || false;
1175   const bool testPieceCounts     = all || false;
1176   const bool testPieceList       = all || false;
1177   const bool testCastlingSquares = all || false;
1178
1179   if (step)
1180       *step = 1;
1181
1182   if (   (sideToMove != WHITE && sideToMove != BLACK)
1183       || piece_on(king_square(WHITE)) != W_KING
1184       || piece_on(king_square(BLACK)) != B_KING
1185       || (   ep_square() != SQ_NONE
1186           && relative_rank(sideToMove, ep_square()) != RANK_6))
1187       return false;
1188
1189   if (step && ++*step, testBitboards)
1190   {
1191       // The intersection of the white and black pieces must be empty
1192       if (pieces(WHITE) & pieces(BLACK))
1193           return false;
1194
1195       // The union of the white and black pieces must be equal to all
1196       // occupied squares
1197       if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1198           return false;
1199
1200       // Separate piece type bitboards must have empty intersections
1201       for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1202           for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1203               if (p1 != p2 && (pieces(p1) & pieces(p2)))
1204                   return false;
1205   }
1206
1207   if (step && ++*step, testState)
1208   {
1209       StateInfo si;
1210       set_state(&si);
1211       if (   st->key != si.key
1212           || st->pawnKey != si.pawnKey
1213           || st->materialKey != si.materialKey
1214           || st->nonPawnMaterial[WHITE] != si.nonPawnMaterial[WHITE]
1215           || st->nonPawnMaterial[BLACK] != si.nonPawnMaterial[BLACK]
1216           || st->psq != si.psq
1217           || st->checkersBB != si.checkersBB)
1218           return false;
1219   }
1220
1221   if (step && ++*step, testKingCount)
1222       if (   std::count(board, board + SQUARE_NB, W_KING) != 1
1223           || std::count(board, board + SQUARE_NB, B_KING) != 1)
1224           return false;
1225
1226   if (step && ++*step, testKingCapture)
1227       if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1228           return false;
1229
1230   if (step && ++*step, testPieceCounts)
1231       for (Color c = WHITE; c <= BLACK; ++c)
1232           for (PieceType pt = PAWN; pt <= KING; ++pt)
1233               if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1234                   return false;
1235
1236   if (step && ++*step, testPieceList)
1237       for (Color c = WHITE; c <= BLACK; ++c)
1238           for (PieceType pt = PAWN; pt <= KING; ++pt)
1239               for (int i = 0; i < pieceCount[c][pt];  ++i)
1240                   if (   board[pieceList[c][pt][i]] != make_piece(c, pt)
1241                       || index[pieceList[c][pt][i]] != i)
1242                       return false;
1243
1244   if (step && ++*step, testCastlingSquares)
1245       for (Color c = WHITE; c <= BLACK; ++c)
1246           for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1247           {
1248               if (!can_castle(c | s))
1249                   continue;
1250
1251               if (  (castlingRightsMask[king_square(c)] & (c | s)) != (c | s)
1252                   || piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1253                   || castlingRightsMask[castlingRookSquare[c | s]] != (c | s))
1254                   return false;
1255           }
1256
1257   return true;
1258 }