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