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