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