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