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