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