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