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