Fix indentation in struct FromToStats
[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 <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
36 using std::string;
37
38 namespace PSQT {
39   extern Score psq[PIECE_NB][SQUARE_NB];
40 }
41
42 namespace Zobrist {
43
44   Key psq[PIECE_NB][SQUARE_NB];
45   Key enpassant[FILE_NB];
46   Key castling[CASTLING_RIGHT_NB];
47   Key side;
48 }
49
50 namespace {
51
52 const string PieceToChar(" PNBRQK  pnbrqk");
53
54 // min_attacker() is a helper function used by see() to locate the least
55 // valuable attacker for the side to move, remove the attacker we just found
56 // from the bitboards and scan for new X-ray attacks behind it.
57
58 template<int Pt>
59 PieceType min_attacker(const Bitboard* bb, Square to, Bitboard stmAttackers,
60                        Bitboard& occupied, Bitboard& attackers) {
61
62   Bitboard b = stmAttackers & bb[Pt];
63   if (!b)
64       return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
65
66   occupied ^= b & ~(b - 1);
67
68   if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
69       attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
70
71   if (Pt == ROOK || Pt == QUEEN)
72       attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
73
74   attackers &= occupied; // After X-ray that may add already processed pieces
75   return (PieceType)Pt;
76 }
77
78 template<>
79 PieceType min_attacker<KING>(const Bitboard*, Square, Bitboard, Bitboard&, Bitboard&) {
80   return KING; // No need to update bitboards: it is the last cycle
81 }
82
83 } // namespace
84
85
86 /// operator<<(Position) returns an ASCII representation of the position
87
88 std::ostream& operator<<(std::ostream& os, const Position& pos) {
89
90   os << "\n +---+---+---+---+---+---+---+---+\n";
91
92   for (Rank r = RANK_8; r >= RANK_1; --r)
93   {
94       for (File f = FILE_A; f <= FILE_H; ++f)
95           os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
96
97       os << " |\n +---+---+---+---+---+---+---+---+\n";
98   }
99
100   os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
101      << std::setfill('0') << std::setw(16) << pos.key() << std::dec << "\nCheckers: ";
102
103   for (Bitboard b = pos.checkers(); b; )
104       os << UCI::square(pop_lsb(&b)) << " ";
105
106   return os;
107 }
108
109
110 /// Position::init() initializes at startup the various arrays used to compute
111 /// hash keys.
112
113 void Position::init() {
114
115   PRNG rng(1070372);
116
117   for (Piece pc : Pieces)
118       for (Square s = SQ_A1; s <= SQ_H8; ++s)
119           Zobrist::psq[pc][s] = rng.rand<Key>();
120
121   for (File f = FILE_A; f <= FILE_H; ++f)
122       Zobrist::enpassant[f] = rng.rand<Key>();
123
124   for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
125   {
126       Zobrist::castling[cr] = 0;
127       Bitboard b = cr;
128       while (b)
129       {
130           Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
131           Zobrist::castling[cr] ^= k ? k : rng.rand<Key>();
132       }
133   }
134
135   Zobrist::side = 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], 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(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), si->pinnersForKing[WHITE]);
300   si->blockersForKing[BLACK] = slider_blockers(pieces(WHITE), square<KING>(BLACK), si->pinnersForKing[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[pc][s];
332       si->psq += PSQT::psq[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[piece_on(s)][s];
347   }
348
349   for (Piece pc : Pieces)
350   {
351       if (type_of(pc) != PAWN && type_of(pc) != KING)
352           si->nonPawnMaterial[color_of(pc)] += pieceCount[pc] * PieceValue[MG][pc];
353
354       for (int cnt = 0; cnt < pieceCount[pc]; ++cnt)
355           si->materialKey ^= Zobrist::psq[pc][cnt];
356   }
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)
424 /// that are blocking attacks on the square 's' from 'sliders'. A piece blocks a
425 /// slider if removing that piece from the board would result in a position where
426 /// square 's' is attacked. For example, a king-attack blocking piece can be either
427 /// a pinned or a discovered check piece, according if its color is the opposite
428 /// or the same of the color of the slider. The pinners bitboard get filled with
429 /// real and potential pinners.
430
431 Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const {
432
433   Bitboard b, p, result = 0;
434
435   // Pinners are sliders that attack 's' when a pinned piece is removed
436   pinners = p = (  (PseudoAttacks[ROOK  ][s] & pieces(QUEEN, ROOK))
437                  | (PseudoAttacks[BISHOP][s] & pieces(QUEEN, BISHOP))) & sliders;
438
439   while (p)
440   {
441       b = between_bb(s, pop_lsb(&p)) & pieces();
442
443       if (!more_than_one(b))
444           result |= b;
445   }
446   return result;
447 }
448
449
450 /// Position::attackers_to() computes a bitboard of all pieces which attack a
451 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
452
453 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
454
455   return  (attacks_from<PAWN>(s, BLACK)    & pieces(WHITE, PAWN))
456         | (attacks_from<PAWN>(s, WHITE)    & pieces(BLACK, PAWN))
457         | (attacks_from<KNIGHT>(s)         & pieces(KNIGHT))
458         | (attacks_bb<ROOK  >(s, occupied) & pieces(ROOK,   QUEEN))
459         | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
460         | (attacks_from<KING>(s)           & pieces(KING));
461 }
462
463
464 /// Position::legal() tests whether a pseudo-legal move is legal
465
466 bool Position::legal(Move m) const {
467
468   assert(is_ok(m));
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_pieces(us) & 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 {
583
584   assert(is_ok(m));
585   assert(color_of(moved_piece(m)) == sideToMove);
586
587   Square from = from_sq(m);
588   Square to = to_sq(m);
589
590   // Is there a direct check?
591   if (st->checkSquares[type_of(piece_on(from))] & to)
592       return true;
593
594   // Is there a discovered check?
595   if (   (discovered_check_candidates() & from)
596       && !aligned(from, to, square<KING>(~sideToMove)))
597       return true;
598
599   switch (type_of(m))
600   {
601   case NORMAL:
602       return false;
603
604   case PROMOTION:
605       return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & square<KING>(~sideToMove);
606
607   // En passant capture with check? We have already handled the case
608   // of direct checks and ordinary discovered check, so the only case we
609   // need to handle is the unusual case of a discovered check through
610   // the captured pawn.
611   case ENPASSANT:
612   {
613       Square capsq = make_square(file_of(to), rank_of(from));
614       Bitboard b = (pieces() ^ from ^ capsq) | to;
615
616       return  (attacks_bb<  ROOK>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))
617             | (attacks_bb<BISHOP>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, BISHOP));
618   }
619   case CASTLING:
620   {
621       Square kfrom = from;
622       Square rfrom = to; // Castling is encoded as 'King captures the rook'
623       Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
624       Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
625
626       return   (PseudoAttacks[ROOK][rto] & square<KING>(~sideToMove))
627             && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & square<KING>(~sideToMove));
628   }
629   default:
630       assert(false);
631       return false;
632   }
633 }
634
635
636 /// Position::do_move() makes a move, and saves all information necessary
637 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
638 /// moves should be filtered out before this function is called.
639
640 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
641
642   assert(is_ok(m));
643   assert(&newSt != st);
644
645   ++nodes;
646   Key k = st->key ^ Zobrist::side;
647
648   // Copy some fields of the old state to our new StateInfo object except the
649   // ones which are going to be recalculated from scratch anyway and then switch
650   // our state pointer to point to the new (ready to be updated) state.
651   std::memcpy(&newSt, st, offsetof(StateInfo, key));
652   newSt.previous = st;
653   st = &newSt;
654
655   // Increment ply counters. In particular, rule50 will be reset to zero later on
656   // in case of a capture or a pawn move.
657   ++gamePly;
658   ++st->rule50;
659   ++st->pliesFromNull;
660
661   Color us = sideToMove;
662   Color them = ~us;
663   Square from = from_sq(m);
664   Square to = to_sq(m);
665   Piece pc = piece_on(from);
666   Piece captured = type_of(m) == ENPASSANT ? make_piece(them, PAWN) : piece_on(to);
667
668   assert(color_of(pc) == us);
669   assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us));
670   assert(type_of(captured) != KING);
671
672   if (type_of(m) == CASTLING)
673   {
674       assert(pc == make_piece(us, KING));
675       assert(captured == make_piece(us, ROOK));
676
677       Square rfrom, rto;
678       do_castling<true>(us, from, to, rfrom, rto);
679
680       st->psq += PSQT::psq[captured][rto] - PSQT::psq[captured][rfrom];
681       k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
682       captured = NO_PIECE;
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 (type_of(captured) == PAWN)
692       {
693           if (type_of(m) == ENPASSANT)
694           {
695               capsq -= pawn_push(us);
696
697               assert(pc == make_piece(us, 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[captured][capsq];
707       }
708       else
709           st->nonPawnMaterial[them] -= PieceValue[MG][captured];
710
711       // Update board and piece lists
712       remove_piece(captured, capsq);
713
714       // Update material hash key and prefetch access to materialTable
715       k ^= Zobrist::psq[captured][capsq];
716       st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];
717       prefetch(thisThread->materialTable[st->materialKey]);
718
719       // Update incremental scores
720       st->psq -= PSQT::psq[captured][capsq];
721
722       // Reset rule 50 counter
723       st->rule50 = 0;
724   }
725
726   // Update hash key
727   k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][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(pc, from, to);
747
748   // If the moving piece is a pawn do some special extra work
749   if (type_of(pc) == 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           Piece promotion = make_piece(us, promotion_type(m));
762
763           assert(relative_rank(us, to) == RANK_8);
764           assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);
765
766           remove_piece(pc, to);
767           put_piece(promotion, to);
768
769           // Update hash keys
770           k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
771           st->pawnKey ^= Zobrist::psq[pc][to];
772           st->materialKey ^=  Zobrist::psq[promotion][pieceCount[promotion]-1]
773                             ^ Zobrist::psq[pc][pieceCount[pc]];
774
775           // Update incremental score
776           st->psq += PSQT::psq[promotion][to] - PSQT::psq[pc][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[pc][from] ^ Zobrist::psq[pc][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[pc][to] - PSQT::psq[pc][from];
792
793   // Set capture piece
794   st->capturedPiece = 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   // Update king attacks used for fast check detection
805   set_check_info(st);
806
807   assert(pos_is_ok());
808 }
809
810
811 /// Position::undo_move() unmakes a move. When it returns, the position should
812 /// be restored to exactly the same state as before the move was made.
813
814 void Position::undo_move(Move m) {
815
816   assert(is_ok(m));
817
818   sideToMove = ~sideToMove;
819
820   Color us = sideToMove;
821   Square from = from_sq(m);
822   Square to = to_sq(m);
823   Piece pc = piece_on(to);
824
825   assert(empty(from) || type_of(m) == CASTLING);
826   assert(type_of(st->capturedPiece) != KING);
827
828   if (type_of(m) == PROMOTION)
829   {
830       assert(relative_rank(us, to) == RANK_8);
831       assert(type_of(pc) == promotion_type(m));
832       assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);
833
834       remove_piece(pc, to);
835       pc = make_piece(us, PAWN);
836       put_piece(pc, to);
837   }
838
839   if (type_of(m) == CASTLING)
840   {
841       Square rfrom, rto;
842       do_castling<false>(us, from, to, rfrom, rto);
843   }
844   else
845   {
846       move_piece(pc, to, from); // Put the piece back at the source square
847
848       if (st->capturedPiece)
849       {
850           Square capsq = to;
851
852           if (type_of(m) == ENPASSANT)
853           {
854               capsq -= pawn_push(us);
855
856               assert(type_of(pc) == PAWN);
857               assert(to == st->previous->epSquare);
858               assert(relative_rank(us, to) == RANK_6);
859               assert(piece_on(capsq) == NO_PIECE);
860               assert(st->capturedPiece == make_piece(~us, PAWN));
861           }
862
863           put_piece(st->capturedPiece, capsq); // Restore the captured piece
864       }
865   }
866
867   // Finally point our state pointer back to the previous state
868   st = st->previous;
869   --gamePly;
870
871   assert(pos_is_ok());
872 }
873
874
875 /// Position::do_castling() is a helper used to do/undo a castling move. This
876 /// is a bit tricky in Chess960 where from/to squares can overlap.
877 template<bool Do>
878 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
879
880   bool kingSide = to > from;
881   rfrom = to; // Castling is encoded as "king captures friendly rook"
882   rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
883   to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
884
885   // Remove both pieces first since squares could overlap in Chess960
886   remove_piece(make_piece(us, KING), Do ? from : to);
887   remove_piece(make_piece(us, ROOK), Do ? rfrom : rto);
888   board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
889   put_piece(make_piece(us, KING), Do ? to : from);
890   put_piece(make_piece(us, ROOK), Do ? rto : rfrom);
891 }
892
893
894 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
895 /// the side to move without executing any move on the board.
896
897 void Position::do_null_move(StateInfo& newSt) {
898
899   assert(!checkers());
900   assert(&newSt != st);
901
902   std::memcpy(&newSt, st, sizeof(StateInfo));
903   newSt.previous = st;
904   st = &newSt;
905
906   if (st->epSquare != SQ_NONE)
907   {
908       st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
909       st->epSquare = SQ_NONE;
910   }
911
912   st->key ^= Zobrist::side;
913   prefetch(TT.first_entry(st->key));
914
915   ++st->rule50;
916   st->pliesFromNull = 0;
917
918   sideToMove = ~sideToMove;
919
920   set_check_info(st);
921
922   assert(pos_is_ok());
923 }
924
925 void Position::undo_null_move() {
926
927   assert(!checkers());
928
929   st = st->previous;
930   sideToMove = ~sideToMove;
931 }
932
933
934 /// Position::key_after() computes the new hash key after the given move. Needed
935 /// for speculative prefetch. It doesn't recognize special moves like castling,
936 /// en-passant and promotions.
937
938 Key Position::key_after(Move m) const {
939
940   Square from = from_sq(m);
941   Square to = to_sq(m);
942   Piece pc = piece_on(from);
943   Piece captured = piece_on(to);
944   Key k = st->key ^ Zobrist::side;
945
946   if (captured)
947       k ^= Zobrist::psq[captured][to];
948
949   return k ^ Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from];
950 }
951
952
953 /// Position::see() is a static exchange evaluator: It tries to estimate the
954 /// material gain or loss resulting from a move.
955
956 Value Position::see_sign(Move m) const {
957
958   assert(is_ok(m));
959
960   // Early return if SEE cannot be negative because captured piece value
961   // is not less then capturing one. Note that king moves always return
962   // here because king midgame value is set to 0.
963   if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
964       return VALUE_KNOWN_WIN;
965
966   return see(m);
967 }
968
969 Value Position::see(Move m) const {
970
971   Square from, to;
972   Bitboard occupied, attackers, stmAttackers;
973   Value swapList[32];
974   int slIndex = 1;
975   PieceType captured;
976   Color stm;
977
978   assert(is_ok(m));
979
980   from = from_sq(m);
981   to = to_sq(m);
982   swapList[0] = PieceValue[MG][piece_on(to)];
983   stm = color_of(piece_on(from));
984   occupied = pieces() ^ from;
985
986   // Castling moves are implemented as king capturing the rook so cannot
987   // be handled correctly. Simply return VALUE_ZERO that is always correct
988   // unless in the rare case the rook ends up under attack.
989   if (type_of(m) == CASTLING)
990       return VALUE_ZERO;
991
992   if (type_of(m) == ENPASSANT)
993   {
994       occupied ^= to - pawn_push(stm); // Remove the captured pawn
995       swapList[0] = PieceValue[MG][PAWN];
996   }
997
998   // Find all attackers to the destination square, with the moving piece
999   // removed, but possibly an X-ray attacker added behind it.
1000   attackers = attackers_to(to, occupied) & occupied;
1001
1002   // If the opponent has no attackers we are finished
1003   stm = ~stm;
1004   stmAttackers = attackers & pieces(stm);
1005   occupied ^= to; // For the case when captured piece is a pinner
1006
1007   // Don't allow pinned pieces to attack as long all pinners (this includes also
1008   // potential ones) are on their original square. When a pinner moves to the
1009   // exchange-square or get captured on it, we fall back to standard SEE behaviour.
1010   if (   (stmAttackers & pinned_pieces(stm))
1011       && (st->pinnersForKing[stm] & occupied) == st->pinnersForKing[stm])
1012       stmAttackers &= ~pinned_pieces(stm);
1013
1014   if (!stmAttackers)
1015         return swapList[0];
1016
1017   // The destination square is defended, which makes things rather more
1018   // difficult to compute. We proceed by building up a "swap list" containing
1019   // the material gain or loss at each stop in a sequence of captures to the
1020   // destination square, where the sides alternately capture, and always
1021   // capture with the least valuable piece. After each capture, we look for
1022   // new X-ray attacks from behind the capturing piece.
1023   captured = type_of(piece_on(from));
1024
1025   do {
1026       assert(slIndex < 32);
1027
1028       // Add the new entry to the swap list
1029       swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1030
1031       // Locate and remove the next least valuable attacker
1032       captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1033       stm = ~stm;
1034       stmAttackers = attackers & pieces(stm);
1035       if (   (stmAttackers & pinned_pieces(stm))
1036           && (st->pinnersForKing[stm] & occupied) == st->pinnersForKing[stm])
1037           stmAttackers &= ~pinned_pieces(stm);
1038
1039       ++slIndex;
1040
1041   } while (stmAttackers && (captured != KING || (--slIndex, false))); // Stop before a king capture
1042
1043   // Having built the swap list, we negamax through it to find the best
1044   // achievable score from the point of view of the side to move.
1045   while (--slIndex)
1046       swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1047
1048   return swapList[0];
1049 }
1050
1051
1052 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1053 /// or by repetition. It does not detect stalemates.
1054
1055 bool Position::is_draw() const {
1056
1057   if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1058       return true;
1059
1060   StateInfo* stp = st;
1061   for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1062   {
1063       stp = stp->previous->previous;
1064
1065       if (stp->key == st->key)
1066           return true; // Draw at first repetition
1067   }
1068
1069   return false;
1070 }
1071
1072
1073 /// Position::flip() flips position with the white and black sides reversed. This
1074 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1075
1076 void Position::flip() {
1077
1078   string f, token;
1079   std::stringstream ss(fen());
1080
1081   for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1082   {
1083       std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1084       f.insert(0, token + (f.empty() ? " " : "/"));
1085   }
1086
1087   ss >> token; // Active color
1088   f += (token == "w" ? "B " : "W "); // Will be lowercased later
1089
1090   ss >> token; // Castling availability
1091   f += token + " ";
1092
1093   std::transform(f.begin(), f.end(), f.begin(),
1094                  [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1095
1096   ss >> token; // En passant square
1097   f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1098
1099   std::getline(ss, token); // Half and full moves
1100   f += token;
1101
1102   set(f, is_chess960(), st, this_thread());
1103
1104   assert(pos_is_ok());
1105 }
1106
1107
1108 /// Position::pos_is_ok() performs some consistency checks for the position object.
1109 /// This is meant to be helpful when debugging.
1110
1111 bool Position::pos_is_ok(int* failedStep) const {
1112
1113   const bool Fast = true; // Quick (default) or full check?
1114
1115   enum { Default, King, Bitboards, State, Lists, Castling };
1116
1117   for (int step = Default; step <= (Fast ? Default : Castling); step++)
1118   {
1119       if (failedStep)
1120           *failedStep = step;
1121
1122       if (step == Default)
1123           if (   (sideToMove != WHITE && sideToMove != BLACK)
1124               || piece_on(square<KING>(WHITE)) != W_KING
1125               || piece_on(square<KING>(BLACK)) != B_KING
1126               || (   ep_square() != SQ_NONE
1127                   && relative_rank(sideToMove, ep_square()) != RANK_6))
1128               return false;
1129
1130       if (step == King)
1131           if (   std::count(board, board + SQUARE_NB, W_KING) != 1
1132               || std::count(board, board + SQUARE_NB, B_KING) != 1
1133               || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1134               return false;
1135
1136       if (step == Bitboards)
1137       {
1138           if (  (pieces(WHITE) & pieces(BLACK))
1139               ||(pieces(WHITE) | pieces(BLACK)) != pieces())
1140               return false;
1141
1142           for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1143               for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1144                   if (p1 != p2 && (pieces(p1) & pieces(p2)))
1145                       return false;
1146       }
1147
1148       if (step == State)
1149       {
1150           StateInfo si = *st;
1151           set_state(&si);
1152           if (std::memcmp(&si, st, sizeof(StateInfo)))
1153               return false;
1154       }
1155
1156       if (step == Lists)
1157           for (Piece pc : Pieces)
1158           {
1159               if (pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc))))
1160                   return false;
1161
1162               for (int i = 0; i < pieceCount[pc]; ++i)
1163                   if (board[pieceList[pc][i]] != pc || index[pieceList[pc][i]] != i)
1164                       return false;
1165           }
1166
1167       if (step == Castling)
1168           for (Color c = WHITE; c <= BLACK; ++c)
1169               for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1170               {
1171                   if (!can_castle(c | s))
1172                       continue;
1173
1174                   if (   piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1175                       || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1176                       ||(castlingRightsMask[square<KING>(c)] & (c | s)) != (c | s))
1177                       return false;
1178               }
1179   }
1180
1181   return true;
1182 }