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