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