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