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