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