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