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