310e46e36190704121571efff452399bf53911a9
[stockfish] / src / position.cpp
1 /*
2   Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3   Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
4   Copyright (C) 2008-2012 Marco Costalba, Joona Kiiski, Tord Romstad
5
6   Stockfish is free software: you can redistribute it and/or modify
7   it under the terms of the GNU General Public License as published by
8   the Free Software Foundation, either version 3 of the License, or
9   (at your option) any later version.
10
11   Stockfish is distributed in the hope that it will be useful,
12   but WITHOUT ANY WARRANTY; without even the implied warranty of
13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   GNU General Public License for more details.
15
16   You should have received a copy of the GNU General Public License
17   along with this program.  If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include <cassert>
21 #include <cstring>
22 #include <iostream>
23 #include <sstream>
24 #include <algorithm>
25
26 #include "bitcount.h"
27 #include "movegen.h"
28 #include "notation.h"
29 #include "position.h"
30 #include "psqtab.h"
31 #include "rkiss.h"
32 #include "thread.h"
33 #include "tt.h"
34
35 using std::string;
36 using std::cout;
37 using std::endl;
38
39 static const string PieceToChar(" PNBRQK  pnbrqk");
40
41 CACHE_LINE_ALIGNMENT
42
43 Score pieceSquareTable[PIECE_NB][SQUARE_NB];
44 Value PieceValue[PHASE_NB][PIECE_NB] = {
45 { VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg },
46 { VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } };
47
48 namespace Zobrist {
49
50 Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
51 Key enpassant[FILE_NB];
52 Key castle[CASTLE_RIGHT_NB];
53 Key side;
54 Key exclusion;
55
56 /// init() initializes at startup the various arrays used to compute hash keys
57 /// and the piece square tables. The latter is a two-step operation: First, the
58 /// white halves of the tables are copied from PSQT[] tables. Second, the black
59 /// halves of the tables are initialized by flipping and changing the sign of
60 /// the white scores.
61
62 void init() {
63
64   RKISS rk;
65
66   for (Color c = WHITE; c <= BLACK; c++)
67       for (PieceType pt = PAWN; pt <= KING; pt++)
68           for (Square s = SQ_A1; s <= SQ_H8; s++)
69               psq[c][pt][s] = rk.rand<Key>();
70
71   for (File f = FILE_A; f <= FILE_H; f++)
72       enpassant[f] = rk.rand<Key>();
73
74   for (int cr = CASTLES_NONE; cr <= ALL_CASTLES; cr++)
75   {
76       Bitboard b = cr;
77       while (b)
78       {
79           Key k = castle[1ULL << pop_lsb(&b)];
80           castle[cr] ^= k ? k : rk.rand<Key>();
81       }
82   }
83
84   side = rk.rand<Key>();
85   exclusion  = rk.rand<Key>();
86
87   for (PieceType pt = PAWN; pt <= KING; pt++)
88   {
89       PieceValue[MG][make_piece(BLACK, pt)] = PieceValue[MG][pt];
90       PieceValue[EG][make_piece(BLACK, pt)] = PieceValue[EG][pt];
91
92       Score v = make_score(PieceValue[MG][pt], PieceValue[EG][pt]);
93
94       for (Square s = SQ_A1; s <= SQ_H8; s++)
95       {
96           pieceSquareTable[make_piece(WHITE, pt)][ s] =  (v + PSQT[pt][s]);
97           pieceSquareTable[make_piece(BLACK, pt)][~s] = -(v + PSQT[pt][s]);
98       }
99   }
100 }
101
102 } // namespace Zobrist
103
104
105 namespace {
106
107 /// next_attacker() is an helper function used by see() to locate the least
108 /// valuable attacker for the side to move, remove the attacker we just found
109 /// from the 'occupied' bitboard and scan for new X-ray attacks behind it.
110
111 template<int Pt> FORCE_INLINE
112 PieceType next_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
113                         Bitboard& occupied, Bitboard& attackers) {
114
115   if (stmAttackers & bb[Pt])
116   {
117       Bitboard b = stmAttackers & bb[Pt];
118       occupied ^= b & ~(b - 1);
119
120       if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
121           attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
122
123       if (Pt == ROOK || Pt == QUEEN)
124           attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
125
126       return (PieceType)Pt;
127   }
128   return next_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
129 }
130
131 template<> FORCE_INLINE
132 PieceType next_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
133   return KING; // No need to update bitboards, it is the last cycle
134 }
135
136 } // namespace
137
138
139 /// CheckInfo c'tor
140
141 CheckInfo::CheckInfo(const Position& pos) {
142
143   Color them = ~pos.side_to_move();
144   ksq = pos.king_square(them);
145
146   pinned = pos.pinned_pieces();
147   dcCandidates = pos.discovered_check_candidates();
148
149   checkSq[PAWN]   = pos.attacks_from<PAWN>(ksq, them);
150   checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
151   checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
152   checkSq[ROOK]   = pos.attacks_from<ROOK>(ksq);
153   checkSq[QUEEN]  = checkSq[BISHOP] | checkSq[ROOK];
154   checkSq[KING]   = 0;
155 }
156
157
158 /// Position::operator=() creates a copy of 'pos'. We want the new born Position
159 /// object do not depend on any external data so we detach state pointer from
160 /// the source one.
161
162 Position& Position::operator=(const Position& pos) {
163
164   memcpy(this, &pos, sizeof(Position));
165   startState = *st;
166   st = &startState;
167   nodes = 0;
168
169   assert(pos_is_ok());
170
171   return *this;
172 }
173
174
175 /// Position::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 >> startPosPly;
282
283   // Convert from fullmove starting from 1 to ply starting from 0,
284   // handle also common incorrect FEN with fullmove = 0.
285   startPosPly = std::max(2 * (startPosPly - 1), 0) + int(sideToMove == BLACK);
286
287   st->key = compute_key();
288   st->pawnKey = compute_pawn_key();
289   st->materialKey = compute_material_key();
290   st->psqScore = compute_psq_score();
291   st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
292   st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
293   st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
294   chess960 = isChess960;
295   thisThread = th;
296
297   assert(pos_is_ok());
298 }
299
300
301 /// Position::set_castle_right() is an helper function used to set castling
302 /// rights given the corresponding color and the rook starting square.
303
304 void Position::set_castle_right(Color c, Square rfrom) {
305
306   Square kfrom = king_square(c);
307   CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
308   CastleRight cr = make_castle_right(c, cs);
309
310   st->castleRights |= cr;
311   castleRightsMask[kfrom] |= cr;
312   castleRightsMask[rfrom] |= cr;
313   castleRookSquare[c][cs] = rfrom;
314
315   Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
316   Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
317
318   for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); s++)
319       if (s != kfrom && s != rfrom)
320           castlePath[c][cs] |= s;
321
322   for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); s++)
323       if (s != kfrom && s != rfrom)
324           castlePath[c][cs] |= s;
325 }
326
327
328 /// Position::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 + (startPosPly - 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 the 50 moves rule draw counter. Resetting it to zero in the
739   // case of a capture or a pawn move is taken care of later.
740   st->rule50++;
741   st->pliesFromNull++;
742
743   Color us = sideToMove;
744   Color them = ~us;
745   Square from = from_sq(m);
746   Square to = to_sq(m);
747   Piece piece = piece_on(from);
748   PieceType pt = type_of(piece);
749   PieceType capture = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
750
751   assert(color_of(piece) == us);
752   assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLE);
753   assert(capture != KING);
754
755   if (type_of(m) == CASTLE)
756   {
757       assert(piece == make_piece(us, KING));
758
759       bool kingSide = to > from;
760       Square rfrom = to; // Castle is encoded as "king captures friendly rook"
761       Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
762       to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
763       capture = NO_PIECE_TYPE;
764
765       do_castle(from, to, rfrom, rto);
766
767       st->psqScore += psq_delta(make_piece(us, ROOK), rfrom, rto);
768       k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
769   }
770
771   if (capture)
772   {
773       Square capsq = to;
774
775       // If the captured piece is a pawn, update pawn hash key, otherwise
776       // update non-pawn material.
777       if (capture == PAWN)
778       {
779           if (type_of(m) == ENPASSANT)
780           {
781               capsq += pawn_push(them);
782
783               assert(pt == PAWN);
784               assert(to == st->epSquare);
785               assert(relative_rank(us, to) == RANK_6);
786               assert(piece_on(to) == NO_PIECE);
787               assert(piece_on(capsq) == make_piece(them, PAWN));
788
789               board[capsq] = NO_PIECE;
790           }
791
792           st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
793       }
794       else
795           st->npMaterial[them] -= PieceValue[MG][capture];
796
797       // Remove the captured piece
798       byTypeBB[ALL_PIECES] ^= capsq;
799       byTypeBB[capture] ^= capsq;
800       byColorBB[them] ^= capsq;
801
802       // Update piece list, move the last piece at index[capsq] position and
803       // shrink the list.
804       //
805       // WARNING: This is a not revresible operation. When we will reinsert the
806       // captured piece in undo_move() we will put it at the end of the list and
807       // not in its original place, it means index[] and pieceList[] are not
808       // guaranteed to be invariant to a do_move() + undo_move() sequence.
809       Square lastSquare = pieceList[them][capture][--pieceCount[them][capture]];
810       index[lastSquare] = index[capsq];
811       pieceList[them][capture][index[lastSquare]] = lastSquare;
812       pieceList[them][capture][pieceCount[them][capture]] = SQ_NONE;
813
814       // Update material hash key and prefetch access to materialTable
815       k ^= Zobrist::psq[them][capture][capsq];
816       st->materialKey ^= Zobrist::psq[them][capture][pieceCount[them][capture]];
817       prefetch((char*)thisThread->materialTable[st->materialKey]);
818
819       // Update incremental scores
820       st->psqScore -= pieceSquareTable[make_piece(them, capture)][capsq];
821
822       // Reset rule 50 counter
823       st->rule50 = 0;
824   }
825
826   // Update hash key
827   k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
828
829   // Reset en passant square
830   if (st->epSquare != SQ_NONE)
831   {
832       k ^= Zobrist::enpassant[file_of(st->epSquare)];
833       st->epSquare = SQ_NONE;
834   }
835
836   // Update castle rights if needed
837   if (st->castleRights && (castleRightsMask[from] | castleRightsMask[to]))
838   {
839       int cr = castleRightsMask[from] | castleRightsMask[to];
840       k ^= Zobrist::castle[st->castleRights & cr];
841       st->castleRights &= ~cr;
842   }
843
844   // Prefetch TT access as soon as we know the new hash key
845   prefetch((char*)TT.first_entry(k));
846
847   // Move the piece. The tricky Chess960 castle is handled earlier
848   if (type_of(m) != CASTLE)
849   {
850       Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
851       byTypeBB[ALL_PIECES] ^= from_to_bb;
852       byTypeBB[pt] ^= from_to_bb;
853       byColorBB[us] ^= from_to_bb;
854
855       board[from] = NO_PIECE;
856       board[to] = piece;
857
858       // Update piece lists, index[from] is not updated and becomes stale. This
859       // works as long as index[] is accessed just by known occupied squares.
860       index[to] = index[from];
861       pieceList[us][pt][index[to]] = to;
862   }
863
864   // If the moving piece is a pawn do some special extra work
865   if (pt == PAWN)
866   {
867       // Set en-passant square, only if moved pawn can be captured
868       if (   (int(to) ^ int(from)) == 16
869           && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
870       {
871           st->epSquare = Square((from + to) / 2);
872           k ^= Zobrist::enpassant[file_of(st->epSquare)];
873       }
874
875       if (type_of(m) == PROMOTION)
876       {
877           PieceType promotion = promotion_type(m);
878
879           assert(relative_rank(us, to) == RANK_8);
880           assert(promotion >= KNIGHT && promotion <= QUEEN);
881
882           // Replace the pawn with the promoted piece
883           byTypeBB[PAWN] ^= to;
884           byTypeBB[promotion] |= to;
885           board[to] = make_piece(us, promotion);
886
887           // Update piece lists, move the last pawn at index[to] position
888           // and shrink the list. Add a new promotion piece to the list.
889           Square lastSquare = pieceList[us][PAWN][--pieceCount[us][PAWN]];
890           index[lastSquare] = index[to];
891           pieceList[us][PAWN][index[lastSquare]] = lastSquare;
892           pieceList[us][PAWN][pieceCount[us][PAWN]] = SQ_NONE;
893           index[to] = pieceCount[us][promotion];
894           pieceList[us][promotion][index[to]] = to;
895
896           // Update hash keys
897           k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
898           st->pawnKey ^= Zobrist::psq[us][PAWN][to];
899           st->materialKey ^=  Zobrist::psq[us][promotion][pieceCount[us][promotion]++]
900                             ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
901
902           // Update incremental score
903           st->psqScore +=  pieceSquareTable[make_piece(us, promotion)][to]
904                          - pieceSquareTable[make_piece(us, PAWN)][to];
905
906           // Update material
907           st->npMaterial[us] += PieceValue[MG][promotion];
908       }
909
910       // Update pawn hash key and prefetch access to pawnsTable
911       st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
912       prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
913
914       // Reset rule 50 draw counter
915       st->rule50 = 0;
916   }
917
918   // Update incremental scores
919   st->psqScore += psq_delta(piece, from, to);
920
921   // Set capture piece
922   st->capturedType = capture;
923
924   // Update the key with the final value
925   st->key = k;
926
927   // Update checkers bitboard, piece must be already moved
928   st->checkersBB = 0;
929
930   if (moveIsCheck)
931   {
932       if (type_of(m) != NORMAL)
933           st->checkersBB = attackers_to(king_square(them)) & pieces(us);
934       else
935       {
936           // Direct checks
937           if (ci.checkSq[pt] & to)
938               st->checkersBB |= to;
939
940           // Discovery checks
941           if (ci.dcCandidates && (ci.dcCandidates & from))
942           {
943               if (pt != ROOK)
944                   st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
945
946               if (pt != BISHOP)
947                   st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
948           }
949       }
950   }
951
952   sideToMove = ~sideToMove;
953
954   assert(pos_is_ok());
955 }
956
957
958 /// Position::undo_move() unmakes a move. When it returns, the position should
959 /// be restored to exactly the same state as before the move was made.
960
961 void Position::undo_move(Move m) {
962
963   assert(is_ok(m));
964
965   sideToMove = ~sideToMove;
966
967   Color us = sideToMove;
968   Color them = ~us;
969   Square from = from_sq(m);
970   Square to = to_sq(m);
971   PieceType pt = type_of(piece_on(to));
972   PieceType capture = st->capturedType;
973
974   assert(is_empty(from) || type_of(m) == CASTLE);
975   assert(capture != KING);
976
977   if (type_of(m) == PROMOTION)
978   {
979       PieceType promotion = promotion_type(m);
980
981       assert(promotion == pt);
982       assert(relative_rank(us, to) == RANK_8);
983       assert(promotion >= KNIGHT && promotion <= QUEEN);
984
985       // Replace the promoted piece with the pawn
986       byTypeBB[promotion] ^= to;
987       byTypeBB[PAWN] |= to;
988       board[to] = make_piece(us, PAWN);
989
990       // Update piece lists, move the last promoted piece at index[to] position
991       // and shrink the list. Add a new pawn to the list.
992       Square lastSquare = pieceList[us][promotion][--pieceCount[us][promotion]];
993       index[lastSquare] = index[to];
994       pieceList[us][promotion][index[lastSquare]] = lastSquare;
995       pieceList[us][promotion][pieceCount[us][promotion]] = SQ_NONE;
996       index[to] = pieceCount[us][PAWN]++;
997       pieceList[us][PAWN][index[to]] = to;
998
999       pt = PAWN;
1000   }
1001
1002   if (type_of(m) == CASTLE)
1003   {
1004       bool kingSide = to > from;
1005       Square rfrom = to; // Castle is encoded as "king captures friendly rook"
1006       Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
1007       to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
1008       capture = NO_PIECE_TYPE;
1009       pt = KING;
1010       do_castle(to, from, rto, rfrom);
1011   }
1012   else
1013   {
1014       // Put the piece back at the source square
1015       Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
1016       byTypeBB[ALL_PIECES] ^= from_to_bb;
1017       byTypeBB[pt] ^= from_to_bb;
1018       byColorBB[us] ^= from_to_bb;
1019
1020       board[to] = NO_PIECE;
1021       board[from] = make_piece(us, pt);
1022
1023       // Update piece lists, index[to] is not updated and becomes stale. This
1024       // works as long as index[] is accessed just by known occupied squares.
1025       index[from] = index[to];
1026       pieceList[us][pt][index[from]] = from;
1027   }
1028
1029   if (capture)
1030   {
1031       Square capsq = to;
1032
1033       if (type_of(m) == ENPASSANT)
1034       {
1035           capsq -= pawn_push(us);
1036
1037           assert(pt == PAWN);
1038           assert(to == st->previous->epSquare);
1039           assert(relative_rank(us, to) == RANK_6);
1040           assert(piece_on(capsq) == NO_PIECE);
1041       }
1042
1043       // Restore the captured piece
1044       byTypeBB[ALL_PIECES] |= capsq;
1045       byTypeBB[capture] |= capsq;
1046       byColorBB[them] |= capsq;
1047
1048       board[capsq] = make_piece(them, capture);
1049
1050       // Update piece list, add a new captured piece in capsq square
1051       index[capsq] = pieceCount[them][capture]++;
1052       pieceList[them][capture][index[capsq]] = capsq;
1053   }
1054
1055   // Finally point our state pointer back to the previous state
1056   st = st->previous;
1057
1058   assert(pos_is_ok());
1059 }
1060
1061
1062 /// Position::do_castle() is a helper used to do/undo a castling move. This
1063 /// is a bit tricky, especially in Chess960.
1064
1065 void Position::do_castle(Square kfrom, Square kto, Square rfrom, Square rto) {
1066
1067   Color us = sideToMove;
1068   Bitboard k_from_to_bb = SquareBB[kfrom] ^ SquareBB[kto];
1069   Bitboard r_from_to_bb = SquareBB[rfrom] ^ SquareBB[rto];
1070   byTypeBB[KING] ^= k_from_to_bb;
1071   byTypeBB[ROOK] ^= r_from_to_bb;
1072   byTypeBB[ALL_PIECES] ^= k_from_to_bb ^ r_from_to_bb;
1073   byColorBB[us] ^= k_from_to_bb ^ r_from_to_bb;
1074
1075   // Could be from == to, so first set NO_PIECE then KING and ROOK
1076   board[kfrom] = board[rfrom] = NO_PIECE;
1077   board[kto] = make_piece(us, KING);
1078   board[rto] = make_piece(us, ROOK);
1079
1080   // Could be kfrom == rto, so use a 'tmp' variable
1081   int tmp = index[kfrom];
1082   index[rto] = index[rfrom];
1083   index[kto] = tmp;
1084   pieceList[us][KING][index[kto]] = kto;
1085   pieceList[us][ROOK][index[rto]] = rto;
1086 }
1087
1088
1089 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
1090 /// the side to move without executing any move on the board.
1091
1092 void Position::do_null_move(StateInfo& newSt) {
1093
1094   assert(!checkers());
1095
1096   memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
1097
1098   newSt.previous = st;
1099   st = &newSt;
1100
1101   if (st->epSquare != SQ_NONE)
1102   {
1103       st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
1104       st->epSquare = SQ_NONE;
1105   }
1106
1107   st->key ^= Zobrist::side;
1108   prefetch((char*)TT.first_entry(st->key));
1109
1110   st->rule50++;
1111   st->pliesFromNull = 0;
1112
1113   sideToMove = ~sideToMove;
1114
1115   assert(pos_is_ok());
1116 }
1117
1118 void Position::undo_null_move() {
1119
1120   assert(!checkers());
1121
1122   st = st->previous;
1123   sideToMove = ~sideToMove;
1124 }
1125
1126
1127 /// Position::see() is a static exchange evaluator: It tries to estimate the
1128 /// material gain or loss resulting from a move. There are three versions of
1129 /// this function: One which takes a destination square as input, one takes a
1130 /// move, and one which takes a 'from' and a 'to' square. The function does
1131 /// not yet understand promotions captures.
1132
1133 int Position::see_sign(Move m) const {
1134
1135   assert(is_ok(m));
1136
1137   // Early return if SEE cannot be negative because captured piece value
1138   // is not less then capturing one. Note that king moves always return
1139   // here because king midgame value is set to 0.
1140   if (PieceValue[MG][piece_on(to_sq(m))] >= PieceValue[MG][piece_moved(m)])
1141       return 1;
1142
1143   return see(m);
1144 }
1145
1146 int Position::see(Move m) const {
1147
1148   Square from, to;
1149   Bitboard occupied, attackers, stmAttackers;
1150   int swapList[32], slIndex = 1;
1151   PieceType captured;
1152   Color stm;
1153
1154   assert(is_ok(m));
1155
1156   from = from_sq(m);
1157   to = to_sq(m);
1158   captured = type_of(piece_on(to));
1159   occupied = pieces() ^ from;
1160
1161   // Handle en passant moves
1162   if (type_of(m) == ENPASSANT)
1163   {
1164       Square capQq = to - pawn_push(sideToMove);
1165
1166       assert(!captured);
1167       assert(type_of(piece_on(capQq)) == PAWN);
1168
1169       // Remove the captured pawn
1170       occupied ^= capQq;
1171       captured = PAWN;
1172   }
1173   else if (type_of(m) == CASTLE)
1174       // Castle moves are implemented as king capturing the rook so cannot be
1175       // handled correctly. Simply return 0 that is always the correct value
1176       // unless the rook is ends up under attack.
1177       return 0;
1178
1179   // Find all attackers to the destination square, with the moving piece
1180   // removed, but possibly an X-ray attacker added behind it.
1181   attackers = attackers_to(to, occupied);
1182
1183   // If the opponent has no attackers we are finished
1184   stm = ~color_of(piece_on(from));
1185   stmAttackers = attackers & pieces(stm);
1186   if (!stmAttackers)
1187       return PieceValue[MG][captured];
1188
1189   // The destination square is defended, which makes things rather more
1190   // difficult to compute. We proceed by building up a "swap list" containing
1191   // the material gain or loss at each stop in a sequence of captures to the
1192   // destination square, where the sides alternately capture, and always
1193   // capture with the least valuable piece. After each capture, we look for
1194   // new X-ray attacks from behind the capturing piece.
1195   swapList[0] = PieceValue[MG][captured];
1196   captured = type_of(piece_on(from));
1197
1198   do {
1199       assert(slIndex < 32);
1200
1201       // Add the new entry to the swap list
1202       swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1203       slIndex++;
1204
1205       // Locate and remove from 'occupied' the next least valuable attacker
1206       captured = next_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1207
1208       attackers &= occupied; // Remove the just found attacker
1209       stm = ~stm;
1210       stmAttackers = attackers & pieces(stm);
1211
1212       if (captured == KING)
1213       {
1214           // Stop before processing a king capture
1215           if (stmAttackers)
1216               swapList[slIndex++] = QueenValueMg * 16;
1217
1218           break;
1219       }
1220
1221   } while (stmAttackers);
1222
1223   // Having built the swap list, we negamax through it to find the best
1224   // achievable score from the point of view of the side to move.
1225   while (--slIndex)
1226       swapList[slIndex-1] = std::min(-swapList[slIndex], swapList[slIndex-1]);
1227
1228   return swapList[0];
1229 }
1230
1231
1232 /// Position::clear() erases the position object to a pristine state, with an
1233 /// empty board, white to move, and no castling rights.
1234
1235 void Position::clear() {
1236
1237   memset(this, 0, sizeof(Position));
1238   startState.epSquare = SQ_NONE;
1239   st = &startState;
1240
1241   for (int i = 0; i < 8; i++)
1242       for (int j = 0; j < 16; j++)
1243           pieceList[0][i][j] = pieceList[1][i][j] = SQ_NONE;
1244 }
1245
1246
1247 /// Position::put_piece() puts a piece on the given square of the board,
1248 /// updating the board array, pieces list, bitboards, and piece counts.
1249
1250 void Position::put_piece(Piece p, Square s) {
1251
1252   Color c = color_of(p);
1253   PieceType pt = type_of(p);
1254
1255   board[s] = p;
1256   index[s] = pieceCount[c][pt]++;
1257   pieceList[c][pt][index[s]] = s;
1258
1259   byTypeBB[ALL_PIECES] |= s;
1260   byTypeBB[pt] |= s;
1261   byColorBB[c] |= s;
1262 }
1263
1264
1265 /// Position::compute_key() computes the hash key of the position. The hash
1266 /// key is usually updated incrementally as moves are made and unmade, the
1267 /// compute_key() function is only used when a new position is set up, and
1268 /// to verify the correctness of the hash key when running in debug mode.
1269
1270 Key Position::compute_key() const {
1271
1272   Key k = Zobrist::castle[st->castleRights];
1273
1274   for (Bitboard b = pieces(); b; )
1275   {
1276       Square s = pop_lsb(&b);
1277       k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1278   }
1279
1280   if (ep_square() != SQ_NONE)
1281       k ^= Zobrist::enpassant[file_of(ep_square())];
1282
1283   if (sideToMove == BLACK)
1284       k ^= Zobrist::side;
1285
1286   return k;
1287 }
1288
1289
1290 /// Position::compute_pawn_key() computes the hash key of the position. The
1291 /// hash key is usually updated incrementally as moves are made and unmade,
1292 /// the compute_pawn_key() function is only used when a new position is set
1293 /// up, and to verify the correctness of the pawn hash key when running in
1294 /// debug mode.
1295
1296 Key Position::compute_pawn_key() const {
1297
1298   Key k = 0;
1299
1300   for (Bitboard b = pieces(PAWN); b; )
1301   {
1302       Square s = pop_lsb(&b);
1303       k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1304   }
1305
1306   return k;
1307 }
1308
1309
1310 /// Position::compute_material_key() computes the hash key of the position.
1311 /// The hash key is usually updated incrementally as moves are made and unmade,
1312 /// the compute_material_key() function is only used when a new position is set
1313 /// up, and to verify the correctness of the material hash key when running in
1314 /// debug mode.
1315
1316 Key Position::compute_material_key() const {
1317
1318   Key k = 0;
1319
1320   for (Color c = WHITE; c <= BLACK; c++)
1321       for (PieceType pt = PAWN; pt <= QUEEN; pt++)
1322           for (int cnt = 0; cnt < piece_count(c, pt); cnt++)
1323               k ^= Zobrist::psq[c][pt][cnt];
1324
1325   return k;
1326 }
1327
1328
1329 /// Position::compute_psq_score() computes the incremental scores for the middle
1330 /// game and the endgame. These functions are used to initialize the incremental
1331 /// scores when a new position is set up, and to verify that the scores are correctly
1332 /// updated by do_move and undo_move when the program is running in debug mode.
1333 Score Position::compute_psq_score() const {
1334
1335   Score score = SCORE_ZERO;
1336
1337   for (Bitboard b = pieces(); b; )
1338   {
1339       Square s = pop_lsb(&b);
1340       score += pieceSquareTable[piece_on(s)][s];
1341   }
1342
1343   return score;
1344 }
1345
1346
1347 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1348 /// game material value for the given side. Material values are updated
1349 /// incrementally during the search, this function is only used while
1350 /// initializing a new Position object.
1351
1352 Value Position::compute_non_pawn_material(Color c) const {
1353
1354   Value value = VALUE_ZERO;
1355
1356   for (PieceType pt = KNIGHT; pt <= QUEEN; pt++)
1357       value += piece_count(c, pt) * PieceValue[MG][pt];
1358
1359   return value;
1360 }
1361
1362
1363 /// Position::is_draw() tests whether the position is drawn by material,
1364 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1365 /// must be done by the search.
1366 template<bool SkipRepetition>
1367 bool Position::is_draw() const {
1368
1369   // Draw by material?
1370   if (   !pieces(PAWN)
1371       && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1372       return true;
1373
1374   // Draw by the 50 moves rule?
1375   if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1376       return true;
1377
1378   // Draw by repetition?
1379   if (!SkipRepetition)
1380   {
1381       int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1382
1383       if (i <= e)
1384       {
1385           StateInfo* stp = st->previous->previous;
1386
1387           do {
1388               stp = stp->previous->previous;
1389
1390               if (stp->key == st->key)
1391                   return true;
1392
1393               i += 2;
1394
1395           } while (i <= e);
1396       }
1397   }
1398
1399   return false;
1400 }
1401
1402 // Explicit template instantiations
1403 template bool Position::is_draw<false>() const;
1404 template bool Position::is_draw<true>() const;
1405
1406
1407 /// Position::flip() flips position with the white and black sides reversed. This
1408 /// is only useful for debugging especially for finding evaluation symmetry bugs.
1409
1410 void Position::flip() {
1411
1412   const Position pos(*this);
1413
1414   clear();
1415
1416   sideToMove = ~pos.side_to_move();
1417   thisThread = pos.this_thread();
1418   nodes = pos.nodes_searched();
1419   chess960 = pos.is_chess960();
1420   startPosPly = pos.startpos_ply_counter();
1421
1422   for (Square s = SQ_A1; s <= SQ_H8; s++)
1423       if (!pos.is_empty(s))
1424           put_piece(Piece(pos.piece_on(s) ^ 8), ~s);
1425
1426   if (pos.can_castle(WHITE_OO))
1427       set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, KING_SIDE));
1428   if (pos.can_castle(WHITE_OOO))
1429       set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, QUEEN_SIDE));
1430   if (pos.can_castle(BLACK_OO))
1431       set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, KING_SIDE));
1432   if (pos.can_castle(BLACK_OOO))
1433       set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, QUEEN_SIDE));
1434
1435   if (pos.st->epSquare != SQ_NONE)
1436       st->epSquare = ~pos.st->epSquare;
1437
1438   st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
1439
1440   st->key = compute_key();
1441   st->pawnKey = compute_pawn_key();
1442   st->materialKey = compute_material_key();
1443   st->psqScore = compute_psq_score();
1444   st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
1445   st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
1446
1447   assert(pos_is_ok());
1448 }
1449
1450
1451 /// Position::pos_is_ok() performs some consitency checks for the position object.
1452 /// This is meant to be helpful when debugging.
1453
1454 bool Position::pos_is_ok(int* failedStep) const {
1455
1456   int dummy, *step = failedStep ? failedStep : &dummy;
1457
1458   // What features of the position should be verified?
1459   const bool all = false;
1460
1461   const bool debugBitboards       = all || false;
1462   const bool debugKingCount       = all || false;
1463   const bool debugKingCapture     = all || false;
1464   const bool debugCheckerCount    = all || false;
1465   const bool debugKey             = all || false;
1466   const bool debugMaterialKey     = all || false;
1467   const bool debugPawnKey         = all || false;
1468   const bool debugIncrementalEval = all || false;
1469   const bool debugNonPawnMaterial = all || false;
1470   const bool debugPieceCounts     = all || false;
1471   const bool debugPieceList       = all || false;
1472   const bool debugCastleSquares   = all || false;
1473
1474   *step = 1;
1475
1476   if (sideToMove != WHITE && sideToMove != BLACK)
1477       return false;
1478
1479   if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1480       return false;
1481
1482   if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1483       return false;
1484
1485   if ((*step)++, debugKingCount)
1486   {
1487       int kingCount[COLOR_NB] = {};
1488
1489       for (Square s = SQ_A1; s <= SQ_H8; s++)
1490           if (type_of(piece_on(s)) == KING)
1491               kingCount[color_of(piece_on(s))]++;
1492
1493       if (kingCount[0] != 1 || kingCount[1] != 1)
1494           return false;
1495   }
1496
1497   if ((*step)++, debugKingCapture)
1498       if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1499           return false;
1500
1501   if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1502       return false;
1503
1504   if ((*step)++, debugBitboards)
1505   {
1506       // The intersection of the white and black pieces must be empty
1507       if (pieces(WHITE) & pieces(BLACK))
1508           return false;
1509
1510       // The union of the white and black pieces must be equal to all
1511       // occupied squares
1512       if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1513           return false;
1514
1515       // Separate piece type bitboards must have empty intersections
1516       for (PieceType p1 = PAWN; p1 <= KING; p1++)
1517           for (PieceType p2 = PAWN; p2 <= KING; p2++)
1518               if (p1 != p2 && (pieces(p1) & pieces(p2)))
1519                   return false;
1520   }
1521
1522   if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1523       return false;
1524
1525   if ((*step)++, debugKey && st->key != compute_key())
1526       return false;
1527
1528   if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1529       return false;
1530
1531   if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1532       return false;
1533
1534   if ((*step)++, debugIncrementalEval && st->psqScore != compute_psq_score())
1535       return false;
1536
1537   if ((*step)++, debugNonPawnMaterial)
1538   {
1539       if (   st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1540           || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1541           return false;
1542   }
1543
1544   if ((*step)++, debugPieceCounts)
1545       for (Color c = WHITE; c <= BLACK; c++)
1546           for (PieceType pt = PAWN; pt <= KING; pt++)
1547               if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1548                   return false;
1549
1550   if ((*step)++, debugPieceList)
1551       for (Color c = WHITE; c <= BLACK; c++)
1552           for (PieceType pt = PAWN; pt <= KING; pt++)
1553               for (int i = 0; i < pieceCount[c][pt]; i++)
1554               {
1555                   if (piece_on(piece_list(c, pt)[i]) != make_piece(c, pt))
1556                       return false;
1557
1558                   if (index[piece_list(c, pt)[i]] != i)
1559                       return false;
1560               }
1561
1562   if ((*step)++, debugCastleSquares)
1563       for (Color c = WHITE; c <= BLACK; c++)
1564           for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1565           {
1566               CastleRight cr = make_castle_right(c, s);
1567
1568               if (!can_castle(cr))
1569                   continue;
1570
1571               if ((castleRightsMask[king_square(c)] & cr) != cr)
1572                   return false;
1573
1574               if (   piece_on(castleRookSquare[c][s]) != make_piece(c, ROOK)
1575                   || castleRightsMask[castleRookSquare[c][s]] != cr)
1576                   return false;
1577           }
1578
1579   *step = 0;
1580   return true;
1581 }