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