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