Move game_phase() to material.cpp
[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::slider_blockers() returns a bitboard of all the pieces (both colors)
454 /// that are blocking attacks on the square 's' from 'sliders'. A piece blocks a
455 /// slider if removing that piece from the board would result in a position where
456 /// square 's' is attacked. For example, a king-attack blocking piece can be either
457 /// a pinned or a discovered check piece, according if its color is the opposite
458 /// or the same of the color of the slider.
459
460 Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const {
461
462   Bitboard result = 0;
463   pinners = 0;
464
465   // Snipers are sliders that attack 's' when a piece is removed
466   Bitboard snipers = (  (PseudoAttacks[  ROOK][s] & pieces(QUEEN, ROOK))
467                       | (PseudoAttacks[BISHOP][s] & pieces(QUEEN, BISHOP))) & sliders;
468
469   while (snipers)
470   {
471     Square sniperSq = pop_lsb(&snipers);
472     Bitboard b = between_bb(s, sniperSq) & pieces();
473
474     if (!more_than_one(b))
475     {
476         result |= b;
477         if (b & pieces(color_of(piece_on(s))))
478             pinners |= sniperSq;
479     }
480   }
481   return result;
482 }
483
484
485 /// Position::attackers_to() computes a bitboard of all pieces which attack a
486 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
487
488 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
489
490   return  (attacks_from<PAWN>(s, BLACK)    & pieces(WHITE, PAWN))
491         | (attacks_from<PAWN>(s, WHITE)    & pieces(BLACK, PAWN))
492         | (attacks_from<KNIGHT>(s)         & pieces(KNIGHT))
493         | (attacks_bb<  ROOK>(s, occupied) & pieces(  ROOK, QUEEN))
494         | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
495         | (attacks_from<KING>(s)           & pieces(KING));
496 }
497
498
499 /// Position::legal() tests whether a pseudo-legal move is legal
500
501 bool Position::legal(Move m) const {
502
503   assert(is_ok(m));
504
505   Color us = sideToMove;
506   Square from = from_sq(m);
507
508   assert(color_of(moved_piece(m)) == us);
509   assert(piece_on(square<KING>(us)) == make_piece(us, KING));
510
511   // En passant captures are a tricky special case. Because they are rather
512   // uncommon, we do it simply by testing whether the king is attacked after
513   // the move is made.
514   if (type_of(m) == ENPASSANT)
515   {
516       Square ksq = square<KING>(us);
517       Square to = to_sq(m);
518       Square capsq = to - pawn_push(us);
519       Bitboard occupied = (pieces() ^ from ^ capsq) | to;
520
521       assert(to == ep_square());
522       assert(moved_piece(m) == make_piece(us, PAWN));
523       assert(piece_on(capsq) == make_piece(~us, PAWN));
524       assert(piece_on(to) == NO_PIECE);
525
526       return   !(attacks_bb<  ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
527             && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
528   }
529
530   // If the moving piece is a king, check whether the destination
531   // square is attacked by the opponent. Castling moves are checked
532   // for legality during move generation.
533   if (type_of(piece_on(from)) == KING)
534       return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
535
536   // A non-king move is legal if and only if it is not pinned or it
537   // is moving along the ray towards or away from the king.
538   return   !(pinned_pieces(us) & from)
539         ||  aligned(from, to_sq(m), square<KING>(us));
540 }
541
542
543 /// Position::pseudo_legal() takes a random move and tests whether the move is
544 /// pseudo legal. It is used to validate moves from TT that can be corrupted
545 /// due to SMP concurrent access or hash position key aliasing.
546
547 bool Position::pseudo_legal(const Move m) const {
548
549   Color us = sideToMove;
550   Square from = from_sq(m);
551   Square to = to_sq(m);
552   Piece pc = moved_piece(m);
553
554   // Use a slower but simpler function for uncommon cases
555   if (type_of(m) != NORMAL)
556       return MoveList<LEGAL>(*this).contains(m);
557
558   // Is not a promotion, so promotion piece must be empty
559   if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
560       return false;
561
562   // If the 'from' square is not occupied by a piece belonging to the side to
563   // move, the move is obviously not legal.
564   if (pc == NO_PIECE || color_of(pc) != us)
565       return false;
566
567   // The destination square cannot be occupied by a friendly piece
568   if (pieces(us) & to)
569       return false;
570
571   // Handle the special case of a pawn move
572   if (type_of(pc) == PAWN)
573   {
574       // We have already handled promotion moves, so destination
575       // cannot be on the 8th/1st rank.
576       if (rank_of(to) == relative_rank(us, RANK_8))
577           return false;
578
579       if (   !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
580           && !((from + pawn_push(us) == to) && empty(to))       // Not a single push
581           && !(   (from + 2 * pawn_push(us) == to)              // Not a double push
582                && (rank_of(from) == relative_rank(us, RANK_2))
583                && empty(to)
584                && empty(to - pawn_push(us))))
585           return false;
586   }
587   else if (!(attacks_from(type_of(pc), from) & to))
588       return false;
589
590   // Evasions generator already takes care to avoid some kind of illegal moves
591   // and legal() relies on this. We therefore have to take care that the same
592   // kind of moves are filtered out here.
593   if (checkers())
594   {
595       if (type_of(pc) != KING)
596       {
597           // Double check? In this case a king move is required
598           if (more_than_one(checkers()))
599               return false;
600
601           // Our move must be a blocking evasion or a capture of the checking piece
602           if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
603               return false;
604       }
605       // In case of king moves under check we have to remove king so as to catch
606       // invalid moves like b1a1 when opposite queen is on c1.
607       else if (attackers_to(to, pieces() ^ from) & pieces(~us))
608           return false;
609   }
610
611   return true;
612 }
613
614
615 /// Position::gives_check() tests whether a pseudo-legal move gives a check
616
617 bool Position::gives_check(Move m) const {
618
619   assert(is_ok(m));
620   assert(color_of(moved_piece(m)) == sideToMove);
621
622   Square from = from_sq(m);
623   Square to = to_sq(m);
624
625   // Is there a direct check?
626   if (st->checkSquares[type_of(piece_on(from))] & to)
627       return true;
628
629   // Is there a discovered check?
630   if (   (discovered_check_candidates() & from)
631       && !aligned(from, to, square<KING>(~sideToMove)))
632       return true;
633
634   switch (type_of(m))
635   {
636   case NORMAL:
637       return false;
638
639   case PROMOTION:
640       return attacks_bb(promotion_type(m), to, pieces() ^ from) & square<KING>(~sideToMove);
641
642   // En passant capture with check? We have already handled the case
643   // of direct checks and ordinary discovered check, so the only case we
644   // need to handle is the unusual case of a discovered check through
645   // the captured pawn.
646   case ENPASSANT:
647   {
648       Square capsq = make_square(file_of(to), rank_of(from));
649       Bitboard b = (pieces() ^ from ^ capsq) | to;
650
651       return  (attacks_bb<  ROOK>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))
652             | (attacks_bb<BISHOP>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, BISHOP));
653   }
654   case CASTLING:
655   {
656       Square kfrom = from;
657       Square rfrom = to; // Castling is encoded as 'King captures the rook'
658       Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
659       Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
660
661       return   (PseudoAttacks[ROOK][rto] & square<KING>(~sideToMove))
662             && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & square<KING>(~sideToMove));
663   }
664   default:
665       assert(false);
666       return false;
667   }
668 }
669
670
671 /// Position::do_move() makes a move, and saves all information necessary
672 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
673 /// moves should be filtered out before this function is called.
674
675 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
676
677   assert(is_ok(m));
678   assert(&newSt != st);
679
680   thisThread->nodes.fetch_add(1, std::memory_order_relaxed);
681   Key k = st->key ^ Zobrist::side;
682
683   // Copy some fields of the old state to our new StateInfo object except the
684   // ones which are going to be recalculated from scratch anyway and then switch
685   // our state pointer to point to the new (ready to be updated) state.
686   std::memcpy(&newSt, st, offsetof(StateInfo, key));
687   newSt.previous = st;
688   st = &newSt;
689
690   // Increment ply counters. In particular, rule50 will be reset to zero later on
691   // in case of a capture or a pawn move.
692   ++gamePly;
693   ++st->rule50;
694   ++st->pliesFromNull;
695
696   Color us = sideToMove;
697   Color them = ~us;
698   Square from = from_sq(m);
699   Square to = to_sq(m);
700   Piece pc = piece_on(from);
701   Piece captured = type_of(m) == ENPASSANT ? make_piece(them, PAWN) : piece_on(to);
702
703   assert(color_of(pc) == us);
704   assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us));
705   assert(type_of(captured) != KING);
706
707   if (type_of(m) == CASTLING)
708   {
709       assert(pc == make_piece(us, KING));
710       assert(captured == make_piece(us, ROOK));
711
712       Square rfrom, rto;
713       do_castling<true>(us, from, to, rfrom, rto);
714
715       st->psq += PSQT::psq[captured][rto] - PSQT::psq[captured][rfrom];
716       k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
717       captured = NO_PIECE;
718   }
719
720   if (captured)
721   {
722       Square capsq = to;
723
724       // If the captured piece is a pawn, update pawn hash key, otherwise
725       // update non-pawn material.
726       if (type_of(captured) == PAWN)
727       {
728           if (type_of(m) == ENPASSANT)
729           {
730               capsq -= pawn_push(us);
731
732               assert(pc == make_piece(us, PAWN));
733               assert(to == st->epSquare);
734               assert(relative_rank(us, to) == RANK_6);
735               assert(piece_on(to) == NO_PIECE);
736               assert(piece_on(capsq) == make_piece(them, PAWN));
737
738               board[capsq] = NO_PIECE; // Not done by remove_piece()
739           }
740
741           st->pawnKey ^= Zobrist::psq[captured][capsq];
742       }
743       else
744           st->nonPawnMaterial[them] -= PieceValue[MG][captured];
745
746       // Update board and piece lists
747       remove_piece(captured, capsq);
748
749       // Update material hash key and prefetch access to materialTable
750       k ^= Zobrist::psq[captured][capsq];
751       st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];
752       prefetch(thisThread->materialTable[st->materialKey]);
753
754       // Update incremental scores
755       st->psq -= PSQT::psq[captured][capsq];
756
757       // Reset rule 50 counter
758       st->rule50 = 0;
759   }
760
761   // Update hash key
762   k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
763
764   // Reset en passant square
765   if (st->epSquare != SQ_NONE)
766   {
767       k ^= Zobrist::enpassant[file_of(st->epSquare)];
768       st->epSquare = SQ_NONE;
769   }
770
771   // Update castling rights if needed
772   if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
773   {
774       int cr = castlingRightsMask[from] | castlingRightsMask[to];
775       k ^= Zobrist::castling[st->castlingRights & cr];
776       st->castlingRights &= ~cr;
777   }
778
779   // Move the piece. The tricky Chess960 castling is handled earlier
780   if (type_of(m) != CASTLING)
781       move_piece(pc, from, to);
782
783   // If the moving piece is a pawn do some special extra work
784   if (type_of(pc) == PAWN)
785   {
786       // Set en-passant square if the moved pawn can be captured
787       if (   (int(to) ^ int(from)) == 16
788           && (attacks_from<PAWN>(to - pawn_push(us), us) & pieces(them, PAWN)))
789       {
790           st->epSquare = (from + to) / 2;
791           k ^= Zobrist::enpassant[file_of(st->epSquare)];
792       }
793
794       else if (type_of(m) == PROMOTION)
795       {
796           Piece promotion = make_piece(us, promotion_type(m));
797
798           assert(relative_rank(us, to) == RANK_8);
799           assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);
800
801           remove_piece(pc, to);
802           put_piece(promotion, to);
803
804           // Update hash keys
805           k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
806           st->pawnKey ^= Zobrist::psq[pc][to];
807           st->materialKey ^=  Zobrist::psq[promotion][pieceCount[promotion]-1]
808                             ^ Zobrist::psq[pc][pieceCount[pc]];
809
810           // Update incremental score
811           st->psq += PSQT::psq[promotion][to] - PSQT::psq[pc][to];
812
813           // Update material
814           st->nonPawnMaterial[us] += PieceValue[MG][promotion];
815       }
816
817       // Update pawn hash key and prefetch access to pawnsTable
818       st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
819       prefetch2(thisThread->pawnsTable[st->pawnKey]);
820
821       // Reset rule 50 draw counter
822       st->rule50 = 0;
823   }
824
825   // Update incremental scores
826   st->psq += PSQT::psq[pc][to] - PSQT::psq[pc][from];
827
828   // Set capture piece
829   st->capturedPiece = captured;
830
831   // Update the key with the final value
832   st->key = k;
833
834   // Calculate checkers bitboard (if move gives check)
835   st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
836
837   sideToMove = ~sideToMove;
838
839   // Update king attacks used for fast check detection
840   set_check_info(st);
841
842   assert(pos_is_ok());
843 }
844
845
846 /// Position::undo_move() unmakes a move. When it returns, the position should
847 /// be restored to exactly the same state as before the move was made.
848
849 void Position::undo_move(Move m) {
850
851   assert(is_ok(m));
852
853   sideToMove = ~sideToMove;
854
855   Color us = sideToMove;
856   Square from = from_sq(m);
857   Square to = to_sq(m);
858   Piece pc = piece_on(to);
859
860   assert(empty(from) || type_of(m) == CASTLING);
861   assert(type_of(st->capturedPiece) != KING);
862
863   if (type_of(m) == PROMOTION)
864   {
865       assert(relative_rank(us, to) == RANK_8);
866       assert(type_of(pc) == promotion_type(m));
867       assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);
868
869       remove_piece(pc, to);
870       pc = make_piece(us, PAWN);
871       put_piece(pc, to);
872   }
873
874   if (type_of(m) == CASTLING)
875   {
876       Square rfrom, rto;
877       do_castling<false>(us, from, to, rfrom, rto);
878   }
879   else
880   {
881       move_piece(pc, to, from); // Put the piece back at the source square
882
883       if (st->capturedPiece)
884       {
885           Square capsq = to;
886
887           if (type_of(m) == ENPASSANT)
888           {
889               capsq -= pawn_push(us);
890
891               assert(type_of(pc) == PAWN);
892               assert(to == st->previous->epSquare);
893               assert(relative_rank(us, to) == RANK_6);
894               assert(piece_on(capsq) == NO_PIECE);
895               assert(st->capturedPiece == make_piece(~us, PAWN));
896           }
897
898           put_piece(st->capturedPiece, capsq); // Restore the captured piece
899       }
900   }
901
902   // Finally point our state pointer back to the previous state
903   st = st->previous;
904   --gamePly;
905
906   assert(pos_is_ok());
907 }
908
909
910 /// Position::do_castling() is a helper used to do/undo a castling move. This
911 /// is a bit tricky in Chess960 where from/to squares can overlap.
912 template<bool Do>
913 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
914
915   bool kingSide = to > from;
916   rfrom = to; // Castling is encoded as "king captures friendly rook"
917   rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
918   to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
919
920   // Remove both pieces first since squares could overlap in Chess960
921   remove_piece(make_piece(us, KING), Do ? from : to);
922   remove_piece(make_piece(us, ROOK), Do ? rfrom : rto);
923   board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
924   put_piece(make_piece(us, KING), Do ? to : from);
925   put_piece(make_piece(us, ROOK), Do ? rto : rfrom);
926 }
927
928
929 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
930 /// the side to move without executing any move on the board.
931
932 void Position::do_null_move(StateInfo& newSt) {
933
934   assert(!checkers());
935   assert(&newSt != st);
936
937   std::memcpy(&newSt, st, sizeof(StateInfo));
938   newSt.previous = st;
939   st = &newSt;
940
941   if (st->epSquare != SQ_NONE)
942   {
943       st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
944       st->epSquare = SQ_NONE;
945   }
946
947   st->key ^= Zobrist::side;
948   prefetch(TT.first_entry(st->key));
949
950   ++st->rule50;
951   st->pliesFromNull = 0;
952
953   sideToMove = ~sideToMove;
954
955   set_check_info(st);
956
957   assert(pos_is_ok());
958 }
959
960 void Position::undo_null_move() {
961
962   assert(!checkers());
963
964   st = st->previous;
965   sideToMove = ~sideToMove;
966 }
967
968
969 /// Position::key_after() computes the new hash key after the given move. Needed
970 /// for speculative prefetch. It doesn't recognize special moves like castling,
971 /// en-passant and promotions.
972
973 Key Position::key_after(Move m) const {
974
975   Square from = from_sq(m);
976   Square to = to_sq(m);
977   Piece pc = piece_on(from);
978   Piece captured = piece_on(to);
979   Key k = st->key ^ Zobrist::side;
980
981   if (captured)
982       k ^= Zobrist::psq[captured][to];
983
984   return k ^ Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from];
985 }
986
987
988 /// Position::see_ge (Static Exchange Evaluation Greater or Equal) tests if the
989 /// SEE value of move is greater or equal to the given threshold. We'll use an
990 /// algorithm similar to alpha-beta pruning with a null window.
991
992 bool Position::see_ge(Move m, Value threshold) const {
993
994   assert(is_ok(m));
995
996   // Castling moves are implemented as king capturing the rook so cannot be
997   // handled correctly. Simply assume the SEE value is VALUE_ZERO that is always
998   // correct unless in the rare case the rook ends up under attack.
999   if (type_of(m) == CASTLING)
1000       return VALUE_ZERO >= threshold;
1001
1002   Square from = from_sq(m), to = to_sq(m);
1003   PieceType nextVictim = type_of(piece_on(from));
1004   Color stm = ~color_of(piece_on(from)); // First consider opponent's move
1005   Value balance; // Values of the pieces taken by us minus opponent's ones
1006   Bitboard occupied, stmAttackers;
1007
1008   if (type_of(m) == ENPASSANT)
1009   {
1010       occupied = SquareBB[to - pawn_push(~stm)]; // Remove the captured pawn
1011       balance = PieceValue[MG][PAWN];
1012   }
1013   else
1014   {
1015       balance = PieceValue[MG][piece_on(to)];
1016       occupied = 0;
1017   }
1018
1019   if (balance < threshold)
1020       return false;
1021
1022   if (nextVictim == KING)
1023       return true;
1024
1025   balance -= PieceValue[MG][nextVictim];
1026
1027   if (balance >= threshold)
1028       return true;
1029
1030   bool relativeStm = true; // True if the opponent is to move
1031   occupied ^= pieces() ^ from ^ to;
1032
1033   // Find all attackers to the destination square, with the moving piece removed,
1034   // but possibly an X-ray attacker added behind it.
1035   Bitboard attackers = attackers_to(to, occupied) & occupied;
1036
1037   while (true)
1038   {
1039       stmAttackers = attackers & pieces(stm);
1040
1041       // Don't allow pinned pieces to attack pieces except the king as long all
1042       // pinners are on their original square.
1043       if (!(st->pinnersForKing[stm] & ~occupied))
1044           stmAttackers &= ~st->blockersForKing[stm];
1045
1046       if (!stmAttackers)
1047           return relativeStm;
1048
1049       // Locate and remove the next least valuable attacker
1050       nextVictim = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1051
1052       if (nextVictim == KING)
1053           return relativeStm == bool(attackers & pieces(~stm));
1054
1055       balance += relativeStm ?  PieceValue[MG][nextVictim]
1056                              : -PieceValue[MG][nextVictim];
1057
1058       relativeStm = !relativeStm;
1059
1060       if (relativeStm == (balance >= threshold))
1061           return relativeStm;
1062
1063       stm = ~stm;
1064   }
1065 }
1066
1067
1068 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1069 /// or by repetition. It does not detect stalemates.
1070
1071 bool Position::is_draw(int ply) const {
1072
1073   if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1074       return true;
1075
1076   int end = std::min(st->rule50, st->pliesFromNull);
1077
1078   if (end < 4)
1079     return false;
1080
1081   StateInfo* stp = st->previous->previous;
1082   int cnt = 0;
1083
1084   for (int i = 4; i <= end; i += 2)
1085   {
1086       stp = stp->previous->previous;
1087
1088       // At root position ply is 1, so return a draw score if a position
1089       // repeats once earlier but strictly after the root, or repeats twice
1090       // before or at the root.
1091       if (   stp->key == st->key
1092           && ++cnt + (ply - 1 > i) == 2)
1093           return true;
1094   }
1095
1096   return false;
1097 }
1098
1099
1100 /// Position::flip() flips position with the white and black sides reversed. This
1101 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1102
1103 void Position::flip() {
1104
1105   string f, token;
1106   std::stringstream ss(fen());
1107
1108   for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1109   {
1110       std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1111       f.insert(0, token + (f.empty() ? " " : "/"));
1112   }
1113
1114   ss >> token; // Active color
1115   f += (token == "w" ? "B " : "W "); // Will be lowercased later
1116
1117   ss >> token; // Castling availability
1118   f += token + " ";
1119
1120   std::transform(f.begin(), f.end(), f.begin(),
1121                  [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1122
1123   ss >> token; // En passant square
1124   f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1125
1126   std::getline(ss, token); // Half and full moves
1127   f += token;
1128
1129   set(f, is_chess960(), st, this_thread());
1130
1131   assert(pos_is_ok());
1132 }
1133
1134
1135 /// Position::pos_is_ok() performs some consistency checks for the
1136 /// position object and raises an asserts if something wrong is detected.
1137 /// This is meant to be helpful when debugging.
1138
1139 bool Position::pos_is_ok() const {
1140
1141   const bool Fast = true; // Quick (default) or full check?
1142
1143   if (   (sideToMove != WHITE && sideToMove != BLACK)
1144       || piece_on(square<KING>(WHITE)) != W_KING
1145       || piece_on(square<KING>(BLACK)) != B_KING
1146       || (   ep_square() != SQ_NONE
1147           && relative_rank(sideToMove, ep_square()) != RANK_6))
1148       assert(0 && "pos_is_ok: Default");
1149
1150   if (Fast)
1151       return true;
1152
1153   if (   pieceCount[W_KING] != 1
1154       || pieceCount[B_KING] != 1
1155       || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1156       assert(0 && "pos_is_ok: Kings");
1157
1158   if (   (pieces(PAWN) & (Rank1BB | Rank8BB))
1159       || pieceCount[W_PAWN] > 8
1160       || pieceCount[B_PAWN] > 8)
1161       assert(0 && "pos_is_ok: Pawns");
1162
1163   if (   (pieces(WHITE) & pieces(BLACK))
1164       || (pieces(WHITE) | pieces(BLACK)) != pieces()
1165       || popcount(pieces(WHITE)) > 16
1166       || popcount(pieces(BLACK)) > 16)
1167       assert(0 && "pos_is_ok: Bitboards");
1168
1169   for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1170       for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1171           if (p1 != p2 && (pieces(p1) & pieces(p2)))
1172               assert(0 && "pos_is_ok: Bitboards");
1173
1174   StateInfo si = *st;
1175   set_state(&si);
1176   if (std::memcmp(&si, st, sizeof(StateInfo)))
1177       assert(0 && "pos_is_ok: State");
1178
1179   for (Piece pc : Pieces)
1180   {
1181       if (   pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc)))
1182           || pieceCount[pc] != std::count(board, board + SQUARE_NB, pc))
1183           assert(0 && "pos_is_ok: Pieces");
1184
1185       for (int i = 0; i < pieceCount[pc]; ++i)
1186           if (board[pieceList[pc][i]] != pc || index[pieceList[pc][i]] != i)
1187               assert(0 && "pos_is_ok: Index");
1188   }
1189
1190   for (Color c = WHITE; c <= BLACK; ++c)
1191       for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1192       {
1193           if (!can_castle(c | s))
1194               continue;
1195
1196           if (   piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1197               || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1198               || (castlingRightsMask[square<KING>(c)] & (c | s)) != (c | s))
1199               assert(0 && "pos_is_ok: Castling");
1200       }
1201
1202   return true;
1203 }