ef5fd97091cc4f0f478b41954090ba8e72a1799f
[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::is_pseudo_legal() takes a random move and tests whether the move
525 /// is pseudo legal. It is used to validate moves from TT that can be corrupted
526 /// due to SMP concurrent access or hash position key aliasing.
527
528 bool Position::is_pseudo_legal(const Move m) const {
529
530   Color us = sideToMove;
531   Square from = from_sq(m);
532   Square to = to_sq(m);
533   Piece pc = piece_moved(m);
534
535   // Use a slower but simpler function for uncommon cases
536   if (type_of(m) != NORMAL)
537       return MoveList<LEGAL>(*this).contains(m);
538
539   // Is not a promotion, so promotion piece must be empty
540   if (promotion_type(m) - 2 != NO_PIECE_TYPE)
541       return false;
542
543   // If the from square is not occupied by a piece belonging to the side to
544   // move, the move is obviously not legal.
545   if (pc == NO_PIECE || color_of(pc) != us)
546       return false;
547
548   // The destination square cannot be occupied by a friendly piece
549   if (piece_on(to) != NO_PIECE && color_of(piece_on(to)) == us)
550       return false;
551
552   // Handle the special case of a pawn move
553   if (type_of(pc) == PAWN)
554   {
555       // Move direction must be compatible with pawn color
556       int direction = to - from;
557       if ((us == WHITE) != (direction > 0))
558           return false;
559
560       // We have already handled promotion moves, so destination
561       // cannot be on the 8/1th rank.
562       if (rank_of(to) == RANK_8 || rank_of(to) == RANK_1)
563           return false;
564
565       // Proceed according to the square delta between the origin and
566       // destination squares.
567       switch (direction)
568       {
569       case DELTA_NW:
570       case DELTA_NE:
571       case DELTA_SW:
572       case DELTA_SE:
573       // Capture. The destination square must be occupied by an enemy
574       // piece (en passant captures was handled earlier).
575       if (piece_on(to) == NO_PIECE || color_of(piece_on(to)) != ~us)
576           return false;
577
578       // From and to files must be one file apart, avoids a7h5
579       if (abs(file_of(from) - file_of(to)) != 1)
580           return false;
581       break;
582
583       case DELTA_N:
584       case DELTA_S:
585       // Pawn push. The destination square must be empty.
586       if (!is_empty(to))
587           return false;
588       break;
589
590       case DELTA_NN:
591       // Double white pawn push. The destination square must be on the fourth
592       // rank, and both the destination square and the square between the
593       // source and destination squares must be empty.
594       if (    rank_of(to) != RANK_4
595           || !is_empty(to)
596           || !is_empty(from + DELTA_N))
597           return false;
598       break;
599
600       case DELTA_SS:
601       // Double black pawn push. The destination square must be on the fifth
602       // rank, and both the destination square and the square between the
603       // source and destination squares must be empty.
604       if (    rank_of(to) != RANK_5
605           || !is_empty(to)
606           || !is_empty(from + DELTA_S))
607           return false;
608       break;
609
610       default:
611           return false;
612       }
613   }
614   else if (!(attacks_from(pc, from) & to))
615       return false;
616
617   // Evasions generator already takes care to avoid some kind of illegal moves
618   // and pl_move_is_legal() relies on this. So we have to take care that the
619   // same kind of moves are filtered out here.
620   if (in_check())
621   {
622       if (type_of(pc) != KING)
623       {
624           // Double check? In this case a king move is required
625           if (more_than_one(checkers()))
626               return false;
627
628           // Our move must be a blocking evasion or a capture of the checking piece
629           if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
630               return false;
631       }
632       // In case of king moves under check we have to remove king so to catch
633       // as invalid moves like b1a1 when opposite queen is on c1.
634       else if (attackers_to(to, pieces() ^ from) & pieces(~us))
635           return false;
636   }
637
638   return true;
639 }
640
641
642 /// Position::move_gives_check() tests whether a pseudo-legal move gives a check
643
644 bool Position::move_gives_check(Move m, const CheckInfo& ci) const {
645
646   assert(is_ok(m));
647   assert(ci.dcCandidates == discovered_check_candidates());
648   assert(color_of(piece_moved(m)) == sideToMove);
649
650   Square from = from_sq(m);
651   Square to = to_sq(m);
652   PieceType pt = type_of(piece_on(from));
653
654   // Direct check ?
655   if (ci.checkSq[pt] & to)
656       return true;
657
658   // Discovery check ?
659   if (ci.dcCandidates && (ci.dcCandidates & from))
660   {
661       // For pawn and king moves we need to verify also direction
662       if (   (pt != PAWN && pt != KING)
663           || !squares_aligned(from, to, king_square(~sideToMove)))
664           return true;
665   }
666
667   // Can we skip the ugly special cases ?
668   if (type_of(m) == NORMAL)
669       return false;
670
671   Color us = sideToMove;
672   Square ksq = king_square(~us);
673
674   switch (type_of(m))
675   {
676   case PROMOTION:
677       return attacks_from(Piece(promotion_type(m)), to, pieces() ^ from) & ksq;
678
679   // En passant capture with check ? We have already handled the case
680   // of direct checks and ordinary discovered check, the only case we
681   // need to handle is the unusual case of a discovered check through
682   // the captured pawn.
683   case ENPASSANT:
684   {
685       Square capsq = file_of(to) | rank_of(from);
686       Bitboard b = (pieces() ^ from ^ capsq) | to;
687
688       return  (attacks_bb<  ROOK>(ksq, b) & pieces(us, QUEEN, ROOK))
689             | (attacks_bb<BISHOP>(ksq, b) & pieces(us, QUEEN, BISHOP));
690   }
691   case CASTLE:
692   {
693       Square kfrom = from;
694       Square rfrom = to; // 'King captures the rook' notation
695       Square kto = relative_square(us, rfrom > kfrom ? SQ_G1 : SQ_C1);
696       Square rto = relative_square(us, rfrom > kfrom ? SQ_F1 : SQ_D1);
697       Bitboard b = (pieces() ^ kfrom ^ rfrom) | rto | kto;
698
699       return attacks_bb<ROOK>(rto, b) & ksq;
700   }
701   default:
702       assert(false);
703       return false;
704   }
705 }
706
707
708 /// Position::do_move() makes a move, and saves all information necessary
709 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
710 /// moves should be filtered out before this function is called.
711
712 void Position::do_move(Move m, StateInfo& newSt) {
713
714   CheckInfo ci(*this);
715   do_move(m, newSt, ci, move_gives_check(m, ci));
716 }
717
718 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
719
720   assert(is_ok(m));
721   assert(&newSt != st);
722
723   nodes++;
724   Key k = st->key;
725
726   // Copy some fields of old state to our new StateInfo object except the ones
727   // which are going to be recalculated from scratch anyway, then switch our state
728   // pointer to point to the new, ready to be updated, state.
729   memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
730
731   newSt.previous = st;
732   st = &newSt;
733
734   // Update side to move
735   k ^= Zobrist::side;
736
737   // Increment the 50 moves rule draw counter. Resetting it to zero in the
738   // case of a capture or a pawn move is taken care of later.
739   st->rule50++;
740   st->pliesFromNull++;
741
742   if (type_of(m) == CASTLE)
743   {
744       st->key = k;
745       do_castle_move<true>(m);
746       return;
747   }
748
749   Color us = sideToMove;
750   Color them = ~us;
751   Square from = from_sq(m);
752   Square to = to_sq(m);
753   Piece piece = piece_on(from);
754   PieceType pt = type_of(piece);
755   PieceType capture = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
756
757   assert(color_of(piece) == us);
758   assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them);
759   assert(capture != KING);
760
761   if (capture)
762   {
763       Square capsq = to;
764
765       // If the captured piece is a pawn, update pawn hash key, otherwise
766       // update non-pawn material.
767       if (capture == PAWN)
768       {
769           if (type_of(m) == ENPASSANT)
770           {
771               capsq += pawn_push(them);
772
773               assert(pt == PAWN);
774               assert(to == st->epSquare);
775               assert(relative_rank(us, to) == RANK_6);
776               assert(piece_on(to) == NO_PIECE);
777               assert(piece_on(capsq) == make_piece(them, PAWN));
778
779               board[capsq] = NO_PIECE;
780           }
781
782           st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
783       }
784       else
785           st->npMaterial[them] -= PieceValue[MG][capture];
786
787       // Remove the captured piece
788       byTypeBB[ALL_PIECES] ^= capsq;
789       byTypeBB[capture] ^= capsq;
790       byColorBB[them] ^= capsq;
791
792       // Update piece list, move the last piece at index[capsq] position and
793       // shrink the list.
794       //
795       // WARNING: This is a not revresible operation. When we will reinsert the
796       // captured piece in undo_move() we will put it at the end of the list and
797       // not in its original place, it means index[] and pieceList[] are not
798       // guaranteed to be invariant to a do_move() + undo_move() sequence.
799       Square lastSquare = pieceList[them][capture][--pieceCount[them][capture]];
800       index[lastSquare] = index[capsq];
801       pieceList[them][capture][index[lastSquare]] = lastSquare;
802       pieceList[them][capture][pieceCount[them][capture]] = SQ_NONE;
803
804       // Update hash keys
805       k ^= Zobrist::psq[them][capture][capsq];
806       st->materialKey ^= Zobrist::psq[them][capture][pieceCount[them][capture]];
807
808       // Update incremental scores
809       st->psqScore -= pieceSquareTable[make_piece(them, capture)][capsq];
810
811       // Reset rule 50 counter
812       st->rule50 = 0;
813   }
814
815   // Update hash key
816   k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
817
818   // Reset en passant square
819   if (st->epSquare != SQ_NONE)
820   {
821       k ^= Zobrist::enpassant[file_of(st->epSquare)];
822       st->epSquare = SQ_NONE;
823   }
824
825   // Update castle rights if needed
826   if (st->castleRights && (castleRightsMask[from] | castleRightsMask[to]))
827   {
828       int cr = castleRightsMask[from] | castleRightsMask[to];
829       k ^= Zobrist::castle[st->castleRights & cr];
830       st->castleRights &= ~cr;
831   }
832
833   // Prefetch TT access as soon as we know key is updated
834   prefetch((char*)TT.first_entry(k));
835
836   // Move the piece
837   Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
838   byTypeBB[ALL_PIECES] ^= from_to_bb;
839   byTypeBB[pt] ^= from_to_bb;
840   byColorBB[us] ^= from_to_bb;
841
842   board[to] = board[from];
843   board[from] = NO_PIECE;
844
845   // Update piece lists, index[from] is not updated and becomes stale. This
846   // works as long as index[] is accessed just by known occupied squares.
847   index[to] = index[from];
848   pieceList[us][pt][index[to]] = to;
849
850   // If the moving piece is a pawn do some special extra work
851   if (pt == PAWN)
852   {
853       // Set en-passant square, only if moved pawn can be captured
854       if (   (int(to) ^ int(from)) == 16
855           && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
856       {
857           st->epSquare = Square((from + to) / 2);
858           k ^= Zobrist::enpassant[file_of(st->epSquare)];
859       }
860
861       if (type_of(m) == PROMOTION)
862       {
863           PieceType promotion = promotion_type(m);
864
865           assert(relative_rank(us, to) == RANK_8);
866           assert(promotion >= KNIGHT && promotion <= QUEEN);
867
868           // Replace the pawn with the promoted piece
869           byTypeBB[PAWN] ^= to;
870           byTypeBB[promotion] |= to;
871           board[to] = make_piece(us, promotion);
872
873           // Update piece lists, move the last pawn at index[to] position
874           // and shrink the list. Add a new promotion piece to the list.
875           Square lastSquare = pieceList[us][PAWN][--pieceCount[us][PAWN]];
876           index[lastSquare] = index[to];
877           pieceList[us][PAWN][index[lastSquare]] = lastSquare;
878           pieceList[us][PAWN][pieceCount[us][PAWN]] = SQ_NONE;
879           index[to] = pieceCount[us][promotion];
880           pieceList[us][promotion][index[to]] = to;
881
882           // Update hash keys
883           k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
884           st->pawnKey ^= Zobrist::psq[us][PAWN][to];
885           st->materialKey ^=  Zobrist::psq[us][promotion][pieceCount[us][promotion]++]
886                             ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
887
888           // Update incremental score
889           st->psqScore +=  pieceSquareTable[make_piece(us, promotion)][to]
890                          - pieceSquareTable[make_piece(us, PAWN)][to];
891
892           // Update material
893           st->npMaterial[us] += PieceValue[MG][promotion];
894       }
895
896       // Update pawn hash key
897       st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
898
899       // Reset rule 50 draw counter
900       st->rule50 = 0;
901   }
902
903   // Prefetch pawn and material hash tables
904   prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
905   prefetch((char*)thisThread->materialTable[st->materialKey]);
906
907   // Update incremental scores
908   st->psqScore += psq_delta(piece, from, to);
909
910   // Set capture piece
911   st->capturedType = capture;
912
913   // Update the key with the final value
914   st->key = k;
915
916   // Update checkers bitboard, piece must be already moved
917   st->checkersBB = 0;
918
919   if (moveIsCheck)
920   {
921       if (type_of(m) != NORMAL)
922           st->checkersBB = attackers_to(king_square(them)) & pieces(us);
923       else
924       {
925           // Direct checks
926           if (ci.checkSq[pt] & to)
927               st->checkersBB |= to;
928
929           // Discovery checks
930           if (ci.dcCandidates && (ci.dcCandidates & from))
931           {
932               if (pt != ROOK)
933                   st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
934
935               if (pt != BISHOP)
936                   st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
937           }
938       }
939   }
940
941   sideToMove = ~sideToMove;
942
943   assert(pos_is_ok());
944 }
945
946
947 /// Position::undo_move() unmakes a move. When it returns, the position should
948 /// be restored to exactly the same state as before the move was made.
949
950 void Position::undo_move(Move m) {
951
952   assert(is_ok(m));
953
954   sideToMove = ~sideToMove;
955
956   if (type_of(m) == CASTLE)
957   {
958       do_castle_move<false>(m);
959       return;
960   }
961
962   Color us = sideToMove;
963   Color them = ~us;
964   Square from = from_sq(m);
965   Square to = to_sq(m);
966   Piece piece = piece_on(to);
967   PieceType pt = type_of(piece);
968   PieceType capture = st->capturedType;
969
970   assert(is_empty(from));
971   assert(color_of(piece) == us);
972   assert(capture != KING);
973
974   if (type_of(m) == PROMOTION)
975   {
976       PieceType promotion = promotion_type(m);
977
978       assert(promotion == pt);
979       assert(relative_rank(us, to) == RANK_8);
980       assert(promotion >= KNIGHT && promotion <= QUEEN);
981
982       // Replace the promoted piece with the pawn
983       byTypeBB[promotion] ^= to;
984       byTypeBB[PAWN] |= to;
985       board[to] = make_piece(us, PAWN);
986
987       // Update piece lists, move the last promoted piece at index[to] position
988       // and shrink the list. Add a new pawn to the list.
989       Square lastSquare = pieceList[us][promotion][--pieceCount[us][promotion]];
990       index[lastSquare] = index[to];
991       pieceList[us][promotion][index[lastSquare]] = lastSquare;
992       pieceList[us][promotion][pieceCount[us][promotion]] = SQ_NONE;
993       index[to] = pieceCount[us][PAWN]++;
994       pieceList[us][PAWN][index[to]] = to;
995
996       pt = PAWN;
997   }
998
999   // Put the piece back at the source square
1000   Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
1001   byTypeBB[ALL_PIECES] ^= from_to_bb;
1002   byTypeBB[pt] ^= from_to_bb;
1003   byColorBB[us] ^= from_to_bb;
1004
1005   board[from] = board[to];
1006   board[to] = NO_PIECE;
1007
1008   // Update piece lists, index[to] is not updated and becomes stale. This
1009   // works as long as index[] is accessed just by known occupied squares.
1010   index[from] = index[to];
1011   pieceList[us][pt][index[from]] = from;
1012
1013   if (capture)
1014   {
1015       Square capsq = to;
1016
1017       if (type_of(m) == ENPASSANT)
1018       {
1019           capsq -= pawn_push(us);
1020
1021           assert(pt == PAWN);
1022           assert(to == st->previous->epSquare);
1023           assert(relative_rank(us, to) == RANK_6);
1024           assert(piece_on(capsq) == NO_PIECE);
1025       }
1026
1027       // Restore the captured piece
1028       byTypeBB[ALL_PIECES] |= capsq;
1029       byTypeBB[capture] |= capsq;
1030       byColorBB[them] |= capsq;
1031
1032       board[capsq] = make_piece(them, capture);
1033
1034       // Update piece list, add a new captured piece in capsq square
1035       index[capsq] = pieceCount[them][capture]++;
1036       pieceList[them][capture][index[capsq]] = capsq;
1037   }
1038
1039   // Finally point our state pointer back to the previous state
1040   st = st->previous;
1041
1042   assert(pos_is_ok());
1043 }
1044
1045
1046 /// Position::do_castle_move() is a private method used to do/undo a castling
1047 /// move. Note that castling moves are encoded as "king captures friendly rook"
1048 /// moves, for instance white short castling in a non-Chess960 game is encoded
1049 /// as e1h1.
1050 template<bool Do>
1051 void Position::do_castle_move(Move m) {
1052
1053   assert(is_ok(m));
1054   assert(type_of(m) == CASTLE);
1055
1056   Square kto, kfrom, rfrom, rto, kAfter, rAfter;
1057
1058   Color us = sideToMove;
1059   Square kBefore = from_sq(m);
1060   Square rBefore = to_sq(m);
1061
1062   // Find after-castle squares for king and rook
1063   if (rBefore > kBefore) // O-O
1064   {
1065       kAfter = relative_square(us, SQ_G1);
1066       rAfter = relative_square(us, SQ_F1);
1067   }
1068   else // O-O-O
1069   {
1070       kAfter = relative_square(us, SQ_C1);
1071       rAfter = relative_square(us, SQ_D1);
1072   }
1073
1074   kfrom = Do ? kBefore : kAfter;
1075   rfrom = Do ? rBefore : rAfter;
1076
1077   kto = Do ? kAfter : kBefore;
1078   rto = Do ? rAfter : rBefore;
1079
1080   assert(piece_on(kfrom) == make_piece(us, KING));
1081   assert(piece_on(rfrom) == make_piece(us, ROOK));
1082
1083   // Move the pieces, with some care; in chess960 could be kto == rfrom
1084   Bitboard k_from_to_bb = SquareBB[kfrom] ^ SquareBB[kto];
1085   Bitboard r_from_to_bb = SquareBB[rfrom] ^ SquareBB[rto];
1086   byTypeBB[KING] ^= k_from_to_bb;
1087   byTypeBB[ROOK] ^= r_from_to_bb;
1088   byTypeBB[ALL_PIECES] ^= k_from_to_bb ^ r_from_to_bb;
1089   byColorBB[us] ^= k_from_to_bb ^ r_from_to_bb;
1090
1091   // Update board
1092   Piece king = make_piece(us, KING);
1093   Piece rook = make_piece(us, ROOK);
1094   board[kfrom] = board[rfrom] = NO_PIECE;
1095   board[kto] = king;
1096   board[rto] = rook;
1097
1098   // Update piece lists
1099   pieceList[us][KING][index[kfrom]] = kto;
1100   pieceList[us][ROOK][index[rfrom]] = rto;
1101   int tmp = index[rfrom]; // In Chess960 could be kto == rfrom
1102   index[kto] = index[kfrom];
1103   index[rto] = tmp;
1104
1105   if (Do)
1106   {
1107       // Reset capture field
1108       st->capturedType = NO_PIECE_TYPE;
1109
1110       // Update incremental scores
1111       st->psqScore += psq_delta(king, kfrom, kto);
1112       st->psqScore += psq_delta(rook, rfrom, rto);
1113
1114       // Update hash key
1115       st->key ^= Zobrist::psq[us][KING][kfrom] ^ Zobrist::psq[us][KING][kto];
1116       st->key ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
1117
1118       // Clear en passant square
1119       if (st->epSquare != SQ_NONE)
1120       {
1121           st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
1122           st->epSquare = SQ_NONE;
1123       }
1124
1125       // Update castling rights
1126       st->key ^= Zobrist::castle[st->castleRights & castleRightsMask[kfrom]];
1127       st->castleRights &= ~castleRightsMask[kfrom];
1128
1129       // Update checkers BB
1130       st->checkersBB = attackers_to(king_square(~us)) & pieces(us);
1131
1132       sideToMove = ~sideToMove;
1133   }
1134   else
1135       // Undo: point our state pointer back to the previous state
1136       st = st->previous;
1137
1138   assert(pos_is_ok());
1139 }
1140
1141
1142 /// Position::do_null_move() is used to do/undo a "null move": It flips the side
1143 /// to move and updates the hash key without executing any move on the board.
1144 template<bool Do>
1145 void Position::do_null_move(StateInfo& backupSt) {
1146
1147   assert(!in_check());
1148
1149   // Back up the information necessary to undo the null move to the supplied
1150   // StateInfo object. Note that differently from normal case here backupSt
1151   // is actually used as a backup storage not as the new state. This reduces
1152   // the number of fields to be copied.
1153   StateInfo* src = Do ? st : &backupSt;
1154   StateInfo* dst = Do ? &backupSt : st;
1155
1156   dst->key      = src->key;
1157   dst->epSquare = src->epSquare;
1158   dst->psqScore = src->psqScore;
1159   dst->rule50   = src->rule50;
1160   dst->pliesFromNull = src->pliesFromNull;
1161
1162   sideToMove = ~sideToMove;
1163
1164   if (Do)
1165   {
1166       if (st->epSquare != SQ_NONE)
1167           st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
1168
1169       st->key ^= Zobrist::side;
1170       prefetch((char*)TT.first_entry(st->key));
1171
1172       st->epSquare = SQ_NONE;
1173       st->rule50++;
1174       st->pliesFromNull = 0;
1175   }
1176
1177   assert(pos_is_ok());
1178 }
1179
1180 // Explicit template instantiations
1181 template void Position::do_null_move<false>(StateInfo& backupSt);
1182 template void Position::do_null_move<true>(StateInfo& backupSt);
1183
1184
1185 /// Position::see() is a static exchange evaluator: It tries to estimate the
1186 /// material gain or loss resulting from a move. There are three versions of
1187 /// this function: One which takes a destination square as input, one takes a
1188 /// move, and one which takes a 'from' and a 'to' square. The function does
1189 /// not yet understand promotions captures.
1190
1191 int Position::see_sign(Move m) const {
1192
1193   assert(is_ok(m));
1194
1195   // Early return if SEE cannot be negative because captured piece value
1196   // is not less then capturing one. Note that king moves always return
1197   // here because king midgame value is set to 0.
1198   if (PieceValue[MG][piece_on(to_sq(m))] >= PieceValue[MG][piece_moved(m)])
1199       return 1;
1200
1201   return see(m);
1202 }
1203
1204 int Position::see(Move m) const {
1205
1206   Square from, to;
1207   Bitboard occupied, attackers, stmAttackers;
1208   int swapList[32], slIndex = 1;
1209   PieceType captured;
1210   Color stm;
1211
1212   assert(is_ok(m));
1213
1214   from = from_sq(m);
1215   to = to_sq(m);
1216   captured = type_of(piece_on(to));
1217   occupied = pieces() ^ from;
1218
1219   // Handle en passant moves
1220   if (type_of(m) == ENPASSANT)
1221   {
1222       Square capQq = to - pawn_push(sideToMove);
1223
1224       assert(!captured);
1225       assert(type_of(piece_on(capQq)) == PAWN);
1226
1227       // Remove the captured pawn
1228       occupied ^= capQq;
1229       captured = PAWN;
1230   }
1231   else if (type_of(m) == CASTLE)
1232       // Castle moves are implemented as king capturing the rook so cannot be
1233       // handled correctly. Simply return 0 that is always the correct value
1234       // unless the rook is ends up under attack.
1235       return 0;
1236
1237   // Find all attackers to the destination square, with the moving piece
1238   // removed, but possibly an X-ray attacker added behind it.
1239   attackers = attackers_to(to, occupied);
1240
1241   // If the opponent has no attackers we are finished
1242   stm = ~color_of(piece_on(from));
1243   stmAttackers = attackers & pieces(stm);
1244   if (!stmAttackers)
1245       return PieceValue[MG][captured];
1246
1247   // The destination square is defended, which makes things rather more
1248   // difficult to compute. We proceed by building up a "swap list" containing
1249   // the material gain or loss at each stop in a sequence of captures to the
1250   // destination square, where the sides alternately capture, and always
1251   // capture with the least valuable piece. After each capture, we look for
1252   // new X-ray attacks from behind the capturing piece.
1253   swapList[0] = PieceValue[MG][captured];
1254   captured = type_of(piece_on(from));
1255
1256   do {
1257       assert(slIndex < 32);
1258
1259       // Add the new entry to the swap list
1260       swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1261       slIndex++;
1262
1263       // Locate and remove from 'occupied' the next least valuable attacker
1264       captured = next_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1265
1266       attackers &= occupied; // Remove the just found attacker
1267       stm = ~stm;
1268       stmAttackers = attackers & pieces(stm);
1269
1270       if (captured == KING)
1271       {
1272           // Stop before processing a king capture
1273           if (stmAttackers)
1274               swapList[slIndex++] = QueenValueMg * 16;
1275
1276           break;
1277       }
1278
1279   } while (stmAttackers);
1280
1281   // Having built the swap list, we negamax through it to find the best
1282   // achievable score from the point of view of the side to move.
1283   while (--slIndex)
1284       swapList[slIndex-1] = std::min(-swapList[slIndex], swapList[slIndex-1]);
1285
1286   return swapList[0];
1287 }
1288
1289
1290 /// Position::clear() erases the position object to a pristine state, with an
1291 /// empty board, white to move, and no castling rights.
1292
1293 void Position::clear() {
1294
1295   memset(this, 0, sizeof(Position));
1296   startState.epSquare = SQ_NONE;
1297   st = &startState;
1298
1299   for (int i = 0; i < 8; i++)
1300       for (int j = 0; j < 16; j++)
1301           pieceList[0][i][j] = pieceList[1][i][j] = SQ_NONE;
1302 }
1303
1304
1305 /// Position::put_piece() puts a piece on the given square of the board,
1306 /// updating the board array, pieces list, bitboards, and piece counts.
1307
1308 void Position::put_piece(Piece p, Square s) {
1309
1310   Color c = color_of(p);
1311   PieceType pt = type_of(p);
1312
1313   board[s] = p;
1314   index[s] = pieceCount[c][pt]++;
1315   pieceList[c][pt][index[s]] = s;
1316
1317   byTypeBB[ALL_PIECES] |= s;
1318   byTypeBB[pt] |= s;
1319   byColorBB[c] |= s;
1320 }
1321
1322
1323 /// Position::compute_key() computes the hash key of the position. The hash
1324 /// key is usually updated incrementally as moves are made and unmade, the
1325 /// compute_key() function is only used when a new position is set up, and
1326 /// to verify the correctness of the hash key when running in debug mode.
1327
1328 Key Position::compute_key() const {
1329
1330   Key k = Zobrist::castle[st->castleRights];
1331
1332   for (Bitboard b = pieces(); b; )
1333   {
1334       Square s = pop_lsb(&b);
1335       k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1336   }
1337
1338   if (ep_square() != SQ_NONE)
1339       k ^= Zobrist::enpassant[file_of(ep_square())];
1340
1341   if (sideToMove == BLACK)
1342       k ^= Zobrist::side;
1343
1344   return k;
1345 }
1346
1347
1348 /// Position::compute_pawn_key() computes the hash key of the position. The
1349 /// hash key is usually updated incrementally as moves are made and unmade,
1350 /// the compute_pawn_key() function is only used when a new position is set
1351 /// up, and to verify the correctness of the pawn hash key when running in
1352 /// debug mode.
1353
1354 Key Position::compute_pawn_key() const {
1355
1356   Key k = 0;
1357
1358   for (Bitboard b = pieces(PAWN); b; )
1359   {
1360       Square s = pop_lsb(&b);
1361       k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1362   }
1363
1364   return k;
1365 }
1366
1367
1368 /// Position::compute_material_key() computes the hash key of the position.
1369 /// The hash key is usually updated incrementally as moves are made and unmade,
1370 /// the compute_material_key() function is only used when a new position is set
1371 /// up, and to verify the correctness of the material hash key when running in
1372 /// debug mode.
1373
1374 Key Position::compute_material_key() const {
1375
1376   Key k = 0;
1377
1378   for (Color c = WHITE; c <= BLACK; c++)
1379       for (PieceType pt = PAWN; pt <= QUEEN; pt++)
1380           for (int cnt = 0; cnt < piece_count(c, pt); cnt++)
1381               k ^= Zobrist::psq[c][pt][cnt];
1382
1383   return k;
1384 }
1385
1386
1387 /// Position::compute_psq_score() computes the incremental scores for the middle
1388 /// game and the endgame. These functions are used to initialize the incremental
1389 /// scores when a new position is set up, and to verify that the scores are correctly
1390 /// updated by do_move and undo_move when the program is running in debug mode.
1391 Score Position::compute_psq_score() const {
1392
1393   Score score = SCORE_ZERO;
1394
1395   for (Bitboard b = pieces(); b; )
1396   {
1397       Square s = pop_lsb(&b);
1398       score += pieceSquareTable[piece_on(s)][s];
1399   }
1400
1401   return score;
1402 }
1403
1404
1405 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1406 /// game material value for the given side. Material values are updated
1407 /// incrementally during the search, this function is only used while
1408 /// initializing a new Position object.
1409
1410 Value Position::compute_non_pawn_material(Color c) const {
1411
1412   Value value = VALUE_ZERO;
1413
1414   for (PieceType pt = KNIGHT; pt <= QUEEN; pt++)
1415       value += piece_count(c, pt) * PieceValue[MG][pt];
1416
1417   return value;
1418 }
1419
1420
1421 /// Position::is_draw() tests whether the position is drawn by material,
1422 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1423 /// must be done by the search.
1424 template<bool CheckRepetition, bool CheckThreeFold>
1425 bool Position::is_draw() const {
1426
1427   if (   !pieces(PAWN)
1428       && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1429       return true;
1430
1431   if (st->rule50 > 99 && (!in_check() || MoveList<LEGAL>(*this).size()))
1432       return true;
1433
1434   if (CheckRepetition)
1435   {
1436       int i = 4, e = std::min(st->rule50, st->pliesFromNull), cnt;
1437
1438       if (i <= e)
1439       {
1440           StateInfo* stp = st->previous->previous;
1441
1442           for (cnt = 0; i <= e; i += 2)
1443           {
1444               stp = stp->previous->previous;
1445
1446               if (stp->key == st->key && (!CheckThreeFold || ++cnt >= 2))
1447                   return true;
1448           }
1449       }
1450   }
1451
1452   return false;
1453 }
1454
1455 // Explicit template instantiations
1456 template bool Position::is_draw<true,  true>() const;
1457 template bool Position::is_draw<true, false>() const;
1458 template bool Position::is_draw<false,false>() const;
1459
1460
1461 /// Position::flip() flips position with the white and black sides reversed. This
1462 /// is only useful for debugging especially for finding evaluation symmetry bugs.
1463
1464 void Position::flip() {
1465
1466   const Position pos(*this);
1467
1468   clear();
1469
1470   sideToMove = ~pos.side_to_move();
1471   thisThread = pos.this_thread();
1472   nodes = pos.nodes_searched();
1473   chess960 = pos.is_chess960();
1474   startPosPly = pos.startpos_ply_counter();
1475
1476   for (Square s = SQ_A1; s <= SQ_H8; s++)
1477       if (!pos.is_empty(s))
1478           put_piece(Piece(pos.piece_on(s) ^ 8), ~s);
1479
1480   if (pos.can_castle(WHITE_OO))
1481       set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, KING_SIDE));
1482   if (pos.can_castle(WHITE_OOO))
1483       set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, QUEEN_SIDE));
1484   if (pos.can_castle(BLACK_OO))
1485       set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, KING_SIDE));
1486   if (pos.can_castle(BLACK_OOO))
1487       set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, QUEEN_SIDE));
1488
1489   if (pos.st->epSquare != SQ_NONE)
1490       st->epSquare = ~pos.st->epSquare;
1491
1492   st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
1493
1494   st->key = compute_key();
1495   st->pawnKey = compute_pawn_key();
1496   st->materialKey = compute_material_key();
1497   st->psqScore = compute_psq_score();
1498   st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
1499   st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
1500
1501   assert(pos_is_ok());
1502 }
1503
1504
1505 /// Position::pos_is_ok() performs some consitency checks for the position object.
1506 /// This is meant to be helpful when debugging.
1507
1508 bool Position::pos_is_ok(int* failedStep) const {
1509
1510   int dummy, *step = failedStep ? failedStep : &dummy;
1511
1512   // What features of the position should be verified?
1513   const bool all = false;
1514
1515   const bool debugBitboards       = all || false;
1516   const bool debugKingCount       = all || false;
1517   const bool debugKingCapture     = all || false;
1518   const bool debugCheckerCount    = all || false;
1519   const bool debugKey             = all || false;
1520   const bool debugMaterialKey     = all || false;
1521   const bool debugPawnKey         = all || false;
1522   const bool debugIncrementalEval = all || false;
1523   const bool debugNonPawnMaterial = all || false;
1524   const bool debugPieceCounts     = all || false;
1525   const bool debugPieceList       = all || false;
1526   const bool debugCastleSquares   = all || false;
1527
1528   *step = 1;
1529
1530   if (sideToMove != WHITE && sideToMove != BLACK)
1531       return false;
1532
1533   if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1534       return false;
1535
1536   if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1537       return false;
1538
1539   if ((*step)++, debugKingCount)
1540   {
1541       int kingCount[COLOR_NB] = {};
1542
1543       for (Square s = SQ_A1; s <= SQ_H8; s++)
1544           if (type_of(piece_on(s)) == KING)
1545               kingCount[color_of(piece_on(s))]++;
1546
1547       if (kingCount[0] != 1 || kingCount[1] != 1)
1548           return false;
1549   }
1550
1551   if ((*step)++, debugKingCapture)
1552       if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1553           return false;
1554
1555   if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1556       return false;
1557
1558   if ((*step)++, debugBitboards)
1559   {
1560       // The intersection of the white and black pieces must be empty
1561       if (pieces(WHITE) & pieces(BLACK))
1562           return false;
1563
1564       // The union of the white and black pieces must be equal to all
1565       // occupied squares
1566       if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1567           return false;
1568
1569       // Separate piece type bitboards must have empty intersections
1570       for (PieceType p1 = PAWN; p1 <= KING; p1++)
1571           for (PieceType p2 = PAWN; p2 <= KING; p2++)
1572               if (p1 != p2 && (pieces(p1) & pieces(p2)))
1573                   return false;
1574   }
1575
1576   if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1577       return false;
1578
1579   if ((*step)++, debugKey && st->key != compute_key())
1580       return false;
1581
1582   if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1583       return false;
1584
1585   if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1586       return false;
1587
1588   if ((*step)++, debugIncrementalEval && st->psqScore != compute_psq_score())
1589       return false;
1590
1591   if ((*step)++, debugNonPawnMaterial)
1592   {
1593       if (   st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1594           || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1595           return false;
1596   }
1597
1598   if ((*step)++, debugPieceCounts)
1599       for (Color c = WHITE; c <= BLACK; c++)
1600           for (PieceType pt = PAWN; pt <= KING; pt++)
1601               if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1602                   return false;
1603
1604   if ((*step)++, debugPieceList)
1605       for (Color c = WHITE; c <= BLACK; c++)
1606           for (PieceType pt = PAWN; pt <= KING; pt++)
1607               for (int i = 0; i < pieceCount[c][pt]; i++)
1608               {
1609                   if (piece_on(piece_list(c, pt)[i]) != make_piece(c, pt))
1610                       return false;
1611
1612                   if (index[piece_list(c, pt)[i]] != i)
1613                       return false;
1614               }
1615
1616   if ((*step)++, debugCastleSquares)
1617       for (Color c = WHITE; c <= BLACK; c++)
1618           for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1619           {
1620               CastleRight cr = make_castle_right(c, s);
1621
1622               if (!can_castle(cr))
1623                   continue;
1624
1625               if ((castleRightsMask[king_square(c)] & cr) != cr)
1626                   return false;
1627
1628               if (   piece_on(castleRookSquare[c][s]) != make_piece(c, ROOK)
1629                   || castleRightsMask[castleRookSquare[c][s]] != cr)
1630                   return false;
1631           }
1632
1633   *step = 0;
1634   return true;
1635 }