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