0ed2fff4db4007737aeab8216ebc4a51e87d350f
[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-2012 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 <cassert>
21 #include <cstring>
22 #include <iostream>
23 #include <sstream>
24 #include <algorithm>
25
26 #include "bitcount.h"
27 #include "movegen.h"
28 #include "notation.h"
29 #include "position.h"
30 #include "psqtab.h"
31 #include "rkiss.h"
32 #include "thread.h"
33 #include "tt.h"
34
35 using std::string;
36 using std::cout;
37 using std::endl;
38
39 static const string PieceToChar(" PNBRQK  pnbrqk");
40
41 CACHE_LINE_ALIGNMENT
42
43 Score pieceSquareTable[PIECE_NB][SQUARE_NB];
44 Value PieceValue[PHASE_NB][PIECE_NB] = {
45 { VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg },
46 { VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } };
47
48 namespace Zobrist {
49
50 Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
51 Key enpassant[FILE_NB];
52 Key castle[CASTLE_RIGHT_NB];
53 Key side;
54 Key exclusion;
55
56 /// init() initializes at startup the various arrays used to compute hash keys
57 /// and the piece square tables. The latter is a two-step operation: First, the
58 /// white halves of the tables are copied from PSQT[] tables. Second, the black
59 /// halves of the tables are initialized by flipping and changing the sign of
60 /// the white scores.
61
62 void init() {
63
64   RKISS rk;
65
66   for (Color c = WHITE; c <= BLACK; c++)
67       for (PieceType pt = PAWN; pt <= KING; pt++)
68           for (Square s = SQ_A1; s <= SQ_H8; s++)
69               psq[c][pt][s] = rk.rand<Key>();
70
71   for (File f = FILE_A; f <= FILE_H; f++)
72       enpassant[f] = rk.rand<Key>();
73
74   for (int cr = CASTLES_NONE; cr <= ALL_CASTLES; cr++)
75   {
76       Bitboard b = cr;
77       while (b)
78       {
79           Key k = castle[1ULL << pop_lsb(&b)];
80           castle[cr] ^= k ? k : rk.rand<Key>();
81       }
82   }
83
84   side = rk.rand<Key>();
85   exclusion  = rk.rand<Key>();
86
87   for (PieceType pt = PAWN; pt <= KING; pt++)
88   {
89       PieceValue[MG][make_piece(BLACK, pt)] = PieceValue[MG][pt];
90       PieceValue[EG][make_piece(BLACK, pt)] = PieceValue[EG][pt];
91
92       Score v = make_score(PieceValue[MG][pt], PieceValue[EG][pt]);
93
94       for (Square s = SQ_A1; s <= SQ_H8; s++)
95       {
96           pieceSquareTable[make_piece(WHITE, pt)][ s] =  (v + PSQT[pt][s]);
97           pieceSquareTable[make_piece(BLACK, pt)][~s] = -(v + PSQT[pt][s]);
98       }
99   }
100 }
101
102 } // namespace Zobrist
103
104
105 namespace {
106
107 /// next_attacker() is an helper function used by see() to locate the least
108 /// valuable attacker for the side to move, remove the attacker we just found
109 /// from the 'occupied' bitboard and scan for new X-ray attacks behind it.
110
111 template<int Pt> FORCE_INLINE
112 PieceType next_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
113                         Bitboard& occupied, Bitboard& attackers) {
114
115   if (stmAttackers & bb[Pt])
116   {
117       Bitboard b = stmAttackers & bb[Pt];
118       occupied ^= b & ~(b - 1);
119
120       if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
121           attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
122
123       if (Pt == ROOK || Pt == QUEEN)
124           attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
125
126       return (PieceType)Pt;
127   }
128   return next_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
129 }
130
131 template<> FORCE_INLINE
132 PieceType next_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
133   return KING; // No need to update bitboards, it is the last cycle
134 }
135
136 } // namespace
137
138
139 /// CheckInfo c'tor
140
141 CheckInfo::CheckInfo(const Position& pos) {
142
143   Color them = ~pos.side_to_move();
144   ksq = pos.king_square(them);
145
146   pinned = pos.pinned_pieces();
147   dcCandidates = pos.discovered_check_candidates();
148
149   checkSq[PAWN]   = pos.attacks_from<PAWN>(ksq, them);
150   checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
151   checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
152   checkSq[ROOK]   = pos.attacks_from<ROOK>(ksq);
153   checkSq[QUEEN]  = checkSq[BISHOP] | checkSq[ROOK];
154   checkSq[KING]   = 0;
155 }
156
157
158 /// Position::operator=() creates a copy of 'pos'. We want the new born Position
159 /// object do not depend on any external data so we detach state pointer from
160 /// the source one.
161
162 Position& Position::operator=(const Position& pos) {
163
164   memcpy(this, &pos, sizeof(Position));
165   startState = *st;
166   st = &startState;
167   nodes = 0;
168
169   assert(pos_is_ok());
170
171   return *this;
172 }
173
174
175 /// Position::set() initializes the position object with the given FEN string.
176 /// This function is not very robust - make sure that input FENs are correct,
177 /// this is assumed to be the responsibility of the GUI.
178
179 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
180 /*
181    A FEN string defines a particular position using only the ASCII character set.
182
183    A FEN string contains six fields separated by a space. The fields are:
184
185    1) Piece placement (from white's perspective). Each rank is described, starting
186       with rank 8 and ending with rank 1; within each rank, the contents of each
187       square are described from file A through file H. Following the Standard
188       Algebraic Notation (SAN), each piece is identified by a single letter taken
189       from the standard English names. White pieces are designated using upper-case
190       letters ("PNBRQK") while Black take lowercase ("pnbrqk"). Blank squares are
191       noted using digits 1 through 8 (the number of blank squares), and "/"
192       separates ranks.
193
194    2) Active color. "w" means white moves next, "b" means black.
195
196    3) Castling availability. If neither side can castle, this is "-". Otherwise,
197       this has one or more letters: "K" (White can castle kingside), "Q" (White
198       can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
199       can castle queenside).
200
201    4) En passant target square (in algebraic notation). If there's no en passant
202       target square, this is "-". If a pawn has just made a 2-square move, this
203       is the position "behind" the pawn. This is recorded regardless of whether
204       there is a pawn in position to make an en passant capture.
205
206    5) Halfmove clock. This is the number of halfmoves since the last pawn advance
207       or capture. This is used to determine if a draw can be claimed under the
208       fifty-move rule.
209
210    6) Fullmove number. The number of the full move. It starts at 1, and is
211       incremented after Black's move.
212 */
213
214   char col, row, token;
215   size_t p;
216   Square sq = SQ_A8;
217   std::istringstream ss(fenStr);
218
219   clear();
220   ss >> std::noskipws;
221
222   // 1. Piece placement
223   while ((ss >> token) && !isspace(token))
224   {
225       if (isdigit(token))
226           sq += Square(token - '0'); // Advance the given number of files
227
228       else if (token == '/')
229           sq -= Square(16);
230
231       else if ((p = PieceToChar.find(token)) != string::npos)
232       {
233           put_piece(Piece(p), sq);
234           sq++;
235       }
236   }
237
238   // 2. Active color
239   ss >> token;
240   sideToMove = (token == 'w' ? WHITE : BLACK);
241   ss >> token;
242
243   // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
244   // Shredder-FEN that uses the letters of the columns on which the rooks began
245   // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
246   // if an inner rook is associated with the castling right, the castling tag is
247   // replaced by the file letter of the involved rook, as for the Shredder-FEN.
248   while ((ss >> token) && !isspace(token))
249   {
250       Square rsq;
251       Color c = islower(token) ? BLACK : WHITE;
252
253       token = char(toupper(token));
254
255       if (token == 'K')
256           for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; rsq--) {}
257
258       else if (token == 'Q')
259           for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; rsq++) {}
260
261       else if (token >= 'A' && token <= 'H')
262           rsq = File(token - 'A') | relative_rank(c, RANK_1);
263
264       else
265           continue;
266
267       set_castle_right(c, rsq);
268   }
269
270   // 4. En passant square. Ignore if no pawn capture is possible
271   if (   ((ss >> col) && (col >= 'a' && col <= 'h'))
272       && ((ss >> row) && (row == '3' || row == '6')))
273   {
274       st->epSquare = File(col - 'a') | Rank(row - '1');
275
276       if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
277           st->epSquare = SQ_NONE;
278   }
279
280   // 5-6. Halfmove clock and fullmove number
281   ss >> std::skipws >> st->rule50 >> startPosPly;
282
283   // Convert from fullmove starting from 1 to ply starting from 0,
284   // handle also common incorrect FEN with fullmove = 0.
285   startPosPly = std::max(2 * (startPosPly - 1), 0) + int(sideToMove == BLACK);
286
287   st->key = compute_key();
288   st->pawnKey = compute_pawn_key();
289   st->materialKey = compute_material_key();
290   st->psqScore = compute_psq_score();
291   st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
292   st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
293   st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
294   chess960 = isChess960;
295   thisThread = th;
296
297   assert(pos_is_ok());
298 }
299
300
301 /// Position::set_castle_right() is an helper function used to set castling
302 /// rights given the corresponding color and the rook starting square.
303
304 void Position::set_castle_right(Color c, Square rfrom) {
305
306   Square kfrom = king_square(c);
307   CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
308   CastleRight cr = make_castle_right(c, cs);
309
310   st->castleRights |= cr;
311   castleRightsMask[kfrom] |= cr;
312   castleRightsMask[rfrom] |= cr;
313   castleRookSquare[c][cs] = rfrom;
314
315   Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
316   Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
317
318   for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); s++)
319       if (s != kfrom && s != rfrom)
320           castlePath[c][cs] |= s;
321
322   for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); s++)
323       if (s != kfrom && s != rfrom)
324           castlePath[c][cs] |= s;
325 }
326
327
328 /// Position::fen() returns a FEN representation of the position. In case
329 /// of Chess960 the Shredder-FEN notation is used. Mainly a debugging function.
330
331 const string Position::fen() const {
332
333   std::ostringstream ss;
334   Square sq;
335   int emptyCnt;
336
337   for (Rank rank = RANK_8; rank >= RANK_1; rank--)
338   {
339       emptyCnt = 0;
340
341       for (File file = FILE_A; file <= FILE_H; file++)
342       {
343           sq = file | rank;
344
345           if (is_empty(sq))
346               emptyCnt++;
347           else
348           {
349               if (emptyCnt > 0)
350               {
351                   ss << emptyCnt;
352                   emptyCnt = 0;
353               }
354               ss << PieceToChar[piece_on(sq)];
355           }
356       }
357
358       if (emptyCnt > 0)
359           ss << emptyCnt;
360
361       if (rank > RANK_1)
362           ss << '/';
363   }
364
365   ss << (sideToMove == WHITE ? " w " : " b ");
366
367   if (can_castle(WHITE_OO))
368       ss << (chess960 ? char(toupper(file_to_char(file_of(castle_rook_square(WHITE, KING_SIDE))))) : 'K');
369
370   if (can_castle(WHITE_OOO))
371       ss << (chess960 ? char(toupper(file_to_char(file_of(castle_rook_square(WHITE, QUEEN_SIDE))))) : 'Q');
372
373   if (can_castle(BLACK_OO))
374       ss << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, KING_SIDE))) : 'k');
375
376   if (can_castle(BLACK_OOO))
377       ss << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, QUEEN_SIDE))) : 'q');
378
379   if (st->castleRights == CASTLES_NONE)
380       ss << '-';
381
382   ss << (ep_square() == SQ_NONE ? " - " : " " + square_to_string(ep_square()) + " ")
383       << st->rule50 << " " << 1 + (startPosPly - int(sideToMove == BLACK)) / 2;
384
385   return ss.str();
386 }
387
388
389 /// Position::pretty() returns an ASCII representation of the position to be
390 /// printed to the standard output together with the move's san notation.
391
392 const string Position::pretty(Move move) const {
393
394   const string dottedLine =            "\n+---+---+---+---+---+---+---+---+";
395   const string twoRows =  dottedLine + "\n|   | . |   | . |   | . |   | . |"
396                         + dottedLine + "\n| . |   | . |   | . |   | . |   |";
397
398   string brd = twoRows + twoRows + twoRows + twoRows + dottedLine;
399
400   std::ostringstream ss;
401
402   if (move)
403       ss << "\nMove is: " << (sideToMove == BLACK ? ".." : "")
404          << move_to_san(*const_cast<Position*>(this), move);
405
406   for (Square sq = SQ_A1; sq <= SQ_H8; sq++)
407       if (piece_on(sq) != NO_PIECE)
408           brd[513 - 68*rank_of(sq) + 4*file_of(sq)] = PieceToChar[piece_on(sq)];
409
410   ss << brd << "\nFen is: " << fen() << "\nKey is: " << st->key;
411   return ss.str();
412 }
413
414
415 /// Position:hidden_checkers<>() returns a bitboard of all pinned (against the
416 /// king) pieces for the given color. Or, when template parameter FindPinned is
417 /// false, the function return the pieces of the given color candidate for a
418 /// discovery check against the enemy king.
419 template<bool FindPinned>
420 Bitboard Position::hidden_checkers() const {
421
422   // Pinned pieces protect our king, dicovery checks attack the enemy king
423   Bitboard b, result = 0;
424   Bitboard pinners = pieces(FindPinned ? ~sideToMove : sideToMove);
425   Square ksq = king_square(FindPinned ? sideToMove : ~sideToMove);
426
427   // Pinners are sliders, that give check when candidate pinned is removed
428   pinners &=  (pieces(ROOK, QUEEN) & PseudoAttacks[ROOK][ksq])
429             | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq]);
430
431   while (pinners)
432   {
433       b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
434
435       if (b && !more_than_one(b) && (b & pieces(sideToMove)))
436           result |= b;
437   }
438   return result;
439 }
440
441 // Explicit template instantiations
442 template Bitboard Position::hidden_checkers<true>() const;
443 template Bitboard Position::hidden_checkers<false>() const;
444
445
446 /// Position::attackers_to() computes a bitboard of all pieces which attack a
447 /// given square. Slider attacks use occ bitboard as occupancy.
448
449 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
450
451   return  (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
452         | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
453         | (attacks_from<KNIGHT>(s)      & pieces(KNIGHT))
454         | (attacks_bb<ROOK>(s, occ)     & pieces(ROOK, QUEEN))
455         | (attacks_bb<BISHOP>(s, occ)   & pieces(BISHOP, QUEEN))
456         | (attacks_from<KING>(s)        & pieces(KING));
457 }
458
459
460 /// Position::attacks_from() computes a bitboard of all attacks of a given piece
461 /// put in a given square. Slider attacks use occ bitboard as occupancy.
462
463 Bitboard Position::attacks_from(Piece p, Square s, Bitboard occ) {
464
465   assert(is_ok(s));
466
467   switch (type_of(p))
468   {
469   case BISHOP: return attacks_bb<BISHOP>(s, occ);
470   case ROOK  : return attacks_bb<ROOK>(s, occ);
471   case QUEEN : return attacks_bb<BISHOP>(s, occ) | attacks_bb<ROOK>(s, occ);
472   default    : return StepAttacksBB[p][s];
473   }
474 }
475
476
477 /// Position::pl_move_is_legal() tests whether a pseudo-legal move is legal
478
479 bool Position::pl_move_is_legal(Move m, Bitboard pinned) const {
480
481   assert(is_ok(m));
482   assert(pinned == pinned_pieces());
483
484   Color us = sideToMove;
485   Square from = from_sq(m);
486
487   assert(color_of(piece_moved(m)) == us);
488   assert(piece_on(king_square(us)) == make_piece(us, KING));
489
490   // En passant captures are a tricky special case. Because they are rather
491   // uncommon, we do it simply by testing whether the king is attacked after
492   // the move is made.
493   if (type_of(m) == ENPASSANT)
494   {
495       Color them = ~us;
496       Square to = to_sq(m);
497       Square capsq = to + pawn_push(them);
498       Square ksq = king_square(us);
499       Bitboard b = (pieces() ^ from ^ capsq) | to;
500
501       assert(to == ep_square());
502       assert(piece_moved(m) == make_piece(us, PAWN));
503       assert(piece_on(capsq) == make_piece(them, PAWN));
504       assert(piece_on(to) == NO_PIECE);
505
506       return   !(attacks_bb<  ROOK>(ksq, b) & pieces(them, QUEEN, ROOK))
507             && !(attacks_bb<BISHOP>(ksq, b) & pieces(them, QUEEN, BISHOP));
508   }
509
510   // If the moving piece is a king, check whether the destination
511   // square is attacked by the opponent. Castling moves are checked
512   // for legality during move generation.
513   if (type_of(piece_on(from)) == KING)
514       return type_of(m) == CASTLE || !(attackers_to(to_sq(m)) & pieces(~us));
515
516   // A non-king move is legal if and only if it is not pinned or it
517   // is moving along the ray towards or away from the king.
518   return   !pinned
519         || !(pinned & from)
520         ||  squares_aligned(from, to_sq(m), king_square(us));
521 }
522
523
524 /// Position::move_is_legal() takes a random move and tests whether the move
525 /// is legal. This version is not very fast and should be used only in non
526 /// time-critical paths.
527
528 bool Position::move_is_legal(const Move m) const {
529
530   for (MoveList<LEGAL> ml(*this); !ml.end(); ++ml)
531       if (ml.move() == m)
532           return true;
533
534   return false;
535 }
536
537
538 /// Position::is_pseudo_legal() takes a random move and tests whether the move
539 /// is pseudo legal. It is used to validate moves from TT that can be corrupted
540 /// due to SMP concurrent access or hash position key aliasing.
541
542 bool Position::is_pseudo_legal(const Move m) const {
543
544   Color us = sideToMove;
545   Color them = ~sideToMove;
546   Square from = from_sq(m);
547   Square to = to_sq(m);
548   Piece pc = piece_moved(m);
549
550   // Use a slower but simpler function for uncommon cases
551   if (type_of(m) != NORMAL)
552       return move_is_legal(m);
553
554   // Is not a promotion, so promotion piece must be empty
555   if (promotion_type(m) - 2 != NO_PIECE_TYPE)
556       return false;
557
558   // If the from square is not occupied by a piece belonging to the side to
559   // move, the move is obviously not legal.
560   if (pc == NO_PIECE || color_of(pc) != us)
561       return false;
562
563   // The destination square cannot be occupied by a friendly piece
564   if (piece_on(to) != NO_PIECE && color_of(piece_on(to)) == us)
565       return false;
566
567   // Handle the special case of a pawn move
568   if (type_of(pc) == PAWN)
569   {
570       // Move direction must be compatible with pawn color
571       int direction = to - from;
572       if ((us == WHITE) != (direction > 0))
573           return false;
574
575       // We have already handled promotion moves, so destination
576       // cannot be on the 8/1th rank.
577       if (rank_of(to) == RANK_8 || rank_of(to) == RANK_1)
578           return false;
579
580       // Proceed according to the square delta between the origin and
581       // destination squares.
582       switch (direction)
583       {
584       case DELTA_NW:
585       case DELTA_NE:
586       case DELTA_SW:
587       case DELTA_SE:
588       // Capture. The destination square must be occupied by an enemy
589       // piece (en passant captures was handled earlier).
590       if (piece_on(to) == NO_PIECE || color_of(piece_on(to)) != them)
591           return false;
592
593       // From and to files must be one file apart, avoids a7h5
594       if (abs(file_of(from) - file_of(to)) != 1)
595           return false;
596       break;
597
598       case DELTA_N:
599       case DELTA_S:
600       // Pawn push. The destination square must be empty.
601       if (!is_empty(to))
602           return false;
603       break;
604
605       case DELTA_NN:
606       // Double white pawn push. The destination square must be on the fourth
607       // rank, and both the destination square and the square between the
608       // source and destination squares must be empty.
609       if (    rank_of(to) != RANK_4
610           || !is_empty(to)
611           || !is_empty(from + DELTA_N))
612           return false;
613       break;
614
615       case DELTA_SS:
616       // Double black pawn push. The destination square must be on the fifth
617       // rank, and both the destination square and the square between the
618       // source and destination squares must be empty.
619       if (    rank_of(to) != RANK_5
620           || !is_empty(to)
621           || !is_empty(from + DELTA_S))
622           return false;
623       break;
624
625       default:
626           return false;
627       }
628   }
629   else if (!(attacks_from(pc, from) & to))
630       return false;
631
632   // Evasions generator already takes care to avoid some kind of illegal moves
633   // and pl_move_is_legal() relies on this. So we have to take care that the
634   // same kind of moves are filtered out here.
635   if (in_check())
636   {
637       if (type_of(pc) != KING)
638       {
639           Bitboard b = checkers();
640           Square checksq = pop_lsb(&b);
641
642           if (b) // double check ? In this case a king move is required
643               return false;
644
645           // Our move must be a blocking evasion or a capture of the checking piece
646           if (!((between_bb(checksq, king_square(us)) | checkers()) & to))
647               return false;
648       }
649       // In case of king moves under check we have to remove king so to catch
650       // as invalid moves like b1a1 when opposite queen is on c1.
651       else if (attackers_to(to, pieces() ^ from) & pieces(~us))
652           return false;
653   }
654
655   return true;
656 }
657
658
659 /// Position::move_gives_check() tests whether a pseudo-legal move gives a check
660
661 bool Position::move_gives_check(Move m, const CheckInfo& ci) const {
662
663   assert(is_ok(m));
664   assert(ci.dcCandidates == discovered_check_candidates());
665   assert(color_of(piece_moved(m)) == sideToMove);
666
667   Square from = from_sq(m);
668   Square to = to_sq(m);
669   PieceType pt = type_of(piece_on(from));
670
671   // Direct check ?
672   if (ci.checkSq[pt] & to)
673       return true;
674
675   // Discovery check ?
676   if (ci.dcCandidates && (ci.dcCandidates & from))
677   {
678       // For pawn and king moves we need to verify also direction
679       if (   (pt != PAWN && pt != KING)
680           || !squares_aligned(from, to, king_square(~sideToMove)))
681           return true;
682   }
683
684   // Can we skip the ugly special cases ?
685   if (type_of(m) == NORMAL)
686       return false;
687
688   Color us = sideToMove;
689   Square ksq = king_square(~us);
690
691   switch (type_of(m))
692   {
693   case PROMOTION:
694       return attacks_from(Piece(promotion_type(m)), to, pieces() ^ from) & ksq;
695
696   // En passant capture with check ? We have already handled the case
697   // of direct checks and ordinary discovered check, the only case we
698   // need to handle is the unusual case of a discovered check through
699   // the captured pawn.
700   case ENPASSANT:
701   {
702       Square capsq = file_of(to) | rank_of(from);
703       Bitboard b = (pieces() ^ from ^ capsq) | to;
704
705       return  (attacks_bb<  ROOK>(ksq, b) & pieces(us, QUEEN, ROOK))
706             | (attacks_bb<BISHOP>(ksq, b) & pieces(us, QUEEN, BISHOP));
707   }
708   case CASTLE:
709   {
710       Square kfrom = from;
711       Square rfrom = to; // 'King captures the rook' notation
712       Square kto = relative_square(us, rfrom > kfrom ? SQ_G1 : SQ_C1);
713       Square rto = relative_square(us, rfrom > kfrom ? SQ_F1 : SQ_D1);
714       Bitboard b = (pieces() ^ kfrom ^ rfrom) | rto | kto;
715
716       return attacks_bb<ROOK>(rto, b) & ksq;
717   }
718   default:
719       assert(false);
720       return false;
721   }
722 }
723
724
725 /// Position::do_move() makes a move, and saves all information necessary
726 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
727 /// moves should be filtered out before this function is called.
728
729 void Position::do_move(Move m, StateInfo& newSt) {
730
731   CheckInfo ci(*this);
732   do_move(m, newSt, ci, move_gives_check(m, ci));
733 }
734
735 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
736
737   assert(is_ok(m));
738   assert(&newSt != st);
739
740   nodes++;
741   Key k = st->key;
742
743   // Copy some fields of old state to our new StateInfo object except the ones
744   // which are going to be recalculated from scratch anyway, then switch our state
745   // pointer to point to the new, ready to be updated, state.
746   memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
747
748   newSt.previous = st;
749   st = &newSt;
750
751   // Update side to move
752   k ^= Zobrist::side;
753
754   // Increment the 50 moves rule draw counter. Resetting it to zero in the
755   // case of a capture or a pawn move is taken care of later.
756   st->rule50++;
757   st->pliesFromNull++;
758
759   if (type_of(m) == CASTLE)
760   {
761       st->key = k;
762       do_castle_move<true>(m);
763       return;
764   }
765
766   Color us = sideToMove;
767   Color them = ~us;
768   Square from = from_sq(m);
769   Square to = to_sq(m);
770   Piece piece = piece_on(from);
771   PieceType pt = type_of(piece);
772   PieceType capture = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
773
774   assert(color_of(piece) == us);
775   assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them);
776   assert(capture != KING);
777
778   if (capture)
779   {
780       Square capsq = to;
781
782       // If the captured piece is a pawn, update pawn hash key, otherwise
783       // update non-pawn material.
784       if (capture == PAWN)
785       {
786           if (type_of(m) == ENPASSANT)
787           {
788               capsq += pawn_push(them);
789
790               assert(pt == PAWN);
791               assert(to == st->epSquare);
792               assert(relative_rank(us, to) == RANK_6);
793               assert(piece_on(to) == NO_PIECE);
794               assert(piece_on(capsq) == make_piece(them, PAWN));
795
796               board[capsq] = NO_PIECE;
797           }
798
799           st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
800       }
801       else
802           st->npMaterial[them] -= PieceValue[MG][capture];
803
804       // Remove the captured piece
805       byTypeBB[ALL_PIECES] ^= capsq;
806       byTypeBB[capture] ^= capsq;
807       byColorBB[them] ^= capsq;
808
809       // Update piece list, move the last piece at index[capsq] position and
810       // shrink the list.
811       //
812       // WARNING: This is a not revresible operation. When we will reinsert the
813       // captured piece in undo_move() we will put it at the end of the list and
814       // not in its original place, it means index[] and pieceList[] are not
815       // guaranteed to be invariant to a do_move() + undo_move() sequence.
816       Square lastSquare = pieceList[them][capture][--pieceCount[them][capture]];
817       index[lastSquare] = index[capsq];
818       pieceList[them][capture][index[lastSquare]] = lastSquare;
819       pieceList[them][capture][pieceCount[them][capture]] = SQ_NONE;
820
821       // Update hash keys
822       k ^= Zobrist::psq[them][capture][capsq];
823       st->materialKey ^= Zobrist::psq[them][capture][pieceCount[them][capture]];
824
825       // Update incremental scores
826       st->psqScore -= pieceSquareTable[make_piece(them, capture)][capsq];
827
828       // Reset rule 50 counter
829       st->rule50 = 0;
830   }
831
832   // Update hash key
833   k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
834
835   // Reset en passant square
836   if (st->epSquare != SQ_NONE)
837   {
838       k ^= Zobrist::enpassant[file_of(st->epSquare)];
839       st->epSquare = SQ_NONE;
840   }
841
842   // Update castle rights if needed
843   if (st->castleRights && (castleRightsMask[from] | castleRightsMask[to]))
844   {
845       int cr = castleRightsMask[from] | castleRightsMask[to];
846       k ^= Zobrist::castle[st->castleRights & cr];
847       st->castleRights &= ~cr;
848   }
849
850   // Prefetch TT access as soon as we know key is updated
851   prefetch((char*)TT.first_entry(k));
852
853   // Move the piece
854   Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
855   byTypeBB[ALL_PIECES] ^= from_to_bb;
856   byTypeBB[pt] ^= from_to_bb;
857   byColorBB[us] ^= from_to_bb;
858
859   board[to] = board[from];
860   board[from] = NO_PIECE;
861
862   // Update piece lists, index[from] is not updated and becomes stale. This
863   // works as long as index[] is accessed just by known occupied squares.
864   index[to] = index[from];
865   pieceList[us][pt][index[to]] = to;
866
867   // If the moving piece is a pawn do some special extra work
868   if (pt == PAWN)
869   {
870       // Set en-passant square, only if moved pawn can be captured
871       if (   (int(to) ^ int(from)) == 16
872           && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
873       {
874           st->epSquare = Square((from + to) / 2);
875           k ^= Zobrist::enpassant[file_of(st->epSquare)];
876       }
877
878       if (type_of(m) == PROMOTION)
879       {
880           PieceType promotion = promotion_type(m);
881
882           assert(relative_rank(us, to) == RANK_8);
883           assert(promotion >= KNIGHT && promotion <= QUEEN);
884
885           // Replace the pawn with the promoted piece
886           byTypeBB[PAWN] ^= to;
887           byTypeBB[promotion] |= to;
888           board[to] = make_piece(us, promotion);
889
890           // Update piece lists, move the last pawn at index[to] position
891           // and shrink the list. Add a new promotion piece to the list.
892           Square lastSquare = pieceList[us][PAWN][--pieceCount[us][PAWN]];
893           index[lastSquare] = index[to];
894           pieceList[us][PAWN][index[lastSquare]] = lastSquare;
895           pieceList[us][PAWN][pieceCount[us][PAWN]] = SQ_NONE;
896           index[to] = pieceCount[us][promotion];
897           pieceList[us][promotion][index[to]] = to;
898
899           // Update hash keys
900           k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
901           st->pawnKey ^= Zobrist::psq[us][PAWN][to];
902           st->materialKey ^=  Zobrist::psq[us][promotion][pieceCount[us][promotion]++]
903                             ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
904
905           // Update incremental score
906           st->psqScore +=  pieceSquareTable[make_piece(us, promotion)][to]
907                          - pieceSquareTable[make_piece(us, PAWN)][to];
908
909           // Update material
910           st->npMaterial[us] += PieceValue[MG][promotion];
911       }
912
913       // Update pawn hash key
914       st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
915
916       // Reset rule 50 draw counter
917       st->rule50 = 0;
918   }
919
920   // Prefetch pawn and material hash tables
921   prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
922   prefetch((char*)thisThread->materialTable[st->materialKey]);
923
924   // Update incremental scores
925   st->psqScore += psq_delta(piece, from, to);
926
927   // Set capture piece
928   st->capturedType = capture;
929
930   // Update the key with the final value
931   st->key = k;
932
933   // Update checkers bitboard, piece must be already moved
934   st->checkersBB = 0;
935
936   if (moveIsCheck)
937   {
938       if (type_of(m) != NORMAL)
939           st->checkersBB = attackers_to(king_square(them)) & pieces(us);
940       else
941       {
942           // Direct checks
943           if (ci.checkSq[pt] & to)
944               st->checkersBB |= to;
945
946           // Discovery checks
947           if (ci.dcCandidates && (ci.dcCandidates & from))
948           {
949               if (pt != ROOK)
950                   st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
951
952               if (pt != BISHOP)
953                   st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
954           }
955       }
956   }
957
958   sideToMove = ~sideToMove;
959
960   assert(pos_is_ok());
961 }
962
963
964 /// Position::undo_move() unmakes a move. When it returns, the position should
965 /// be restored to exactly the same state as before the move was made.
966
967 void Position::undo_move(Move m) {
968
969   assert(is_ok(m));
970
971   sideToMove = ~sideToMove;
972
973   if (type_of(m) == CASTLE)
974   {
975       do_castle_move<false>(m);
976       return;
977   }
978
979   Color us = sideToMove;
980   Color them = ~us;
981   Square from = from_sq(m);
982   Square to = to_sq(m);
983   Piece piece = piece_on(to);
984   PieceType pt = type_of(piece);
985   PieceType capture = st->capturedType;
986
987   assert(is_empty(from));
988   assert(color_of(piece) == us);
989   assert(capture != KING);
990
991   if (type_of(m) == PROMOTION)
992   {
993       PieceType promotion = promotion_type(m);
994
995       assert(promotion == pt);
996       assert(relative_rank(us, to) == RANK_8);
997       assert(promotion >= KNIGHT && promotion <= QUEEN);
998
999       // Replace the promoted piece with the pawn
1000       byTypeBB[promotion] ^= to;
1001       byTypeBB[PAWN] |= to;
1002       board[to] = make_piece(us, PAWN);
1003
1004       // Update piece lists, move the last promoted piece at index[to] position
1005       // and shrink the list. Add a new pawn to the list.
1006       Square lastSquare = pieceList[us][promotion][--pieceCount[us][promotion]];
1007       index[lastSquare] = index[to];
1008       pieceList[us][promotion][index[lastSquare]] = lastSquare;
1009       pieceList[us][promotion][pieceCount[us][promotion]] = SQ_NONE;
1010       index[to] = pieceCount[us][PAWN]++;
1011       pieceList[us][PAWN][index[to]] = to;
1012
1013       pt = PAWN;
1014   }
1015
1016   // Put the piece back at the source square
1017   Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
1018   byTypeBB[ALL_PIECES] ^= from_to_bb;
1019   byTypeBB[pt] ^= from_to_bb;
1020   byColorBB[us] ^= from_to_bb;
1021
1022   board[from] = board[to];
1023   board[to] = NO_PIECE;
1024
1025   // Update piece lists, index[to] is not updated and becomes stale. This
1026   // works as long as index[] is accessed just by known occupied squares.
1027   index[from] = index[to];
1028   pieceList[us][pt][index[from]] = from;
1029
1030   if (capture)
1031   {
1032       Square capsq = to;
1033
1034       if (type_of(m) == ENPASSANT)
1035       {
1036           capsq -= pawn_push(us);
1037
1038           assert(pt == PAWN);
1039           assert(to == st->previous->epSquare);
1040           assert(relative_rank(us, to) == RANK_6);
1041           assert(piece_on(capsq) == NO_PIECE);
1042       }
1043
1044       // Restore the captured piece
1045       byTypeBB[ALL_PIECES] |= capsq;
1046       byTypeBB[capture] |= capsq;
1047       byColorBB[them] |= capsq;
1048
1049       board[capsq] = make_piece(them, capture);
1050
1051       // Update piece list, add a new captured piece in capsq square
1052       index[capsq] = pieceCount[them][capture]++;
1053       pieceList[them][capture][index[capsq]] = capsq;
1054   }
1055
1056   // Finally point our state pointer back to the previous state
1057   st = st->previous;
1058
1059   assert(pos_is_ok());
1060 }
1061
1062
1063 /// Position::do_castle_move() is a private method used to do/undo a castling
1064 /// move. Note that castling moves are encoded as "king captures friendly rook"
1065 /// moves, for instance white short castling in a non-Chess960 game is encoded
1066 /// as e1h1.
1067 template<bool Do>
1068 void Position::do_castle_move(Move m) {
1069
1070   assert(is_ok(m));
1071   assert(type_of(m) == CASTLE);
1072
1073   Square kto, kfrom, rfrom, rto, kAfter, rAfter;
1074
1075   Color us = sideToMove;
1076   Square kBefore = from_sq(m);
1077   Square rBefore = to_sq(m);
1078
1079   // Find after-castle squares for king and rook
1080   if (rBefore > kBefore) // O-O
1081   {
1082       kAfter = relative_square(us, SQ_G1);
1083       rAfter = relative_square(us, SQ_F1);
1084   }
1085   else // O-O-O
1086   {
1087       kAfter = relative_square(us, SQ_C1);
1088       rAfter = relative_square(us, SQ_D1);
1089   }
1090
1091   kfrom = Do ? kBefore : kAfter;
1092   rfrom = Do ? rBefore : rAfter;
1093
1094   kto = Do ? kAfter : kBefore;
1095   rto = Do ? rAfter : rBefore;
1096
1097   assert(piece_on(kfrom) == make_piece(us, KING));
1098   assert(piece_on(rfrom) == make_piece(us, ROOK));
1099
1100   // Move the pieces, with some care; in chess960 could be kto == rfrom
1101   Bitboard k_from_to_bb = SquareBB[kfrom] ^ SquareBB[kto];
1102   Bitboard r_from_to_bb = SquareBB[rfrom] ^ SquareBB[rto];
1103   byTypeBB[KING] ^= k_from_to_bb;
1104   byTypeBB[ROOK] ^= r_from_to_bb;
1105   byTypeBB[ALL_PIECES] ^= k_from_to_bb ^ r_from_to_bb;
1106   byColorBB[us] ^= k_from_to_bb ^ r_from_to_bb;
1107
1108   // Update board
1109   Piece king = make_piece(us, KING);
1110   Piece rook = make_piece(us, ROOK);
1111   board[kfrom] = board[rfrom] = NO_PIECE;
1112   board[kto] = king;
1113   board[rto] = rook;
1114
1115   // Update piece lists
1116   pieceList[us][KING][index[kfrom]] = kto;
1117   pieceList[us][ROOK][index[rfrom]] = rto;
1118   int tmp = index[rfrom]; // In Chess960 could be kto == rfrom
1119   index[kto] = index[kfrom];
1120   index[rto] = tmp;
1121
1122   if (Do)
1123   {
1124       // Reset capture field
1125       st->capturedType = NO_PIECE_TYPE;
1126
1127       // Update incremental scores
1128       st->psqScore += psq_delta(king, kfrom, kto);
1129       st->psqScore += psq_delta(rook, rfrom, rto);
1130
1131       // Update hash key
1132       st->key ^= Zobrist::psq[us][KING][kfrom] ^ Zobrist::psq[us][KING][kto];
1133       st->key ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
1134
1135       // Clear en passant square
1136       if (st->epSquare != SQ_NONE)
1137       {
1138           st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
1139           st->epSquare = SQ_NONE;
1140       }
1141
1142       // Update castling rights
1143       st->key ^= Zobrist::castle[st->castleRights & castleRightsMask[kfrom]];
1144       st->castleRights &= ~castleRightsMask[kfrom];
1145
1146       // Update checkers BB
1147       st->checkersBB = attackers_to(king_square(~us)) & pieces(us);
1148
1149       sideToMove = ~sideToMove;
1150   }
1151   else
1152       // Undo: point our state pointer back to the previous state
1153       st = st->previous;
1154
1155   assert(pos_is_ok());
1156 }
1157
1158
1159 /// Position::do_null_move() is used to do/undo a "null move": It flips the side
1160 /// to move and updates the hash key without executing any move on the board.
1161 template<bool Do>
1162 void Position::do_null_move(StateInfo& backupSt) {
1163
1164   assert(!in_check());
1165
1166   // Back up the information necessary to undo the null move to the supplied
1167   // StateInfo object. Note that differently from normal case here backupSt
1168   // is actually used as a backup storage not as the new state. This reduces
1169   // the number of fields to be copied.
1170   StateInfo* src = Do ? st : &backupSt;
1171   StateInfo* dst = Do ? &backupSt : st;
1172
1173   dst->key      = src->key;
1174   dst->epSquare = src->epSquare;
1175   dst->psqScore = src->psqScore;
1176   dst->rule50   = src->rule50;
1177   dst->pliesFromNull = src->pliesFromNull;
1178
1179   sideToMove = ~sideToMove;
1180
1181   if (Do)
1182   {
1183       if (st->epSquare != SQ_NONE)
1184           st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
1185
1186       st->key ^= Zobrist::side;
1187       prefetch((char*)TT.first_entry(st->key));
1188
1189       st->epSquare = SQ_NONE;
1190       st->rule50++;
1191       st->pliesFromNull = 0;
1192   }
1193
1194   assert(pos_is_ok());
1195 }
1196
1197 // Explicit template instantiations
1198 template void Position::do_null_move<false>(StateInfo& backupSt);
1199 template void Position::do_null_move<true>(StateInfo& backupSt);
1200
1201
1202 /// Position::see() is a static exchange evaluator: It tries to estimate the
1203 /// material gain or loss resulting from a move. There are three versions of
1204 /// this function: One which takes a destination square as input, one takes a
1205 /// move, and one which takes a 'from' and a 'to' square. The function does
1206 /// not yet understand promotions captures.
1207
1208 int Position::see_sign(Move m) const {
1209
1210   assert(is_ok(m));
1211
1212   // Early return if SEE cannot be negative because captured piece value
1213   // is not less then capturing one. Note that king moves always return
1214   // here because king midgame value is set to 0.
1215   if (PieceValue[MG][piece_on(to_sq(m))] >= PieceValue[MG][piece_moved(m)])
1216       return 1;
1217
1218   return see(m);
1219 }
1220
1221 int Position::see(Move m) const {
1222
1223   Square from, to;
1224   Bitboard occupied, attackers, stmAttackers;
1225   int swapList[32], slIndex = 1;
1226   PieceType captured;
1227   Color stm;
1228
1229   assert(is_ok(m));
1230
1231   from = from_sq(m);
1232   to = to_sq(m);
1233   captured = type_of(piece_on(to));
1234   occupied = pieces() ^ from;
1235
1236   // Handle en passant moves
1237   if (type_of(m) == ENPASSANT)
1238   {
1239       Square capQq = to - pawn_push(sideToMove);
1240
1241       assert(!captured);
1242       assert(type_of(piece_on(capQq)) == PAWN);
1243
1244       // Remove the captured pawn
1245       occupied ^= capQq;
1246       captured = PAWN;
1247   }
1248   else if (type_of(m) == CASTLE)
1249       // Castle moves are implemented as king capturing the rook so cannot be
1250       // handled correctly. Simply return 0 that is always the correct value
1251       // unless the rook is ends up under attack.
1252       return 0;
1253
1254   // Find all attackers to the destination square, with the moving piece
1255   // removed, but possibly an X-ray attacker added behind it.
1256   attackers = attackers_to(to, occupied);
1257
1258   // If the opponent has no attackers we are finished
1259   stm = ~color_of(piece_on(from));
1260   stmAttackers = attackers & pieces(stm);
1261   if (!stmAttackers)
1262       return PieceValue[MG][captured];
1263
1264   // The destination square is defended, which makes things rather more
1265   // difficult to compute. We proceed by building up a "swap list" containing
1266   // the material gain or loss at each stop in a sequence of captures to the
1267   // destination square, where the sides alternately capture, and always
1268   // capture with the least valuable piece. After each capture, we look for
1269   // new X-ray attacks from behind the capturing piece.
1270   swapList[0] = PieceValue[MG][captured];
1271   captured = type_of(piece_on(from));
1272
1273   do {
1274       assert(slIndex < 32);
1275
1276       // Add the new entry to the swap list
1277       swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1278       slIndex++;
1279
1280       // Locate and remove from 'occupied' the next least valuable attacker
1281       captured = next_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1282
1283       attackers &= occupied; // Remove the just found attacker
1284       stm = ~stm;
1285       stmAttackers = attackers & pieces(stm);
1286
1287       if (captured == KING)
1288       {
1289           // Stop before processing a king capture
1290           if (stmAttackers)
1291               swapList[slIndex++] = QueenValueMg * 16;
1292
1293           break;
1294       }
1295
1296   } while (stmAttackers);
1297
1298   // Having built the swap list, we negamax through it to find the best
1299   // achievable score from the point of view of the side to move.
1300   while (--slIndex)
1301       swapList[slIndex-1] = std::min(-swapList[slIndex], swapList[slIndex-1]);
1302
1303   return swapList[0];
1304 }
1305
1306
1307 /// Position::clear() erases the position object to a pristine state, with an
1308 /// empty board, white to move, and no castling rights.
1309
1310 void Position::clear() {
1311
1312   memset(this, 0, sizeof(Position));
1313   startState.epSquare = SQ_NONE;
1314   st = &startState;
1315
1316   for (int i = 0; i < 8; i++)
1317       for (int j = 0; j < 16; j++)
1318           pieceList[0][i][j] = pieceList[1][i][j] = SQ_NONE;
1319 }
1320
1321
1322 /// Position::put_piece() puts a piece on the given square of the board,
1323 /// updating the board array, pieces list, bitboards, and piece counts.
1324
1325 void Position::put_piece(Piece p, Square s) {
1326
1327   Color c = color_of(p);
1328   PieceType pt = type_of(p);
1329
1330   board[s] = p;
1331   index[s] = pieceCount[c][pt]++;
1332   pieceList[c][pt][index[s]] = s;
1333
1334   byTypeBB[ALL_PIECES] |= s;
1335   byTypeBB[pt] |= s;
1336   byColorBB[c] |= s;
1337 }
1338
1339
1340 /// Position::compute_key() computes the hash key of the position. The hash
1341 /// key is usually updated incrementally as moves are made and unmade, the
1342 /// compute_key() function is only used when a new position is set up, and
1343 /// to verify the correctness of the hash key when running in debug mode.
1344
1345 Key Position::compute_key() const {
1346
1347   Key k = Zobrist::castle[st->castleRights];
1348
1349   for (Bitboard b = pieces(); b; )
1350   {
1351       Square s = pop_lsb(&b);
1352       k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1353   }
1354
1355   if (ep_square() != SQ_NONE)
1356       k ^= Zobrist::enpassant[file_of(ep_square())];
1357
1358   if (sideToMove == BLACK)
1359       k ^= Zobrist::side;
1360
1361   return k;
1362 }
1363
1364
1365 /// Position::compute_pawn_key() computes the hash key of the position. The
1366 /// hash key is usually updated incrementally as moves are made and unmade,
1367 /// the compute_pawn_key() function is only used when a new position is set
1368 /// up, and to verify the correctness of the pawn hash key when running in
1369 /// debug mode.
1370
1371 Key Position::compute_pawn_key() const {
1372
1373   Key k = 0;
1374
1375   for (Bitboard b = pieces(PAWN); b; )
1376   {
1377       Square s = pop_lsb(&b);
1378       k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1379   }
1380
1381   return k;
1382 }
1383
1384
1385 /// Position::compute_material_key() computes the hash key of the position.
1386 /// The hash key is usually updated incrementally as moves are made and unmade,
1387 /// the compute_material_key() function is only used when a new position is set
1388 /// up, and to verify the correctness of the material hash key when running in
1389 /// debug mode.
1390
1391 Key Position::compute_material_key() const {
1392
1393   Key k = 0;
1394
1395   for (Color c = WHITE; c <= BLACK; c++)
1396       for (PieceType pt = PAWN; pt <= QUEEN; pt++)
1397           for (int cnt = 0; cnt < piece_count(c, pt); cnt++)
1398               k ^= Zobrist::psq[c][pt][cnt];
1399
1400   return k;
1401 }
1402
1403
1404 /// Position::compute_psq_score() computes the incremental scores for the middle
1405 /// game and the endgame. These functions are used to initialize the incremental
1406 /// scores when a new position is set up, and to verify that the scores are correctly
1407 /// updated by do_move and undo_move when the program is running in debug mode.
1408 Score Position::compute_psq_score() const {
1409
1410   Score score = SCORE_ZERO;
1411
1412   for (Bitboard b = pieces(); b; )
1413   {
1414       Square s = pop_lsb(&b);
1415       score += pieceSquareTable[piece_on(s)][s];
1416   }
1417
1418   return score;
1419 }
1420
1421
1422 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1423 /// game material value for the given side. Material values are updated
1424 /// incrementally during the search, this function is only used while
1425 /// initializing a new Position object.
1426
1427 Value Position::compute_non_pawn_material(Color c) const {
1428
1429   Value value = VALUE_ZERO;
1430
1431   for (PieceType pt = KNIGHT; pt <= QUEEN; pt++)
1432       value += piece_count(c, pt) * PieceValue[MG][pt];
1433
1434   return value;
1435 }
1436
1437
1438 /// Position::is_draw() tests whether the position is drawn by material,
1439 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1440 /// must be done by the search.
1441 template<bool CheckRepetition, bool CheckThreeFold>
1442 bool Position::is_draw() const {
1443
1444   if (   !pieces(PAWN)
1445       && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1446       return true;
1447
1448   if (st->rule50 > 99 && (!in_check() || MoveList<LEGAL>(*this).size()))
1449       return true;
1450
1451   if (CheckRepetition)
1452   {
1453       int i = 4, e = std::min(st->rule50, st->pliesFromNull), cnt;
1454
1455       if (i <= e)
1456       {
1457           StateInfo* stp = st->previous->previous;
1458
1459           for (cnt = 0; i <= e; i += 2)
1460           {
1461               stp = stp->previous->previous;
1462
1463               if (stp->key == st->key && (!CheckThreeFold || ++cnt >= 2))
1464                   return true;
1465           }
1466       }
1467   }
1468
1469   return false;
1470 }
1471
1472 // Explicit template instantiations
1473 template bool Position::is_draw<true,  true>() const;
1474 template bool Position::is_draw<true, false>() const;
1475 template bool Position::is_draw<false,false>() const;
1476
1477
1478 /// Position::flip() flips position with the white and black sides reversed. This
1479 /// is only useful for debugging especially for finding evaluation symmetry bugs.
1480
1481 void Position::flip() {
1482
1483   const Position pos(*this);
1484
1485   clear();
1486
1487   sideToMove = ~pos.side_to_move();
1488   thisThread = pos.this_thread();
1489   nodes = pos.nodes_searched();
1490   chess960 = pos.is_chess960();
1491   startPosPly = pos.startpos_ply_counter();
1492
1493   for (Square s = SQ_A1; s <= SQ_H8; s++)
1494       if (!pos.is_empty(s))
1495           put_piece(Piece(pos.piece_on(s) ^ 8), ~s);
1496
1497   if (pos.can_castle(WHITE_OO))
1498       set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, KING_SIDE));
1499   if (pos.can_castle(WHITE_OOO))
1500       set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, QUEEN_SIDE));
1501   if (pos.can_castle(BLACK_OO))
1502       set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, KING_SIDE));
1503   if (pos.can_castle(BLACK_OOO))
1504       set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, QUEEN_SIDE));
1505
1506   if (pos.st->epSquare != SQ_NONE)
1507       st->epSquare = ~pos.st->epSquare;
1508
1509   st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
1510
1511   st->key = compute_key();
1512   st->pawnKey = compute_pawn_key();
1513   st->materialKey = compute_material_key();
1514   st->psqScore = compute_psq_score();
1515   st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
1516   st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
1517
1518   assert(pos_is_ok());
1519 }
1520
1521
1522 /// Position::pos_is_ok() performs some consitency checks for the position object.
1523 /// This is meant to be helpful when debugging.
1524
1525 bool Position::pos_is_ok(int* failedStep) const {
1526
1527   int dummy, *step = failedStep ? failedStep : &dummy;
1528
1529   // What features of the position should be verified?
1530   const bool all = false;
1531
1532   const bool debugBitboards       = all || false;
1533   const bool debugKingCount       = all || false;
1534   const bool debugKingCapture     = all || false;
1535   const bool debugCheckerCount    = all || false;
1536   const bool debugKey             = all || false;
1537   const bool debugMaterialKey     = all || false;
1538   const bool debugPawnKey         = all || false;
1539   const bool debugIncrementalEval = all || false;
1540   const bool debugNonPawnMaterial = all || false;
1541   const bool debugPieceCounts     = all || false;
1542   const bool debugPieceList       = all || false;
1543   const bool debugCastleSquares   = all || false;
1544
1545   *step = 1;
1546
1547   if (sideToMove != WHITE && sideToMove != BLACK)
1548       return false;
1549
1550   if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1551       return false;
1552
1553   if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1554       return false;
1555
1556   if ((*step)++, debugKingCount)
1557   {
1558       int kingCount[COLOR_NB] = {};
1559
1560       for (Square s = SQ_A1; s <= SQ_H8; s++)
1561           if (type_of(piece_on(s)) == KING)
1562               kingCount[color_of(piece_on(s))]++;
1563
1564       if (kingCount[0] != 1 || kingCount[1] != 1)
1565           return false;
1566   }
1567
1568   if ((*step)++, debugKingCapture)
1569       if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1570           return false;
1571
1572   if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1573       return false;
1574
1575   if ((*step)++, debugBitboards)
1576   {
1577       // The intersection of the white and black pieces must be empty
1578       if (pieces(WHITE) & pieces(BLACK))
1579           return false;
1580
1581       // The union of the white and black pieces must be equal to all
1582       // occupied squares
1583       if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1584           return false;
1585
1586       // Separate piece type bitboards must have empty intersections
1587       for (PieceType p1 = PAWN; p1 <= KING; p1++)
1588           for (PieceType p2 = PAWN; p2 <= KING; p2++)
1589               if (p1 != p2 && (pieces(p1) & pieces(p2)))
1590                   return false;
1591   }
1592
1593   if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1594       return false;
1595
1596   if ((*step)++, debugKey && st->key != compute_key())
1597       return false;
1598
1599   if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1600       return false;
1601
1602   if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1603       return false;
1604
1605   if ((*step)++, debugIncrementalEval && st->psqScore != compute_psq_score())
1606       return false;
1607
1608   if ((*step)++, debugNonPawnMaterial)
1609   {
1610       if (   st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1611           || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1612           return false;
1613   }
1614
1615   if ((*step)++, debugPieceCounts)
1616       for (Color c = WHITE; c <= BLACK; c++)
1617           for (PieceType pt = PAWN; pt <= KING; pt++)
1618               if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1619                   return false;
1620
1621   if ((*step)++, debugPieceList)
1622       for (Color c = WHITE; c <= BLACK; c++)
1623           for (PieceType pt = PAWN; pt <= KING; pt++)
1624               for (int i = 0; i < pieceCount[c][pt]; i++)
1625               {
1626                   if (piece_on(piece_list(c, pt)[i]) != make_piece(c, pt))
1627                       return false;
1628
1629                   if (index[piece_list(c, pt)[i]] != i)
1630                       return false;
1631               }
1632
1633   if ((*step)++, debugCastleSquares)
1634       for (Color c = WHITE; c <= BLACK; c++)
1635           for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1636           {
1637               CastleRight cr = make_castle_right(c, s);
1638
1639               if (!can_castle(cr))
1640                   continue;
1641
1642               if ((castleRightsMask[king_square(c)] & cr) != cr)
1643                   return false;
1644
1645               if (   piece_on(castleRookSquare[c][s]) != make_piece(c, ROOK)
1646                   || castleRightsMask[castleRookSquare[c][s]] != cr)
1647                   return false;
1648           }
1649
1650   *step = 0;
1651   return true;
1652 }