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