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