Base work for exclusion search
[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-2009 Marco Costalba
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
21 ////
22 //// Includes
23 ////
24
25 #include <cassert>
26 #include <cstring>
27 #include <fstream>
28 #include <iostream>
29
30 #include "bitcount.h"
31 #include "mersenne.h"
32 #include "movegen.h"
33 #include "movepick.h"
34 #include "position.h"
35 #include "psqtab.h"
36 #include "san.h"
37 #include "tt.h"
38 #include "ucioption.h"
39
40 using std::string;
41
42
43 ////
44 //// Variables
45 ////
46
47 int Position::castleRightsMask[64];
48
49 Key Position::zobrist[2][8][64];
50 Key Position::zobEp[64];
51 Key Position::zobCastle[16];
52 Key Position::zobMaterial[2][8][16];
53 Key Position::zobSideToMove;
54 Key Position::zobExclusion;
55
56 Score Position::PieceSquareTable[16][64];
57
58 static bool RequestPending = false;
59
60
61 /// Constructors
62
63 CheckInfo::CheckInfo(const Position& pos) {
64
65   Color us = pos.side_to_move();
66   Color them = opposite_color(us);
67
68   ksq = pos.king_square(them);
69   dcCandidates = pos.discovered_check_candidates(us);
70
71   checkSq[PAWN] = pos.attacks_from<PAWN>(ksq, them);
72   checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
73   checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
74   checkSq[ROOK] = pos.attacks_from<ROOK>(ksq);
75   checkSq[QUEEN] = checkSq[BISHOP] | checkSq[ROOK];
76   checkSq[KING] = EmptyBoardBB;
77 }
78
79 Position::Position(const Position& pos) {
80   copy(pos);
81 }
82
83 Position::Position(const string& fen) {
84   from_fen(fen);
85 }
86
87
88 /// Position::from_fen() initializes the position object with the given FEN
89 /// string. This function is not very robust - make sure that input FENs are
90 /// correct (this is assumed to be the responsibility of the GUI).
91
92 void Position::from_fen(const string& fen) {
93
94   static const string pieceLetters = "KQRBNPkqrbnp";
95   static const Piece pieces[] = { WK, WQ, WR, WB, WN, WP, BK, BQ, BR, BB, BN, BP };
96
97   clear();
98
99   // Board
100   Rank rank = RANK_8;
101   File file = FILE_A;
102   size_t i = 0;
103   for ( ; fen[i] != ' '; i++)
104   {
105       if (isdigit(fen[i]))
106       {
107           // Skip the given number of files
108           file += (fen[i] - '1' + 1);
109           continue;
110       }
111       else if (fen[i] == '/')
112       {
113           file = FILE_A;
114           rank--;
115           continue;
116       }
117       size_t idx = pieceLetters.find(fen[i]);
118       if (idx == string::npos)
119       {
120            std::cout << "Error in FEN at character " << i << std::endl;
121            return;
122       }
123       Square square = make_square(file, rank);
124       put_piece(pieces[idx], square);
125       file++;
126   }
127
128   // Side to move
129   i++;
130   if (fen[i] != 'w' && fen[i] != 'b')
131   {
132       std::cout << "Error in FEN at character " << i << std::endl;
133       return;
134   }
135   sideToMove = (fen[i] == 'w' ? WHITE : BLACK);
136
137   // Castling rights
138   i++;
139   if (fen[i] != ' ')
140   {
141       std::cout << "Error in FEN at character " << i << std::endl;
142       return;
143   }
144
145   i++;
146   while(strchr("KQkqabcdefghABCDEFGH-", fen[i])) {
147     if (fen[i] == '-')
148     {
149       i++;
150       break;
151     }
152     else if(fen[i] == 'K') allow_oo(WHITE);
153     else if(fen[i] == 'Q') allow_ooo(WHITE);
154     else if(fen[i] == 'k') allow_oo(BLACK);
155     else if(fen[i] == 'q') allow_ooo(BLACK);
156     else if(fen[i] >= 'A' && fen[i] <= 'H') {
157       File rookFile, kingFile = FILE_NONE;
158       for(Square square = SQ_B1; square <= SQ_G1; square++)
159         if(piece_on(square) == WK)
160           kingFile = square_file(square);
161       if(kingFile == FILE_NONE) {
162         std::cout << "Error in FEN at character " << i << std::endl;
163         return;
164       }
165       initialKFile = kingFile;
166       rookFile = File(fen[i] - 'A') + FILE_A;
167       if(rookFile < initialKFile) {
168         allow_ooo(WHITE);
169         initialQRFile = rookFile;
170       }
171       else {
172         allow_oo(WHITE);
173         initialKRFile = rookFile;
174       }
175     }
176     else if(fen[i] >= 'a' && fen[i] <= 'h') {
177       File rookFile, kingFile = FILE_NONE;
178       for(Square square = SQ_B8; square <= SQ_G8; square++)
179         if(piece_on(square) == BK)
180           kingFile = square_file(square);
181       if(kingFile == FILE_NONE) {
182         std::cout << "Error in FEN at character " << i << std::endl;
183         return;
184       }
185       initialKFile = kingFile;
186       rookFile = File(fen[i] - 'a') + FILE_A;
187       if(rookFile < initialKFile) {
188         allow_ooo(BLACK);
189         initialQRFile = rookFile;
190       }
191       else {
192         allow_oo(BLACK);
193         initialKRFile = rookFile;
194       }
195     }
196     else {
197       std::cout << "Error in FEN at character " << i << std::endl;
198       return;
199     }
200     i++;
201   }
202
203   // Skip blanks
204   while (fen[i] == ' ')
205       i++;
206
207   // En passant square
208   if (    i <= fen.length() - 2
209       && (fen[i] >= 'a' && fen[i] <= 'h')
210       && (fen[i+1] == '3' || fen[i+1] == '6'))
211       st->epSquare = square_from_string(fen.substr(i, 2));
212
213   // Various initialisation
214   for (Square sq = SQ_A1; sq <= SQ_H8; sq++)
215       castleRightsMask[sq] = ALL_CASTLES;
216
217   castleRightsMask[make_square(initialKFile,  RANK_1)] ^= (WHITE_OO|WHITE_OOO);
218   castleRightsMask[make_square(initialKFile,  RANK_8)] ^= (BLACK_OO|BLACK_OOO);
219   castleRightsMask[make_square(initialKRFile, RANK_1)] ^= WHITE_OO;
220   castleRightsMask[make_square(initialKRFile, RANK_8)] ^= BLACK_OO;
221   castleRightsMask[make_square(initialQRFile, RANK_1)] ^= WHITE_OOO;
222   castleRightsMask[make_square(initialQRFile, RANK_8)] ^= BLACK_OOO;
223
224   find_checkers();
225
226   st->key = compute_key();
227   st->pawnKey = compute_pawn_key();
228   st->materialKey = compute_material_key();
229   st->value = compute_value();
230   st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
231   st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
232 }
233
234
235 /// Position::to_fen() converts the position object to a FEN string. This is
236 /// probably only useful for debugging.
237
238 const string Position::to_fen() const {
239
240   static const string pieceLetters = " PNBRQK  pnbrqk";
241   string fen;
242   int skip;
243
244   for (Rank rank = RANK_8; rank >= RANK_1; rank--)
245   {
246       skip = 0;
247       for (File file = FILE_A; file <= FILE_H; file++)
248       {
249           Square sq = make_square(file, rank);
250           if (!square_is_occupied(sq))
251           {   skip++;
252               continue;
253           }
254           if (skip > 0)
255           {
256               fen += (char)skip + '0';
257               skip = 0;
258           }
259           fen += pieceLetters[piece_on(sq)];
260       }
261       if (skip > 0)
262           fen += (char)skip + '0';
263
264       fen += (rank > RANK_1 ? '/' : ' ');
265   }
266   fen += (sideToMove == WHITE ? "w " : "b ");
267   if (st->castleRights != NO_CASTLES)
268   {
269     if (can_castle_kingside(WHITE))  fen += 'K';
270     if (can_castle_queenside(WHITE)) fen += 'Q';
271     if (can_castle_kingside(BLACK))  fen += 'k';
272     if (can_castle_queenside(BLACK)) fen += 'q';
273   } else
274       fen += '-';
275
276   fen += ' ';
277   if (ep_square() != SQ_NONE)
278       fen += square_to_string(ep_square());
279   else
280       fen += '-';
281
282   return fen;
283 }
284
285
286 /// Position::print() prints an ASCII representation of the position to
287 /// the standard output. If a move is given then also the san is print.
288
289 void Position::print(Move m) const {
290
291   static const string pieceLetters = " PNBRQK  PNBRQK .";
292
293   // Check for reentrancy, as example when called from inside
294   // MovePicker that is used also here in move_to_san()
295   if (RequestPending)
296       return;
297
298   RequestPending = true;
299
300   std::cout << std::endl;
301   if (m != MOVE_NONE)
302   {
303       string col = (color_of_piece_on(move_from(m)) == BLACK ? ".." : "");
304       std::cout << "Move is: " << col << move_to_san(*this, m) << std::endl;
305   }
306   for (Rank rank = RANK_8; rank >= RANK_1; rank--)
307   {
308       std::cout << "+---+---+---+---+---+---+---+---+" << std::endl;
309       for (File file = FILE_A; file <= FILE_H; file++)
310       {
311           Square sq = make_square(file, rank);
312           Piece piece = piece_on(sq);
313           if (piece == EMPTY && square_color(sq) == WHITE)
314               piece = NO_PIECE;
315
316           char col = (color_of_piece_on(sq) == BLACK ? '=' : ' ');
317           std::cout << '|' << col << pieceLetters[piece] << col;
318       }
319       std::cout << '|' << std::endl;
320   }
321   std::cout << "+---+---+---+---+---+---+---+---+" << std::endl
322             << "Fen is: " << to_fen() << std::endl
323             << "Key is: " << st->key << std::endl;
324
325   RequestPending = false;
326 }
327
328
329 /// Position::copy() creates a copy of the input position.
330
331 void Position::copy(const Position& pos) {
332
333   memcpy(this, &pos, sizeof(Position));
334   saveState(); // detach and copy state info
335 }
336
337
338 /// Position:hidden_checkers<>() returns a bitboard of all pinned (against the
339 /// king) pieces for the given color and for the given pinner type. Or, when
340 /// template parameter FindPinned is false, the pieces of the given color
341 /// candidate for a discovery check against the enemy king.
342 /// Note that checkersBB bitboard must be already updated.
343
344 template<bool FindPinned>
345 Bitboard Position::hidden_checkers(Color c) const {
346
347   Bitboard result = EmptyBoardBB;
348   Bitboard pinners = pieces_of_color(FindPinned ? opposite_color(c) : c);
349
350   // Pinned pieces protect our king, dicovery checks attack
351   // the enemy king.
352   Square ksq = king_square(FindPinned ? c : opposite_color(c));
353
354   // Pinners are sliders, not checkers, that give check when candidate pinned is removed
355   pinners &= (pieces(ROOK, QUEEN) & RookPseudoAttacks[ksq]) | (pieces(BISHOP, QUEEN) & BishopPseudoAttacks[ksq]);
356
357   if (FindPinned && pinners)
358       pinners &= ~st->checkersBB;
359
360   while (pinners)
361   {
362       Square s = pop_1st_bit(&pinners);
363       Bitboard b = squares_between(s, ksq) & occupied_squares();
364
365       assert(b);
366
367       if (  !(b & (b - 1)) // Only one bit set?
368           && (b & pieces_of_color(c))) // Is an our piece?
369           result |= b;
370   }
371   return result;
372 }
373
374
375 /// Position:pinned_pieces() returns a bitboard of all pinned (against the
376 /// king) pieces for the given color.
377
378 Bitboard Position::pinned_pieces(Color c) const {
379
380   return hidden_checkers<true>(c);
381 }
382
383
384 /// Position:discovered_check_candidates() returns a bitboard containing all
385 /// pieces for the given side which are candidates for giving a discovered
386 /// check.
387
388 Bitboard Position::discovered_check_candidates(Color c) const {
389
390   return hidden_checkers<false>(c);
391 }
392
393 /// Position::attackers_to() computes a bitboard containing all pieces which
394 /// attacks a given square.
395
396 Bitboard Position::attackers_to(Square s) const {
397
398   return  (attacks_from<PAWN>(s, BLACK) & pieces(PAWN, WHITE))
399         | (attacks_from<PAWN>(s, WHITE) & pieces(PAWN, BLACK))
400         | (attacks_from<KNIGHT>(s)      & pieces(KNIGHT))
401         | (attacks_from<ROOK>(s)        & pieces(ROOK, QUEEN))
402         | (attacks_from<BISHOP>(s)      & pieces(BISHOP, QUEEN))
403         | (attacks_from<KING>(s)        & pieces(KING));
404 }
405
406 /// Position::attacks_from() computes a bitboard of all attacks
407 /// of a given piece put in a given square.
408
409 Bitboard Position::attacks_from(Piece p, Square s) const {
410
411   assert(square_is_ok(s));
412
413   switch (p)
414   {
415   case WP:          return attacks_from<PAWN>(s, WHITE);
416   case BP:          return attacks_from<PAWN>(s, BLACK);
417   case WN: case BN: return attacks_from<KNIGHT>(s);
418   case WB: case BB: return attacks_from<BISHOP>(s);
419   case WR: case BR: return attacks_from<ROOK>(s);
420   case WQ: case BQ: return attacks_from<QUEEN>(s);
421   case WK: case BK: return attacks_from<KING>(s);
422   default: break;
423   }
424   return false;
425 }
426
427
428 /// Position::move_attacks_square() tests whether a move from the current
429 /// position attacks a given square.
430
431 bool Position::move_attacks_square(Move m, Square s) const {
432
433   assert(move_is_ok(m));
434   assert(square_is_ok(s));
435
436   Square f = move_from(m), t = move_to(m);
437
438   assert(square_is_occupied(f));
439
440   if (bit_is_set(attacks_from(piece_on(f), t), s))
441       return true;
442
443   // Move the piece and scan for X-ray attacks behind it
444   Bitboard occ = occupied_squares();
445   Color us = color_of_piece_on(f);
446   clear_bit(&occ, f);
447   set_bit(&occ, t);
448   Bitboard xray = ( (rook_attacks_bb(s, occ) &  pieces(ROOK, QUEEN))
449                    |(bishop_attacks_bb(s, occ) & pieces(BISHOP, QUEEN))) & pieces_of_color(us);
450
451   // If we have attacks we need to verify that are caused by our move
452   // and are not already existent ones.
453   return xray && (xray ^ (xray & attacks_from<QUEEN>(s)));
454 }
455
456
457 /// Position::find_checkers() computes the checkersBB bitboard, which
458 /// contains a nonzero bit for each checking piece (0, 1 or 2). It
459 /// currently works by calling Position::attackers_to, which is probably
460 /// inefficient. Consider rewriting this function to use the last move
461 /// played, like in non-bitboard versions of Glaurung.
462
463 void Position::find_checkers() {
464
465   Color us = side_to_move();
466   st->checkersBB = attackers_to(king_square(us)) & pieces_of_color(opposite_color(us));
467 }
468
469
470 /// Position::pl_move_is_legal() tests whether a pseudo-legal move is legal
471
472 bool Position::pl_move_is_legal(Move m, Bitboard pinned) const {
473
474   assert(is_ok());
475   assert(move_is_ok(m));
476   assert(pinned == pinned_pieces(side_to_move()));
477
478   // Castling moves are checked for legality during move generation.
479   if (move_is_castle(m))
480       return true;
481
482   Color us = side_to_move();
483   Square from = move_from(m);
484
485   assert(color_of_piece_on(from) == us);
486   assert(piece_on(king_square(us)) == piece_of_color_and_type(us, KING));
487
488   // En passant captures are a tricky special case. Because they are
489   // rather uncommon, we do it simply by testing whether the king is attacked
490   // after the move is made
491   if (move_is_ep(m))
492   {
493       Color them = opposite_color(us);
494       Square to = move_to(m);
495       Square capsq = make_square(square_file(to), square_rank(from));
496       Bitboard b = occupied_squares();
497       Square ksq = king_square(us);
498
499       assert(to == ep_square());
500       assert(piece_on(from) == piece_of_color_and_type(us, PAWN));
501       assert(piece_on(capsq) == piece_of_color_and_type(them, PAWN));
502       assert(piece_on(to) == EMPTY);
503
504       clear_bit(&b, from);
505       clear_bit(&b, capsq);
506       set_bit(&b, to);
507
508       return   !(rook_attacks_bb(ksq, b) & pieces(ROOK, QUEEN, them))
509             && !(bishop_attacks_bb(ksq, b) & pieces(BISHOP, QUEEN, them));
510   }
511
512   // If the moving piece is a king, check whether the destination
513   // square is attacked by the opponent.
514   if (type_of_piece_on(from) == KING)
515       return !(attackers_to(move_to(m)) & pieces_of_color(opposite_color(us)));
516
517   // A non-king move is legal if and only if it is not pinned or it
518   // is moving along the ray towards or away from the king.
519   return (   !pinned
520           || !bit_is_set(pinned, from)
521           || (direction_between_squares(from, king_square(us)) == direction_between_squares(move_to(m), king_square(us))));
522 }
523
524
525 /// Position::pl_move_is_evasion() tests whether a pseudo-legal move is a legal evasion
526
527 bool Position::pl_move_is_evasion(Move m, Bitboard pinned) const
528 {
529   assert(is_check());
530
531   Color us = side_to_move();
532   Square from = move_from(m);
533   Square to = move_to(m);
534
535   // King moves and en-passant captures are verified in pl_move_is_legal()
536   if (type_of_piece_on(from) == KING || move_is_ep(m))
537       return pl_move_is_legal(m, pinned);
538
539   Bitboard target = checkers();
540   Square checksq = pop_1st_bit(&target);
541
542   if (target) // double check ?
543       return false;
544
545   // Our move must be a blocking evasion or a capture of the checking piece
546   target = squares_between(checksq, king_square(us)) | checkers();
547   return bit_is_set(target, to) && pl_move_is_legal(m, pinned);
548 }
549
550
551 /// Position::move_is_check() tests whether a pseudo-legal move is a check
552
553 bool Position::move_is_check(Move m) const {
554
555   return move_is_check(m, CheckInfo(*this));
556 }
557
558 bool Position::move_is_check(Move m, const CheckInfo& ci) const {
559
560   assert(is_ok());
561   assert(move_is_ok(m));
562   assert(ci.dcCandidates == discovered_check_candidates(side_to_move()));
563   assert(color_of_piece_on(move_from(m)) == side_to_move());
564   assert(piece_on(ci.ksq) == piece_of_color_and_type(opposite_color(side_to_move()), KING));
565
566   Square from = move_from(m);
567   Square to = move_to(m);
568   PieceType pt = type_of_piece_on(from);
569
570   // Direct check ?
571   if (bit_is_set(ci.checkSq[pt], to))
572       return true;
573
574   // Discovery check ?
575   if (ci.dcCandidates && bit_is_set(ci.dcCandidates, from))
576   {
577       // For pawn and king moves we need to verify also direction
578       if (  (pt != PAWN && pt != KING)
579           ||(direction_between_squares(from, ci.ksq) != direction_between_squares(to, ci.ksq)))
580           return true;
581   }
582
583   // Can we skip the ugly special cases ?
584   if (!move_is_special(m))
585       return false;
586
587   Color us = side_to_move();
588   Bitboard b = occupied_squares();
589
590   // Promotion with check ?
591   if (move_is_promotion(m))
592   {
593       clear_bit(&b, from);
594
595       switch (move_promotion_piece(m))
596       {
597       case KNIGHT:
598           return bit_is_set(attacks_from<KNIGHT>(to), ci.ksq);
599       case BISHOP:
600           return bit_is_set(bishop_attacks_bb(to, b), ci.ksq);
601       case ROOK:
602           return bit_is_set(rook_attacks_bb(to, b), ci.ksq);
603       case QUEEN:
604           return bit_is_set(queen_attacks_bb(to, b), ci.ksq);
605       default:
606           assert(false);
607       }
608   }
609
610   // En passant capture with check?  We have already handled the case
611   // of direct checks and ordinary discovered check, the only case we
612   // need to handle is the unusual case of a discovered check through the
613   // captured pawn.
614   if (move_is_ep(m))
615   {
616       Square capsq = make_square(square_file(to), square_rank(from));
617       clear_bit(&b, from);
618       clear_bit(&b, capsq);
619       set_bit(&b, to);
620       return  (rook_attacks_bb(ci.ksq, b) & pieces(ROOK, QUEEN, us))
621             ||(bishop_attacks_bb(ci.ksq, b) & pieces(BISHOP, QUEEN, us));
622   }
623
624   // Castling with check ?
625   if (move_is_castle(m))
626   {
627       Square kfrom, kto, rfrom, rto;
628       kfrom = from;
629       rfrom = to;
630
631       if (rfrom > kfrom)
632       {
633           kto = relative_square(us, SQ_G1);
634           rto = relative_square(us, SQ_F1);
635       } else {
636           kto = relative_square(us, SQ_C1);
637           rto = relative_square(us, SQ_D1);
638       }
639       clear_bit(&b, kfrom);
640       clear_bit(&b, rfrom);
641       set_bit(&b, rto);
642       set_bit(&b, kto);
643       return bit_is_set(rook_attacks_bb(rto, b), ci.ksq);
644   }
645
646   return false;
647 }
648
649
650 /// Position::do_move() makes a move, and saves all information necessary
651 /// to a StateInfo object. The move is assumed to be legal.
652 /// Pseudo-legal moves should be filtered out before this function is called.
653
654 void Position::do_move(Move m, StateInfo& newSt) {
655
656   CheckInfo ci(*this);
657   do_move(m, newSt, ci, move_is_check(m, ci));
658 }
659
660 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
661
662   assert(is_ok());
663   assert(move_is_ok(m));
664
665   Bitboard key = st->key;
666
667   // Copy some fields of old state to our new StateInfo object except the
668   // ones which are recalculated from scratch anyway, then switch our state
669   // pointer to point to the new, ready to be updated, state.
670   struct ReducedStateInfo {
671     Key pawnKey, materialKey;
672     int castleRights, rule50, pliesFromNull;
673     Square epSquare;
674     Value value;
675     Value npMaterial[2];
676   };
677
678   memcpy(&newSt, st, sizeof(ReducedStateInfo));
679   newSt.previous = st;
680   st = &newSt;
681
682   // Save the current key to the history[] array, in order to be able to
683   // detect repetition draws.
684   history[gamePly] = key;
685   gamePly++;
686
687   // Update side to move
688   key ^= zobSideToMove;
689
690   // Increment the 50 moves rule draw counter. Resetting it to zero in the
691   // case of non-reversible moves is taken care of later.
692   st->rule50++;
693   st->pliesFromNull++;
694
695   if (move_is_castle(m))
696   {
697       st->key = key;
698       do_castle_move(m);
699       return;
700   }
701
702   Color us = side_to_move();
703   Color them = opposite_color(us);
704   Square from = move_from(m);
705   Square to = move_to(m);
706   bool ep = move_is_ep(m);
707   bool pm = move_is_promotion(m);
708
709   Piece piece = piece_on(from);
710   PieceType pt = type_of_piece(piece);
711   PieceType capture = ep ? PAWN : type_of_piece_on(to);
712
713   assert(color_of_piece_on(from) == us);
714   assert(color_of_piece_on(to) == them || square_is_empty(to));
715   assert(!(ep || pm) || piece == piece_of_color_and_type(us, PAWN));
716   assert(!pm || relative_rank(us, to) == RANK_8);
717
718   if (capture)
719       do_capture_move(key, capture, them, to, ep);
720
721   // Update hash key
722   key ^= zobrist[us][pt][from] ^ zobrist[us][pt][to];
723
724   // Reset en passant square
725   if (st->epSquare != SQ_NONE)
726   {
727       key ^= zobEp[st->epSquare];
728       st->epSquare = SQ_NONE;
729   }
730
731   // Update castle rights, try to shortcut a common case
732   int cm = castleRightsMask[from] & castleRightsMask[to];
733   if (cm != ALL_CASTLES && ((cm & st->castleRights) != st->castleRights))
734   {
735       key ^= zobCastle[st->castleRights];
736       st->castleRights &= castleRightsMask[from];
737       st->castleRights &= castleRightsMask[to];
738       key ^= zobCastle[st->castleRights];
739   }
740
741   // Prefetch TT access as soon as we know key is updated
742   TT.prefetch(key);
743
744   // Move the piece
745   Bitboard move_bb = make_move_bb(from, to);
746   do_move_bb(&(byColorBB[us]), move_bb);
747   do_move_bb(&(byTypeBB[pt]), move_bb);
748   do_move_bb(&(byTypeBB[0]), move_bb); // HACK: byTypeBB[0] == occupied squares
749
750   board[to] = board[from];
751   board[from] = EMPTY;
752
753   // Update piece lists, note that index[from] is not updated and
754   // becomes stale. This works as long as index[] is accessed just
755   // by known occupied squares.
756   index[to] = index[from];
757   pieceList[us][pt][index[to]] = to;
758
759   // If the moving piece was a pawn do some special extra work
760   if (pt == PAWN)
761   {
762       // Reset rule 50 draw counter
763       st->rule50 = 0;
764
765       // Update pawn hash key
766       st->pawnKey ^= zobrist[us][PAWN][from] ^ zobrist[us][PAWN][to];
767
768       // Set en passant square, only if moved pawn can be captured
769       if ((to ^ from) == 16)
770       {
771           if (attacks_from<PAWN>(from + (us == WHITE ? DELTA_N : DELTA_S), us) & pieces(PAWN, them))
772           {
773               st->epSquare = Square((int(from) + int(to)) / 2);
774               key ^= zobEp[st->epSquare];
775           }
776       }
777   }
778
779   // Update incremental scores
780   st->value += pst_delta(piece, from, to);
781
782   // Set capture piece
783   st->capture = capture;
784
785   if (pm) // promotion ?
786   {
787       PieceType promotion = move_promotion_piece(m);
788
789       assert(promotion >= KNIGHT && promotion <= QUEEN);
790
791       // Insert promoted piece instead of pawn
792       clear_bit(&(byTypeBB[PAWN]), to);
793       set_bit(&(byTypeBB[promotion]), to);
794       board[to] = piece_of_color_and_type(us, promotion);
795
796       // Update material key
797       st->materialKey ^= zobMaterial[us][PAWN][pieceCount[us][PAWN]];
798       st->materialKey ^= zobMaterial[us][promotion][pieceCount[us][promotion]+1];
799
800       // Update piece counts
801       pieceCount[us][PAWN]--;
802       pieceCount[us][promotion]++;
803
804       // Update piece lists, move the last pawn at index[to] position
805       // and shrink the list. Add a new promotion piece to the list.
806       Square lastPawnSquare = pieceList[us][PAWN][pieceCount[us][PAWN]];
807       index[lastPawnSquare] = index[to];
808       pieceList[us][PAWN][index[lastPawnSquare]] = lastPawnSquare;
809       pieceList[us][PAWN][pieceCount[us][PAWN]] = SQ_NONE;
810       index[to] = pieceCount[us][promotion] - 1;
811       pieceList[us][promotion][index[to]] = to;
812
813       // Partially revert hash keys update
814       key ^= zobrist[us][PAWN][to] ^ zobrist[us][promotion][to];
815       st->pawnKey ^= zobrist[us][PAWN][to];
816
817       // Partially revert and update incremental scores
818       st->value -= pst(us, PAWN, to);
819       st->value += pst(us, promotion, to);
820
821       // Update material
822       st->npMaterial[us] += piece_value_midgame(promotion);
823   }
824
825   // Update the key with the final value
826   st->key = key;
827
828   // Update checkers bitboard, piece must be already moved
829   st->checkersBB = EmptyBoardBB;
830
831   if (moveIsCheck)
832   {
833       if (ep | pm)
834           st->checkersBB = attackers_to(king_square(them)) & pieces_of_color(us);
835       else
836       {
837           // Direct checks
838           if (bit_is_set(ci.checkSq[pt], to))
839               st->checkersBB = SetMaskBB[to];
840
841           // Discovery checks
842           if (ci.dcCandidates && bit_is_set(ci.dcCandidates, from))
843           {
844               if (pt != ROOK)
845                   st->checkersBB |= (attacks_from<ROOK>(ci.ksq) & pieces(ROOK, QUEEN, us));
846
847               if (pt != BISHOP)
848                   st->checkersBB |= (attacks_from<BISHOP>(ci.ksq) & pieces(BISHOP, QUEEN, us));
849           }
850       }
851   }
852
853   // Finish
854   sideToMove = opposite_color(sideToMove);
855   st->value += (sideToMove == WHITE ?  TempoValue : -TempoValue);
856
857   assert(is_ok());
858 }
859
860
861 /// Position::do_capture_move() is a private method used to update captured
862 /// piece info. It is called from the main Position::do_move function.
863
864 void Position::do_capture_move(Bitboard& key, PieceType capture, Color them, Square to, bool ep) {
865
866     assert(capture != KING);
867
868     Square capsq = to;
869
870     if (ep) // en passant ?
871     {
872         capsq = (them == BLACK)? (to - DELTA_N) : (to - DELTA_S);
873
874         assert(to == st->epSquare);
875         assert(relative_rank(opposite_color(them), to) == RANK_6);
876         assert(piece_on(to) == EMPTY);
877         assert(piece_on(capsq) == piece_of_color_and_type(them, PAWN));
878
879         board[capsq] = EMPTY;
880     }
881
882     // Remove captured piece
883     clear_bit(&(byColorBB[them]), capsq);
884     clear_bit(&(byTypeBB[capture]), capsq);
885     clear_bit(&(byTypeBB[0]), capsq);
886
887     // Update hash key
888     key ^= zobrist[them][capture][capsq];
889
890     // Update incremental scores
891     st->value -= pst(them, capture, capsq);
892
893     // If the captured piece was a pawn, update pawn hash key,
894     // otherwise update non-pawn material.
895     if (capture == PAWN)
896         st->pawnKey ^= zobrist[them][PAWN][capsq];
897     else
898         st->npMaterial[them] -= piece_value_midgame(capture);
899
900     // Update material hash key
901     st->materialKey ^= zobMaterial[them][capture][pieceCount[them][capture]];
902
903     // Update piece count
904     pieceCount[them][capture]--;
905
906     // Update piece list, move the last piece at index[capsq] position
907     //
908     // WARNING: This is a not perfectly revresible operation. When we
909     // will reinsert the captured piece in undo_move() we will put it
910     // at the end of the list and not in its original place, it means
911     // index[] and pieceList[] are not guaranteed to be invariant to a
912     // do_move() + undo_move() sequence.
913     Square lastPieceSquare = pieceList[them][capture][pieceCount[them][capture]];
914     index[lastPieceSquare] = index[capsq];
915     pieceList[them][capture][index[lastPieceSquare]] = lastPieceSquare;
916     pieceList[them][capture][pieceCount[them][capture]] = SQ_NONE;
917
918     // Reset rule 50 counter
919     st->rule50 = 0;
920 }
921
922
923 /// Position::do_castle_move() is a private method used to make a castling
924 /// move. It is called from the main Position::do_move function. Note that
925 /// castling moves are encoded as "king captures friendly rook" moves, for
926 /// instance white short castling in a non-Chess960 game is encoded as e1h1.
927
928 void Position::do_castle_move(Move m) {
929
930   assert(move_is_ok(m));
931   assert(move_is_castle(m));
932
933   Color us = side_to_move();
934   Color them = opposite_color(us);
935
936   // Reset capture field
937   st->capture = NO_PIECE_TYPE;
938
939   // Find source squares for king and rook
940   Square kfrom = move_from(m);
941   Square rfrom = move_to(m);  // HACK: See comment at beginning of function
942   Square kto, rto;
943
944   assert(piece_on(kfrom) == piece_of_color_and_type(us, KING));
945   assert(piece_on(rfrom) == piece_of_color_and_type(us, ROOK));
946
947   // Find destination squares for king and rook
948   if (rfrom > kfrom) // O-O
949   {
950       kto = relative_square(us, SQ_G1);
951       rto = relative_square(us, SQ_F1);
952   } else { // O-O-O
953       kto = relative_square(us, SQ_C1);
954       rto = relative_square(us, SQ_D1);
955   }
956
957   // Remove pieces from source squares:
958   clear_bit(&(byColorBB[us]), kfrom);
959   clear_bit(&(byTypeBB[KING]), kfrom);
960   clear_bit(&(byTypeBB[0]), kfrom); // HACK: byTypeBB[0] == occupied squares
961   clear_bit(&(byColorBB[us]), rfrom);
962   clear_bit(&(byTypeBB[ROOK]), rfrom);
963   clear_bit(&(byTypeBB[0]), rfrom); // HACK: byTypeBB[0] == occupied squares
964
965   // Put pieces on destination squares:
966   set_bit(&(byColorBB[us]), kto);
967   set_bit(&(byTypeBB[KING]), kto);
968   set_bit(&(byTypeBB[0]), kto); // HACK: byTypeBB[0] == occupied squares
969   set_bit(&(byColorBB[us]), rto);
970   set_bit(&(byTypeBB[ROOK]), rto);
971   set_bit(&(byTypeBB[0]), rto); // HACK: byTypeBB[0] == occupied squares
972   
973   // Update board array
974   Piece king = piece_of_color_and_type(us, KING);
975   Piece rook = piece_of_color_and_type(us, ROOK);
976   board[kfrom] = board[rfrom] = EMPTY;
977   board[kto] = king;
978   board[rto] = rook;
979
980   // Update piece lists
981   pieceList[us][KING][index[kfrom]] = kto;
982   pieceList[us][ROOK][index[rfrom]] = rto;
983   int tmp = index[rfrom]; // In Chess960 could be rto == kfrom
984   index[kto] = index[kfrom];
985   index[rto] = tmp;
986
987   // Update incremental scores
988   st->value += pst_delta(king, kfrom, kto);
989   st->value += pst_delta(rook, rfrom, rto);
990
991   // Update hash key
992   st->key ^= zobrist[us][KING][kfrom] ^ zobrist[us][KING][kto];
993   st->key ^= zobrist[us][ROOK][rfrom] ^ zobrist[us][ROOK][rto];
994
995   // Clear en passant square
996   if (st->epSquare != SQ_NONE)
997   {
998       st->key ^= zobEp[st->epSquare];
999       st->epSquare = SQ_NONE;
1000   }
1001
1002   // Update castling rights
1003   st->key ^= zobCastle[st->castleRights];
1004   st->castleRights &= castleRightsMask[kfrom];
1005   st->key ^= zobCastle[st->castleRights];
1006
1007   // Reset rule 50 counter
1008   st->rule50 = 0;
1009
1010   // Update checkers BB
1011   st->checkersBB = attackers_to(king_square(them)) & pieces_of_color(us);
1012
1013   // Finish
1014   sideToMove = opposite_color(sideToMove);
1015   st->value += (sideToMove == WHITE ?  TempoValue : -TempoValue);
1016
1017   assert(is_ok());
1018 }
1019
1020
1021 /// Position::undo_move() unmakes a move. When it returns, the position should
1022 /// be restored to exactly the same state as before the move was made.
1023
1024 void Position::undo_move(Move m) {
1025
1026   assert(is_ok());
1027   assert(move_is_ok(m));
1028
1029   gamePly--;
1030   sideToMove = opposite_color(sideToMove);
1031
1032   if (move_is_castle(m))
1033   {
1034       undo_castle_move(m);
1035       return;
1036   }
1037
1038   Color us = side_to_move();
1039   Color them = opposite_color(us);
1040   Square from = move_from(m);
1041   Square to = move_to(m);
1042   bool ep = move_is_ep(m);
1043   bool pm = move_is_promotion(m);
1044
1045   PieceType pt = type_of_piece_on(to);
1046
1047   assert(square_is_empty(from));
1048   assert(color_of_piece_on(to) == us);
1049   assert(!pm || relative_rank(us, to) == RANK_8);
1050   assert(!ep || to == st->previous->epSquare);
1051   assert(!ep || relative_rank(us, to) == RANK_6);
1052   assert(!ep || piece_on(to) == piece_of_color_and_type(us, PAWN));
1053
1054   if (pm) // promotion ?
1055   {
1056       PieceType promotion = move_promotion_piece(m);
1057       pt = PAWN;
1058
1059       assert(promotion >= KNIGHT && promotion <= QUEEN);
1060       assert(piece_on(to) == piece_of_color_and_type(us, promotion));
1061
1062       // Replace promoted piece with a pawn
1063       clear_bit(&(byTypeBB[promotion]), to);
1064       set_bit(&(byTypeBB[PAWN]), to);
1065
1066       // Update piece counts
1067       pieceCount[us][promotion]--;
1068       pieceCount[us][PAWN]++;
1069
1070       // Update piece list replacing promotion piece with a pawn
1071       Square lastPromotionSquare = pieceList[us][promotion][pieceCount[us][promotion]];
1072       index[lastPromotionSquare] = index[to];
1073       pieceList[us][promotion][index[lastPromotionSquare]] = lastPromotionSquare;
1074       pieceList[us][promotion][pieceCount[us][promotion]] = SQ_NONE;
1075       index[to] = pieceCount[us][PAWN] - 1;
1076       pieceList[us][PAWN][index[to]] = to;
1077   }
1078
1079
1080   // Put the piece back at the source square
1081   Bitboard move_bb = make_move_bb(to, from);
1082   do_move_bb(&(byColorBB[us]), move_bb);
1083   do_move_bb(&(byTypeBB[pt]), move_bb);
1084   do_move_bb(&(byTypeBB[0]), move_bb); // HACK: byTypeBB[0] == occupied squares
1085
1086   board[from] = piece_of_color_and_type(us, pt);
1087   board[to] = EMPTY;
1088
1089   // Update piece list
1090   index[from] = index[to];
1091   pieceList[us][pt][index[from]] = from;
1092
1093   if (st->capture)
1094   {
1095       Square capsq = to;
1096
1097       if (ep)
1098           capsq = (us == WHITE)? (to - DELTA_N) : (to - DELTA_S);
1099
1100       assert(st->capture != KING);
1101       assert(!ep || square_is_empty(capsq));
1102
1103       // Restore the captured piece
1104       set_bit(&(byColorBB[them]), capsq);
1105       set_bit(&(byTypeBB[st->capture]), capsq);
1106       set_bit(&(byTypeBB[0]), capsq);
1107
1108       board[capsq] = piece_of_color_and_type(them, st->capture);
1109
1110       // Update piece count
1111       pieceCount[them][st->capture]++;
1112
1113       // Update piece list, add a new captured piece in capsq square
1114       index[capsq] = pieceCount[them][st->capture] - 1;
1115       pieceList[them][st->capture][index[capsq]] = capsq;
1116   }
1117
1118   // Finally point our state pointer back to the previous state
1119   st = st->previous;
1120
1121   assert(is_ok());
1122 }
1123
1124
1125 /// Position::undo_castle_move() is a private method used to unmake a castling
1126 /// move. It is called from the main Position::undo_move function. Note that
1127 /// castling moves are encoded as "king captures friendly rook" moves, for
1128 /// instance white short castling in a non-Chess960 game is encoded as e1h1.
1129
1130 void Position::undo_castle_move(Move m) {
1131
1132   assert(move_is_ok(m));
1133   assert(move_is_castle(m));
1134
1135   // When we have arrived here, some work has already been done by
1136   // Position::undo_move.  In particular, the side to move has been switched,
1137   // so the code below is correct.
1138   Color us = side_to_move();
1139
1140   // Find source squares for king and rook
1141   Square kfrom = move_from(m);
1142   Square rfrom = move_to(m);  // HACK: See comment at beginning of function
1143   Square kto, rto;
1144
1145   // Find destination squares for king and rook
1146   if (rfrom > kfrom) // O-O
1147   {
1148       kto = relative_square(us, SQ_G1);
1149       rto = relative_square(us, SQ_F1);
1150   } else { // O-O-O
1151       kto = relative_square(us, SQ_C1);
1152       rto = relative_square(us, SQ_D1);
1153   }
1154
1155   assert(piece_on(kto) == piece_of_color_and_type(us, KING));
1156   assert(piece_on(rto) == piece_of_color_and_type(us, ROOK));
1157   
1158   // Remove pieces from destination squares:
1159   clear_bit(&(byColorBB[us]), kto);
1160   clear_bit(&(byTypeBB[KING]), kto);
1161   clear_bit(&(byTypeBB[0]), kto); // HACK: byTypeBB[0] == occupied squares
1162   clear_bit(&(byColorBB[us]), rto);
1163   clear_bit(&(byTypeBB[ROOK]), rto);
1164   clear_bit(&(byTypeBB[0]), rto); // HACK: byTypeBB[0] == occupied squares
1165  
1166   // Put pieces on source squares:
1167   set_bit(&(byColorBB[us]), kfrom);
1168   set_bit(&(byTypeBB[KING]), kfrom);
1169   set_bit(&(byTypeBB[0]), kfrom); // HACK: byTypeBB[0] == occupied squares
1170   set_bit(&(byColorBB[us]), rfrom);
1171   set_bit(&(byTypeBB[ROOK]), rfrom);
1172   set_bit(&(byTypeBB[0]), rfrom); // HACK: byTypeBB[0] == occupied squares
1173
1174   // Update board
1175   board[rto] = board[kto] = EMPTY;
1176   board[rfrom] = piece_of_color_and_type(us, ROOK);
1177   board[kfrom] = piece_of_color_and_type(us, KING);
1178
1179   // Update piece lists
1180   pieceList[us][KING][index[kto]] = kfrom;
1181   pieceList[us][ROOK][index[rto]] = rfrom;
1182   int tmp = index[rto];  // In Chess960 could be rto == kfrom
1183   index[kfrom] = index[kto];
1184   index[rfrom] = tmp;
1185
1186   // Finally point our state pointer back to the previous state
1187   st = st->previous;
1188
1189   assert(is_ok());
1190 }
1191
1192
1193 /// Position::do_null_move makes() a "null move": It switches the side to move
1194 /// and updates the hash key without executing any move on the board.
1195
1196 void Position::do_null_move(StateInfo& backupSt) {
1197
1198   assert(is_ok());
1199   assert(!is_check());
1200
1201   // Back up the information necessary to undo the null move to the supplied
1202   // StateInfo object.
1203   // Note that differently from normal case here backupSt is actually used as
1204   // a backup storage not as a new state to be used.
1205   backupSt.key      = st->key;
1206   backupSt.epSquare = st->epSquare;
1207   backupSt.value    = st->value;
1208   backupSt.previous = st->previous;
1209   backupSt.pliesFromNull = st->pliesFromNull;
1210   st->previous = &backupSt;
1211
1212   // Save the current key to the history[] array, in order to be able to
1213   // detect repetition draws.
1214   history[gamePly] = st->key;
1215
1216   // Update the necessary information
1217   if (st->epSquare != SQ_NONE)
1218       st->key ^= zobEp[st->epSquare];
1219
1220   st->key ^= zobSideToMove;
1221   TT.prefetch(st->key);
1222
1223   sideToMove = opposite_color(sideToMove);
1224   st->epSquare = SQ_NONE;
1225   st->rule50++;
1226   st->pliesFromNull = 0;
1227   st->value += (sideToMove == WHITE) ?  TempoValue : -TempoValue;
1228   gamePly++;
1229 }
1230
1231
1232 /// Position::undo_null_move() unmakes a "null move".
1233
1234 void Position::undo_null_move() {
1235
1236   assert(is_ok());
1237   assert(!is_check());
1238
1239   // Restore information from the our backup StateInfo object
1240   StateInfo* backupSt = st->previous;
1241   st->key      = backupSt->key;
1242   st->epSquare = backupSt->epSquare;
1243   st->value    = backupSt->value;
1244   st->previous = backupSt->previous;
1245   st->pliesFromNull = backupSt->pliesFromNull;
1246
1247   // Update the necessary information
1248   sideToMove = opposite_color(sideToMove);
1249   st->rule50--;
1250   gamePly--;
1251 }
1252
1253
1254 /// Position::see() is a static exchange evaluator: It tries to estimate the
1255 /// material gain or loss resulting from a move. There are three versions of
1256 /// this function: One which takes a destination square as input, one takes a
1257 /// move, and one which takes a 'from' and a 'to' square. The function does
1258 /// not yet understand promotions captures.
1259
1260 int Position::see(Square to) const {
1261
1262   assert(square_is_ok(to));
1263   return see(SQ_NONE, to);
1264 }
1265
1266 int Position::see(Move m) const {
1267
1268   assert(move_is_ok(m));
1269   return see(move_from(m), move_to(m));
1270 }
1271
1272 int Position::see_sign(Move m) const {
1273
1274   assert(move_is_ok(m));
1275
1276   Square from = move_from(m);
1277   Square to = move_to(m);
1278
1279   // Early return if SEE cannot be negative because capturing piece value
1280   // is not bigger then captured one.
1281   if (   midgame_value_of_piece_on(from) <= midgame_value_of_piece_on(to)
1282       && type_of_piece_on(from) != KING)
1283          return 1;
1284
1285   return see(from, to);
1286 }
1287
1288 int Position::see(Square from, Square to) const {
1289
1290   // Material values
1291   static const int seeValues[18] = {
1292     0, PawnValueMidgame, KnightValueMidgame, BishopValueMidgame,
1293        RookValueMidgame, QueenValueMidgame, QueenValueMidgame*10, 0,
1294     0, PawnValueMidgame, KnightValueMidgame, BishopValueMidgame,
1295        RookValueMidgame, QueenValueMidgame, QueenValueMidgame*10, 0,
1296     0, 0
1297   };
1298
1299   Bitboard attackers, stmAttackers, b;
1300
1301   assert(square_is_ok(from) || from == SQ_NONE);
1302   assert(square_is_ok(to));
1303
1304   // Initialize colors
1305   Color us = (from != SQ_NONE ? color_of_piece_on(from) : opposite_color(color_of_piece_on(to)));
1306   Color them = opposite_color(us);
1307
1308   // Initialize pieces
1309   Piece piece = piece_on(from);
1310   Piece capture = piece_on(to);
1311   Bitboard occ = occupied_squares();
1312
1313   // King cannot be recaptured
1314   if (type_of_piece(piece) == KING)
1315       return seeValues[capture];
1316
1317   // Handle en passant moves
1318   if (st->epSquare == to && type_of_piece_on(from) == PAWN)
1319   {
1320       assert(capture == EMPTY);
1321
1322       Square capQq = (side_to_move() == WHITE)? (to - DELTA_N) : (to - DELTA_S);
1323       capture = piece_on(capQq);
1324       assert(type_of_piece_on(capQq) == PAWN);
1325
1326       // Remove the captured pawn
1327       clear_bit(&occ, capQq);
1328   }
1329
1330   while (true)
1331   {
1332       // Find all attackers to the destination square, with the moving piece
1333       // removed, but possibly an X-ray attacker added behind it.
1334       clear_bit(&occ, from);
1335       attackers =  (rook_attacks_bb(to, occ)      & pieces(ROOK, QUEEN))
1336                  | (bishop_attacks_bb(to, occ)    & pieces(BISHOP, QUEEN))
1337                  | (attacks_from<KNIGHT>(to)      & pieces(KNIGHT))
1338                  | (attacks_from<KING>(to)        & pieces(KING))
1339                  | (attacks_from<PAWN>(to, WHITE) & pieces(PAWN, BLACK))
1340                  | (attacks_from<PAWN>(to, BLACK) & pieces(PAWN, WHITE));
1341
1342       if (from != SQ_NONE)
1343           break;
1344
1345       // If we don't have any attacker we are finished
1346       if ((attackers & pieces_of_color(us)) == EmptyBoardBB)
1347           return 0;
1348
1349       // Locate the least valuable attacker to the destination square
1350       // and use it to initialize from square.
1351       stmAttackers = attackers & pieces_of_color(us);
1352       PieceType pt;
1353       for (pt = PAWN; !(stmAttackers & pieces(pt)); pt++)
1354           assert(pt < KING);
1355
1356       from = first_1(stmAttackers & pieces(pt));
1357       piece = piece_on(from);
1358   }
1359
1360   // If the opponent has no attackers we are finished
1361   stmAttackers = attackers & pieces_of_color(them);
1362   if (!stmAttackers)
1363       return seeValues[capture];
1364
1365   attackers &= occ; // Remove the moving piece
1366
1367   // The destination square is defended, which makes things rather more
1368   // difficult to compute. We proceed by building up a "swap list" containing
1369   // the material gain or loss at each stop in a sequence of captures to the
1370   // destination square, where the sides alternately capture, and always
1371   // capture with the least valuable piece. After each capture, we look for
1372   // new X-ray attacks from behind the capturing piece.
1373   int lastCapturingPieceValue = seeValues[piece];
1374   int swapList[32], n = 1;
1375   Color c = them;
1376   PieceType pt;
1377
1378   swapList[0] = seeValues[capture];
1379
1380   do {
1381       // Locate the least valuable attacker for the side to move. The loop
1382       // below looks like it is potentially infinite, but it isn't. We know
1383       // that the side to move still has at least one attacker left.
1384       for (pt = PAWN; !(stmAttackers & pieces(pt)); pt++)
1385           assert(pt < KING);
1386
1387       // Remove the attacker we just found from the 'attackers' bitboard,
1388       // and scan for new X-ray attacks behind the attacker.
1389       b = stmAttackers & pieces(pt);
1390       occ ^= (b & (~b + 1));
1391       attackers |=  (rook_attacks_bb(to, occ) &  pieces(ROOK, QUEEN))
1392                   | (bishop_attacks_bb(to, occ) & pieces(BISHOP, QUEEN));
1393
1394       attackers &= occ;
1395
1396       // Add the new entry to the swap list
1397       assert(n < 32);
1398       swapList[n] = -swapList[n - 1] + lastCapturingPieceValue;
1399       n++;
1400
1401       // Remember the value of the capturing piece, and change the side to move
1402       // before beginning the next iteration
1403       lastCapturingPieceValue = seeValues[pt];
1404       c = opposite_color(c);
1405       stmAttackers = attackers & pieces_of_color(c);
1406
1407       // Stop after a king capture
1408       if (pt == KING && stmAttackers)
1409       {
1410           assert(n < 32);
1411           swapList[n++] = QueenValueMidgame*10;
1412           break;
1413       }
1414   } while (stmAttackers);
1415
1416   // Having built the swap list, we negamax through it to find the best
1417   // achievable score from the point of view of the side to move
1418   while (--n)
1419       swapList[n-1] = Min(-swapList[n], swapList[n-1]);
1420
1421   return swapList[0];
1422 }
1423
1424
1425 /// Position::saveState() copies the content of the current state
1426 /// inside startState and makes st point to it. This is needed
1427 /// when the st pointee could become stale, as example because
1428 /// the caller is about to going out of scope.
1429
1430 void Position::saveState() {
1431
1432   startState = *st;
1433   st = &startState;
1434   st->previous = NULL; // as a safe guard
1435 }
1436
1437
1438 /// Position::clear() erases the position object to a pristine state, with an
1439 /// empty board, white to move, and no castling rights.
1440
1441 void Position::clear() {
1442
1443   st = &startState;
1444   memset(st, 0, sizeof(StateInfo));
1445   st->epSquare = SQ_NONE;
1446
1447   memset(byColorBB,  0, sizeof(Bitboard) * 2);
1448   memset(byTypeBB,   0, sizeof(Bitboard) * 8);
1449   memset(pieceCount, 0, sizeof(int) * 2 * 8);
1450   memset(index,      0, sizeof(int) * 64);
1451
1452   for (int i = 0; i < 64; i++)
1453       board[i] = EMPTY;
1454
1455   for (int i = 0; i < 8; i++)
1456       for (int j = 0; j < 16; j++)
1457           pieceList[0][i][j] = pieceList[1][i][j] = SQ_NONE;
1458
1459   sideToMove = WHITE;
1460   gamePly = 0;
1461   initialKFile = FILE_E;
1462   initialKRFile = FILE_H;
1463   initialQRFile = FILE_A;
1464 }
1465
1466
1467 /// Position::reset_game_ply() simply sets gamePly to 0. It is used from the
1468 /// UCI interface code, whenever a non-reversible move is made in a
1469 /// 'position fen <fen> moves m1 m2 ...' command.  This makes it possible
1470 /// for the program to handle games of arbitrary length, as long as the GUI
1471 /// handles draws by the 50 move rule correctly.
1472
1473 void Position::reset_game_ply() {
1474
1475   gamePly = 0;
1476 }
1477
1478
1479 /// Position::put_piece() puts a piece on the given square of the board,
1480 /// updating the board array, bitboards, and piece counts.
1481
1482 void Position::put_piece(Piece p, Square s) {
1483
1484   Color c = color_of_piece(p);
1485   PieceType pt = type_of_piece(p);
1486
1487   board[s] = p;
1488   index[s] = pieceCount[c][pt];
1489   pieceList[c][pt][index[s]] = s;
1490
1491   set_bit(&(byTypeBB[pt]), s);
1492   set_bit(&(byColorBB[c]), s);
1493   set_bit(&byTypeBB[0], s); // HACK: byTypeBB[0] contains all occupied squares.
1494
1495   pieceCount[c][pt]++;
1496 }
1497
1498
1499 /// Position::allow_oo() gives the given side the right to castle kingside.
1500 /// Used when setting castling rights during parsing of FEN strings.
1501
1502 void Position::allow_oo(Color c) {
1503
1504   st->castleRights |= (1 + int(c));
1505 }
1506
1507
1508 /// Position::allow_ooo() gives the given side the right to castle queenside.
1509 /// Used when setting castling rights during parsing of FEN strings.
1510
1511 void Position::allow_ooo(Color c) {
1512
1513   st->castleRights |= (4 + 4*int(c));
1514 }
1515
1516
1517 /// Position::compute_key() computes the hash key of the position. The hash
1518 /// key is usually updated incrementally as moves are made and unmade, the
1519 /// compute_key() function is only used when a new position is set up, and
1520 /// to verify the correctness of the hash key when running in debug mode.
1521
1522 Key Position::compute_key() const {
1523
1524   Key result = Key(0ULL);
1525
1526   for (Square s = SQ_A1; s <= SQ_H8; s++)
1527       if (square_is_occupied(s))
1528           result ^= zobrist[color_of_piece_on(s)][type_of_piece_on(s)][s];
1529
1530   if (ep_square() != SQ_NONE)
1531       result ^= zobEp[ep_square()];
1532
1533   result ^= zobCastle[st->castleRights];
1534   if (side_to_move() == BLACK)
1535       result ^= zobSideToMove;
1536
1537   return result;
1538 }
1539
1540
1541 /// Position::compute_pawn_key() computes the hash key of the position. The
1542 /// hash key is usually updated incrementally as moves are made and unmade,
1543 /// the compute_pawn_key() function is only used when a new position is set
1544 /// up, and to verify the correctness of the pawn hash key when running in
1545 /// debug mode.
1546
1547 Key Position::compute_pawn_key() const {
1548
1549   Key result = Key(0ULL);
1550   Bitboard b;
1551   Square s;
1552
1553   for (Color c = WHITE; c <= BLACK; c++)
1554   {
1555       b = pieces(PAWN, c);
1556       while(b)
1557       {
1558           s = pop_1st_bit(&b);
1559           result ^= zobrist[c][PAWN][s];
1560       }
1561   }
1562   return result;
1563 }
1564
1565
1566 /// Position::compute_material_key() computes the hash key of the position.
1567 /// The hash key is usually updated incrementally as moves are made and unmade,
1568 /// the compute_material_key() function is only used when a new position is set
1569 /// up, and to verify the correctness of the material hash key when running in
1570 /// debug mode.
1571
1572 Key Position::compute_material_key() const {
1573
1574   Key result = Key(0ULL);
1575   for (Color c = WHITE; c <= BLACK; c++)
1576       for (PieceType pt = PAWN; pt <= QUEEN; pt++)
1577       {
1578           int count = piece_count(c, pt);
1579           for (int i = 0; i <= count; i++)
1580               result ^= zobMaterial[c][pt][i];
1581       }
1582   return result;
1583 }
1584
1585
1586 /// Position::compute_value() compute the incremental scores for the middle
1587 /// game and the endgame. These functions are used to initialize the incremental
1588 /// scores when a new position is set up, and to verify that the scores are correctly
1589 /// updated by do_move and undo_move when the program is running in debug mode.
1590 Score Position::compute_value() const {
1591
1592   Score result = make_score(0, 0);
1593   Bitboard b;
1594   Square s;
1595
1596   for (Color c = WHITE; c <= BLACK; c++)
1597       for (PieceType pt = PAWN; pt <= KING; pt++)
1598       {
1599           b = pieces(pt, c);
1600           while(b)
1601           {
1602               s = pop_1st_bit(&b);
1603               assert(piece_on(s) == piece_of_color_and_type(c, pt));
1604               result += pst(c, pt, s);
1605           }
1606       }
1607
1608   result += (side_to_move() == WHITE ? TempoValue / 2 : -TempoValue / 2);
1609   return result;
1610 }
1611
1612
1613 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1614 /// game material score for the given side. Material scores are updated
1615 /// incrementally during the search, this function is only used while
1616 /// initializing a new Position object.
1617
1618 Value Position::compute_non_pawn_material(Color c) const {
1619
1620   Value result = Value(0);
1621
1622   for (PieceType pt = KNIGHT; pt <= QUEEN; pt++)
1623   {
1624       Bitboard b = pieces(pt, c);
1625       while (b)
1626       {
1627           assert(piece_on(first_1(b)) == piece_of_color_and_type(c, pt));
1628           pop_1st_bit(&b);
1629           result += piece_value_midgame(pt);
1630       }
1631   }
1632   return result;
1633 }
1634
1635
1636 /// Position::is_draw() tests whether the position is drawn by material,
1637 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1638 /// must be done by the search.
1639
1640 bool Position::is_draw() const {
1641
1642   // Draw by material?
1643   if (   !pieces(PAWN)
1644       && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMidgame))
1645       return true;
1646
1647   // Draw by the 50 moves rule?
1648   if (st->rule50 > 100 || (st->rule50 == 100 && !is_check()))
1649       return true;
1650
1651   // Draw by repetition?
1652   for (int i = 2; i < Min(Min(gamePly, st->rule50), st->pliesFromNull); i += 2)
1653       if (history[gamePly - i] == st->key)
1654           return true;
1655
1656   return false;
1657 }
1658
1659
1660 /// Position::is_mate() returns true or false depending on whether the
1661 /// side to move is checkmated.
1662
1663 bool Position::is_mate() const {
1664
1665   MoveStack moves[256];
1666   return is_check() && (generate_moves(*this, moves, false) == moves);
1667 }
1668
1669
1670 /// Position::has_mate_threat() tests whether a given color has a mate in one
1671 /// from the current position.
1672
1673 bool Position::has_mate_threat(Color c) {
1674
1675   StateInfo st1, st2;
1676   Color stm = side_to_move();
1677
1678   if (is_check())
1679       return false;
1680
1681   // If the input color is not equal to the side to move, do a null move
1682   if (c != stm)
1683       do_null_move(st1);
1684
1685   MoveStack mlist[120];
1686   bool result = false;
1687   Bitboard pinned = pinned_pieces(sideToMove);
1688
1689   // Generate pseudo-legal non-capture and capture check moves
1690   MoveStack* last = generate_non_capture_checks(*this, mlist);
1691   last = generate_captures(*this, last);
1692
1693   // Loop through the moves, and see if one of them is mate
1694   for (MoveStack* cur = mlist; cur != last; cur++)
1695   {
1696       Move move = cur->move;
1697       if (!pl_move_is_legal(move, pinned))
1698           continue;
1699
1700       do_move(move, st2);
1701       if (is_mate())
1702           result = true;
1703
1704       undo_move(move);
1705   }
1706
1707   // Undo null move, if necessary
1708   if (c != stm)
1709       undo_null_move();
1710
1711   return result;
1712 }
1713
1714
1715 /// Position::init_zobrist() is a static member function which initializes the
1716 /// various arrays used to compute hash keys.
1717
1718 void Position::init_zobrist() {
1719
1720   for (int i = 0; i < 2; i++)
1721       for (int j = 0; j < 8; j++)
1722           for (int k = 0; k < 64; k++)
1723               zobrist[i][j][k] = Key(genrand_int64());
1724
1725   for (int i = 0; i < 64; i++)
1726       zobEp[i] = Key(genrand_int64());
1727
1728   for (int i = 0; i < 16; i++)
1729       zobCastle[i] = genrand_int64();
1730
1731   zobSideToMove = genrand_int64();
1732
1733   for (int i = 0; i < 2; i++)
1734       for (int j = 0; j < 8; j++)
1735           for (int k = 0; k < 16; k++)
1736               zobMaterial[i][j][k] = (k > 0)? Key(genrand_int64()) : Key(0LL);
1737
1738   for (int i = 0; i < 16; i++)
1739       zobMaterial[0][KING][i] = zobMaterial[1][KING][i] = Key(0ULL);
1740
1741   zobExclusion = genrand_int64();
1742 }
1743
1744
1745 /// Position::init_piece_square_tables() initializes the piece square tables.
1746 /// This is a two-step operation:  First, the white halves of the tables are
1747 /// copied from the MgPST[][] and EgPST[][] arrays, with a small random number
1748 /// added to each entry if the "Randomness" UCI parameter is non-zero.
1749 /// Second, the black halves of the tables are initialized by mirroring
1750 /// and changing the sign of the corresponding white scores.
1751
1752 void Position::init_piece_square_tables() {
1753
1754   int r = get_option_value_int("Randomness"), i;
1755   for (Square s = SQ_A1; s <= SQ_H8; s++)
1756       for (Piece p = WP; p <= WK; p++)
1757       {
1758           i = (r == 0)? 0 : (genrand_int32() % (r*2) - r);
1759           PieceSquareTable[p][s] = make_score(MgPST[p][s] + i, EgPST[p][s] + i);
1760       }
1761
1762   for (Square s = SQ_A1; s <= SQ_H8; s++)
1763       for (Piece p = BP; p <= BK; p++)
1764           PieceSquareTable[p][s] = -PieceSquareTable[p-8][flip_square(s)];
1765 }
1766
1767
1768 /// Position::flipped_copy() makes a copy of the input position, but with
1769 /// the white and black sides reversed. This is only useful for debugging,
1770 /// especially for finding evaluation symmetry bugs.
1771
1772 void Position::flipped_copy(const Position& pos) {
1773
1774   assert(pos.is_ok());
1775
1776   clear();
1777
1778   // Board
1779   for (Square s = SQ_A1; s <= SQ_H8; s++)
1780       if (!pos.square_is_empty(s))
1781           put_piece(Piece(int(pos.piece_on(s)) ^ 8), flip_square(s));
1782
1783   // Side to move
1784   sideToMove = opposite_color(pos.side_to_move());
1785
1786   // Castling rights
1787   if (pos.can_castle_kingside(WHITE))  allow_oo(BLACK);
1788   if (pos.can_castle_queenside(WHITE)) allow_ooo(BLACK);
1789   if (pos.can_castle_kingside(BLACK))  allow_oo(WHITE);
1790   if (pos.can_castle_queenside(BLACK)) allow_ooo(WHITE);
1791
1792   initialKFile  = pos.initialKFile;
1793   initialKRFile = pos.initialKRFile;
1794   initialQRFile = pos.initialQRFile;
1795
1796   for (Square sq = SQ_A1; sq <= SQ_H8; sq++)
1797       castleRightsMask[sq] = ALL_CASTLES;
1798
1799   castleRightsMask[make_square(initialKFile,  RANK_1)] ^= (WHITE_OO | WHITE_OOO);
1800   castleRightsMask[make_square(initialKFile,  RANK_8)] ^= (BLACK_OO | BLACK_OOO);
1801   castleRightsMask[make_square(initialKRFile, RANK_1)] ^=  WHITE_OO;
1802   castleRightsMask[make_square(initialKRFile, RANK_8)] ^=  BLACK_OO;
1803   castleRightsMask[make_square(initialQRFile, RANK_1)] ^=  WHITE_OOO;
1804   castleRightsMask[make_square(initialQRFile, RANK_8)] ^=  BLACK_OOO;
1805
1806   // En passant square
1807   if (pos.st->epSquare != SQ_NONE)
1808       st->epSquare = flip_square(pos.st->epSquare);
1809
1810   // Checkers
1811   find_checkers();
1812
1813   // Hash keys
1814   st->key = compute_key();
1815   st->pawnKey = compute_pawn_key();
1816   st->materialKey = compute_material_key();
1817
1818   // Incremental scores
1819   st->value = compute_value();
1820
1821   // Material
1822   st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
1823   st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
1824
1825   assert(is_ok());
1826 }
1827
1828
1829 /// Position::is_ok() performs some consitency checks for the position object.
1830 /// This is meant to be helpful when debugging.
1831
1832 bool Position::is_ok(int* failedStep) const {
1833
1834   // What features of the position should be verified?
1835   static const bool debugBitboards = false;
1836   static const bool debugKingCount = false;
1837   static const bool debugKingCapture = false;
1838   static const bool debugCheckerCount = false;
1839   static const bool debugKey = false;
1840   static const bool debugMaterialKey = false;
1841   static const bool debugPawnKey = false;
1842   static const bool debugIncrementalEval = false;
1843   static const bool debugNonPawnMaterial = false;
1844   static const bool debugPieceCounts = false;
1845   static const bool debugPieceList = false;
1846
1847   if (failedStep) *failedStep = 1;
1848
1849   // Side to move OK?
1850   if (!color_is_ok(side_to_move()))
1851       return false;
1852
1853   // Are the king squares in the position correct?
1854   if (failedStep) (*failedStep)++;
1855   if (piece_on(king_square(WHITE)) != WK)
1856       return false;
1857
1858   if (failedStep) (*failedStep)++;
1859   if (piece_on(king_square(BLACK)) != BK)
1860       return false;
1861
1862   // Castle files OK?
1863   if (failedStep) (*failedStep)++;
1864   if (!file_is_ok(initialKRFile))
1865       return false;
1866
1867   if (!file_is_ok(initialQRFile))
1868       return false;
1869
1870   // Do both sides have exactly one king?
1871   if (failedStep) (*failedStep)++;
1872   if (debugKingCount)
1873   {
1874       int kingCount[2] = {0, 0};
1875       for (Square s = SQ_A1; s <= SQ_H8; s++)
1876           if (type_of_piece_on(s) == KING)
1877               kingCount[color_of_piece_on(s)]++;
1878
1879       if (kingCount[0] != 1 || kingCount[1] != 1)
1880           return false;
1881   }
1882
1883   // Can the side to move capture the opponent's king?
1884   if (failedStep) (*failedStep)++;
1885   if (debugKingCapture)
1886   {
1887       Color us = side_to_move();
1888       Color them = opposite_color(us);
1889       Square ksq = king_square(them);
1890       if (attackers_to(ksq) & pieces_of_color(us))
1891           return false;
1892   }
1893
1894   // Is there more than 2 checkers?
1895   if (failedStep) (*failedStep)++;
1896   if (debugCheckerCount && count_1s(st->checkersBB) > 2)
1897       return false;
1898
1899   // Bitboards OK?
1900   if (failedStep) (*failedStep)++;
1901   if (debugBitboards)
1902   {
1903       // The intersection of the white and black pieces must be empty
1904       if ((pieces_of_color(WHITE) & pieces_of_color(BLACK)) != EmptyBoardBB)
1905           return false;
1906
1907       // The union of the white and black pieces must be equal to all
1908       // occupied squares
1909       if ((pieces_of_color(WHITE) | pieces_of_color(BLACK)) != occupied_squares())
1910           return false;
1911
1912       // Separate piece type bitboards must have empty intersections
1913       for (PieceType p1 = PAWN; p1 <= KING; p1++)
1914           for (PieceType p2 = PAWN; p2 <= KING; p2++)
1915               if (p1 != p2 && (pieces(p1) & pieces(p2)))
1916                   return false;
1917   }
1918
1919   // En passant square OK?
1920   if (failedStep) (*failedStep)++;
1921   if (ep_square() != SQ_NONE)
1922   {
1923       // The en passant square must be on rank 6, from the point of view of the
1924       // side to move.
1925       if (relative_rank(side_to_move(), ep_square()) != RANK_6)
1926           return false;
1927   }
1928
1929   // Hash key OK?
1930   if (failedStep) (*failedStep)++;
1931   if (debugKey && st->key != compute_key())
1932       return false;
1933
1934   // Pawn hash key OK?
1935   if (failedStep) (*failedStep)++;
1936   if (debugPawnKey && st->pawnKey != compute_pawn_key())
1937       return false;
1938
1939   // Material hash key OK?
1940   if (failedStep) (*failedStep)++;
1941   if (debugMaterialKey && st->materialKey != compute_material_key())
1942       return false;
1943
1944   // Incremental eval OK?
1945   if (failedStep) (*failedStep)++;
1946   if (debugIncrementalEval && st->value != compute_value())
1947       return false;
1948
1949   // Non-pawn material OK?
1950   if (failedStep) (*failedStep)++;
1951   if (debugNonPawnMaterial)
1952   {
1953       if (st->npMaterial[WHITE] != compute_non_pawn_material(WHITE))
1954           return false;
1955
1956       if (st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1957           return false;
1958   }
1959
1960   // Piece counts OK?
1961   if (failedStep) (*failedStep)++;
1962   if (debugPieceCounts)
1963       for (Color c = WHITE; c <= BLACK; c++)
1964           for (PieceType pt = PAWN; pt <= KING; pt++)
1965               if (pieceCount[c][pt] != count_1s(pieces(pt, c)))
1966                   return false;
1967
1968   if (failedStep) (*failedStep)++;
1969   if (debugPieceList)
1970   {
1971       for(Color c = WHITE; c <= BLACK; c++)
1972           for(PieceType pt = PAWN; pt <= KING; pt++)
1973               for(int i = 0; i < pieceCount[c][pt]; i++)
1974               {
1975                   if (piece_on(piece_list(c, pt, i)) != piece_of_color_and_type(c, pt))
1976                       return false;
1977
1978                   if (index[piece_list(c, pt, i)] != i)
1979                       return false;
1980               }
1981   }
1982   if (failedStep) *failedStep = 0;
1983   return true;
1984 }