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