7709fdd22c201d3e55dc228d15d3c4c2b7839eee
[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[16][64]; // [piece][square]
44 Value PieceValue[2][18] = {     // [Mg / Eg][piece / pieceType]
45 { VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg },
46 { VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } };
47
48 namespace Zobrist {
49
50 Key psq[2][8][64]; // [color][pieceType][square / piece count]
51 Key enpassant[8];  // [file]
52 Key castle[16];    // [castleRight]
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 /// CheckInfo c'tor
106
107 CheckInfo::CheckInfo(const Position& pos) {
108
109   Color them = ~pos.side_to_move();
110   ksq = pos.king_square(them);
111
112   pinned = pos.pinned_pieces();
113   dcCandidates = pos.discovered_check_candidates();
114
115   checkSq[PAWN]   = pos.attacks_from<PAWN>(ksq, them);
116   checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
117   checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
118   checkSq[ROOK]   = pos.attacks_from<ROOK>(ksq);
119   checkSq[QUEEN]  = checkSq[BISHOP] | checkSq[ROOK];
120   checkSq[KING]   = 0;
121 }
122
123
124 /// Position::operator=() creates a copy of 'pos'. We want the new born Position
125 /// object do not depend on any external data so we detach state pointer from
126 /// the source one.
127
128 Position& Position::operator=(const Position& pos) {
129
130   memcpy(this, &pos, sizeof(Position));
131   startState = *st;
132   st = &startState;
133   nodes = 0;
134
135   assert(pos_is_ok());
136
137   return *this;
138 }
139
140
141 /// Position::from_fen() initializes the position object with the given FEN
142 /// string. This function is not very robust - make sure that input FENs are
143 /// correct (this is assumed to be the responsibility of the GUI).
144
145 void Position::from_fen(const string& fenStr, bool isChess960, Thread* th) {
146 /*
147    A FEN string defines a particular position using only the ASCII character set.
148
149    A FEN string contains six fields separated by a space. The fields are:
150
151    1) Piece placement (from white's perspective). Each rank is described, starting
152       with rank 8 and ending with rank 1; within each rank, the contents of each
153       square are described from file A through file H. Following the Standard
154       Algebraic Notation (SAN), each piece is identified by a single letter taken
155       from the standard English names. White pieces are designated using upper-case
156       letters ("PNBRQK") while Black take lowercase ("pnbrqk"). Blank squares are
157       noted using digits 1 through 8 (the number of blank squares), and "/"
158       separates ranks.
159
160    2) Active color. "w" means white moves next, "b" means black.
161
162    3) Castling availability. If neither side can castle, this is "-". Otherwise,
163       this has one or more letters: "K" (White can castle kingside), "Q" (White
164       can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
165       can castle queenside).
166
167    4) En passant target square (in algebraic notation). If there's no en passant
168       target square, this is "-". If a pawn has just made a 2-square move, this
169       is the position "behind" the pawn. This is recorded regardless of whether
170       there is a pawn in position to make an en passant capture.
171
172    5) Halfmove clock. This is the number of halfmoves since the last pawn advance
173       or capture. This is used to determine if a draw can be claimed under the
174       fifty-move rule.
175
176    6) Fullmove number. The number of the full move. It starts at 1, and is
177       incremented after Black's move.
178 */
179
180   char col, row, token;
181   size_t p;
182   Square sq = SQ_A8;
183   std::istringstream fen(fenStr);
184
185   clear();
186   fen >> std::noskipws;
187
188   // 1. Piece placement
189   while ((fen >> token) && !isspace(token))
190   {
191       if (isdigit(token))
192           sq += Square(token - '0'); // Advance the given number of files
193
194       else if (token == '/')
195           sq -= Square(16);
196
197       else if ((p = PieceToChar.find(token)) != string::npos)
198       {
199           put_piece(Piece(p), sq);
200           sq++;
201       }
202   }
203
204   // 2. Active color
205   fen >> token;
206   sideToMove = (token == 'w' ? WHITE : BLACK);
207   fen >> token;
208
209   // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
210   // Shredder-FEN that uses the letters of the columns on which the rooks began
211   // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
212   // if an inner rook is associated with the castling right, the castling tag is
213   // replaced by the file letter of the involved rook, as for the Shredder-FEN.
214   while ((fen >> token) && !isspace(token))
215   {
216       Square rsq;
217       Color c = islower(token) ? BLACK : WHITE;
218
219       token = char(toupper(token));
220
221       if (token == 'K')
222           for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; rsq--) {}
223
224       else if (token == 'Q')
225           for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; rsq++) {}
226
227       else if (token >= 'A' && token <= 'H')
228           rsq = File(token - 'A') | relative_rank(c, RANK_1);
229
230       else
231           continue;
232
233       set_castle_right(c, rsq);
234   }
235
236   // 4. En passant square. Ignore if no pawn capture is possible
237   if (   ((fen >> col) && (col >= 'a' && col <= 'h'))
238       && ((fen >> row) && (row == '3' || row == '6')))
239   {
240       st->epSquare = File(col - 'a') | Rank(row - '1');
241
242       if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
243           st->epSquare = SQ_NONE;
244   }
245
246   // 5-6. Halfmove clock and fullmove number
247   fen >> std::skipws >> st->rule50 >> startPosPly;
248
249   // Convert from fullmove starting from 1 to ply starting from 0,
250   // handle also common incorrect FEN with fullmove = 0.
251   startPosPly = std::max(2 * (startPosPly - 1), 0) + int(sideToMove == BLACK);
252
253   st->key = compute_key();
254   st->pawnKey = compute_pawn_key();
255   st->materialKey = compute_material_key();
256   st->psqScore = compute_psq_score();
257   st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
258   st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
259   st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
260   chess960 = isChess960;
261   thisThread = th;
262
263   assert(pos_is_ok());
264 }
265
266
267 /// Position::set_castle_right() is an helper function used to set castling
268 /// rights given the corresponding color and the rook starting square.
269
270 void Position::set_castle_right(Color c, Square rfrom) {
271
272   Square kfrom = king_square(c);
273   CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
274   CastleRight cr = make_castle_right(c, cs);
275
276   st->castleRights |= cr;
277   castleRightsMask[kfrom] |= cr;
278   castleRightsMask[rfrom] |= cr;
279   castleRookSquare[c][cs] = rfrom;
280
281   Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
282   Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
283
284   for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); s++)
285       if (s != kfrom && s != rfrom)
286           castlePath[c][cs] |= s;
287
288   for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); s++)
289       if (s != kfrom && s != rfrom)
290           castlePath[c][cs] |= s;
291 }
292
293
294 /// Position::to_fen() returns a FEN representation of the position. In case
295 /// of Chess960 the Shredder-FEN notation is used. Mainly a debugging function.
296
297 const string Position::to_fen() const {
298
299   std::ostringstream fen;
300   Square sq;
301   int emptyCnt;
302
303   for (Rank rank = RANK_8; rank >= RANK_1; rank--)
304   {
305       emptyCnt = 0;
306
307       for (File file = FILE_A; file <= FILE_H; file++)
308       {
309           sq = file | rank;
310
311           if (is_empty(sq))
312               emptyCnt++;
313           else
314           {
315               if (emptyCnt > 0)
316               {
317                   fen << emptyCnt;
318                   emptyCnt = 0;
319               }
320               fen << PieceToChar[piece_on(sq)];
321           }
322       }
323
324       if (emptyCnt > 0)
325           fen << emptyCnt;
326
327       if (rank > RANK_1)
328           fen << '/';
329   }
330
331   fen << (sideToMove == WHITE ? " w " : " b ");
332
333   if (can_castle(WHITE_OO))
334       fen << (chess960 ? char(toupper(file_to_char(file_of(castle_rook_square(WHITE, KING_SIDE))))) : 'K');
335
336   if (can_castle(WHITE_OOO))
337       fen << (chess960 ? char(toupper(file_to_char(file_of(castle_rook_square(WHITE, QUEEN_SIDE))))) : 'Q');
338
339   if (can_castle(BLACK_OO))
340       fen << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, KING_SIDE))) : 'k');
341
342   if (can_castle(BLACK_OOO))
343       fen << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, QUEEN_SIDE))) : 'q');
344
345   if (st->castleRights == CASTLES_NONE)
346       fen << '-';
347
348   fen << (ep_square() == SQ_NONE ? " - " : " " + square_to_string(ep_square()) + " ")
349       << st->rule50 << " " << 1 + (startPosPly - int(sideToMove == BLACK)) / 2;
350
351   return fen.str();
352 }
353
354
355 /// Position::print() prints an ASCII representation of the position to
356 /// the standard output. If a move is given then also the san is printed.
357
358 void Position::print(Move move) const {
359
360   const string dottedLine =            "\n+---+---+---+---+---+---+---+---+";
361   const string twoRows =  dottedLine + "\n|   | . |   | . |   | . |   | . |"
362                         + dottedLine + "\n| . |   | . |   | . |   | . |   |";
363
364   string brd = twoRows + twoRows + twoRows + twoRows + dottedLine;
365
366   sync_cout;
367
368   if (move)
369   {
370       Position p(*this);
371       cout << "\nMove is: " << (sideToMove == BLACK ? ".." : "") << move_to_san(p, move);
372   }
373
374   for (Square sq = SQ_A1; sq <= SQ_H8; sq++)
375       if (piece_on(sq) != NO_PIECE)
376           brd[513 - 68*rank_of(sq) + 4*file_of(sq)] = PieceToChar[piece_on(sq)];
377
378   cout << brd << "\nFen is: " << to_fen() << "\nKey is: " << st->key << sync_endl;
379 }
380
381
382 /// Position:hidden_checkers<>() returns a bitboard of all pinned (against the
383 /// king) pieces for the given color. Or, when template parameter FindPinned is
384 /// false, the function return the pieces of the given color candidate for a
385 /// discovery check against the enemy king.
386 template<bool FindPinned>
387 Bitboard Position::hidden_checkers() const {
388
389   // Pinned pieces protect our king, dicovery checks attack the enemy king
390   Bitboard b, result = 0;
391   Bitboard pinners = pieces(FindPinned ? ~sideToMove : sideToMove);
392   Square ksq = king_square(FindPinned ? sideToMove : ~sideToMove);
393
394   // Pinners are sliders, that give check when candidate pinned is removed
395   pinners &=  (pieces(ROOK, QUEEN) & PseudoAttacks[ROOK][ksq])
396             | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq]);
397
398   while (pinners)
399   {
400       b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
401
402       if (b && !more_than_one(b) && (b & pieces(sideToMove)))
403           result |= b;
404   }
405   return result;
406 }
407
408 // Explicit template instantiations
409 template Bitboard Position::hidden_checkers<true>() const;
410 template Bitboard Position::hidden_checkers<false>() const;
411
412
413 /// Position::attackers_to() computes a bitboard of all pieces which attack a
414 /// given square. Slider attacks use occ bitboard as occupancy.
415
416 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
417
418   return  (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
419         | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
420         | (attacks_from<KNIGHT>(s)      & pieces(KNIGHT))
421         | (attacks_bb<ROOK>(s, occ)     & pieces(ROOK, QUEEN))
422         | (attacks_bb<BISHOP>(s, occ)   & pieces(BISHOP, QUEEN))
423         | (attacks_from<KING>(s)        & pieces(KING));
424 }
425
426
427 /// Position::attacks_from() computes a bitboard of all attacks of a given piece
428 /// put in a given square. Slider attacks use occ bitboard as occupancy.
429
430 Bitboard Position::attacks_from(Piece p, Square s, Bitboard occ) {
431
432   assert(is_ok(s));
433
434   switch (type_of(p))
435   {
436   case BISHOP: return attacks_bb<BISHOP>(s, occ);
437   case ROOK  : return attacks_bb<ROOK>(s, occ);
438   case QUEEN : return attacks_bb<BISHOP>(s, occ) | attacks_bb<ROOK>(s, occ);
439   default    : return StepAttacksBB[p][s];
440   }
441 }
442
443
444 /// Position::move_attacks_square() tests whether a move from the current
445 /// position attacks a given square.
446
447 bool Position::move_attacks_square(Move m, Square s) const {
448
449   assert(is_ok(m));
450   assert(is_ok(s));
451
452   Bitboard occ, xray;
453   Square from = from_sq(m);
454   Square to = to_sq(m);
455   Piece piece = piece_moved(m);
456
457   assert(!is_empty(from));
458
459   // Update occupancy as if the piece is moving
460   occ = pieces() ^ from ^ to;
461
462   // The piece moved in 'to' attacks the square 's' ?
463   if (attacks_from(piece, to, occ) & s)
464       return true;
465
466   // Scan for possible X-ray attackers behind the moved piece
467   xray =  (attacks_bb<  ROOK>(s, occ) & pieces(color_of(piece), QUEEN, ROOK))
468         | (attacks_bb<BISHOP>(s, occ) & pieces(color_of(piece), QUEEN, BISHOP));
469
470   // Verify attackers are triggered by our move and not already existing
471   return xray && (xray ^ (xray & attacks_from<QUEEN>(s)));
472 }
473
474
475 /// Position::pl_move_is_legal() tests whether a pseudo-legal move is legal
476
477 bool Position::pl_move_is_legal(Move m, Bitboard pinned) const {
478
479   assert(is_ok(m));
480   assert(pinned == pinned_pieces());
481
482   Color us = sideToMove;
483   Square from = from_sq(m);
484
485   assert(color_of(piece_moved(m)) == us);
486   assert(piece_on(king_square(us)) == make_piece(us, KING));
487
488   // En passant captures are a tricky special case. Because they are rather
489   // uncommon, we do it simply by testing whether the king is attacked after
490   // the move is made.
491   if (type_of(m) == ENPASSANT)
492   {
493       Color them = ~us;
494       Square to = to_sq(m);
495       Square capsq = to + pawn_push(them);
496       Square ksq = king_square(us);
497       Bitboard b = (pieces() ^ from ^ capsq) | to;
498
499       assert(to == ep_square());
500       assert(piece_moved(m) == make_piece(us, PAWN));
501       assert(piece_on(capsq) == make_piece(them, PAWN));
502       assert(piece_on(to) == NO_PIECE);
503
504       return   !(attacks_bb<  ROOK>(ksq, b) & pieces(them, QUEEN, ROOK))
505             && !(attacks_bb<BISHOP>(ksq, b) & pieces(them, QUEEN, BISHOP));
506   }
507
508   // If the moving piece is a king, check whether the destination
509   // square is attacked by the opponent. Castling moves are checked
510   // for legality during move generation.
511   if (type_of(piece_on(from)) == KING)
512       return type_of(m) == CASTLE || !(attackers_to(to_sq(m)) & pieces(~us));
513
514   // A non-king move is legal if and only if it is not pinned or it
515   // is moving along the ray towards or away from the king.
516   return   !pinned
517         || !(pinned & from)
518         ||  squares_aligned(from, to_sq(m), king_square(us));
519 }
520
521
522 /// Position::move_is_legal() takes a random move and tests whether the move
523 /// is legal. This version is not very fast and should be used only in non
524 /// time-critical paths.
525
526 bool Position::move_is_legal(const Move m) const {
527
528   for (MoveList<LEGAL> ml(*this); !ml.end(); ++ml)
529       if (ml.move() == m)
530           return true;
531
532   return false;
533 }
534
535
536 /// Position::is_pseudo_legal() takes a random move and tests whether the move
537 /// is pseudo legal. It is used to validate moves from TT that can be corrupted
538 /// due to SMP concurrent access or hash position key aliasing.
539
540 bool Position::is_pseudo_legal(const Move m) const {
541
542   Color us = sideToMove;
543   Color them = ~sideToMove;
544   Square from = from_sq(m);
545   Square to = to_sq(m);
546   Piece pc = piece_moved(m);
547
548   // Use a slower but simpler function for uncommon cases
549   if (type_of(m) != NORMAL)
550       return move_is_legal(m);
551
552   // Is not a promotion, so promotion piece must be empty
553   if (promotion_type(m) - 2 != NO_PIECE_TYPE)
554       return false;
555
556   // If the from square is not occupied by a piece belonging to the side to
557   // move, the move is obviously not legal.
558   if (pc == NO_PIECE || color_of(pc) != us)
559       return false;
560
561   // The destination square cannot be occupied by a friendly piece
562   if (color_of(piece_on(to)) == us)
563       return false;
564
565   // Handle the special case of a pawn move
566   if (type_of(pc) == PAWN)
567   {
568       // Move direction must be compatible with pawn color
569       int direction = to - from;
570       if ((us == WHITE) != (direction > 0))
571           return false;
572
573       // We have already handled promotion moves, so destination
574       // cannot be on the 8/1th rank.
575       if (rank_of(to) == RANK_8 || rank_of(to) == RANK_1)
576           return false;
577
578       // Proceed according to the square delta between the origin and
579       // destination squares.
580       switch (direction)
581       {
582       case DELTA_NW:
583       case DELTA_NE:
584       case DELTA_SW:
585       case DELTA_SE:
586       // Capture. The destination square must be occupied by an enemy
587       // piece (en passant captures was handled earlier).
588       if (color_of(piece_on(to)) != them)
589           return false;
590
591       // From and to files must be one file apart, avoids a7h5
592       if (abs(file_of(from) - file_of(to)) != 1)
593           return false;
594       break;
595
596       case DELTA_N:
597       case DELTA_S:
598       // Pawn push. The destination square must be empty.
599       if (!is_empty(to))
600           return false;
601       break;
602
603       case DELTA_NN:
604       // Double white pawn push. The destination square must be on the fourth
605       // rank, and both the destination square and the square between the
606       // source and destination squares must be empty.
607       if (    rank_of(to) != RANK_4
608           || !is_empty(to)
609           || !is_empty(from + DELTA_N))
610           return false;
611       break;
612
613       case DELTA_SS:
614       // Double black pawn push. The destination square must be on the fifth
615       // rank, and both the destination square and the square between the
616       // source and destination squares must be empty.
617       if (    rank_of(to) != RANK_5
618           || !is_empty(to)
619           || !is_empty(from + DELTA_S))
620           return false;
621       break;
622
623       default:
624           return false;
625       }
626   }
627   else if (!(attacks_from(pc, from) & to))
628       return false;
629
630   // Evasions generator already takes care to avoid some kind of illegal moves
631   // and pl_move_is_legal() relies on this. So we have to take care that the
632   // same kind of moves are filtered out here.
633   if (in_check())
634   {
635       if (type_of(pc) != KING)
636       {
637           Bitboard b = checkers();
638           Square checksq = pop_lsb(&b);
639
640           if (b) // double check ? In this case a king move is required
641               return false;
642
643           // Our move must be a blocking evasion or a capture of the checking piece
644           if (!((between_bb(checksq, king_square(us)) | checkers()) & to))
645               return false;
646       }
647       // In case of king moves under check we have to remove king so to catch
648       // as invalid moves like b1a1 when opposite queen is on c1.
649       else if (attackers_to(to, pieces() ^ from) & pieces(~us))
650           return false;
651   }
652
653   return true;
654 }
655
656
657 /// Position::move_gives_check() tests whether a pseudo-legal move gives a check
658
659 bool Position::move_gives_check(Move m, const CheckInfo& ci) const {
660
661   assert(is_ok(m));
662   assert(ci.dcCandidates == discovered_check_candidates());
663   assert(color_of(piece_moved(m)) == sideToMove);
664
665   Square from = from_sq(m);
666   Square to = to_sq(m);
667   PieceType pt = type_of(piece_on(from));
668
669   // Direct check ?
670   if (ci.checkSq[pt] & to)
671       return true;
672
673   // Discovery check ?
674   if (ci.dcCandidates && (ci.dcCandidates & from))
675   {
676       // For pawn and king moves we need to verify also direction
677       if (   (pt != PAWN && pt != KING)
678           || !squares_aligned(from, to, king_square(~sideToMove)))
679           return true;
680   }
681
682   // Can we skip the ugly special cases ?
683   if (type_of(m) == NORMAL)
684       return false;
685
686   Color us = sideToMove;
687   Square ksq = king_square(~us);
688
689   // Promotion with check ?
690   if (type_of(m) == 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   if (type_of(m) == 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
706   // Castling with check ?
707   if (type_of(m) == CASTLE)
708   {
709       Square kfrom = from;
710       Square rfrom = to; // 'King captures the rook' notation
711       Square kto = relative_square(us, rfrom > kfrom ? SQ_G1 : SQ_C1);
712       Square rto = relative_square(us, rfrom > kfrom ? SQ_F1 : SQ_D1);
713       Bitboard b = (pieces() ^ kfrom ^ rfrom) | rto | kto;
714
715       return attacks_bb<ROOK>(rto, b) & ksq;
716   }
717
718   return false;
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 recalculated from scratch anyway, then switch our state pointer
742   // to point to the new, ready to be updated, state.
743   memcpy(&newSt, st, sizeof(ReducedStateInfo));
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(color_of(piece_on(to)) != us);
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->pawnTable.entries[st->pawnKey]);
919   prefetch((char*)thisThread->materialTable.entries[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 occ, attackers, stmAttackers, b;
1222   int swapList[32], slIndex = 1;
1223   PieceType capturedType, pt;
1224   Color stm;
1225
1226   assert(is_ok(m));
1227
1228   // As castle moves are implemented as capturing the rook, they have
1229   // SEE == RookValueMidgame most of the times (unless the rook is under
1230   // attack).
1231   if (type_of(m) == CASTLE)
1232       return 0;
1233
1234   from = from_sq(m);
1235   to = to_sq(m);
1236   capturedType = type_of(piece_on(to));
1237   occ = pieces();
1238
1239   // Handle en passant moves
1240   if (type_of(m) == ENPASSANT)
1241   {
1242       Square capQq = to - pawn_push(sideToMove);
1243
1244       assert(!capturedType);
1245       assert(type_of(piece_on(capQq)) == PAWN);
1246
1247       // Remove the captured pawn
1248       occ ^= capQq;
1249       capturedType = PAWN;
1250   }
1251
1252   // Find all attackers to the destination square, with the moving piece
1253   // removed, but possibly an X-ray attacker added behind it.
1254   occ ^= from;
1255   attackers = attackers_to(to, occ);
1256
1257   // If the opponent has no attackers we are finished
1258   stm = ~color_of(piece_on(from));
1259   stmAttackers = attackers & pieces(stm);
1260   if (!stmAttackers)
1261       return PieceValue[Mg][capturedType];
1262
1263   // The destination square is defended, which makes things rather more
1264   // difficult to compute. We proceed by building up a "swap list" containing
1265   // the material gain or loss at each stop in a sequence of captures to the
1266   // destination square, where the sides alternately capture, and always
1267   // capture with the least valuable piece. After each capture, we look for
1268   // new X-ray attacks from behind the capturing piece.
1269   swapList[0] = PieceValue[Mg][capturedType];
1270   capturedType = type_of(piece_on(from));
1271
1272   do {
1273       // Locate the least valuable attacker for the side to move. The loop
1274       // below looks like it is potentially infinite, but it isn't. We know
1275       // that the side to move still has at least one attacker left.
1276       for (pt = PAWN; (b = stmAttackers & pieces(pt)) == 0; pt++)
1277           assert(pt < KING);
1278
1279       // Remove the attacker we just found from the 'occupied' bitboard,
1280       // and scan for new X-ray attacks behind the attacker.
1281       occ ^= (b & (~b + 1));
1282       attackers |=  (attacks_bb<ROOK>(to, occ)   & pieces(ROOK, QUEEN))
1283                   | (attacks_bb<BISHOP>(to, occ) & pieces(BISHOP, QUEEN));
1284
1285       attackers &= occ; // Cut out pieces we've already done
1286
1287       // Add the new entry to the swap list
1288       assert(slIndex < 32);
1289       swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[Mg][capturedType];
1290       slIndex++;
1291
1292       // Remember the value of the capturing piece, and change the side to
1293       // move before beginning the next iteration.
1294       capturedType = pt;
1295       stm = ~stm;
1296       stmAttackers = attackers & pieces(stm);
1297
1298       // Stop before processing a king capture
1299       if (capturedType == KING && stmAttackers)
1300       {
1301           assert(slIndex < 32);
1302           swapList[slIndex++] = QueenValueMg * 16;
1303           break;
1304       }
1305   } while (stmAttackers);
1306
1307   // Having built the swap list, we negamax through it to find the best
1308   // achievable score from the point of view of the side to move.
1309   while (--slIndex)
1310       swapList[slIndex-1] = std::min(-swapList[slIndex], swapList[slIndex-1]);
1311
1312   return swapList[0];
1313 }
1314
1315
1316 /// Position::clear() erases the position object to a pristine state, with an
1317 /// empty board, white to move, and no castling rights.
1318
1319 void Position::clear() {
1320
1321   memset(this, 0, sizeof(Position));
1322   startState.epSquare = SQ_NONE;
1323   st = &startState;
1324
1325   for (int i = 0; i < 8; i++)
1326       for (int j = 0; j < 16; j++)
1327           pieceList[0][i][j] = pieceList[1][i][j] = SQ_NONE;
1328
1329   for (Square sq = SQ_A1; sq <= SQ_H8; sq++)
1330       board[sq] = NO_PIECE;
1331 }
1332
1333
1334 /// Position::put_piece() puts a piece on the given square of the board,
1335 /// updating the board array, pieces list, bitboards, and piece counts.
1336
1337 void Position::put_piece(Piece p, Square s) {
1338
1339   Color c = color_of(p);
1340   PieceType pt = type_of(p);
1341
1342   board[s] = p;
1343   index[s] = pieceCount[c][pt]++;
1344   pieceList[c][pt][index[s]] = s;
1345
1346   byTypeBB[ALL_PIECES] |= s;
1347   byTypeBB[pt] |= s;
1348   byColorBB[c] |= s;
1349 }
1350
1351
1352 /// Position::compute_key() computes the hash key of the position. The hash
1353 /// key is usually updated incrementally as moves are made and unmade, the
1354 /// compute_key() function is only used when a new position is set up, and
1355 /// to verify the correctness of the hash key when running in debug mode.
1356
1357 Key Position::compute_key() const {
1358
1359   Key k = Zobrist::castle[st->castleRights];
1360
1361   for (Bitboard b = pieces(); b; )
1362   {
1363       Square s = pop_lsb(&b);
1364       k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1365   }
1366
1367   if (ep_square() != SQ_NONE)
1368       k ^= Zobrist::enpassant[file_of(ep_square())];
1369
1370   if (sideToMove == BLACK)
1371       k ^= Zobrist::side;
1372
1373   return k;
1374 }
1375
1376
1377 /// Position::compute_pawn_key() computes the hash key of the position. The
1378 /// hash key is usually updated incrementally as moves are made and unmade,
1379 /// the compute_pawn_key() function is only used when a new position is set
1380 /// up, and to verify the correctness of the pawn hash key when running in
1381 /// debug mode.
1382
1383 Key Position::compute_pawn_key() const {
1384
1385   Key k = 0;
1386
1387   for (Bitboard b = pieces(PAWN); b; )
1388   {
1389       Square s = pop_lsb(&b);
1390       k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1391   }
1392
1393   return k;
1394 }
1395
1396
1397 /// Position::compute_material_key() computes the hash key of the position.
1398 /// The hash key is usually updated incrementally as moves are made and unmade,
1399 /// the compute_material_key() function is only used when a new position is set
1400 /// up, and to verify the correctness of the material hash key when running in
1401 /// debug mode.
1402
1403 Key Position::compute_material_key() const {
1404
1405   Key k = 0;
1406
1407   for (Color c = WHITE; c <= BLACK; c++)
1408       for (PieceType pt = PAWN; pt <= QUEEN; pt++)
1409           for (int cnt = 0; cnt < piece_count(c, pt); cnt++)
1410               k ^= Zobrist::psq[c][pt][cnt];
1411
1412   return k;
1413 }
1414
1415
1416 /// Position::compute_psq_score() computes the incremental scores for the middle
1417 /// game and the endgame. These functions are used to initialize the incremental
1418 /// scores when a new position is set up, and to verify that the scores are correctly
1419 /// updated by do_move and undo_move when the program is running in debug mode.
1420 Score Position::compute_psq_score() const {
1421
1422   Score score = SCORE_ZERO;
1423
1424   for (Bitboard b = pieces(); b; )
1425   {
1426       Square s = pop_lsb(&b);
1427       score += pieceSquareTable[piece_on(s)][s];
1428   }
1429
1430   return score;
1431 }
1432
1433
1434 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1435 /// game material value for the given side. Material values are updated
1436 /// incrementally during the search, this function is only used while
1437 /// initializing a new Position object.
1438
1439 Value Position::compute_non_pawn_material(Color c) const {
1440
1441   Value value = VALUE_ZERO;
1442
1443   for (PieceType pt = KNIGHT; pt <= QUEEN; pt++)
1444       value += piece_count(c, pt) * PieceValue[Mg][pt];
1445
1446   return value;
1447 }
1448
1449
1450 /// Position::is_draw() tests whether the position is drawn by material,
1451 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1452 /// must be done by the search.
1453 template<bool SkipRepetition>
1454 bool Position::is_draw() const {
1455
1456   // Draw by material?
1457   if (   !pieces(PAWN)
1458       && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1459       return true;
1460
1461   // Draw by the 50 moves rule?
1462   if (st->rule50 > 99 && (!in_check() || MoveList<LEGAL>(*this).size()))
1463       return true;
1464
1465   // Draw by repetition?
1466   if (!SkipRepetition)
1467   {
1468       int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1469
1470       if (i <= e)
1471       {
1472           StateInfo* stp = st->previous->previous;
1473
1474           do {
1475               stp = stp->previous->previous;
1476
1477               if (stp->key == st->key)
1478                   return true;
1479
1480               i +=2;
1481
1482           } while (i <= e);
1483       }
1484   }
1485
1486   return false;
1487 }
1488
1489 // Explicit template instantiations
1490 template bool Position::is_draw<false>() const;
1491 template bool Position::is_draw<true>() const;
1492
1493
1494 /// Position::flip() flips position with the white and black sides reversed. This
1495 /// is only useful for debugging especially for finding evaluation symmetry bugs.
1496
1497 void Position::flip() {
1498
1499   const Position pos(*this);
1500
1501   clear();
1502
1503   sideToMove = ~pos.side_to_move();
1504   thisThread = pos.this_thread();
1505   nodes = pos.nodes_searched();
1506   chess960 = pos.is_chess960();
1507   startPosPly = pos.startpos_ply_counter();
1508
1509   for (Square s = SQ_A1; s <= SQ_H8; s++)
1510       if (!pos.is_empty(s))
1511           put_piece(Piece(pos.piece_on(s) ^ 8), ~s);
1512
1513   if (pos.can_castle(WHITE_OO))
1514       set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, KING_SIDE));
1515   if (pos.can_castle(WHITE_OOO))
1516       set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, QUEEN_SIDE));
1517   if (pos.can_castle(BLACK_OO))
1518       set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, KING_SIDE));
1519   if (pos.can_castle(BLACK_OOO))
1520       set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, QUEEN_SIDE));
1521
1522   if (pos.st->epSquare != SQ_NONE)
1523       st->epSquare = ~pos.st->epSquare;
1524
1525   st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
1526
1527   st->key = compute_key();
1528   st->pawnKey = compute_pawn_key();
1529   st->materialKey = compute_material_key();
1530   st->psqScore = compute_psq_score();
1531   st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
1532   st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
1533
1534   assert(pos_is_ok());
1535 }
1536
1537
1538 /// Position::pos_is_ok() performs some consitency checks for the position object.
1539 /// This is meant to be helpful when debugging.
1540
1541 bool Position::pos_is_ok(int* failedStep) const {
1542
1543   int dummy, *step = failedStep ? failedStep : &dummy;
1544
1545   // What features of the position should be verified?
1546   const bool all = false;
1547
1548   const bool debugBitboards       = all || false;
1549   const bool debugKingCount       = all || false;
1550   const bool debugKingCapture     = all || false;
1551   const bool debugCheckerCount    = all || false;
1552   const bool debugKey             = all || false;
1553   const bool debugMaterialKey     = all || false;
1554   const bool debugPawnKey         = all || false;
1555   const bool debugIncrementalEval = all || false;
1556   const bool debugNonPawnMaterial = all || false;
1557   const bool debugPieceCounts     = all || false;
1558   const bool debugPieceList       = all || false;
1559   const bool debugCastleSquares   = all || false;
1560
1561   *step = 1;
1562
1563   if (sideToMove != WHITE && sideToMove != BLACK)
1564       return false;
1565
1566   if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1567       return false;
1568
1569   if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1570       return false;
1571
1572   if ((*step)++, debugKingCount)
1573   {
1574       int kingCount[2] = {};
1575
1576       for (Square s = SQ_A1; s <= SQ_H8; s++)
1577           if (type_of(piece_on(s)) == KING)
1578               kingCount[color_of(piece_on(s))]++;
1579
1580       if (kingCount[0] != 1 || kingCount[1] != 1)
1581           return false;
1582   }
1583
1584   if ((*step)++, debugKingCapture)
1585       if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1586           return false;
1587
1588   if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1589       return false;
1590
1591   if ((*step)++, debugBitboards)
1592   {
1593       // The intersection of the white and black pieces must be empty
1594       if (pieces(WHITE) & pieces(BLACK))
1595           return false;
1596
1597       // The union of the white and black pieces must be equal to all
1598       // occupied squares
1599       if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1600           return false;
1601
1602       // Separate piece type bitboards must have empty intersections
1603       for (PieceType p1 = PAWN; p1 <= KING; p1++)
1604           for (PieceType p2 = PAWN; p2 <= KING; p2++)
1605               if (p1 != p2 && (pieces(p1) & pieces(p2)))
1606                   return false;
1607   }
1608
1609   if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1610       return false;
1611
1612   if ((*step)++, debugKey && st->key != compute_key())
1613       return false;
1614
1615   if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1616       return false;
1617
1618   if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1619       return false;
1620
1621   if ((*step)++, debugIncrementalEval && st->psqScore != compute_psq_score())
1622       return false;
1623
1624   if ((*step)++, debugNonPawnMaterial)
1625   {
1626       if (   st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1627           || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1628           return false;
1629   }
1630
1631   if ((*step)++, debugPieceCounts)
1632       for (Color c = WHITE; c <= BLACK; c++)
1633           for (PieceType pt = PAWN; pt <= KING; pt++)
1634               if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1635                   return false;
1636
1637   if ((*step)++, debugPieceList)
1638       for (Color c = WHITE; c <= BLACK; c++)
1639           for (PieceType pt = PAWN; pt <= KING; pt++)
1640               for (int i = 0; i < pieceCount[c][pt]; i++)
1641               {
1642                   if (piece_on(piece_list(c, pt)[i]) != make_piece(c, pt))
1643                       return false;
1644
1645                   if (index[piece_list(c, pt)[i]] != i)
1646                       return false;
1647               }
1648
1649   if ((*step)++, debugCastleSquares)
1650       for (Color c = WHITE; c <= BLACK; c++)
1651           for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1652           {
1653               CastleRight cr = make_castle_right(c, s);
1654
1655               if (!can_castle(cr))
1656                   continue;
1657
1658               if ((castleRightsMask[king_square(c)] & cr) != cr)
1659                   return false;
1660
1661               if (   piece_on(castleRookSquare[c][s]) != make_piece(c, ROOK)
1662                   || castleRightsMask[castleRookSquare[c][s]] != cr)
1663                   return false;
1664           }
1665
1666   *step = 0;
1667   return true;
1668 }