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