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