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