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