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