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