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