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