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