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