Merge pull request #1 from Panthee/master
[stockfish] / src / position.cpp
1 /*
2   Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3   Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
4   Copyright (C) 2008-2010 Marco Costalba, Joona Kiiski, Tord Romstad
5
6   Stockfish is free software: you can redistribute it and/or modify
7   it under the terms of the GNU General Public License as published by
8   the Free Software Foundation, either version 3 of the License, or
9   (at your option) any later version.
10
11   Stockfish is distributed in the hope that it will be useful,
12   but WITHOUT ANY WARRANTY; without even the implied warranty of
13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   GNU General Public License for more details.
15
16   You should have received a copy of the GNU General Public License
17   along with this program.  If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include <cassert>
21 #include <cstring>
22 #include <fstream>
23 #include <iostream>
24 #include <sstream>
25 #include <algorithm>
26
27 #include "bitcount.h"
28 #include "movegen.h"
29 #include "position.h"
30 #include "psqtab.h"
31 #include "rkiss.h"
32 #include "thread.h"
33 #include "tt.h"
34
35 using std::string;
36 using std::cout;
37 using std::endl;
38
39 Key Position::zobrist[2][8][64];
40 Key Position::zobEp[64];
41 Key Position::zobCastle[16];
42 Key Position::zobSideToMove;
43 Key Position::zobExclusion;
44
45 Score Position::pieceSquareTable[16][64];
46
47 // Material values arrays, indexed by Piece
48 const Value PieceValueMidgame[17] = {
49   VALUE_ZERO,
50   PawnValueMidgame, KnightValueMidgame, BishopValueMidgame,
51   RookValueMidgame, QueenValueMidgame,
52   VALUE_ZERO, VALUE_ZERO, VALUE_ZERO,
53   PawnValueMidgame, KnightValueMidgame, BishopValueMidgame,
54   RookValueMidgame, QueenValueMidgame
55 };
56
57 const Value PieceValueEndgame[17] = {
58   VALUE_ZERO,
59   PawnValueEndgame, KnightValueEndgame, BishopValueEndgame,
60   RookValueEndgame, QueenValueEndgame,
61   VALUE_ZERO, VALUE_ZERO, VALUE_ZERO,
62   PawnValueEndgame, KnightValueEndgame, BishopValueEndgame,
63   RookValueEndgame, QueenValueEndgame
64 };
65
66
67 namespace {
68
69   // Bonus for having the side to move (modified by Joona Kiiski)
70   const Score TempoValue = make_score(48, 22);
71
72   // To convert a Piece to and from a FEN char
73   const string PieceToChar(".PNBRQK  pnbrqk  ");
74 }
75
76
77 /// CheckInfo c'tor
78
79 CheckInfo::CheckInfo(const Position& pos) {
80
81   Color them = flip(pos.side_to_move());
82   Square ksq = pos.king_square(them);
83
84   pinned = pos.pinned_pieces();
85   dcCandidates = pos.discovered_check_candidates();
86
87   checkSq[PAWN]   = pos.attacks_from<PAWN>(ksq, them);
88   checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
89   checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
90   checkSq[ROOK]   = pos.attacks_from<ROOK>(ksq);
91   checkSq[QUEEN]  = checkSq[BISHOP] | checkSq[ROOK];
92   checkSq[KING]   = EmptyBoardBB;
93 }
94
95
96 /// Position c'tors. Here we always create a copy of the original position
97 /// or the FEN string, we want the new born Position object do not depend
98 /// on any external data so we detach state pointer from the source one.
99
100 Position::Position(const Position& pos, int th) {
101
102   memcpy(this, &pos, sizeof(Position));
103   threadID = th;
104   nodes = 0;
105
106   assert(pos_is_ok());
107 }
108
109 Position::Position(const string& fen, bool isChess960, int th) {
110
111   from_fen(fen, isChess960);
112   threadID = th;
113 }
114
115
116 /// Position::from_fen() initializes the position object with the given FEN
117 /// string. This function is not very robust - make sure that input FENs are
118 /// correct (this is assumed to be the responsibility of the GUI).
119
120 void Position::from_fen(const string& fenStr, bool isChess960) {
121 /*
122    A FEN string defines a particular position using only the ASCII character set.
123
124    A FEN string contains six fields separated by a space. The fields are:
125
126    1) Piece placement (from white's perspective). Each rank is described, starting
127       with rank 8 and ending with rank 1; within each rank, the contents of each
128       square are described from file A through file H. Following the Standard
129       Algebraic Notation (SAN), each piece is identified by a single letter taken
130       from the standard English names. White pieces are designated using upper-case
131       letters ("PNBRQK") while Black take lowercase ("pnbrqk"). Blank squares are
132       noted using digits 1 through 8 (the number of blank squares), and "/"
133       separates ranks.
134
135    2) Active color. "w" means white moves next, "b" means black.
136
137    3) Castling availability. If neither side can castle, this is "-". Otherwise,
138       this has one or more letters: "K" (White can castle kingside), "Q" (White
139       can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
140       can castle queenside).
141
142    4) En passant target square (in algebraic notation). If there's no en passant
143       target square, this is "-". If a pawn has just made a 2-square move, this
144       is the position "behind" the pawn. This is recorded regardless of whether
145       there is a pawn in position to make an en passant capture.
146
147    5) Halfmove clock. This is the number of halfmoves since the last pawn advance
148       or capture. This is used to determine if a draw can be claimed under the
149       fifty-move rule.
150
151    6) Fullmove number. The number of the full move. It starts at 1, and is
152       incremented after Black's move.
153 */
154
155   char col, row, token;
156   size_t p;
157   Square sq = SQ_A8;
158   std::istringstream fen(fenStr);
159
160   clear();
161   fen >> std::noskipws;
162
163   // 1. Piece placement
164   while ((fen >> token) && !isspace(token))
165   {
166       if (token == '/')
167           sq -= Square(16); // Jump back of 2 rows
168
169       else if (isdigit(token))
170           sq += Square(token - '0'); // Skip the given number of files
171
172       else if ((p = PieceToChar.find(token)) != string::npos)
173       {
174           put_piece(Piece(p), sq);
175           sq++;
176       }
177   }
178
179   // 2. Active color
180   fen >> token;
181   sideToMove = (token == 'w' ? WHITE : BLACK);
182   fen >> token;
183
184   // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
185   // Shredder-FEN that uses the letters of the columns on which the rooks began
186   // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
187   // if an inner rook is associated with the castling right, the castling tag is
188   // replaced by the file letter of the involved rook, as for the Shredder-FEN.
189   while ((fen >> token) && !isspace(token))
190   {
191       Square rsq;
192       Color c = islower(token) ? BLACK : WHITE;
193       Piece rook = make_piece(c, ROOK);
194
195       token = char(toupper(token));
196
197       if (token == 'K')
198           for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; rsq--) {}
199
200       else if (token == 'Q')
201           for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; rsq++) {}
202
203       else if (token >= 'A' && token <= 'H')
204           rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
205
206       else
207           continue;
208
209       set_castle_right(king_square(c), rsq);
210   }
211
212   // 4. En passant square. Ignore if no pawn capture is possible
213   if (   ((fen >> col) && (col >= 'a' && col <= 'h'))
214       && ((fen >> row) && (row == '3' || row == '6')))
215   {
216       st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
217
218       if (!(attackers_to(st->epSquare) & pieces(PAWN, sideToMove)))
219           st->epSquare = SQ_NONE;
220   }
221
222   // 5-6. Halfmove clock and fullmove number
223   fen >> std::skipws >> st->rule50 >> startPosPly;
224
225   // Convert from fullmove starting from 1 to ply starting from 0,
226   // handle also common incorrect FEN with fullmove = 0.
227   startPosPly = std::max(2 * (startPosPly - 1), 0) + int(sideToMove == BLACK);
228
229   st->key = compute_key();
230   st->pawnKey = compute_pawn_key();
231   st->materialKey = compute_material_key();
232   st->value = compute_value();
233   st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
234   st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
235   st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(flip(sideToMove));
236   chess960 = isChess960;
237
238   assert(pos_is_ok());
239 }
240
241
242 /// Position::set_castle_right() is an helper function used to set castling
243 /// rights given the corresponding king and rook starting squares.
244
245 void Position::set_castle_right(Square ksq, Square rsq) {
246
247   int f = (rsq < ksq ? WHITE_OOO : WHITE_OO) << color_of(piece_on(ksq));
248
249   st->castleRights |= f;
250   castleRightsMask[ksq] ^= f;
251   castleRightsMask[rsq] ^= f;
252   castleRookSquare[f] = rsq;
253 }
254
255
256 /// Position::to_fen() returns a FEN representation of the position. In case
257 /// of Chess960 the Shredder-FEN notation is used. Mainly a debugging function.
258
259 const string Position::to_fen() const {
260
261   std::ostringstream fen;
262   Square sq;
263   int emptyCnt;
264
265   for (Rank rank = RANK_8; rank >= RANK_1; rank--)
266   {
267       emptyCnt = 0;
268
269       for (File file = FILE_A; file <= FILE_H; file++)
270       {
271           sq = make_square(file, rank);
272
273           if (square_is_empty(sq))
274               emptyCnt++;
275           else
276           {
277               if (emptyCnt > 0)
278               {
279                   fen << emptyCnt;
280                   emptyCnt = 0;
281               }
282               fen << PieceToChar[piece_on(sq)];
283           }
284       }
285
286       if (emptyCnt > 0)
287           fen << emptyCnt;
288
289       if (rank > RANK_1)
290           fen << '/';
291   }
292
293   fen << (sideToMove == WHITE ? " w " : " b ");
294
295   if (can_castle(WHITE_OO))
296       fen << (chess960 ? char(toupper(file_to_char(file_of(castle_rook_square(WHITE_OO))))) : 'K');
297
298   if (can_castle(WHITE_OOO))
299       fen << (chess960 ? char(toupper(file_to_char(file_of(castle_rook_square(WHITE_OOO))))) : 'Q');
300
301   if (can_castle(BLACK_OO))
302       fen << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK_OO))) : 'k');
303
304   if (can_castle(BLACK_OOO))
305       fen << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK_OOO))) : 'q');
306
307   if (st->castleRights == CASTLES_NONE)
308       fen << '-';
309
310   fen << (ep_square() == SQ_NONE ? " - " : " " + square_to_string(ep_square()) + " ")
311       << st->rule50 << " " << 1 + (startPosPly - int(sideToMove == BLACK)) / 2;
312
313   return fen.str();
314 }
315
316
317 /// Position::print() prints an ASCII representation of the position to
318 /// the standard output. If a move is given then also the san is printed.
319
320 void Position::print(Move move) const {
321
322   const char* dottedLine = "\n+---+---+---+---+---+---+---+---+\n";
323
324   if (move)
325   {
326       Position p(*this, thread());
327       cout << "\nMove is: " << (sideToMove == BLACK ? ".." : "") << move_to_san(p, move);
328   }
329
330   for (Rank rank = RANK_8; rank >= RANK_1; rank--)
331   {
332       cout << dottedLine << '|';
333       for (File file = FILE_A; file <= FILE_H; file++)
334       {
335           Square sq = make_square(file, rank);
336           Piece piece = piece_on(sq);
337           char c = (color_of(piece) == BLACK ? '=' : ' ');
338
339           if (piece == PIECE_NONE && color_of(sq) == DARK)
340               piece = PIECE_NONE_DARK_SQ;
341
342           cout << c << PieceToChar[piece] << c << '|';
343       }
344   }
345   cout << dottedLine << "Fen is: " << to_fen() << "\nKey is: " << st->key << endl;
346 }
347
348
349 /// Position:hidden_checkers<>() returns a bitboard of all pinned (against the
350 /// king) pieces for the given color. Or, when template parameter FindPinned is
351 /// false, the function return the pieces of the given color candidate for a
352 /// discovery check against the enemy king.
353 template<bool FindPinned>
354 Bitboard Position::hidden_checkers() const {
355
356   // Pinned pieces protect our king, dicovery checks attack the enemy king
357   Bitboard b, result = 0;
358   Bitboard pinners = pieces(FindPinned ? flip(sideToMove) : sideToMove);
359   Square ksq = king_square(FindPinned ? sideToMove : flip(sideToMove));
360
361   // Pinners are sliders, that give check when candidate pinned is removed
362   pinners &=  (pieces(ROOK, QUEEN) & RookPseudoAttacks[ksq])
363             | (pieces(BISHOP, QUEEN) & BishopPseudoAttacks[ksq]);
364
365   while (pinners)
366   {
367       b = squares_between(ksq, pop_1st_bit(&pinners)) & occupied_squares();
368
369       // Only one bit set and is an our piece?
370       if (b && !(b & (b - 1)) && (b & pieces(sideToMove)))
371           result |= b;
372   }
373   return result;
374 }
375
376 // Explicit template instantiations
377 template Bitboard Position::hidden_checkers<true>() const;
378 template Bitboard Position::hidden_checkers<false>() const;
379
380
381 /// Position::attackers_to() computes a bitboard of all pieces which attack a
382 /// given square. Slider attacks use occ bitboard as occupancy.
383
384 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
385
386   return  (attacks_from<PAWN>(s, BLACK) & pieces(PAWN, WHITE))
387         | (attacks_from<PAWN>(s, WHITE) & pieces(PAWN, BLACK))
388         | (attacks_from<KNIGHT>(s)      & pieces(KNIGHT))
389         | (rook_attacks_bb(s, occ)      & pieces(ROOK, QUEEN))
390         | (bishop_attacks_bb(s, occ)    & pieces(BISHOP, QUEEN))
391         | (attacks_from<KING>(s)        & pieces(KING));
392 }
393
394
395 /// Position::attacks_from() computes a bitboard of all attacks of a given piece
396 /// put in a given square. Slider attacks use occ bitboard as occupancy.
397
398 Bitboard Position::attacks_from(Piece p, Square s, Bitboard occ) {
399
400   assert(square_is_ok(s));
401
402   switch (p)
403   {
404   case WB: case BB: return bishop_attacks_bb(s, occ);
405   case WR: case BR: return rook_attacks_bb(s, occ);
406   case WQ: case BQ: return bishop_attacks_bb(s, occ) | rook_attacks_bb(s, occ);
407   default: return StepAttacksBB[p][s];
408   }
409 }
410
411
412 /// Position::move_attacks_square() tests whether a move from the current
413 /// position attacks a given square.
414
415 bool Position::move_attacks_square(Move m, Square s) const {
416
417   assert(is_ok(m));
418   assert(square_is_ok(s));
419
420   Bitboard occ, xray;
421   Square from = move_from(m);
422   Square to = move_to(m);
423   Piece piece = piece_on(from);
424
425   assert(!square_is_empty(from));
426
427   // Update occupancy as if the piece is moving
428   occ = occupied_squares();
429   do_move_bb(&occ, make_move_bb(from, to));
430
431   // The piece moved in 'to' attacks the square 's' ?
432   if (bit_is_set(attacks_from(piece, to, occ), s))
433       return true;
434
435   // Scan for possible X-ray attackers behind the moved piece
436   xray = (rook_attacks_bb(s, occ)   & pieces(ROOK, QUEEN, color_of(piece)))
437         |(bishop_attacks_bb(s, occ) & pieces(BISHOP, QUEEN, color_of(piece)));
438
439   // Verify attackers are triggered by our move and not already existing
440   return xray && (xray ^ (xray & attacks_from<QUEEN>(s)));
441 }
442
443
444 /// Position::pl_move_is_legal() tests whether a pseudo-legal move is legal
445
446 bool Position::pl_move_is_legal(Move m, Bitboard pinned) const {
447
448   assert(is_ok(m));
449   assert(pinned == pinned_pieces());
450
451   Color us = side_to_move();
452   Square from = move_from(m);
453
454   assert(color_of(piece_on(from)) == us);
455   assert(piece_on(king_square(us)) == make_piece(us, KING));
456
457   // En passant captures are a tricky special case. Because they are rather
458   // uncommon, we do it simply by testing whether the king is attacked after
459   // the move is made.
460   if (is_enpassant(m))
461   {
462       Color them = flip(us);
463       Square to = move_to(m);
464       Square capsq = to + pawn_push(them);
465       Square ksq = king_square(us);
466       Bitboard b = occupied_squares();
467
468       assert(to == ep_square());
469       assert(piece_on(from) == make_piece(us, PAWN));
470       assert(piece_on(capsq) == make_piece(them, PAWN));
471       assert(piece_on(to) == PIECE_NONE);
472
473       clear_bit(&b, from);
474       clear_bit(&b, capsq);
475       set_bit(&b, to);
476
477       return   !(rook_attacks_bb(ksq, b) & pieces(ROOK, QUEEN, them))
478             && !(bishop_attacks_bb(ksq, b) & pieces(BISHOP, QUEEN, them));
479   }
480
481   // If the moving piece is a king, check whether the destination
482   // square is attacked by the opponent. Castling moves are checked
483   // for legality during move generation.
484   if (type_of(piece_on(from)) == KING)
485       return is_castle(m) || !(attackers_to(move_to(m)) & pieces(flip(us)));
486
487   // A non-king move is legal if and only if it is not pinned or it
488   // is moving along the ray towards or away from the king.
489   return   !pinned
490         || !bit_is_set(pinned, from)
491         ||  squares_aligned(from, move_to(m), king_square(us));
492 }
493
494
495 /// Position::move_is_legal() takes a random move and tests whether the move
496 /// is legal. This version is not very fast and should be used only in non
497 /// time-critical paths.
498
499 bool Position::move_is_legal(const Move m) const {
500
501   for (MoveList<MV_LEGAL> ml(*this); !ml.end(); ++ml)
502       if (ml.move() == m)
503           return true;
504
505   return false;
506 }
507
508
509 /// Position::is_pseudo_legal() takes a random move and tests whether the move
510 /// is pseudo legal. It is used to validate moves from TT that can be corrupted
511 /// due to SMP concurrent access or hash position key aliasing.
512
513 bool Position::is_pseudo_legal(const Move m) const {
514
515   Color us = sideToMove;
516   Color them = flip(sideToMove);
517   Square from = move_from(m);
518   Square to = move_to(m);
519   Piece pc = piece_on(from);
520
521   // Use a slower but simpler function for uncommon cases
522   if (is_special(m))
523       return move_is_legal(m);
524
525   // Is not a promotion, so promotion piece must be empty
526   if (promotion_piece_type(m) - 2 != PIECE_TYPE_NONE)
527       return false;
528
529   // If the from square is not occupied by a piece belonging to the side to
530   // move, the move is obviously not legal.
531   if (pc == PIECE_NONE || color_of(pc) != us)
532       return false;
533
534   // The destination square cannot be occupied by a friendly piece
535   if (color_of(piece_on(to)) == us)
536       return false;
537
538   // Handle the special case of a pawn move
539   if (type_of(pc) == PAWN)
540   {
541       // Move direction must be compatible with pawn color
542       int direction = to - from;
543       if ((us == WHITE) != (direction > 0))
544           return false;
545
546       // We have already handled promotion moves, so destination
547       // cannot be on the 8/1th rank.
548       if (rank_of(to) == RANK_8 || rank_of(to) == RANK_1)
549           return false;
550
551       // Proceed according to the square delta between the origin and
552       // destination squares.
553       switch (direction)
554       {
555       case DELTA_NW:
556       case DELTA_NE:
557       case DELTA_SW:
558       case DELTA_SE:
559       // Capture. The destination square must be occupied by an enemy
560       // piece (en passant captures was handled earlier).
561       if (color_of(piece_on(to)) != them)
562           return false;
563
564       // From and to files must be one file apart, avoids a7h5
565       if (abs(file_of(from) - file_of(to)) != 1)
566           return false;
567       break;
568
569       case DELTA_N:
570       case DELTA_S:
571       // Pawn push. The destination square must be empty.
572       if (!square_is_empty(to))
573           return false;
574       break;
575
576       case DELTA_NN:
577       // Double white pawn push. The destination square must be on the fourth
578       // rank, and both the destination square and the square between the
579       // source and destination squares must be empty.
580       if (   rank_of(to) != RANK_4
581           || !square_is_empty(to)
582           || !square_is_empty(from + DELTA_N))
583           return false;
584       break;
585
586       case DELTA_SS:
587       // Double black pawn push. The destination square must be on the fifth
588       // rank, and both the destination square and the square between the
589       // source and destination squares must be empty.
590       if (   rank_of(to) != RANK_5
591           || !square_is_empty(to)
592           || !square_is_empty(from + DELTA_S))
593           return false;
594       break;
595
596       default:
597           return false;
598       }
599   }
600   else if (!bit_is_set(attacks_from(pc, from), to))
601       return false;
602
603   // Evasions generator already takes care to avoid some kind of illegal moves
604   // and pl_move_is_legal() relies on this. So we have to take care that the
605   // same kind of moves are filtered out here.
606   if (in_check())
607   {
608       // In case of king moves under check we have to remove king so to catch
609       // as invalid moves like b1a1 when opposite queen is on c1.
610       if (type_of(piece_on(from)) == KING)
611       {
612           Bitboard b = occupied_squares();
613           clear_bit(&b, from);
614           if (attackers_to(move_to(m), b) & pieces(flip(us)))
615               return false;
616       }
617       else
618       {
619           Bitboard target = checkers();
620           Square checksq = pop_1st_bit(&target);
621
622           if (target) // double check ? In this case a king move is required
623               return false;
624
625           // Our move must be a blocking evasion or a capture of the checking piece
626           target = squares_between(checksq, king_square(us)) | checkers();
627           if (!bit_is_set(target, move_to(m)))
628               return false;
629       }
630   }
631
632   return true;
633 }
634
635
636 /// Position::move_gives_check() tests whether a pseudo-legal move gives a check
637
638 bool Position::move_gives_check(Move m, const CheckInfo& ci) const {
639
640   assert(is_ok(m));
641   assert(ci.dcCandidates == discovered_check_candidates());
642   assert(color_of(piece_on(move_from(m))) == side_to_move());
643
644   Square from = move_from(m);
645   Square to = move_to(m);
646   PieceType pt = type_of(piece_on(from));
647
648   // Direct check ?
649   if (bit_is_set(ci.checkSq[pt], to))
650       return true;
651
652   // Discovery check ?
653   if (ci.dcCandidates && bit_is_set(ci.dcCandidates, from))
654   {
655       // For pawn and king moves we need to verify also direction
656       if (  (pt != PAWN && pt != KING)
657           || !squares_aligned(from, to, king_square(flip(side_to_move()))))
658           return true;
659   }
660
661   // Can we skip the ugly special cases ?
662   if (!is_special(m))
663       return false;
664
665   Color us = side_to_move();
666   Bitboard b = occupied_squares();
667   Square ksq = king_square(flip(us));
668
669   // Promotion with check ?
670   if (is_promotion(m))
671   {
672       clear_bit(&b, from);
673       return bit_is_set(attacks_from(Piece(promotion_piece_type(m)), to, b), ksq);
674   }
675
676   // En passant capture with check ? We have already handled the case
677   // of direct checks and ordinary discovered check, the only case we
678   // need to handle is the unusual case of a discovered check through
679   // the captured pawn.
680   if (is_enpassant(m))
681   {
682       Square capsq = make_square(file_of(to), rank_of(from));
683       clear_bit(&b, from);
684       clear_bit(&b, capsq);
685       set_bit(&b, to);
686       return  (rook_attacks_bb(ksq, b) & pieces(ROOK, QUEEN, us))
687             ||(bishop_attacks_bb(ksq, b) & pieces(BISHOP, QUEEN, us));
688   }
689
690   // Castling with check ?
691   if (is_castle(m))
692   {
693       Square kfrom, kto, rfrom, rto;
694       kfrom = from;
695       rfrom = to;
696
697       if (rfrom > kfrom)
698       {
699           kto = relative_square(us, SQ_G1);
700           rto = relative_square(us, SQ_F1);
701       } else {
702           kto = relative_square(us, SQ_C1);
703           rto = relative_square(us, SQ_D1);
704       }
705       clear_bit(&b, kfrom);
706       clear_bit(&b, rfrom);
707       set_bit(&b, rto);
708       set_bit(&b, kto);
709       return bit_is_set(rook_attacks_bb(rto, b), ksq);
710   }
711
712   return false;
713 }
714
715
716 /// Position::do_move() makes a move, and saves all information necessary
717 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
718 /// moves should be filtered out before this function is called.
719
720 void Position::do_move(Move m, StateInfo& newSt) {
721
722   CheckInfo ci(*this);
723   do_move(m, newSt, ci, move_gives_check(m, ci));
724 }
725
726 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
727
728   assert(is_ok(m));
729   assert(&newSt != st);
730
731   nodes++;
732   Key key = st->key;
733
734   // Copy some fields of old state to our new StateInfo object except the ones
735   // which are recalculated from scratch anyway, then switch our state pointer
736   // to point to the new, ready to be updated, state.
737   struct ReducedStateInfo {
738     Key pawnKey, materialKey;
739     Value npMaterial[2];
740     int castleRights, rule50, pliesFromNull;
741     Score value;
742     Square epSquare;
743   };
744
745   memcpy(&newSt, st, sizeof(ReducedStateInfo));
746
747   newSt.previous = st;
748   st = &newSt;
749
750   // Update side to move
751   key ^= zobSideToMove;
752
753   // Increment the 50 moves rule draw counter. Resetting it to zero in the
754   // case of non-reversible moves is taken care of later.
755   st->rule50++;
756   st->pliesFromNull++;
757
758   if (is_castle(m))
759   {
760       st->key = key;
761       do_castle_move<true>(m);
762       return;
763   }
764
765   Color us = side_to_move();
766   Color them = flip(us);
767   Square from = move_from(m);
768   Square to = move_to(m);
769   Piece piece = piece_on(from);
770   PieceType pt = type_of(piece);
771   PieceType capture = is_enpassant(m) ? PAWN : type_of(piece_on(to));
772
773   assert(color_of(piece) == us);
774   assert(color_of(piece_on(to)) != us);
775   assert(capture != KING);
776
777   if (capture)
778   {
779       Square capsq = to;
780
781       // If the captured piece is a pawn, update pawn hash key, otherwise
782       // update non-pawn material.
783       if (capture == PAWN)
784       {
785           if (is_enpassant(m))
786           {
787               capsq += pawn_push(them);
788
789               assert(pt == PAWN);
790               assert(to == st->epSquare);
791               assert(relative_rank(us, to) == RANK_6);
792               assert(piece_on(to) == PIECE_NONE);
793               assert(piece_on(capsq) == make_piece(them, PAWN));
794
795               board[capsq] = PIECE_NONE;
796           }
797
798           st->pawnKey ^= zobrist[them][PAWN][capsq];
799       }
800       else
801           st->npMaterial[them] -= PieceValueMidgame[capture];
802
803       // Remove the captured piece
804       clear_bit(&byColorBB[them], capsq);
805       clear_bit(&byTypeBB[capture], capsq);
806       clear_bit(&occupied, capsq);
807
808       // Update piece list, move the last piece at index[capsq] position and
809       // shrink the list.
810       //
811       // WARNING: This is a not revresible operation. When we will reinsert the
812       // captured piece in undo_move() we will put it at the end of the list and
813       // not in its original place, it means index[] and pieceList[] are not
814       // guaranteed to be invariant to a do_move() + undo_move() sequence.
815       Square lastSquare = pieceList[them][capture][--pieceCount[them][capture]];
816       index[lastSquare] = index[capsq];
817       pieceList[them][capture][index[lastSquare]] = lastSquare;
818       pieceList[them][capture][pieceCount[them][capture]] = SQ_NONE;
819
820       // Update hash keys
821       key ^= zobrist[them][capture][capsq];
822       st->materialKey ^= zobrist[them][capture][pieceCount[them][capture]];
823
824       // Update incremental scores
825       st->value -= pst(make_piece(them, capture), capsq);
826
827       // Reset rule 50 counter
828       st->rule50 = 0;
829   }
830
831   // Update hash key
832   key ^= zobrist[us][pt][from] ^ zobrist[us][pt][to];
833
834   // Reset en passant square
835   if (st->epSquare != SQ_NONE)
836   {
837       key ^= zobEp[st->epSquare];
838       st->epSquare = SQ_NONE;
839   }
840
841   // Update castle rights if needed
842   if (    st->castleRights != CASTLES_NONE
843       && (castleRightsMask[from] & castleRightsMask[to]) != ALL_CASTLES)
844   {
845       key ^= zobCastle[st->castleRights];
846       st->castleRights &= castleRightsMask[from] & castleRightsMask[to];
847       key ^= zobCastle[st->castleRights];
848   }
849
850   // Prefetch TT access as soon as we know key is updated
851   prefetch((char*)TT.first_entry(key));
852
853   // Move the piece
854   Bitboard move_bb = make_move_bb(from, to);
855   do_move_bb(&byColorBB[us], move_bb);
856   do_move_bb(&byTypeBB[pt], move_bb);
857   do_move_bb(&occupied, move_bb);
858
859   board[to] = board[from];
860   board[from] = PIECE_NONE;
861
862   // Update piece lists, index[from] is not updated and becomes stale. This
863   // works as long as index[] is accessed just by known occupied squares.
864   index[to] = index[from];
865   pieceList[us][pt][index[to]] = to;
866
867   // If the moving piece is a pawn do some special extra work
868   if (pt == PAWN)
869   {
870       // Set en-passant square, only if moved pawn can be captured
871       if (   (to ^ from) == 16
872           && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(PAWN, them)))
873       {
874           st->epSquare = Square((from + to) / 2);
875           key ^= zobEp[st->epSquare];
876       }
877
878       if (is_promotion(m))
879       {
880           PieceType promotion = promotion_piece_type(m);
881
882           assert(relative_rank(us, to) == RANK_8);
883           assert(promotion >= KNIGHT && promotion <= QUEEN);
884
885           // Replace the pawn with the promoted piece
886           clear_bit(&byTypeBB[PAWN], to);
887           set_bit(&byTypeBB[promotion], to);
888           board[to] = make_piece(us, promotion);
889
890           // Update piece lists, move the last pawn at index[to] position
891           // and shrink the list. Add a new promotion piece to the list.
892           Square lastSquare = pieceList[us][PAWN][--pieceCount[us][PAWN]];
893           index[lastSquare] = index[to];
894           pieceList[us][PAWN][index[lastSquare]] = lastSquare;
895           pieceList[us][PAWN][pieceCount[us][PAWN]] = SQ_NONE;
896           index[to] = pieceCount[us][promotion];
897           pieceList[us][promotion][index[to]] = to;
898
899           // Update hash keys
900           key ^= zobrist[us][PAWN][to] ^ zobrist[us][promotion][to];
901           st->pawnKey ^= zobrist[us][PAWN][to];
902           st->materialKey ^=  zobrist[us][promotion][pieceCount[us][promotion]++]
903                             ^ zobrist[us][PAWN][pieceCount[us][PAWN]];
904
905           // Update incremental score
906           st->value +=  pst(make_piece(us, promotion), to)
907                       - pst(make_piece(us, PAWN), to);
908
909           // Update material
910           st->npMaterial[us] += PieceValueMidgame[promotion];
911       }
912
913       // Update pawn hash key
914       st->pawnKey ^= zobrist[us][PAWN][from] ^ zobrist[us][PAWN][to];
915
916       // Reset rule 50 draw counter
917       st->rule50 = 0;
918   }
919
920   // Prefetch pawn and material hash tables
921   Threads[threadID].pawnTable.prefetch(st->pawnKey);
922   Threads[threadID].materialTable.prefetch(st->materialKey);
923
924   // Update incremental scores
925   st->value += pst_delta(piece, from, to);
926
927   // Set capture piece
928   st->capturedType = capture;
929
930   // Update the key with the final value
931   st->key = key;
932
933   // Update checkers bitboard, piece must be already moved
934   st->checkersBB = EmptyBoardBB;
935
936   if (moveIsCheck)
937   {
938       if (is_special(m))
939           st->checkersBB = attackers_to(king_square(them)) & pieces(us);
940       else
941       {
942           // Direct checks
943           if (bit_is_set(ci.checkSq[pt], to))
944               st->checkersBB = SetMaskBB[to];
945
946           // Discovery checks
947           if (ci.dcCandidates && bit_is_set(ci.dcCandidates, from))
948           {
949               if (pt != ROOK)
950                   st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(ROOK, QUEEN, us);
951
952               if (pt != BISHOP)
953                   st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(BISHOP, QUEEN, us);
954           }
955       }
956   }
957
958   // Finish
959   sideToMove = flip(sideToMove);
960   st->value += (sideToMove == WHITE ?  TempoValue : -TempoValue);
961
962   assert(pos_is_ok());
963 }
964
965
966 /// Position::undo_move() unmakes a move. When it returns, the position should
967 /// be restored to exactly the same state as before the move was made.
968
969 void Position::undo_move(Move m) {
970
971   assert(is_ok(m));
972
973   sideToMove = flip(sideToMove);
974
975   if (is_castle(m))
976   {
977       do_castle_move<false>(m);
978       return;
979   }
980
981   Color us = side_to_move();
982   Color them = flip(us);
983   Square from = move_from(m);
984   Square to = move_to(m);
985   Piece piece = piece_on(to);
986   PieceType pt = type_of(piece);
987   PieceType capture = st->capturedType;
988
989   assert(square_is_empty(from));
990   assert(color_of(piece) == us);
991   assert(capture != KING);
992
993   if (is_promotion(m))
994   {
995       PieceType promotion = promotion_piece_type(m);
996
997       assert(promotion == pt);
998       assert(relative_rank(us, to) == RANK_8);
999       assert(promotion >= KNIGHT && promotion <= QUEEN);
1000
1001       // Replace the promoted piece with the pawn
1002       clear_bit(&byTypeBB[promotion], to);
1003       set_bit(&byTypeBB[PAWN], to);
1004       board[to] = make_piece(us, PAWN);
1005
1006       // Update piece lists, move the last promoted piece at index[to] position
1007       // and shrink the list. Add a new pawn to the list.
1008       Square lastSquare = pieceList[us][promotion][--pieceCount[us][promotion]];
1009       index[lastSquare] = index[to];
1010       pieceList[us][promotion][index[lastSquare]] = lastSquare;
1011       pieceList[us][promotion][pieceCount[us][promotion]] = SQ_NONE;
1012       index[to] = pieceCount[us][PAWN]++;
1013       pieceList[us][PAWN][index[to]] = to;
1014
1015       pt = PAWN;
1016   }
1017
1018   // Put the piece back at the source square
1019   Bitboard move_bb = make_move_bb(to, from);
1020   do_move_bb(&byColorBB[us], move_bb);
1021   do_move_bb(&byTypeBB[pt], move_bb);
1022   do_move_bb(&occupied, move_bb);
1023
1024   board[from] = board[to];
1025   board[to] = PIECE_NONE;
1026
1027   // Update piece lists, index[to] is not updated and becomes stale. This
1028   // works as long as index[] is accessed just by known occupied squares.
1029   index[from] = index[to];
1030   pieceList[us][pt][index[from]] = from;
1031
1032   if (capture)
1033   {
1034       Square capsq = to;
1035
1036       if (is_enpassant(m))
1037       {
1038           capsq -= pawn_push(us);
1039
1040           assert(pt == PAWN);
1041           assert(to == st->previous->epSquare);
1042           assert(relative_rank(us, to) == RANK_6);
1043           assert(piece_on(capsq) == PIECE_NONE);
1044       }
1045
1046       // Restore the captured piece
1047       set_bit(&byColorBB[them], capsq);
1048       set_bit(&byTypeBB[capture], capsq);
1049       set_bit(&occupied, capsq);
1050
1051       board[capsq] = make_piece(them, capture);
1052
1053       // Update piece list, add a new captured piece in capsq square
1054       index[capsq] = pieceCount[them][capture]++;
1055       pieceList[them][capture][index[capsq]] = capsq;
1056   }
1057
1058   // Finally point our state pointer back to the previous state
1059   st = st->previous;
1060
1061   assert(pos_is_ok());
1062 }
1063
1064
1065 /// Position::do_castle_move() is a private method used to do/undo a castling
1066 /// move. Note that castling moves are encoded as "king captures friendly rook"
1067 /// moves, for instance white short castling in a non-Chess960 game is encoded
1068 /// as e1h1.
1069 template<bool Do>
1070 void Position::do_castle_move(Move m) {
1071
1072   assert(is_ok(m));
1073   assert(is_castle(m));
1074
1075   Square kto, kfrom, rfrom, rto, kAfter, rAfter;
1076
1077   Color us = side_to_move();
1078   Square kBefore = move_from(m);
1079   Square rBefore = move_to(m);
1080
1081   // Find after-castle squares for king and rook
1082   if (rBefore > kBefore) // O-O
1083   {
1084       kAfter = relative_square(us, SQ_G1);
1085       rAfter = relative_square(us, SQ_F1);
1086   }
1087   else // O-O-O
1088   {
1089       kAfter = relative_square(us, SQ_C1);
1090       rAfter = relative_square(us, SQ_D1);
1091   }
1092
1093   kfrom = Do ? kBefore : kAfter;
1094   rfrom = Do ? rBefore : rAfter;
1095
1096   kto = Do ? kAfter : kBefore;
1097   rto = Do ? rAfter : rBefore;
1098
1099   assert(piece_on(kfrom) == make_piece(us, KING));
1100   assert(piece_on(rfrom) == make_piece(us, ROOK));
1101
1102   // Remove pieces from source squares
1103   clear_bit(&byColorBB[us], kfrom);
1104   clear_bit(&byTypeBB[KING], kfrom);
1105   clear_bit(&occupied, kfrom);
1106   clear_bit(&byColorBB[us], rfrom);
1107   clear_bit(&byTypeBB[ROOK], rfrom);
1108   clear_bit(&occupied, rfrom);
1109
1110   // Put pieces on destination squares
1111   set_bit(&byColorBB[us], kto);
1112   set_bit(&byTypeBB[KING], kto);
1113   set_bit(&occupied, kto);
1114   set_bit(&byColorBB[us], rto);
1115   set_bit(&byTypeBB[ROOK], rto);
1116   set_bit(&occupied, rto);
1117
1118   // Update board
1119   Piece king = make_piece(us, KING);
1120   Piece rook = make_piece(us, ROOK);
1121   board[kfrom] = board[rfrom] = PIECE_NONE;
1122   board[kto] = king;
1123   board[rto] = rook;
1124
1125   // Update piece lists
1126   pieceList[us][KING][index[kfrom]] = kto;
1127   pieceList[us][ROOK][index[rfrom]] = rto;
1128   int tmp = index[rfrom]; // In Chess960 could be kto == rfrom
1129   index[kto] = index[kfrom];
1130   index[rto] = tmp;
1131
1132   if (Do)
1133   {
1134       // Reset capture field
1135       st->capturedType = PIECE_TYPE_NONE;
1136
1137       // Update incremental scores
1138       st->value += pst_delta(king, kfrom, kto);
1139       st->value += pst_delta(rook, rfrom, rto);
1140
1141       // Update hash key
1142       st->key ^= zobrist[us][KING][kfrom] ^ zobrist[us][KING][kto];
1143       st->key ^= zobrist[us][ROOK][rfrom] ^ zobrist[us][ROOK][rto];
1144
1145       // Clear en passant square
1146       if (st->epSquare != SQ_NONE)
1147       {
1148           st->key ^= zobEp[st->epSquare];
1149           st->epSquare = SQ_NONE;
1150       }
1151
1152       // Update castling rights
1153       st->key ^= zobCastle[st->castleRights];
1154       st->castleRights &= castleRightsMask[kfrom];
1155       st->key ^= zobCastle[st->castleRights];
1156
1157       // Reset rule 50 counter
1158       st->rule50 = 0;
1159
1160       // Update checkers BB
1161       st->checkersBB = attackers_to(king_square(flip(us))) & pieces(us);
1162
1163       // Finish
1164       sideToMove = flip(sideToMove);
1165       st->value += (sideToMove == WHITE ?  TempoValue : -TempoValue);
1166   }
1167   else
1168       // Undo: point our state pointer back to the previous state
1169       st = st->previous;
1170
1171   assert(pos_is_ok());
1172 }
1173
1174
1175 /// Position::do_null_move() is used to do/undo a "null move": It flips the side
1176 /// to move and updates the hash key without executing any move on the board.
1177 template<bool Do>
1178 void Position::do_null_move(StateInfo& backupSt) {
1179
1180   assert(!in_check());
1181
1182   // Back up the information necessary to undo the null move to the supplied
1183   // StateInfo object. Note that differently from normal case here backupSt
1184   // is actually used as a backup storage not as the new state. This reduces
1185   // the number of fields to be copied.
1186   StateInfo* src = Do ? st : &backupSt;
1187   StateInfo* dst = Do ? &backupSt : st;
1188
1189   dst->key      = src->key;
1190   dst->epSquare = src->epSquare;
1191   dst->value    = src->value;
1192   dst->rule50   = src->rule50;
1193   dst->pliesFromNull = src->pliesFromNull;
1194
1195   sideToMove = flip(sideToMove);
1196
1197   if (Do)
1198   {
1199       if (st->epSquare != SQ_NONE)
1200           st->key ^= zobEp[st->epSquare];
1201
1202       st->key ^= zobSideToMove;
1203       prefetch((char*)TT.first_entry(st->key));
1204
1205       st->epSquare = SQ_NONE;
1206       st->rule50++;
1207       st->pliesFromNull = 0;
1208       st->value += (sideToMove == WHITE) ?  TempoValue : -TempoValue;
1209   }
1210
1211   assert(pos_is_ok());
1212 }
1213
1214 // Explicit template instantiations
1215 template void Position::do_null_move<false>(StateInfo& backupSt);
1216 template void Position::do_null_move<true>(StateInfo& backupSt);
1217
1218
1219 /// Position::see() is a static exchange evaluator: It tries to estimate the
1220 /// material gain or loss resulting from a move. There are three versions of
1221 /// this function: One which takes a destination square as input, one takes a
1222 /// move, and one which takes a 'from' and a 'to' square. The function does
1223 /// not yet understand promotions captures.
1224
1225 int Position::see_sign(Move m) const {
1226
1227   assert(is_ok(m));
1228
1229   Square from = move_from(m);
1230   Square to = move_to(m);
1231
1232   // Early return if SEE cannot be negative because captured piece value
1233   // is not less then capturing one. Note that king moves always return
1234   // here because king midgame value is set to 0.
1235   if (PieceValueMidgame[piece_on(to)] >= PieceValueMidgame[piece_on(from)])
1236       return 1;
1237
1238   return see(m);
1239 }
1240
1241 int Position::see(Move m) const {
1242
1243   Square from, to;
1244   Bitboard occ, attackers, stmAttackers, b;
1245   int swapList[32], slIndex = 1;
1246   PieceType capturedType, pt;
1247   Color stm;
1248
1249   assert(is_ok(m));
1250
1251   // As castle moves are implemented as capturing the rook, they have
1252   // SEE == RookValueMidgame most of the times (unless the rook is under
1253   // attack).
1254   if (is_castle(m))
1255       return 0;
1256
1257   from = move_from(m);
1258   to = move_to(m);
1259   capturedType = type_of(piece_on(to));
1260   occ = occupied_squares();
1261
1262   // Handle en passant moves
1263   if (is_enpassant(m))
1264   {
1265       Square capQq = to - pawn_push(side_to_move());
1266
1267       assert(capturedType == PIECE_TYPE_NONE);
1268       assert(type_of(piece_on(capQq)) == PAWN);
1269
1270       // Remove the captured pawn
1271       clear_bit(&occ, capQq);
1272       capturedType = PAWN;
1273   }
1274
1275   // Find all attackers to the destination square, with the moving piece
1276   // removed, but possibly an X-ray attacker added behind it.
1277   clear_bit(&occ, from);
1278   attackers = attackers_to(to, occ);
1279
1280   // If the opponent has no attackers we are finished
1281   stm = flip(color_of(piece_on(from)));
1282   stmAttackers = attackers & pieces(stm);
1283   if (!stmAttackers)
1284       return PieceValueMidgame[capturedType];
1285
1286   // The destination square is defended, which makes things rather more
1287   // difficult to compute. We proceed by building up a "swap list" containing
1288   // the material gain or loss at each stop in a sequence of captures to the
1289   // destination square, where the sides alternately capture, and always
1290   // capture with the least valuable piece. After each capture, we look for
1291   // new X-ray attacks from behind the capturing piece.
1292   swapList[0] = PieceValueMidgame[capturedType];
1293   capturedType = type_of(piece_on(from));
1294
1295   do {
1296       // Locate the least valuable attacker for the side to move. The loop
1297       // below looks like it is potentially infinite, but it isn't. We know
1298       // that the side to move still has at least one attacker left.
1299       for (pt = PAWN; !(stmAttackers & pieces(pt)); pt++)
1300           assert(pt < KING);
1301
1302       // Remove the attacker we just found from the 'occupied' bitboard,
1303       // and scan for new X-ray attacks behind the attacker.
1304       b = stmAttackers & pieces(pt);
1305       occ ^= (b & (~b + 1));
1306       attackers |=  (rook_attacks_bb(to, occ)   & pieces(ROOK, QUEEN))
1307                   | (bishop_attacks_bb(to, occ) & pieces(BISHOP, QUEEN));
1308
1309       attackers &= occ; // Cut out pieces we've already done
1310
1311       // Add the new entry to the swap list
1312       assert(slIndex < 32);
1313       swapList[slIndex] = -swapList[slIndex - 1] + PieceValueMidgame[capturedType];
1314       slIndex++;
1315
1316       // Remember the value of the capturing piece, and change the side to
1317       // move before beginning the next iteration.
1318       capturedType = pt;
1319       stm = flip(stm);
1320       stmAttackers = attackers & pieces(stm);
1321
1322       // Stop before processing a king capture
1323       if (capturedType == KING && stmAttackers)
1324       {
1325           assert(slIndex < 32);
1326           swapList[slIndex++] = QueenValueMidgame*10;
1327           break;
1328       }
1329   } while (stmAttackers);
1330
1331   // Having built the swap list, we negamax through it to find the best
1332   // achievable score from the point of view of the side to move.
1333   while (--slIndex)
1334       swapList[slIndex-1] = std::min(-swapList[slIndex], swapList[slIndex-1]);
1335
1336   return swapList[0];
1337 }
1338
1339
1340 /// Position::clear() erases the position object to a pristine state, with an
1341 /// empty board, white to move, and no castling rights.
1342
1343 void Position::clear() {
1344
1345   st = &startState;
1346   memset(st, 0, sizeof(StateInfo));
1347   st->epSquare = SQ_NONE;
1348
1349   memset(byColorBB,  0, sizeof(Bitboard) * 2);
1350   memset(byTypeBB,   0, sizeof(Bitboard) * 8);
1351   memset(pieceCount, 0, sizeof(int) * 2 * 8);
1352   memset(index,      0, sizeof(int) * 64);
1353
1354   for (int i = 0; i < 8; i++)
1355       for (int j = 0; j < 16; j++)
1356           pieceList[0][i][j] = pieceList[1][i][j] = SQ_NONE;
1357
1358   for (Square sq = SQ_A1; sq <= SQ_H8; sq++)
1359   {
1360       board[sq] = PIECE_NONE;
1361       castleRightsMask[sq] = ALL_CASTLES;
1362   }
1363   sideToMove = WHITE;
1364   nodes = 0;
1365   occupied = 0;
1366 }
1367
1368
1369 /// Position::put_piece() puts a piece on the given square of the board,
1370 /// updating the board array, pieces list, bitboards, and piece counts.
1371
1372 void Position::put_piece(Piece p, Square s) {
1373
1374   Color c = color_of(p);
1375   PieceType pt = type_of(p);
1376
1377   board[s] = p;
1378   index[s] = pieceCount[c][pt]++;
1379   pieceList[c][pt][index[s]] = s;
1380
1381   set_bit(&byTypeBB[pt], s);
1382   set_bit(&byColorBB[c], s);
1383   set_bit(&occupied, s);
1384 }
1385
1386
1387 /// Position::compute_key() computes the hash key of the position. The hash
1388 /// key is usually updated incrementally as moves are made and unmade, the
1389 /// compute_key() function is only used when a new position is set up, and
1390 /// to verify the correctness of the hash key when running in debug mode.
1391
1392 Key Position::compute_key() const {
1393
1394   Key result = zobCastle[st->castleRights];
1395
1396   for (Square s = SQ_A1; s <= SQ_H8; s++)
1397       if (!square_is_empty(s))
1398           result ^= zobrist[color_of(piece_on(s))][type_of(piece_on(s))][s];
1399
1400   if (ep_square() != SQ_NONE)
1401       result ^= zobEp[ep_square()];
1402
1403   if (side_to_move() == BLACK)
1404       result ^= zobSideToMove;
1405
1406   return result;
1407 }
1408
1409
1410 /// Position::compute_pawn_key() computes the hash key of the position. The
1411 /// hash key is usually updated incrementally as moves are made and unmade,
1412 /// the compute_pawn_key() function is only used when a new position is set
1413 /// up, and to verify the correctness of the pawn hash key when running in
1414 /// debug mode.
1415
1416 Key Position::compute_pawn_key() const {
1417
1418   Bitboard b;
1419   Key result = 0;
1420
1421   for (Color c = WHITE; c <= BLACK; c++)
1422   {
1423       b = pieces(PAWN, c);
1424       while (b)
1425           result ^= zobrist[c][PAWN][pop_1st_bit(&b)];
1426   }
1427   return result;
1428 }
1429
1430
1431 /// Position::compute_material_key() computes the hash key of the position.
1432 /// The hash key is usually updated incrementally as moves are made and unmade,
1433 /// the compute_material_key() function is only used when a new position is set
1434 /// up, and to verify the correctness of the material hash key when running in
1435 /// debug mode.
1436
1437 Key Position::compute_material_key() const {
1438
1439   Key result = 0;
1440
1441   for (Color c = WHITE; c <= BLACK; c++)
1442       for (PieceType pt = PAWN; pt <= QUEEN; pt++)
1443           for (int i = 0; i < piece_count(c, pt); i++)
1444               result ^= zobrist[c][pt][i];
1445
1446   return result;
1447 }
1448
1449
1450 /// Position::compute_value() compute the incremental scores for the middle
1451 /// game and the endgame. These functions are used to initialize the incremental
1452 /// scores when a new position is set up, and to verify that the scores are correctly
1453 /// updated by do_move and undo_move when the program is running in debug mode.
1454 Score Position::compute_value() const {
1455
1456   Bitboard b;
1457   Score result = SCORE_ZERO;
1458
1459   for (Color c = WHITE; c <= BLACK; c++)
1460       for (PieceType pt = PAWN; pt <= KING; pt++)
1461       {
1462           b = pieces(pt, c);
1463           while (b)
1464               result += pst(make_piece(c, pt), pop_1st_bit(&b));
1465       }
1466
1467   result += (side_to_move() == WHITE ? TempoValue / 2 : -TempoValue / 2);
1468   return result;
1469 }
1470
1471
1472 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1473 /// game material value for the given side. Material values are updated
1474 /// incrementally during the search, this function is only used while
1475 /// initializing a new Position object.
1476
1477 Value Position::compute_non_pawn_material(Color c) const {
1478
1479   Value result = VALUE_ZERO;
1480
1481   for (PieceType pt = KNIGHT; pt <= QUEEN; pt++)
1482       result += piece_count(c, pt) * PieceValueMidgame[pt];
1483
1484   return result;
1485 }
1486
1487
1488 /// Position::is_draw() tests whether the position is drawn by material,
1489 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1490 /// must be done by the search.
1491 template<bool SkipRepetition>
1492 bool Position::is_draw() const {
1493
1494   // Draw by material?
1495   if (   !pieces(PAWN)
1496       && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMidgame))
1497       return true;
1498
1499   // Draw by the 50 moves rule?
1500   if (st->rule50 > 99 && !is_mate())
1501       return true;
1502
1503   // Draw by repetition?
1504   if (!SkipRepetition)
1505   {
1506       int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1507
1508       if (i <= e)
1509       {
1510           StateInfo* stp = st->previous->previous;
1511
1512           do {
1513               stp = stp->previous->previous;
1514
1515               if (stp->key == st->key)
1516                   return true;
1517
1518               i +=2;
1519
1520           } while (i <= e);
1521       }
1522   }
1523
1524   return false;
1525 }
1526
1527 // Explicit template instantiations
1528 template bool Position::is_draw<false>() const;
1529 template bool Position::is_draw<true>() const;
1530
1531
1532 /// Position::is_mate() returns true or false depending on whether the
1533 /// side to move is checkmated.
1534
1535 bool Position::is_mate() const {
1536
1537   return in_check() && !MoveList<MV_LEGAL>(*this).size();
1538 }
1539
1540
1541 /// Position::init() is a static member function which initializes at startup
1542 /// the various arrays used to compute hash keys and the piece square tables.
1543 /// The latter is a two-step operation: First, the white halves of the tables
1544 /// are copied from PSQT[] tables. Second, the black halves of the tables are
1545 /// initialized by flipping and changing the sign of the white scores.
1546
1547 void Position::init() {
1548
1549   RKISS rk;
1550
1551   for (Color c = WHITE; c <= BLACK; c++)
1552       for (PieceType pt = PAWN; pt <= KING; pt++)
1553           for (Square s = SQ_A1; s <= SQ_H8; s++)
1554               zobrist[c][pt][s] = rk.rand<Key>();
1555
1556   for (Square s = SQ_A1; s <= SQ_H8; s++)
1557       zobEp[s] = rk.rand<Key>();
1558
1559   for (int i = 0; i < 16; i++)
1560       zobCastle[i] = rk.rand<Key>();
1561
1562   zobSideToMove = rk.rand<Key>();
1563   zobExclusion  = rk.rand<Key>();
1564
1565   for (Piece p = WP; p <= WK; p++)
1566   {
1567       Score ps = make_score(PieceValueMidgame[p], PieceValueEndgame[p]);
1568
1569       for (Square s = SQ_A1; s <= SQ_H8; s++)
1570       {
1571           pieceSquareTable[p][s] = ps + PSQT[p][s];
1572           pieceSquareTable[p+8][flip(s)] = -pieceSquareTable[p][s];
1573       }
1574   }
1575 }
1576
1577
1578 /// Position::flip_me() flips position with the white and black sides reversed. This
1579 /// is only useful for debugging especially for finding evaluation symmetry bugs.
1580
1581 void Position::flip_me() {
1582
1583   // Make a copy of current position before to start changing
1584   const Position pos(*this, threadID);
1585
1586   clear();
1587   threadID = pos.thread();
1588
1589   // Board
1590   for (Square s = SQ_A1; s <= SQ_H8; s++)
1591       if (!pos.square_is_empty(s))
1592           put_piece(Piece(pos.piece_on(s) ^ 8), flip(s));
1593
1594   // Side to move
1595   sideToMove = flip(pos.side_to_move());
1596
1597   // Castling rights
1598   if (pos.can_castle(WHITE_OO))
1599       set_castle_right(king_square(BLACK), flip(pos.castle_rook_square(WHITE_OO)));
1600   if (pos.can_castle(WHITE_OOO))
1601       set_castle_right(king_square(BLACK), flip(pos.castle_rook_square(WHITE_OOO)));
1602   if (pos.can_castle(BLACK_OO))
1603       set_castle_right(king_square(WHITE), flip(pos.castle_rook_square(BLACK_OO)));
1604   if (pos.can_castle(BLACK_OOO))
1605       set_castle_right(king_square(WHITE), flip(pos.castle_rook_square(BLACK_OOO)));
1606
1607   // En passant square
1608   if (pos.st->epSquare != SQ_NONE)
1609       st->epSquare = flip(pos.st->epSquare);
1610
1611   // Checkers
1612   st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(flip(sideToMove));
1613
1614   // Hash keys
1615   st->key = compute_key();
1616   st->pawnKey = compute_pawn_key();
1617   st->materialKey = compute_material_key();
1618
1619   // Incremental scores
1620   st->value = compute_value();
1621
1622   // Material
1623   st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
1624   st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
1625
1626   assert(pos_is_ok());
1627 }
1628
1629
1630 /// Position::pos_is_ok() performs some consitency checks for the position object.
1631 /// This is meant to be helpful when debugging.
1632
1633 bool Position::pos_is_ok(int* failedStep) const {
1634
1635   // What features of the position should be verified?
1636   const bool debugAll = false;
1637
1638   const bool debugBitboards       = debugAll || false;
1639   const bool debugKingCount       = debugAll || false;
1640   const bool debugKingCapture     = debugAll || false;
1641   const bool debugCheckerCount    = debugAll || false;
1642   const bool debugKey             = debugAll || false;
1643   const bool debugMaterialKey     = debugAll || false;
1644   const bool debugPawnKey         = debugAll || false;
1645   const bool debugIncrementalEval = debugAll || false;
1646   const bool debugNonPawnMaterial = debugAll || false;
1647   const bool debugPieceCounts     = debugAll || false;
1648   const bool debugPieceList       = debugAll || false;
1649   const bool debugCastleSquares   = debugAll || false;
1650
1651   if (failedStep) *failedStep = 1;
1652
1653   // Side to move OK?
1654   if (side_to_move() != WHITE && side_to_move() != BLACK)
1655       return false;
1656
1657   // Are the king squares in the position correct?
1658   if (failedStep) (*failedStep)++;
1659   if (piece_on(king_square(WHITE)) != WK)
1660       return false;
1661
1662   if (failedStep) (*failedStep)++;
1663   if (piece_on(king_square(BLACK)) != BK)
1664       return false;
1665
1666   // Do both sides have exactly one king?
1667   if (failedStep) (*failedStep)++;
1668   if (debugKingCount)
1669   {
1670       int kingCount[2] = {0, 0};
1671       for (Square s = SQ_A1; s <= SQ_H8; s++)
1672           if (type_of(piece_on(s)) == KING)
1673               kingCount[color_of(piece_on(s))]++;
1674
1675       if (kingCount[0] != 1 || kingCount[1] != 1)
1676           return false;
1677   }
1678
1679   // Can the side to move capture the opponent's king?
1680   if (failedStep) (*failedStep)++;
1681   if (debugKingCapture)
1682   {
1683       Color us = side_to_move();
1684       Color them = flip(us);
1685       Square ksq = king_square(them);
1686       if (attackers_to(ksq) & pieces(us))
1687           return false;
1688   }
1689
1690   // Is there more than 2 checkers?
1691   if (failedStep) (*failedStep)++;
1692   if (debugCheckerCount && count_1s<CNT32>(st->checkersBB) > 2)
1693       return false;
1694
1695   // Bitboards OK?
1696   if (failedStep) (*failedStep)++;
1697   if (debugBitboards)
1698   {
1699       // The intersection of the white and black pieces must be empty
1700       if ((pieces(WHITE) & pieces(BLACK)) != EmptyBoardBB)
1701           return false;
1702
1703       // The union of the white and black pieces must be equal to all
1704       // occupied squares
1705       if ((pieces(WHITE) | pieces(BLACK)) != occupied_squares())
1706           return false;
1707
1708       // Separate piece type bitboards must have empty intersections
1709       for (PieceType p1 = PAWN; p1 <= KING; p1++)
1710           for (PieceType p2 = PAWN; p2 <= KING; p2++)
1711               if (p1 != p2 && (pieces(p1) & pieces(p2)))
1712                   return false;
1713   }
1714
1715   // En passant square OK?
1716   if (failedStep) (*failedStep)++;
1717   if (ep_square() != SQ_NONE)
1718   {
1719       // The en passant square must be on rank 6, from the point of view of the
1720       // side to move.
1721       if (relative_rank(side_to_move(), ep_square()) != RANK_6)
1722           return false;
1723   }
1724
1725   // Hash key OK?
1726   if (failedStep) (*failedStep)++;
1727   if (debugKey && st->key != compute_key())
1728       return false;
1729
1730   // Pawn hash key OK?
1731   if (failedStep) (*failedStep)++;
1732   if (debugPawnKey && st->pawnKey != compute_pawn_key())
1733       return false;
1734
1735   // Material hash key OK?
1736   if (failedStep) (*failedStep)++;
1737   if (debugMaterialKey && st->materialKey != compute_material_key())
1738       return false;
1739
1740   // Incremental eval OK?
1741   if (failedStep) (*failedStep)++;
1742   if (debugIncrementalEval && st->value != compute_value())
1743       return false;
1744
1745   // Non-pawn material OK?
1746   if (failedStep) (*failedStep)++;
1747   if (debugNonPawnMaterial)
1748   {
1749       if (st->npMaterial[WHITE] != compute_non_pawn_material(WHITE))
1750           return false;
1751
1752       if (st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1753           return false;
1754   }
1755
1756   // Piece counts OK?
1757   if (failedStep) (*failedStep)++;
1758   if (debugPieceCounts)
1759       for (Color c = WHITE; c <= BLACK; c++)
1760           for (PieceType pt = PAWN; pt <= KING; pt++)
1761               if (pieceCount[c][pt] != count_1s<CNT32>(pieces(pt, c)))
1762                   return false;
1763
1764   if (failedStep) (*failedStep)++;
1765   if (debugPieceList)
1766       for (Color c = WHITE; c <= BLACK; c++)
1767           for (PieceType pt = PAWN; pt <= KING; pt++)
1768               for (int i = 0; i < pieceCount[c][pt]; i++)
1769               {
1770                   if (piece_on(piece_list(c, pt)[i]) != make_piece(c, pt))
1771                       return false;
1772
1773                   if (index[piece_list(c, pt)[i]] != i)
1774                       return false;
1775               }
1776
1777   if (failedStep) (*failedStep)++;
1778   if (debugCastleSquares)
1779       for (CastleRight f = WHITE_OO; f <= BLACK_OOO; f = CastleRight(f << 1))
1780       {
1781           if (!can_castle(f))
1782               continue;
1783
1784           Piece rook = (f & (WHITE_OO | WHITE_OOO) ? WR : BR);
1785
1786           if (   castleRightsMask[castleRookSquare[f]] != (ALL_CASTLES ^ f)
1787               || piece_on(castleRookSquare[f]) != rook)
1788               return false;
1789       }
1790
1791   if (failedStep) *failedStep = 0;
1792   return true;
1793 }