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