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