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