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