Fully qualify memset and memcpy
[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   std::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 / discovery check
420 /// pieces, according to the call parameters. Pinned pieces protect our king,
421 /// discovery check pieces attack the enemy king.
422
423 Bitboard Position::hidden_checkers(Square ksq, Color c) const {
424
425   Bitboard b, pinners, result = 0;
426
427   // Pinners are sliders that give check when pinned piece is removed
428   pinners = (  (pieces(  ROOK, QUEEN) & PseudoAttacks[ROOK  ][ksq])
429              | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(c);
430
431   while (pinners)
432   {
433       b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
434
435       if (!more_than_one(b))
436           result |= b & pieces(sideToMove);
437   }
438   return result;
439 }
440
441
442 /// Position::attackers_to() computes a bitboard of all pieces which attack a
443 /// given square. Slider attacks use occ bitboard as occupancy.
444
445 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
446
447   return  (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
448         | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
449         | (attacks_from<KNIGHT>(s)      & pieces(KNIGHT))
450         | (attacks_bb<ROOK>(s, occ)     & pieces(ROOK, QUEEN))
451         | (attacks_bb<BISHOP>(s, occ)   & pieces(BISHOP, QUEEN))
452         | (attacks_from<KING>(s)        & pieces(KING));
453 }
454
455
456 /// Position::attacks_from() computes a bitboard of all attacks of a given piece
457 /// put in a given square. Slider attacks use occ bitboard as occupancy.
458
459 Bitboard Position::attacks_from(Piece p, Square s, Bitboard occ) {
460
461   assert(is_ok(s));
462
463   switch (type_of(p))
464   {
465   case BISHOP: return attacks_bb<BISHOP>(s, occ);
466   case ROOK  : return attacks_bb<ROOK>(s, occ);
467   case QUEEN : return attacks_bb<BISHOP>(s, occ) | attacks_bb<ROOK>(s, occ);
468   default    : return StepAttacksBB[p][s];
469   }
470 }
471
472
473 /// Position::pl_move_is_legal() tests whether a pseudo-legal move is legal
474
475 bool Position::pl_move_is_legal(Move m, Bitboard pinned) const {
476
477   assert(is_ok(m));
478   assert(pinned == pinned_pieces());
479
480   Color us = sideToMove;
481   Square from = from_sq(m);
482
483   assert(color_of(piece_moved(m)) == us);
484   assert(piece_on(king_square(us)) == make_piece(us, KING));
485
486   // En passant captures are a tricky special case. Because they are rather
487   // uncommon, we do it simply by testing whether the king is attacked after
488   // the move is made.
489   if (type_of(m) == ENPASSANT)
490   {
491       Color them = ~us;
492       Square to = to_sq(m);
493       Square capsq = to + pawn_push(them);
494       Square ksq = king_square(us);
495       Bitboard b = (pieces() ^ from ^ capsq) | to;
496
497       assert(to == ep_square());
498       assert(piece_moved(m) == make_piece(us, PAWN));
499       assert(piece_on(capsq) == make_piece(them, PAWN));
500       assert(piece_on(to) == NO_PIECE);
501
502       return   !(attacks_bb<  ROOK>(ksq, b) & pieces(them, QUEEN, ROOK))
503             && !(attacks_bb<BISHOP>(ksq, b) & pieces(them, QUEEN, BISHOP));
504   }
505
506   // If the moving piece is a king, check whether the destination
507   // square is attacked by the opponent. Castling moves are checked
508   // for legality during move generation.
509   if (type_of(piece_on(from)) == KING)
510       return type_of(m) == CASTLE || !(attackers_to(to_sq(m)) & pieces(~us));
511
512   // A non-king move is legal if and only if it is not pinned or it
513   // is moving along the ray towards or away from the king.
514   return   !pinned
515         || !(pinned & from)
516         ||  squares_aligned(from, to_sq(m), king_square(us));
517 }
518
519
520 /// Position::is_pseudo_legal() takes a random move and tests whether the move
521 /// is pseudo legal. It is used to validate moves from TT that can be corrupted
522 /// due to SMP concurrent access or hash position key aliasing.
523
524 bool Position::is_pseudo_legal(const Move m) const {
525
526   Color us = sideToMove;
527   Square from = from_sq(m);
528   Square to = to_sq(m);
529   Piece pc = piece_moved(m);
530
531   // Use a slower but simpler function for uncommon cases
532   if (type_of(m) != NORMAL)
533       return MoveList<LEGAL>(*this).contains(m);
534
535   // Is not a promotion, so promotion piece must be empty
536   if (promotion_type(m) - 2 != NO_PIECE_TYPE)
537       return false;
538
539   // If the from square is not occupied by a piece belonging to the side to
540   // move, the move is obviously not legal.
541   if (pc == NO_PIECE || color_of(pc) != us)
542       return false;
543
544   // The destination square cannot be occupied by a friendly piece
545   if (piece_on(to) != NO_PIECE && color_of(piece_on(to)) == us)
546       return false;
547
548   // Handle the special case of a pawn move
549   if (type_of(pc) == PAWN)
550   {
551       // Move direction must be compatible with pawn color
552       int direction = to - from;
553       if ((us == WHITE) != (direction > 0))
554           return false;
555
556       // We have already handled promotion moves, so destination
557       // cannot be on the 8/1th rank.
558       if (rank_of(to) == RANK_8 || rank_of(to) == RANK_1)
559           return false;
560
561       // Proceed according to the square delta between the origin and
562       // destination squares.
563       switch (direction)
564       {
565       case DELTA_NW:
566       case DELTA_NE:
567       case DELTA_SW:
568       case DELTA_SE:
569       // Capture. The destination square must be occupied by an enemy
570       // piece (en passant captures was handled earlier).
571       if (piece_on(to) == NO_PIECE || color_of(piece_on(to)) != ~us)
572           return false;
573
574       // From and to files must be one file apart, avoids a7h5
575       if (abs(file_of(from) - file_of(to)) != 1)
576           return false;
577       break;
578
579       case DELTA_N:
580       case DELTA_S:
581       // Pawn push. The destination square must be empty.
582       if (!is_empty(to))
583           return false;
584       break;
585
586       case DELTA_NN:
587       // Double white pawn push. The destination square must be on the fourth
588       // rank, and both the destination square and the square between the
589       // source and destination squares must be empty.
590       if (    rank_of(to) != RANK_4
591           || !is_empty(to)
592           || !is_empty(from + DELTA_N))
593           return false;
594       break;
595
596       case DELTA_SS:
597       // Double black pawn push. The destination square must be on the fifth
598       // rank, and both the destination square and the square between the
599       // source and destination squares must be empty.
600       if (    rank_of(to) != RANK_5
601           || !is_empty(to)
602           || !is_empty(from + DELTA_S))
603           return false;
604       break;
605
606       default:
607           return false;
608       }
609   }
610   else if (!(attacks_from(pc, from) & to))
611       return false;
612
613   // Evasions generator already takes care to avoid some kind of illegal moves
614   // and pl_move_is_legal() relies on this. So we have to take care that the
615   // same kind of moves are filtered out here.
616   if (checkers())
617   {
618       if (type_of(pc) != KING)
619       {
620           // Double check? In this case a king move is required
621           if (more_than_one(checkers()))
622               return false;
623
624           // Our move must be a blocking evasion or a capture of the checking piece
625           if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
626               return false;
627       }
628       // In case of king moves under check we have to remove king so to catch
629       // as invalid moves like b1a1 when opposite queen is on c1.
630       else if (attackers_to(to, pieces() ^ from) & pieces(~us))
631           return false;
632   }
633
634   return true;
635 }
636
637
638 /// Position::move_gives_check() tests whether a pseudo-legal move gives a check
639
640 bool Position::move_gives_check(Move m, const CheckInfo& ci) const {
641
642   assert(is_ok(m));
643   assert(ci.dcCandidates == discovered_check_candidates());
644   assert(color_of(piece_moved(m)) == sideToMove);
645
646   Square from = from_sq(m);
647   Square to = to_sq(m);
648   PieceType pt = type_of(piece_on(from));
649
650   // Direct check ?
651   if (ci.checkSq[pt] & to)
652       return true;
653
654   // Discovery check ?
655   if (ci.dcCandidates && (ci.dcCandidates & from))
656   {
657       // For pawn and king moves we need to verify also direction
658       if (   (pt != PAWN && pt != KING)
659           || !squares_aligned(from, to, king_square(~sideToMove)))
660           return true;
661   }
662
663   // Can we skip the ugly special cases ?
664   if (type_of(m) == NORMAL)
665       return false;
666
667   Color us = sideToMove;
668   Square ksq = king_square(~us);
669
670   switch (type_of(m))
671   {
672   case PROMOTION:
673       return attacks_from(Piece(promotion_type(m)), to, pieces() ^ from) & ksq;
674
675   // En passant capture with check ? We have already handled the case
676   // of direct checks and ordinary discovered check, the only case we
677   // need to handle is the unusual case of a discovered check through
678   // the captured pawn.
679   case ENPASSANT:
680   {
681       Square capsq = file_of(to) | rank_of(from);
682       Bitboard b = (pieces() ^ from ^ capsq) | to;
683
684       return  (attacks_bb<  ROOK>(ksq, b) & pieces(us, QUEEN, ROOK))
685             | (attacks_bb<BISHOP>(ksq, b) & pieces(us, QUEEN, BISHOP));
686   }
687   case CASTLE:
688   {
689       Square kfrom = from;
690       Square rfrom = to; // 'King captures the rook' notation
691       Square kto = relative_square(us, rfrom > kfrom ? SQ_G1 : SQ_C1);
692       Square rto = relative_square(us, rfrom > kfrom ? SQ_F1 : SQ_D1);
693       Bitboard b = (pieces() ^ kfrom ^ rfrom) | rto | kto;
694
695       return attacks_bb<ROOK>(rto, b) & ksq;
696   }
697   default:
698       assert(false);
699       return false;
700   }
701 }
702
703
704 /// Position::do_move() makes a move, and saves all information necessary
705 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
706 /// moves should be filtered out before this function is called.
707
708 void Position::do_move(Move m, StateInfo& newSt) {
709
710   CheckInfo ci(*this);
711   do_move(m, newSt, ci, move_gives_check(m, ci));
712 }
713
714 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
715
716   assert(is_ok(m));
717   assert(&newSt != st);
718
719   nodes++;
720   Key k = st->key;
721
722   // Copy some fields of old state to our new StateInfo object except the ones
723   // which are going to be recalculated from scratch anyway, then switch our state
724   // pointer to point to the new, ready to be updated, state.
725   std::memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
726
727   newSt.previous = st;
728   st = &newSt;
729
730   // Update side to move
731   k ^= Zobrist::side;
732
733   // Increment ply counters.In particular rule50 will be later reset it to zero
734   // in case of a capture or a pawn move.
735   gamePly++;
736   st->rule50++;
737   st->pliesFromNull++;
738
739   Color us = sideToMove;
740   Color them = ~us;
741   Square from = from_sq(m);
742   Square to = to_sq(m);
743   Piece pc = piece_on(from);
744   PieceType pt = type_of(pc);
745   PieceType capture = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
746
747   assert(color_of(pc) == us);
748   assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLE);
749   assert(capture != KING);
750
751   if (type_of(m) == CASTLE)
752   {
753       assert(pc == make_piece(us, KING));
754
755       bool kingSide = to > from;
756       Square rfrom = to; // Castle is encoded as "king captures friendly rook"
757       Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
758       to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
759       capture = NO_PIECE_TYPE;
760
761       do_castle(from, to, rfrom, rto);
762
763       st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
764       k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
765   }
766
767   if (capture)
768   {
769       Square capsq = to;
770
771       // If the captured piece is a pawn, update pawn hash key, otherwise
772       // update non-pawn material.
773       if (capture == PAWN)
774       {
775           if (type_of(m) == ENPASSANT)
776           {
777               capsq += pawn_push(them);
778
779               assert(pt == PAWN);
780               assert(to == st->epSquare);
781               assert(relative_rank(us, to) == RANK_6);
782               assert(piece_on(to) == NO_PIECE);
783               assert(piece_on(capsq) == make_piece(them, PAWN));
784
785               board[capsq] = NO_PIECE;
786           }
787
788           st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
789       }
790       else
791           st->npMaterial[them] -= PieceValue[MG][capture];
792
793       // Remove the captured piece
794       byTypeBB[ALL_PIECES] ^= capsq;
795       byTypeBB[capture] ^= capsq;
796       byColorBB[them] ^= capsq;
797
798       // Update piece list, move the last piece at index[capsq] position and
799       // shrink the list.
800       //
801       // WARNING: This is a not reversible operation. When we will reinsert the
802       // captured piece in undo_move() we will put it at the end of the list and
803       // not in its original place, it means index[] and pieceList[] are not
804       // guaranteed to be invariant to a do_move() + undo_move() sequence.
805       Square lastSquare = pieceList[them][capture][--pieceCount[them][capture]];
806       index[lastSquare] = index[capsq];
807       pieceList[them][capture][index[lastSquare]] = lastSquare;
808       pieceList[them][capture][pieceCount[them][capture]] = SQ_NONE;
809
810       // Update material hash key and prefetch access to materialTable
811       k ^= Zobrist::psq[them][capture][capsq];
812       st->materialKey ^= Zobrist::psq[them][capture][pieceCount[them][capture]];
813       prefetch((char*)thisThread->materialTable[st->materialKey]);
814
815       // Update incremental scores
816       st->psq -= psq[them][capture][capsq];
817
818       // Reset rule 50 counter
819       st->rule50 = 0;
820   }
821
822   // Update hash key
823   k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
824
825   // Reset en passant square
826   if (st->epSquare != SQ_NONE)
827   {
828       k ^= Zobrist::enpassant[file_of(st->epSquare)];
829       st->epSquare = SQ_NONE;
830   }
831
832   // Update castle rights if needed
833   if (st->castleRights && (castleRightsMask[from] | castleRightsMask[to]))
834   {
835       int cr = castleRightsMask[from] | castleRightsMask[to];
836       k ^= Zobrist::castle[st->castleRights & cr];
837       st->castleRights &= ~cr;
838   }
839
840   // Prefetch TT access as soon as we know the new hash key
841   prefetch((char*)TT.first_entry(k));
842
843   // Move the piece. The tricky Chess960 castle is handled earlier
844   if (type_of(m) != CASTLE)
845   {
846       Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
847       byTypeBB[ALL_PIECES] ^= from_to_bb;
848       byTypeBB[pt] ^= from_to_bb;
849       byColorBB[us] ^= from_to_bb;
850
851       board[from] = NO_PIECE;
852       board[to] = pc;
853
854       // Update piece lists, index[from] is not updated and becomes stale. This
855       // works as long as index[] is accessed just by known occupied squares.
856       index[to] = index[from];
857       pieceList[us][pt][index[to]] = to;
858   }
859
860   // If the moving piece is a pawn do some special extra work
861   if (pt == PAWN)
862   {
863       // Set en-passant square, only if moved pawn can be captured
864       if (   (int(to) ^ int(from)) == 16
865           && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
866       {
867           st->epSquare = Square((from + to) / 2);
868           k ^= Zobrist::enpassant[file_of(st->epSquare)];
869       }
870
871       if (type_of(m) == PROMOTION)
872       {
873           PieceType promotion = promotion_type(m);
874
875           assert(relative_rank(us, to) == RANK_8);
876           assert(promotion >= KNIGHT && promotion <= QUEEN);
877
878           // Replace the pawn with the promoted piece
879           byTypeBB[PAWN] ^= to;
880           byTypeBB[promotion] |= to;
881           board[to] = make_piece(us, promotion);
882
883           // Update piece lists, move the last pawn at index[to] position
884           // and shrink the list. Add a new promotion piece to the list.
885           Square lastSquare = pieceList[us][PAWN][--pieceCount[us][PAWN]];
886           index[lastSquare] = index[to];
887           pieceList[us][PAWN][index[lastSquare]] = lastSquare;
888           pieceList[us][PAWN][pieceCount[us][PAWN]] = SQ_NONE;
889           index[to] = pieceCount[us][promotion];
890           pieceList[us][promotion][index[to]] = to;
891
892           // Update hash keys
893           k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
894           st->pawnKey ^= Zobrist::psq[us][PAWN][to];
895           st->materialKey ^=  Zobrist::psq[us][promotion][pieceCount[us][promotion]++]
896                             ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
897
898           // Update incremental score
899           st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
900
901           // Update material
902           st->npMaterial[us] += PieceValue[MG][promotion];
903       }
904
905       // Update pawn hash key and prefetch access to pawnsTable
906       st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
907       prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
908
909       // Reset rule 50 draw counter
910       st->rule50 = 0;
911   }
912
913   // Update incremental scores
914   st->psq += psq[us][pt][to] - psq[us][pt][from];
915
916   // Set capture piece
917   st->capturedType = capture;
918
919   // Update the key with the final value
920   st->key = k;
921
922   // Update checkers bitboard, piece must be already moved
923   st->checkersBB = 0;
924
925   if (moveIsCheck)
926   {
927       if (type_of(m) != NORMAL)
928           st->checkersBB = attackers_to(king_square(them)) & pieces(us);
929       else
930       {
931           // Direct checks
932           if (ci.checkSq[pt] & to)
933               st->checkersBB |= to;
934
935           // Discovery checks
936           if (ci.dcCandidates && (ci.dcCandidates & from))
937           {
938               if (pt != ROOK)
939                   st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
940
941               if (pt != BISHOP)
942                   st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
943           }
944       }
945   }
946
947   sideToMove = ~sideToMove;
948
949   assert(pos_is_ok());
950 }
951
952
953 /// Position::undo_move() unmakes a move. When it returns, the position should
954 /// be restored to exactly the same state as before the move was made.
955
956 void Position::undo_move(Move m) {
957
958   assert(is_ok(m));
959
960   sideToMove = ~sideToMove;
961
962   Color us = sideToMove;
963   Color them = ~us;
964   Square from = from_sq(m);
965   Square to = to_sq(m);
966   PieceType pt = type_of(piece_on(to));
967   PieceType capture = st->capturedType;
968
969   assert(is_empty(from) || type_of(m) == CASTLE);
970   assert(capture != KING);
971
972   if (type_of(m) == PROMOTION)
973   {
974       PieceType promotion = promotion_type(m);
975
976       assert(promotion == pt);
977       assert(relative_rank(us, to) == RANK_8);
978       assert(promotion >= KNIGHT && promotion <= QUEEN);
979
980       // Replace the promoted piece with the pawn
981       byTypeBB[promotion] ^= to;
982       byTypeBB[PAWN] |= to;
983       board[to] = make_piece(us, PAWN);
984
985       // Update piece lists, move the last promoted piece at index[to] position
986       // and shrink the list. Add a new pawn to the list.
987       Square lastSquare = pieceList[us][promotion][--pieceCount[us][promotion]];
988       index[lastSquare] = index[to];
989       pieceList[us][promotion][index[lastSquare]] = lastSquare;
990       pieceList[us][promotion][pieceCount[us][promotion]] = SQ_NONE;
991       index[to] = pieceCount[us][PAWN]++;
992       pieceList[us][PAWN][index[to]] = to;
993
994       pt = PAWN;
995   }
996
997   if (type_of(m) == CASTLE)
998   {
999       bool kingSide = to > from;
1000       Square rfrom = to; // Castle is encoded as "king captures friendly rook"
1001       Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
1002       to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
1003       capture = NO_PIECE_TYPE;
1004       pt = KING;
1005       do_castle(to, from, rto, rfrom);
1006   }
1007   else
1008   {
1009       // Put the piece back at the source square
1010       Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
1011       byTypeBB[ALL_PIECES] ^= from_to_bb;
1012       byTypeBB[pt] ^= from_to_bb;
1013       byColorBB[us] ^= from_to_bb;
1014
1015       board[to] = NO_PIECE;
1016       board[from] = make_piece(us, pt);
1017
1018       // Update piece lists, index[to] is not updated and becomes stale. This
1019       // works as long as index[] is accessed just by known occupied squares.
1020       index[from] = index[to];
1021       pieceList[us][pt][index[from]] = from;
1022   }
1023
1024   if (capture)
1025   {
1026       Square capsq = to;
1027
1028       if (type_of(m) == ENPASSANT)
1029       {
1030           capsq -= pawn_push(us);
1031
1032           assert(pt == PAWN);
1033           assert(to == st->previous->epSquare);
1034           assert(relative_rank(us, to) == RANK_6);
1035           assert(piece_on(capsq) == NO_PIECE);
1036       }
1037
1038       // Restore the captured piece
1039       byTypeBB[ALL_PIECES] |= capsq;
1040       byTypeBB[capture] |= capsq;
1041       byColorBB[them] |= capsq;
1042
1043       board[capsq] = make_piece(them, capture);
1044
1045       // Update piece list, add a new captured piece in capsq square
1046       index[capsq] = pieceCount[them][capture]++;
1047       pieceList[them][capture][index[capsq]] = capsq;
1048   }
1049
1050   // Finally point our state pointer back to the previous state
1051   st = st->previous;
1052   gamePly--;
1053
1054   assert(pos_is_ok());
1055 }
1056
1057
1058 /// Position::do_castle() is a helper used to do/undo a castling move. This
1059 /// is a bit tricky, especially in Chess960.
1060
1061 void Position::do_castle(Square kfrom, Square kto, Square rfrom, Square rto) {
1062
1063   Color us = sideToMove;
1064   Bitboard k_from_to_bb = SquareBB[kfrom] ^ SquareBB[kto];
1065   Bitboard r_from_to_bb = SquareBB[rfrom] ^ SquareBB[rto];
1066   byTypeBB[KING] ^= k_from_to_bb;
1067   byTypeBB[ROOK] ^= r_from_to_bb;
1068   byTypeBB[ALL_PIECES] ^= k_from_to_bb ^ r_from_to_bb;
1069   byColorBB[us] ^= k_from_to_bb ^ r_from_to_bb;
1070
1071   // Could be from == to, so first set NO_PIECE then KING and ROOK
1072   board[kfrom] = board[rfrom] = NO_PIECE;
1073   board[kto] = make_piece(us, KING);
1074   board[rto] = make_piece(us, ROOK);
1075
1076   // Could be kfrom == rto, so use a 'tmp' variable
1077   int tmp = index[kfrom];
1078   index[rto] = index[rfrom];
1079   index[kto] = tmp;
1080   pieceList[us][KING][index[kto]] = kto;
1081   pieceList[us][ROOK][index[rto]] = rto;
1082 }
1083
1084
1085 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
1086 /// the side to move without executing any move on the board.
1087
1088 void Position::do_null_move(StateInfo& newSt) {
1089
1090   assert(!checkers());
1091
1092   std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
1093
1094   newSt.previous = st;
1095   st = &newSt;
1096
1097   if (st->epSquare != SQ_NONE)
1098   {
1099       st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
1100       st->epSquare = SQ_NONE;
1101   }
1102
1103   st->key ^= Zobrist::side;
1104   prefetch((char*)TT.first_entry(st->key));
1105
1106   st->rule50++;
1107   st->pliesFromNull = 0;
1108
1109   sideToMove = ~sideToMove;
1110
1111   assert(pos_is_ok());
1112 }
1113
1114 void Position::undo_null_move() {
1115
1116   assert(!checkers());
1117
1118   st = st->previous;
1119   sideToMove = ~sideToMove;
1120 }
1121
1122
1123 /// Position::see() is a static exchange evaluator: It tries to estimate the
1124 /// material gain or loss resulting from a move. Parameter 'asymmThreshold' takes
1125 /// tempi into account. If the side who initiated the capturing sequence does the
1126 /// last capture, he loses a tempo and if the result is below 'asymmThreshold'
1127 /// the capturing sequence is considered bad.
1128
1129 int Position::see_sign(Move m) const {
1130
1131   assert(is_ok(m));
1132
1133   // Early return if SEE cannot be negative because captured piece value
1134   // is not less then capturing one. Note that king moves always return
1135   // here because king midgame value is set to 0.
1136   if (PieceValue[MG][piece_on(to_sq(m))] >= PieceValue[MG][piece_moved(m)])
1137       return 1;
1138
1139   return see(m);
1140 }
1141
1142 int Position::see(Move m, int asymmThreshold) const {
1143
1144   Square from, to;
1145   Bitboard occupied, attackers, stmAttackers;
1146   int swapList[32], slIndex = 1;
1147   PieceType captured;
1148   Color stm;
1149
1150   assert(is_ok(m));
1151
1152   from = from_sq(m);
1153   to = to_sq(m);
1154   captured = type_of(piece_on(to));
1155   occupied = pieces() ^ from;
1156
1157   // Handle en passant moves
1158   if (type_of(m) == ENPASSANT)
1159   {
1160       Square capQq = to - pawn_push(sideToMove);
1161
1162       assert(!captured);
1163       assert(type_of(piece_on(capQq)) == PAWN);
1164
1165       // Remove the captured pawn
1166       occupied ^= capQq;
1167       captured = PAWN;
1168   }
1169   else if (type_of(m) == CASTLE)
1170       // Castle moves are implemented as king capturing the rook so cannot be
1171       // handled correctly. Simply return 0 that is always the correct value
1172       // unless the rook is ends up under attack.
1173       return 0;
1174
1175   // Find all attackers to the destination square, with the moving piece
1176   // removed, but possibly an X-ray attacker added behind it.
1177   attackers = attackers_to(to, occupied);
1178
1179   // If the opponent has no attackers we are finished
1180   stm = ~color_of(piece_on(from));
1181   stmAttackers = attackers & pieces(stm);
1182   if (!stmAttackers)
1183       return PieceValue[MG][captured];
1184
1185   // The destination square is defended, which makes things rather more
1186   // difficult to compute. We proceed by building up a "swap list" containing
1187   // the material gain or loss at each stop in a sequence of captures to the
1188   // destination square, where the sides alternately capture, and always
1189   // capture with the least valuable piece. After each capture, we look for
1190   // new X-ray attacks from behind the capturing piece.
1191   swapList[0] = PieceValue[MG][captured];
1192   captured = type_of(piece_on(from));
1193
1194   do {
1195       assert(slIndex < 32);
1196
1197       // Add the new entry to the swap list
1198       swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1199       slIndex++;
1200
1201       // Locate and remove from 'occupied' the next least valuable attacker
1202       captured = next_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1203
1204       attackers &= occupied; // Remove the just found attacker
1205       stm = ~stm;
1206       stmAttackers = attackers & pieces(stm);
1207
1208       if (captured == KING)
1209       {
1210           // Stop before processing a king capture
1211           if (stmAttackers)
1212               swapList[slIndex++] = QueenValueMg * 16;
1213
1214           break;
1215       }
1216
1217   } while (stmAttackers);
1218
1219   // If we are doing asymmetric SEE evaluation and the same side does the first
1220   // and the last capture, he loses a tempo and gain must be at least worth
1221   // 'asymmThreshold', otherwise we replace the score with a very low value,
1222   // before negamaxing.
1223   if (asymmThreshold)
1224       for (int i = 0; i < slIndex; i += 2)
1225           if (swapList[i] < asymmThreshold)
1226               swapList[i] = - QueenValueMg * 16;
1227
1228   // Having built the swap list, we negamax through it to find the best
1229   // achievable score from the point of view of the side to move.
1230   while (--slIndex)
1231       swapList[slIndex-1] = std::min(-swapList[slIndex], swapList[slIndex-1]);
1232
1233   return swapList[0];
1234 }
1235
1236
1237 /// Position::clear() erases the position object to a pristine state, with an
1238 /// empty board, white to move, and no castling rights.
1239
1240 void Position::clear() {
1241
1242   std::memset(this, 0, sizeof(Position));
1243   startState.epSquare = SQ_NONE;
1244   st = &startState;
1245
1246   for (int i = 0; i < 8; i++)
1247       for (int j = 0; j < 16; j++)
1248           pieceList[0][i][j] = pieceList[1][i][j] = SQ_NONE;
1249 }
1250
1251
1252 /// Position::put_piece() puts a piece on the given square of the board,
1253 /// updating the board array, pieces list, bitboards, and piece counts.
1254
1255 void Position::put_piece(Piece p, Square s) {
1256
1257   Color c = color_of(p);
1258   PieceType pt = type_of(p);
1259
1260   board[s] = p;
1261   index[s] = pieceCount[c][pt]++;
1262   pieceList[c][pt][index[s]] = s;
1263
1264   byTypeBB[ALL_PIECES] |= s;
1265   byTypeBB[pt] |= s;
1266   byColorBB[c] |= s;
1267 }
1268
1269
1270 /// Position::compute_key() computes the hash key of the position. The hash
1271 /// key is usually updated incrementally as moves are made and unmade, the
1272 /// compute_key() function is only used when a new position is set up, and
1273 /// to verify the correctness of the hash key when running in debug mode.
1274
1275 Key Position::compute_key() const {
1276
1277   Key k = Zobrist::castle[st->castleRights];
1278
1279   for (Bitboard b = pieces(); b; )
1280   {
1281       Square s = pop_lsb(&b);
1282       k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1283   }
1284
1285   if (ep_square() != SQ_NONE)
1286       k ^= Zobrist::enpassant[file_of(ep_square())];
1287
1288   if (sideToMove == BLACK)
1289       k ^= Zobrist::side;
1290
1291   return k;
1292 }
1293
1294
1295 /// Position::compute_pawn_key() computes the hash key of the position. The
1296 /// hash key is usually updated incrementally as moves are made and unmade,
1297 /// the compute_pawn_key() function is only used when a new position is set
1298 /// up, and to verify the correctness of the pawn hash key when running in
1299 /// debug mode.
1300
1301 Key Position::compute_pawn_key() const {
1302
1303   Key k = 0;
1304
1305   for (Bitboard b = pieces(PAWN); b; )
1306   {
1307       Square s = pop_lsb(&b);
1308       k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1309   }
1310
1311   return k;
1312 }
1313
1314
1315 /// Position::compute_material_key() computes the hash key of the position.
1316 /// The hash key is usually updated incrementally as moves are made and unmade,
1317 /// the compute_material_key() function is only used when a new position is set
1318 /// up, and to verify the correctness of the material hash key when running in
1319 /// debug mode.
1320
1321 Key Position::compute_material_key() const {
1322
1323   Key k = 0;
1324
1325   for (Color c = WHITE; c <= BLACK; c++)
1326       for (PieceType pt = PAWN; pt <= QUEEN; pt++)
1327           for (int cnt = 0; cnt < pieceCount[c][pt]; cnt++)
1328               k ^= Zobrist::psq[c][pt][cnt];
1329
1330   return k;
1331 }
1332
1333
1334 /// Position::compute_psq_score() computes the incremental scores for the middle
1335 /// game and the endgame. These functions are used to initialize the incremental
1336 /// scores when a new position is set up, and to verify that the scores are correctly
1337 /// updated by do_move and undo_move when the program is running in debug mode.
1338 Score Position::compute_psq_score() const {
1339
1340   Score score = SCORE_ZERO;
1341
1342   for (Bitboard b = pieces(); b; )
1343   {
1344       Square s = pop_lsb(&b);
1345       Piece pc = piece_on(s);
1346       score += psq[color_of(pc)][type_of(pc)][s];
1347   }
1348
1349   return score;
1350 }
1351
1352
1353 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1354 /// game material value for the given side. Material values are updated
1355 /// incrementally during the search, this function is only used while
1356 /// initializing a new Position object.
1357
1358 Value Position::compute_non_pawn_material(Color c) const {
1359
1360   Value value = VALUE_ZERO;
1361
1362   for (PieceType pt = KNIGHT; pt <= QUEEN; pt++)
1363       value += pieceCount[c][pt] * PieceValue[MG][pt];
1364
1365   return value;
1366 }
1367
1368
1369 /// Position::is_draw() tests whether the position is drawn by material,
1370 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1371 /// must be done by the search.
1372 bool Position::is_draw() const {
1373
1374   // Draw by material?
1375   if (   !pieces(PAWN)
1376       && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1377       return true;
1378
1379   // Draw by the 50 moves rule?
1380   if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1381       return true;
1382
1383   // Draw by repetition?
1384   int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1385
1386   if (i <= e)
1387   {
1388       StateInfo* stp = st->previous->previous;
1389
1390       do {
1391           stp = stp->previous->previous;
1392
1393           if (stp->key == st->key)
1394               return true;
1395
1396           i += 2;
1397
1398       } while (i <= e);
1399   }
1400
1401   return false;
1402 }
1403
1404
1405 /// Position::flip() flips position with the white and black sides reversed. This
1406 /// is only useful for debugging especially for finding evaluation symmetry bugs.
1407
1408 void Position::flip() {
1409
1410   const Position pos(*this);
1411
1412   clear();
1413
1414   sideToMove = ~pos.side_to_move();
1415   thisThread = pos.this_thread();
1416   nodes = pos.nodes_searched();
1417   chess960 = pos.is_chess960();
1418   gamePly = pos.game_ply();
1419
1420   for (Square s = SQ_A1; s <= SQ_H8; s++)
1421       if (!pos.is_empty(s))
1422           put_piece(Piece(pos.piece_on(s) ^ 8), ~s);
1423
1424   if (pos.can_castle(WHITE_OO))
1425       set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, KING_SIDE));
1426   if (pos.can_castle(WHITE_OOO))
1427       set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, QUEEN_SIDE));
1428   if (pos.can_castle(BLACK_OO))
1429       set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, KING_SIDE));
1430   if (pos.can_castle(BLACK_OOO))
1431       set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, QUEEN_SIDE));
1432
1433   if (pos.st->epSquare != SQ_NONE)
1434       st->epSquare = ~pos.st->epSquare;
1435
1436   st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
1437
1438   st->key = compute_key();
1439   st->pawnKey = compute_pawn_key();
1440   st->materialKey = compute_material_key();
1441   st->psq = compute_psq_score();
1442   st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
1443   st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
1444
1445   assert(pos_is_ok());
1446 }
1447
1448
1449 /// Position::pos_is_ok() performs some consitency checks for the position object.
1450 /// This is meant to be helpful when debugging.
1451
1452 bool Position::pos_is_ok(int* failedStep) const {
1453
1454   int dummy, *step = failedStep ? failedStep : &dummy;
1455
1456   // What features of the position should be verified?
1457   const bool all = false;
1458
1459   const bool debugBitboards       = all || false;
1460   const bool debugKingCount       = all || false;
1461   const bool debugKingCapture     = all || false;
1462   const bool debugCheckerCount    = all || false;
1463   const bool debugKey             = all || false;
1464   const bool debugMaterialKey     = all || false;
1465   const bool debugPawnKey         = all || false;
1466   const bool debugIncrementalEval = all || false;
1467   const bool debugNonPawnMaterial = all || false;
1468   const bool debugPieceCounts     = all || false;
1469   const bool debugPieceList       = all || false;
1470   const bool debugCastleSquares   = all || false;
1471
1472   *step = 1;
1473
1474   if (sideToMove != WHITE && sideToMove != BLACK)
1475       return false;
1476
1477   if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1478       return false;
1479
1480   if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1481       return false;
1482
1483   if ((*step)++, debugKingCount)
1484   {
1485       int kingCount[COLOR_NB] = {};
1486
1487       for (Square s = SQ_A1; s <= SQ_H8; s++)
1488           if (type_of(piece_on(s)) == KING)
1489               kingCount[color_of(piece_on(s))]++;
1490
1491       if (kingCount[0] != 1 || kingCount[1] != 1)
1492           return false;
1493   }
1494
1495   if ((*step)++, debugKingCapture)
1496       if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1497           return false;
1498
1499   if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1500       return false;
1501
1502   if ((*step)++, debugBitboards)
1503   {
1504       // The intersection of the white and black pieces must be empty
1505       if (pieces(WHITE) & pieces(BLACK))
1506           return false;
1507
1508       // The union of the white and black pieces must be equal to all
1509       // occupied squares
1510       if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1511           return false;
1512
1513       // Separate piece type bitboards must have empty intersections
1514       for (PieceType p1 = PAWN; p1 <= KING; p1++)
1515           for (PieceType p2 = PAWN; p2 <= KING; p2++)
1516               if (p1 != p2 && (pieces(p1) & pieces(p2)))
1517                   return false;
1518   }
1519
1520   if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1521       return false;
1522
1523   if ((*step)++, debugKey && st->key != compute_key())
1524       return false;
1525
1526   if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1527       return false;
1528
1529   if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1530       return false;
1531
1532   if ((*step)++, debugIncrementalEval && st->psq != compute_psq_score())
1533       return false;
1534
1535   if ((*step)++, debugNonPawnMaterial)
1536       if (   st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1537           || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1538           return false;
1539
1540   if ((*step)++, debugPieceCounts)
1541       for (Color c = WHITE; c <= BLACK; c++)
1542           for (PieceType pt = PAWN; pt <= KING; pt++)
1543               if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1544                   return false;
1545
1546   if ((*step)++, debugPieceList)
1547       for (Color c = WHITE; c <= BLACK; c++)
1548           for (PieceType pt = PAWN; pt <= KING; pt++)
1549               for (int i = 0; i < pieceCount[c][pt]; i++)
1550                   if (   board[pieceList[c][pt][i]] != make_piece(c, pt)
1551                       || index[pieceList[c][pt][i]] != i)
1552                       return false;
1553
1554   if ((*step)++, debugCastleSquares)
1555       for (Color c = WHITE; c <= BLACK; c++)
1556           for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1557           {
1558               CastleRight cr = make_castle_right(c, s);
1559
1560               if (!can_castle(cr))
1561                   continue;
1562
1563               if (  (castleRightsMask[king_square(c)] & cr) != cr
1564                   || piece_on(castleRookSquare[c][s]) != make_piece(c, ROOK)
1565                   || castleRightsMask[castleRookSquare[c][s]] != cr)
1566                   return false;
1567           }
1568
1569   *step = 0;
1570   return true;
1571 }