Fix compile with Intel 13.0
[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[16][64]; // [piece][square]
44 Value PieceValue[2][18] = {     // [Mg / Eg][piece / pieceType]
45 { VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg },
46 { VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } };
47
48 namespace Zobrist {
49
50 Key psq[2][8][64]; // [color][pieceType][square / piece count]
51 Key enpassant[8];  // [file]
52 Key castle[16];    // [castleRight]
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::from_fen() initializes the position object with the given FEN
176 /// string. This function is not very robust - make sure that input FENs are
177 /// correct (this is assumed to be the responsibility of the GUI).
178
179 void Position::from_fen(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 fen(fenStr);
218
219   clear();
220   fen >> std::noskipws;
221
222   // 1. Piece placement
223   while ((fen >> 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   fen >> token;
240   sideToMove = (token == 'w' ? WHITE : BLACK);
241   fen >> 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 ((fen >> 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 (   ((fen >> col) && (col >= 'a' && col <= 'h'))
272       && ((fen >> 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   fen >> 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::to_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::to_fen() const {
332
333   std::ostringstream fen;
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                   fen << emptyCnt;
352                   emptyCnt = 0;
353               }
354               fen << PieceToChar[piece_on(sq)];
355           }
356       }
357
358       if (emptyCnt > 0)
359           fen << emptyCnt;
360
361       if (rank > RANK_1)
362           fen << '/';
363   }
364
365   fen << (sideToMove == WHITE ? " w " : " b ");
366
367   if (can_castle(WHITE_OO))
368       fen << (chess960 ? char(toupper(file_to_char(file_of(castle_rook_square(WHITE, KING_SIDE))))) : 'K');
369
370   if (can_castle(WHITE_OOO))
371       fen << (chess960 ? char(toupper(file_to_char(file_of(castle_rook_square(WHITE, QUEEN_SIDE))))) : 'Q');
372
373   if (can_castle(BLACK_OO))
374       fen << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, KING_SIDE))) : 'k');
375
376   if (can_castle(BLACK_OOO))
377       fen << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, QUEEN_SIDE))) : 'q');
378
379   if (st->castleRights == CASTLES_NONE)
380       fen << '-';
381
382   fen << (ep_square() == SQ_NONE ? " - " : " " + square_to_string(ep_square()) + " ")
383       << st->rule50 << " " << 1 + (startPosPly - int(sideToMove == BLACK)) / 2;
384
385   return fen.str();
386 }
387
388
389 /// Position::print() prints an ASCII representation of the position to
390 /// the standard output. If a move is given then also the san is printed.
391
392 void Position::print(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   sync_cout;
401
402   if (move)
403   {
404       Position p(*this);
405       cout << "\nMove is: " << (sideToMove == BLACK ? ".." : "") << move_to_san(p, move);
406   }
407
408   for (Square sq = SQ_A1; sq <= SQ_H8; sq++)
409       if (piece_on(sq) != NO_PIECE)
410           brd[513 - 68*rank_of(sq) + 4*file_of(sq)] = PieceToChar[piece_on(sq)];
411
412   cout << brd << "\nFen is: " << to_fen() << "\nKey is: " << st->key << sync_endl;
413 }
414
415
416 /// Position:hidden_checkers<>() returns a bitboard of all pinned (against the
417 /// king) pieces for the given color. Or, when template parameter FindPinned is
418 /// false, the function return the pieces of the given color candidate for a
419 /// discovery check against the enemy king.
420 template<bool FindPinned>
421 Bitboard Position::hidden_checkers() const {
422
423   // Pinned pieces protect our king, dicovery checks attack the enemy king
424   Bitboard b, result = 0;
425   Bitboard pinners = pieces(FindPinned ? ~sideToMove : sideToMove);
426   Square ksq = king_square(FindPinned ? sideToMove : ~sideToMove);
427
428   // Pinners are sliders, that give check when candidate pinned is removed
429   pinners &=  (pieces(ROOK, QUEEN) & PseudoAttacks[ROOK][ksq])
430             | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq]);
431
432   while (pinners)
433   {
434       b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
435
436       if (b && !more_than_one(b) && (b & pieces(sideToMove)))
437           result |= b;
438   }
439   return result;
440 }
441
442 // Explicit template instantiations
443 template Bitboard Position::hidden_checkers<true>() const;
444 template Bitboard Position::hidden_checkers<false>() const;
445
446
447 /// Position::attackers_to() computes a bitboard of all pieces which attack a
448 /// given square. Slider attacks use occ bitboard as occupancy.
449
450 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
451
452   return  (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
453         | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
454         | (attacks_from<KNIGHT>(s)      & pieces(KNIGHT))
455         | (attacks_bb<ROOK>(s, occ)     & pieces(ROOK, QUEEN))
456         | (attacks_bb<BISHOP>(s, occ)   & pieces(BISHOP, QUEEN))
457         | (attacks_from<KING>(s)        & pieces(KING));
458 }
459
460
461 /// Position::attacks_from() computes a bitboard of all attacks of a given piece
462 /// put in a given square. Slider attacks use occ bitboard as occupancy.
463
464 Bitboard Position::attacks_from(Piece p, Square s, Bitboard occ) {
465
466   assert(is_ok(s));
467
468   switch (type_of(p))
469   {
470   case BISHOP: return attacks_bb<BISHOP>(s, occ);
471   case ROOK  : return attacks_bb<ROOK>(s, occ);
472   case QUEEN : return attacks_bb<BISHOP>(s, occ) | attacks_bb<ROOK>(s, occ);
473   default    : return StepAttacksBB[p][s];
474   }
475 }
476
477
478 /// Position::move_attacks_square() tests whether a move from the current
479 /// position attacks a given square.
480
481 bool Position::move_attacks_square(Move m, Square s) const {
482
483   assert(is_ok(m));
484   assert(is_ok(s));
485
486   Bitboard occ, xray;
487   Square from = from_sq(m);
488   Square to = to_sq(m);
489   Piece piece = piece_moved(m);
490
491   assert(!is_empty(from));
492
493   // Update occupancy as if the piece is moving
494   occ = pieces() ^ from ^ to;
495
496   // The piece moved in 'to' attacks the square 's' ?
497   if (attacks_from(piece, to, occ) & s)
498       return true;
499
500   // Scan for possible X-ray attackers behind the moved piece
501   xray =  (attacks_bb<  ROOK>(s, occ) & pieces(color_of(piece), QUEEN, ROOK))
502         | (attacks_bb<BISHOP>(s, occ) & pieces(color_of(piece), QUEEN, BISHOP));
503
504   // Verify attackers are triggered by our move and not already existing
505   return xray && (xray ^ (xray & attacks_from<QUEEN>(s)));
506 }
507
508
509 /// Position::pl_move_is_legal() tests whether a pseudo-legal move is legal
510
511 bool Position::pl_move_is_legal(Move m, Bitboard pinned) const {
512
513   assert(is_ok(m));
514   assert(pinned == pinned_pieces());
515
516   Color us = sideToMove;
517   Square from = from_sq(m);
518
519   assert(color_of(piece_moved(m)) == us);
520   assert(piece_on(king_square(us)) == make_piece(us, KING));
521
522   // En passant captures are a tricky special case. Because they are rather
523   // uncommon, we do it simply by testing whether the king is attacked after
524   // the move is made.
525   if (type_of(m) == ENPASSANT)
526   {
527       Color them = ~us;
528       Square to = to_sq(m);
529       Square capsq = to + pawn_push(them);
530       Square ksq = king_square(us);
531       Bitboard b = (pieces() ^ from ^ capsq) | to;
532
533       assert(to == ep_square());
534       assert(piece_moved(m) == make_piece(us, PAWN));
535       assert(piece_on(capsq) == make_piece(them, PAWN));
536       assert(piece_on(to) == NO_PIECE);
537
538       return   !(attacks_bb<  ROOK>(ksq, b) & pieces(them, QUEEN, ROOK))
539             && !(attacks_bb<BISHOP>(ksq, b) & pieces(them, QUEEN, BISHOP));
540   }
541
542   // If the moving piece is a king, check whether the destination
543   // square is attacked by the opponent. Castling moves are checked
544   // for legality during move generation.
545   if (type_of(piece_on(from)) == KING)
546       return type_of(m) == CASTLE || !(attackers_to(to_sq(m)) & pieces(~us));
547
548   // A non-king move is legal if and only if it is not pinned or it
549   // is moving along the ray towards or away from the king.
550   return   !pinned
551         || !(pinned & from)
552         ||  squares_aligned(from, to_sq(m), king_square(us));
553 }
554
555
556 /// Position::move_is_legal() takes a random move and tests whether the move
557 /// is legal. This version is not very fast and should be used only in non
558 /// time-critical paths.
559
560 bool Position::move_is_legal(const Move m) const {
561
562   for (MoveList<LEGAL> ml(*this); !ml.end(); ++ml)
563       if (ml.move() == m)
564           return true;
565
566   return false;
567 }
568
569
570 /// Position::is_pseudo_legal() takes a random move and tests whether the move
571 /// is pseudo legal. It is used to validate moves from TT that can be corrupted
572 /// due to SMP concurrent access or hash position key aliasing.
573
574 bool Position::is_pseudo_legal(const Move m) const {
575
576   Color us = sideToMove;
577   Color them = ~sideToMove;
578   Square from = from_sq(m);
579   Square to = to_sq(m);
580   Piece pc = piece_moved(m);
581
582   // Use a slower but simpler function for uncommon cases
583   if (type_of(m) != NORMAL)
584       return move_is_legal(m);
585
586   // Is not a promotion, so promotion piece must be empty
587   if (promotion_type(m) - 2 != NO_PIECE_TYPE)
588       return false;
589
590   // If the from square is not occupied by a piece belonging to the side to
591   // move, the move is obviously not legal.
592   if (pc == NO_PIECE || color_of(pc) != us)
593       return false;
594
595   // The destination square cannot be occupied by a friendly piece
596   if (color_of(piece_on(to)) == us)
597       return false;
598
599   // Handle the special case of a pawn move
600   if (type_of(pc) == PAWN)
601   {
602       // Move direction must be compatible with pawn color
603       int direction = to - from;
604       if ((us == WHITE) != (direction > 0))
605           return false;
606
607       // We have already handled promotion moves, so destination
608       // cannot be on the 8/1th rank.
609       if (rank_of(to) == RANK_8 || rank_of(to) == RANK_1)
610           return false;
611
612       // Proceed according to the square delta between the origin and
613       // destination squares.
614       switch (direction)
615       {
616       case DELTA_NW:
617       case DELTA_NE:
618       case DELTA_SW:
619       case DELTA_SE:
620       // Capture. The destination square must be occupied by an enemy
621       // piece (en passant captures was handled earlier).
622       if (color_of(piece_on(to)) != them)
623           return false;
624
625       // From and to files must be one file apart, avoids a7h5
626       if (abs(file_of(from) - file_of(to)) != 1)
627           return false;
628       break;
629
630       case DELTA_N:
631       case DELTA_S:
632       // Pawn push. The destination square must be empty.
633       if (!is_empty(to))
634           return false;
635       break;
636
637       case DELTA_NN:
638       // Double white pawn push. The destination square must be on the fourth
639       // rank, and both the destination square and the square between the
640       // source and destination squares must be empty.
641       if (    rank_of(to) != RANK_4
642           || !is_empty(to)
643           || !is_empty(from + DELTA_N))
644           return false;
645       break;
646
647       case DELTA_SS:
648       // Double black pawn push. The destination square must be on the fifth
649       // rank, and both the destination square and the square between the
650       // source and destination squares must be empty.
651       if (    rank_of(to) != RANK_5
652           || !is_empty(to)
653           || !is_empty(from + DELTA_S))
654           return false;
655       break;
656
657       default:
658           return false;
659       }
660   }
661   else if (!(attacks_from(pc, from) & to))
662       return false;
663
664   // Evasions generator already takes care to avoid some kind of illegal moves
665   // and pl_move_is_legal() relies on this. So we have to take care that the
666   // same kind of moves are filtered out here.
667   if (in_check())
668   {
669       if (type_of(pc) != KING)
670       {
671           Bitboard b = checkers();
672           Square checksq = pop_lsb(&b);
673
674           if (b) // double check ? In this case a king move is required
675               return false;
676
677           // Our move must be a blocking evasion or a capture of the checking piece
678           if (!((between_bb(checksq, king_square(us)) | checkers()) & to))
679               return false;
680       }
681       // In case of king moves under check we have to remove king so to catch
682       // as invalid moves like b1a1 when opposite queen is on c1.
683       else if (attackers_to(to, pieces() ^ from) & pieces(~us))
684           return false;
685   }
686
687   return true;
688 }
689
690
691 /// Position::move_gives_check() tests whether a pseudo-legal move gives a check
692
693 bool Position::move_gives_check(Move m, const CheckInfo& ci) const {
694
695   assert(is_ok(m));
696   assert(ci.dcCandidates == discovered_check_candidates());
697   assert(color_of(piece_moved(m)) == sideToMove);
698
699   Square from = from_sq(m);
700   Square to = to_sq(m);
701   PieceType pt = type_of(piece_on(from));
702
703   // Direct check ?
704   if (ci.checkSq[pt] & to)
705       return true;
706
707   // Discovery check ?
708   if (ci.dcCandidates && (ci.dcCandidates & from))
709   {
710       // For pawn and king moves we need to verify also direction
711       if (   (pt != PAWN && pt != KING)
712           || !squares_aligned(from, to, king_square(~sideToMove)))
713           return true;
714   }
715
716   // Can we skip the ugly special cases ?
717   if (type_of(m) == NORMAL)
718       return false;
719
720   Color us = sideToMove;
721   Square ksq = king_square(~us);
722
723   // Promotion with check ?
724   if (type_of(m) == PROMOTION)
725       return attacks_from(Piece(promotion_type(m)), to, pieces() ^ from) & ksq;
726
727   // En passant capture with check ? We have already handled the case
728   // of direct checks and ordinary discovered check, the only case we
729   // need to handle is the unusual case of a discovered check through
730   // the captured pawn.
731   if (type_of(m) == ENPASSANT)
732   {
733       Square capsq = file_of(to) | rank_of(from);
734       Bitboard b = (pieces() ^ from ^ capsq) | to;
735
736       return  (attacks_bb<  ROOK>(ksq, b) & pieces(us, QUEEN, ROOK))
737             | (attacks_bb<BISHOP>(ksq, b) & pieces(us, QUEEN, BISHOP));
738   }
739
740   // Castling with check ?
741   if (type_of(m) == CASTLE)
742   {
743       Square kfrom = from;
744       Square rfrom = to; // 'King captures the rook' notation
745       Square kto = relative_square(us, rfrom > kfrom ? SQ_G1 : SQ_C1);
746       Square rto = relative_square(us, rfrom > kfrom ? SQ_F1 : SQ_D1);
747       Bitboard b = (pieces() ^ kfrom ^ rfrom) | rto | kto;
748
749       return attacks_bb<ROOK>(rto, b) & ksq;
750   }
751
752   return false;
753 }
754
755
756 /// Position::do_move() makes a move, and saves all information necessary
757 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
758 /// moves should be filtered out before this function is called.
759
760 void Position::do_move(Move m, StateInfo& newSt) {
761
762   CheckInfo ci(*this);
763   do_move(m, newSt, ci, move_gives_check(m, ci));
764 }
765
766 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
767
768   assert(is_ok(m));
769   assert(&newSt != st);
770
771   nodes++;
772   Key k = st->key;
773
774   // Copy some fields of old state to our new StateInfo object except the ones
775   // which are recalculated from scratch anyway, then switch our state pointer
776   // to point to the new, ready to be updated, state.
777   memcpy(&newSt, st, sizeof(ReducedStateInfo));
778
779   newSt.previous = st;
780   st = &newSt;
781
782   // Update side to move
783   k ^= Zobrist::side;
784
785   // Increment the 50 moves rule draw counter. Resetting it to zero in the
786   // case of a capture or a pawn move is taken care of later.
787   st->rule50++;
788   st->pliesFromNull++;
789
790   if (type_of(m) == CASTLE)
791   {
792       st->key = k;
793       do_castle_move<true>(m);
794       return;
795   }
796
797   Color us = sideToMove;
798   Color them = ~us;
799   Square from = from_sq(m);
800   Square to = to_sq(m);
801   Piece piece = piece_on(from);
802   PieceType pt = type_of(piece);
803   PieceType capture = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
804
805   assert(color_of(piece) == us);
806   assert(color_of(piece_on(to)) != us);
807   assert(capture != KING);
808
809   if (capture)
810   {
811       Square capsq = to;
812
813       // If the captured piece is a pawn, update pawn hash key, otherwise
814       // update non-pawn material.
815       if (capture == PAWN)
816       {
817           if (type_of(m) == ENPASSANT)
818           {
819               capsq += pawn_push(them);
820
821               assert(pt == PAWN);
822               assert(to == st->epSquare);
823               assert(relative_rank(us, to) == RANK_6);
824               assert(piece_on(to) == NO_PIECE);
825               assert(piece_on(capsq) == make_piece(them, PAWN));
826
827               board[capsq] = NO_PIECE;
828           }
829
830           st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
831       }
832       else
833           st->npMaterial[them] -= PieceValue[Mg][capture];
834
835       // Remove the captured piece
836       byTypeBB[ALL_PIECES] ^= capsq;
837       byTypeBB[capture] ^= capsq;
838       byColorBB[them] ^= capsq;
839
840       // Update piece list, move the last piece at index[capsq] position and
841       // shrink the list.
842       //
843       // WARNING: This is a not revresible operation. When we will reinsert the
844       // captured piece in undo_move() we will put it at the end of the list and
845       // not in its original place, it means index[] and pieceList[] are not
846       // guaranteed to be invariant to a do_move() + undo_move() sequence.
847       Square lastSquare = pieceList[them][capture][--pieceCount[them][capture]];
848       index[lastSquare] = index[capsq];
849       pieceList[them][capture][index[lastSquare]] = lastSquare;
850       pieceList[them][capture][pieceCount[them][capture]] = SQ_NONE;
851
852       // Update hash keys
853       k ^= Zobrist::psq[them][capture][capsq];
854       st->materialKey ^= Zobrist::psq[them][capture][pieceCount[them][capture]];
855
856       // Update incremental scores
857       st->psqScore -= pieceSquareTable[make_piece(them, capture)][capsq];
858
859       // Reset rule 50 counter
860       st->rule50 = 0;
861   }
862
863   // Update hash key
864   k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
865
866   // Reset en passant square
867   if (st->epSquare != SQ_NONE)
868   {
869       k ^= Zobrist::enpassant[file_of(st->epSquare)];
870       st->epSquare = SQ_NONE;
871   }
872
873   // Update castle rights if needed
874   if (st->castleRights && (castleRightsMask[from] | castleRightsMask[to]))
875   {
876       int cr = castleRightsMask[from] | castleRightsMask[to];
877       k ^= Zobrist::castle[st->castleRights & cr];
878       st->castleRights &= ~cr;
879   }
880
881   // Prefetch TT access as soon as we know key is updated
882   prefetch((char*)TT.first_entry(k));
883
884   // Move the piece
885   Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
886   byTypeBB[ALL_PIECES] ^= from_to_bb;
887   byTypeBB[pt] ^= from_to_bb;
888   byColorBB[us] ^= from_to_bb;
889
890   board[to] = board[from];
891   board[from] = NO_PIECE;
892
893   // Update piece lists, index[from] is not updated and becomes stale. This
894   // works as long as index[] is accessed just by known occupied squares.
895   index[to] = index[from];
896   pieceList[us][pt][index[to]] = to;
897
898   // If the moving piece is a pawn do some special extra work
899   if (pt == PAWN)
900   {
901       // Set en-passant square, only if moved pawn can be captured
902       if (   (int(to) ^ int(from)) == 16
903           && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
904       {
905           st->epSquare = Square((from + to) / 2);
906           k ^= Zobrist::enpassant[file_of(st->epSquare)];
907       }
908
909       if (type_of(m) == PROMOTION)
910       {
911           PieceType promotion = promotion_type(m);
912
913           assert(relative_rank(us, to) == RANK_8);
914           assert(promotion >= KNIGHT && promotion <= QUEEN);
915
916           // Replace the pawn with the promoted piece
917           byTypeBB[PAWN] ^= to;
918           byTypeBB[promotion] |= to;
919           board[to] = make_piece(us, promotion);
920
921           // Update piece lists, move the last pawn at index[to] position
922           // and shrink the list. Add a new promotion piece to the list.
923           Square lastSquare = pieceList[us][PAWN][--pieceCount[us][PAWN]];
924           index[lastSquare] = index[to];
925           pieceList[us][PAWN][index[lastSquare]] = lastSquare;
926           pieceList[us][PAWN][pieceCount[us][PAWN]] = SQ_NONE;
927           index[to] = pieceCount[us][promotion];
928           pieceList[us][promotion][index[to]] = to;
929
930           // Update hash keys
931           k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
932           st->pawnKey ^= Zobrist::psq[us][PAWN][to];
933           st->materialKey ^=  Zobrist::psq[us][promotion][pieceCount[us][promotion]++]
934                             ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
935
936           // Update incremental score
937           st->psqScore +=  pieceSquareTable[make_piece(us, promotion)][to]
938                          - pieceSquareTable[make_piece(us, PAWN)][to];
939
940           // Update material
941           st->npMaterial[us] += PieceValue[Mg][promotion];
942       }
943
944       // Update pawn hash key
945       st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
946
947       // Reset rule 50 draw counter
948       st->rule50 = 0;
949   }
950
951   // Prefetch pawn and material hash tables
952   prefetch((char*)thisThread->pawnTable.entries[st->pawnKey]);
953   prefetch((char*)thisThread->materialTable.entries[st->materialKey]);
954
955   // Update incremental scores
956   st->psqScore += psq_delta(piece, from, to);
957
958   // Set capture piece
959   st->capturedType = capture;
960
961   // Update the key with the final value
962   st->key = k;
963
964   // Update checkers bitboard, piece must be already moved
965   st->checkersBB = 0;
966
967   if (moveIsCheck)
968   {
969       if (type_of(m) != NORMAL)
970           st->checkersBB = attackers_to(king_square(them)) & pieces(us);
971       else
972       {
973           // Direct checks
974           if (ci.checkSq[pt] & to)
975               st->checkersBB |= to;
976
977           // Discovery checks
978           if (ci.dcCandidates && (ci.dcCandidates & from))
979           {
980               if (pt != ROOK)
981                   st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
982
983               if (pt != BISHOP)
984                   st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
985           }
986       }
987   }
988
989   sideToMove = ~sideToMove;
990
991   assert(pos_is_ok());
992 }
993
994
995 /// Position::undo_move() unmakes a move. When it returns, the position should
996 /// be restored to exactly the same state as before the move was made.
997
998 void Position::undo_move(Move m) {
999
1000   assert(is_ok(m));
1001
1002   sideToMove = ~sideToMove;
1003
1004   if (type_of(m) == CASTLE)
1005   {
1006       do_castle_move<false>(m);
1007       return;
1008   }
1009
1010   Color us = sideToMove;
1011   Color them = ~us;
1012   Square from = from_sq(m);
1013   Square to = to_sq(m);
1014   Piece piece = piece_on(to);
1015   PieceType pt = type_of(piece);
1016   PieceType capture = st->capturedType;
1017
1018   assert(is_empty(from));
1019   assert(color_of(piece) == us);
1020   assert(capture != KING);
1021
1022   if (type_of(m) == PROMOTION)
1023   {
1024       PieceType promotion = promotion_type(m);
1025
1026       assert(promotion == pt);
1027       assert(relative_rank(us, to) == RANK_8);
1028       assert(promotion >= KNIGHT && promotion <= QUEEN);
1029
1030       // Replace the promoted piece with the pawn
1031       byTypeBB[promotion] ^= to;
1032       byTypeBB[PAWN] |= to;
1033       board[to] = make_piece(us, PAWN);
1034
1035       // Update piece lists, move the last promoted piece at index[to] position
1036       // and shrink the list. Add a new pawn to the list.
1037       Square lastSquare = pieceList[us][promotion][--pieceCount[us][promotion]];
1038       index[lastSquare] = index[to];
1039       pieceList[us][promotion][index[lastSquare]] = lastSquare;
1040       pieceList[us][promotion][pieceCount[us][promotion]] = SQ_NONE;
1041       index[to] = pieceCount[us][PAWN]++;
1042       pieceList[us][PAWN][index[to]] = to;
1043
1044       pt = PAWN;
1045   }
1046
1047   // Put the piece back at the source square
1048   Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
1049   byTypeBB[ALL_PIECES] ^= from_to_bb;
1050   byTypeBB[pt] ^= from_to_bb;
1051   byColorBB[us] ^= from_to_bb;
1052
1053   board[from] = board[to];
1054   board[to] = NO_PIECE;
1055
1056   // Update piece lists, index[to] is not updated and becomes stale. This
1057   // works as long as index[] is accessed just by known occupied squares.
1058   index[from] = index[to];
1059   pieceList[us][pt][index[from]] = from;
1060
1061   if (capture)
1062   {
1063       Square capsq = to;
1064
1065       if (type_of(m) == ENPASSANT)
1066       {
1067           capsq -= pawn_push(us);
1068
1069           assert(pt == PAWN);
1070           assert(to == st->previous->epSquare);
1071           assert(relative_rank(us, to) == RANK_6);
1072           assert(piece_on(capsq) == NO_PIECE);
1073       }
1074
1075       // Restore the captured piece
1076       byTypeBB[ALL_PIECES] |= capsq;
1077       byTypeBB[capture] |= capsq;
1078       byColorBB[them] |= capsq;
1079
1080       board[capsq] = make_piece(them, capture);
1081
1082       // Update piece list, add a new captured piece in capsq square
1083       index[capsq] = pieceCount[them][capture]++;
1084       pieceList[them][capture][index[capsq]] = capsq;
1085   }
1086
1087   // Finally point our state pointer back to the previous state
1088   st = st->previous;
1089
1090   assert(pos_is_ok());
1091 }
1092
1093
1094 /// Position::do_castle_move() is a private method used to do/undo a castling
1095 /// move. Note that castling moves are encoded as "king captures friendly rook"
1096 /// moves, for instance white short castling in a non-Chess960 game is encoded
1097 /// as e1h1.
1098 template<bool Do>
1099 void Position::do_castle_move(Move m) {
1100
1101   assert(is_ok(m));
1102   assert(type_of(m) == CASTLE);
1103
1104   Square kto, kfrom, rfrom, rto, kAfter, rAfter;
1105
1106   Color us = sideToMove;
1107   Square kBefore = from_sq(m);
1108   Square rBefore = to_sq(m);
1109
1110   // Find after-castle squares for king and rook
1111   if (rBefore > kBefore) // O-O
1112   {
1113       kAfter = relative_square(us, SQ_G1);
1114       rAfter = relative_square(us, SQ_F1);
1115   }
1116   else // O-O-O
1117   {
1118       kAfter = relative_square(us, SQ_C1);
1119       rAfter = relative_square(us, SQ_D1);
1120   }
1121
1122   kfrom = Do ? kBefore : kAfter;
1123   rfrom = Do ? rBefore : rAfter;
1124
1125   kto = Do ? kAfter : kBefore;
1126   rto = Do ? rAfter : rBefore;
1127
1128   assert(piece_on(kfrom) == make_piece(us, KING));
1129   assert(piece_on(rfrom) == make_piece(us, ROOK));
1130
1131   // Move the pieces, with some care; in chess960 could be kto == rfrom
1132   Bitboard k_from_to_bb = SquareBB[kfrom] ^ SquareBB[kto];
1133   Bitboard r_from_to_bb = SquareBB[rfrom] ^ SquareBB[rto];
1134   byTypeBB[KING] ^= k_from_to_bb;
1135   byTypeBB[ROOK] ^= r_from_to_bb;
1136   byTypeBB[ALL_PIECES] ^= k_from_to_bb ^ r_from_to_bb;
1137   byColorBB[us] ^= k_from_to_bb ^ r_from_to_bb;
1138
1139   // Update board
1140   Piece king = make_piece(us, KING);
1141   Piece rook = make_piece(us, ROOK);
1142   board[kfrom] = board[rfrom] = NO_PIECE;
1143   board[kto] = king;
1144   board[rto] = rook;
1145
1146   // Update piece lists
1147   pieceList[us][KING][index[kfrom]] = kto;
1148   pieceList[us][ROOK][index[rfrom]] = rto;
1149   int tmp = index[rfrom]; // In Chess960 could be kto == rfrom
1150   index[kto] = index[kfrom];
1151   index[rto] = tmp;
1152
1153   if (Do)
1154   {
1155       // Reset capture field
1156       st->capturedType = NO_PIECE_TYPE;
1157
1158       // Update incremental scores
1159       st->psqScore += psq_delta(king, kfrom, kto);
1160       st->psqScore += psq_delta(rook, rfrom, rto);
1161
1162       // Update hash key
1163       st->key ^= Zobrist::psq[us][KING][kfrom] ^ Zobrist::psq[us][KING][kto];
1164       st->key ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
1165
1166       // Clear en passant square
1167       if (st->epSquare != SQ_NONE)
1168       {
1169           st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
1170           st->epSquare = SQ_NONE;
1171       }
1172
1173       // Update castling rights
1174       st->key ^= Zobrist::castle[st->castleRights & castleRightsMask[kfrom]];
1175       st->castleRights &= ~castleRightsMask[kfrom];
1176
1177       // Update checkers BB
1178       st->checkersBB = attackers_to(king_square(~us)) & pieces(us);
1179
1180       sideToMove = ~sideToMove;
1181   }
1182   else
1183       // Undo: point our state pointer back to the previous state
1184       st = st->previous;
1185
1186   assert(pos_is_ok());
1187 }
1188
1189
1190 /// Position::do_null_move() is used to do/undo a "null move": It flips the side
1191 /// to move and updates the hash key without executing any move on the board.
1192 template<bool Do>
1193 void Position::do_null_move(StateInfo& backupSt) {
1194
1195   assert(!in_check());
1196
1197   // Back up the information necessary to undo the null move to the supplied
1198   // StateInfo object. Note that differently from normal case here backupSt
1199   // is actually used as a backup storage not as the new state. This reduces
1200   // the number of fields to be copied.
1201   StateInfo* src = Do ? st : &backupSt;
1202   StateInfo* dst = Do ? &backupSt : st;
1203
1204   dst->key      = src->key;
1205   dst->epSquare = src->epSquare;
1206   dst->psqScore = src->psqScore;
1207   dst->rule50   = src->rule50;
1208   dst->pliesFromNull = src->pliesFromNull;
1209
1210   sideToMove = ~sideToMove;
1211
1212   if (Do)
1213   {
1214       if (st->epSquare != SQ_NONE)
1215           st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
1216
1217       st->key ^= Zobrist::side;
1218       prefetch((char*)TT.first_entry(st->key));
1219
1220       st->epSquare = SQ_NONE;
1221       st->rule50++;
1222       st->pliesFromNull = 0;
1223   }
1224
1225   assert(pos_is_ok());
1226 }
1227
1228 // Explicit template instantiations
1229 template void Position::do_null_move<false>(StateInfo& backupSt);
1230 template void Position::do_null_move<true>(StateInfo& backupSt);
1231
1232
1233 /// Position::see() is a static exchange evaluator: It tries to estimate the
1234 /// material gain or loss resulting from a move. There are three versions of
1235 /// this function: One which takes a destination square as input, one takes a
1236 /// move, and one which takes a 'from' and a 'to' square. The function does
1237 /// not yet understand promotions captures.
1238
1239 int Position::see_sign(Move m) const {
1240
1241   assert(is_ok(m));
1242
1243   // Early return if SEE cannot be negative because captured piece value
1244   // is not less then capturing one. Note that king moves always return
1245   // here because king midgame value is set to 0.
1246   if (PieceValue[Mg][piece_on(to_sq(m))] >= PieceValue[Mg][piece_moved(m)])
1247       return 1;
1248
1249   return see(m);
1250 }
1251
1252 int Position::see(Move m) const {
1253
1254   Square from, to;
1255   Bitboard occupied, attackers, stmAttackers;
1256   int swapList[32], slIndex = 1;
1257   PieceType captured;
1258   Color stm;
1259
1260   assert(is_ok(m));
1261
1262   from = from_sq(m);
1263   to = to_sq(m);
1264   captured = type_of(piece_on(to));
1265   occupied = pieces() ^ from;
1266
1267   // Handle en passant moves
1268   if (type_of(m) == ENPASSANT)
1269   {
1270       Square capQq = to - pawn_push(sideToMove);
1271
1272       assert(!captured);
1273       assert(type_of(piece_on(capQq)) == PAWN);
1274
1275       // Remove the captured pawn
1276       occupied ^= capQq;
1277       captured = PAWN;
1278   }
1279   else if (type_of(m) == CASTLE)
1280       // Castle moves are implemented as king capturing the rook so cannot be
1281       // handled correctly. Simply return 0 that is always the correct value
1282       // unless the rook is ends up under attack.
1283       return 0;
1284
1285   // Find all attackers to the destination square, with the moving piece
1286   // removed, but possibly an X-ray attacker added behind it.
1287   attackers = attackers_to(to, occupied);
1288
1289   // If the opponent has no attackers we are finished
1290   stm = ~color_of(piece_on(from));
1291   stmAttackers = attackers & pieces(stm);
1292   if (!stmAttackers)
1293       return PieceValue[Mg][captured];
1294
1295   // The destination square is defended, which makes things rather more
1296   // difficult to compute. We proceed by building up a "swap list" containing
1297   // the material gain or loss at each stop in a sequence of captures to the
1298   // destination square, where the sides alternately capture, and always
1299   // capture with the least valuable piece. After each capture, we look for
1300   // new X-ray attacks from behind the capturing piece.
1301   swapList[0] = PieceValue[Mg][captured];
1302   captured = type_of(piece_on(from));
1303
1304   do {
1305       assert(slIndex < 32);
1306
1307       // Add the new entry to the swap list
1308       swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[Mg][captured];
1309       slIndex++;
1310
1311       // Locate and remove from 'occupied' the next least valuable attacker
1312       captured = next_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1313
1314       attackers &= occupied; // Remove the just found attacker
1315       stm = ~stm;
1316       stmAttackers = attackers & pieces(stm);
1317
1318       if (captured == KING)
1319       {
1320           // Stop before processing a king capture
1321           if (stmAttackers)
1322               swapList[slIndex++] = QueenValueMg * 16;
1323
1324           break;
1325       }
1326
1327   } while (stmAttackers);
1328
1329   // Having built the swap list, we negamax through it to find the best
1330   // achievable score from the point of view of the side to move.
1331   while (--slIndex)
1332       swapList[slIndex-1] = std::min(-swapList[slIndex], swapList[slIndex-1]);
1333
1334   return swapList[0];
1335 }
1336
1337
1338 /// Position::clear() erases the position object to a pristine state, with an
1339 /// empty board, white to move, and no castling rights.
1340
1341 void Position::clear() {
1342
1343   memset(this, 0, sizeof(Position));
1344   startState.epSquare = SQ_NONE;
1345   st = &startState;
1346
1347   for (int i = 0; i < 8; i++)
1348       for (int j = 0; j < 16; j++)
1349           pieceList[0][i][j] = pieceList[1][i][j] = SQ_NONE;
1350
1351   for (Square sq = SQ_A1; sq <= SQ_H8; sq++)
1352       board[sq] = NO_PIECE;
1353 }
1354
1355
1356 /// Position::put_piece() puts a piece on the given square of the board,
1357 /// updating the board array, pieces list, bitboards, and piece counts.
1358
1359 void Position::put_piece(Piece p, Square s) {
1360
1361   Color c = color_of(p);
1362   PieceType pt = type_of(p);
1363
1364   board[s] = p;
1365   index[s] = pieceCount[c][pt]++;
1366   pieceList[c][pt][index[s]] = s;
1367
1368   byTypeBB[ALL_PIECES] |= s;
1369   byTypeBB[pt] |= s;
1370   byColorBB[c] |= s;
1371 }
1372
1373
1374 /// Position::compute_key() computes the hash key of the position. The hash
1375 /// key is usually updated incrementally as moves are made and unmade, the
1376 /// compute_key() function is only used when a new position is set up, and
1377 /// to verify the correctness of the hash key when running in debug mode.
1378
1379 Key Position::compute_key() const {
1380
1381   Key k = Zobrist::castle[st->castleRights];
1382
1383   for (Bitboard b = pieces(); b; )
1384   {
1385       Square s = pop_lsb(&b);
1386       k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1387   }
1388
1389   if (ep_square() != SQ_NONE)
1390       k ^= Zobrist::enpassant[file_of(ep_square())];
1391
1392   if (sideToMove == BLACK)
1393       k ^= Zobrist::side;
1394
1395   return k;
1396 }
1397
1398
1399 /// Position::compute_pawn_key() computes the hash key of the position. The
1400 /// hash key is usually updated incrementally as moves are made and unmade,
1401 /// the compute_pawn_key() function is only used when a new position is set
1402 /// up, and to verify the correctness of the pawn hash key when running in
1403 /// debug mode.
1404
1405 Key Position::compute_pawn_key() const {
1406
1407   Key k = 0;
1408
1409   for (Bitboard b = pieces(PAWN); b; )
1410   {
1411       Square s = pop_lsb(&b);
1412       k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1413   }
1414
1415   return k;
1416 }
1417
1418
1419 /// Position::compute_material_key() computes the hash key of the position.
1420 /// The hash key is usually updated incrementally as moves are made and unmade,
1421 /// the compute_material_key() function is only used when a new position is set
1422 /// up, and to verify the correctness of the material hash key when running in
1423 /// debug mode.
1424
1425 Key Position::compute_material_key() const {
1426
1427   Key k = 0;
1428
1429   for (Color c = WHITE; c <= BLACK; c++)
1430       for (PieceType pt = PAWN; pt <= QUEEN; pt++)
1431           for (int cnt = 0; cnt < piece_count(c, pt); cnt++)
1432               k ^= Zobrist::psq[c][pt][cnt];
1433
1434   return k;
1435 }
1436
1437
1438 /// Position::compute_psq_score() computes the incremental scores for the middle
1439 /// game and the endgame. These functions are used to initialize the incremental
1440 /// scores when a new position is set up, and to verify that the scores are correctly
1441 /// updated by do_move and undo_move when the program is running in debug mode.
1442 Score Position::compute_psq_score() const {
1443
1444   Score score = SCORE_ZERO;
1445
1446   for (Bitboard b = pieces(); b; )
1447   {
1448       Square s = pop_lsb(&b);
1449       score += pieceSquareTable[piece_on(s)][s];
1450   }
1451
1452   return score;
1453 }
1454
1455
1456 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1457 /// game material value for the given side. Material values are updated
1458 /// incrementally during the search, this function is only used while
1459 /// initializing a new Position object.
1460
1461 Value Position::compute_non_pawn_material(Color c) const {
1462
1463   Value value = VALUE_ZERO;
1464
1465   for (PieceType pt = KNIGHT; pt <= QUEEN; pt++)
1466       value += piece_count(c, pt) * PieceValue[Mg][pt];
1467
1468   return value;
1469 }
1470
1471
1472 /// Position::is_draw() tests whether the position is drawn by material,
1473 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1474 /// must be done by the search.
1475 template<bool SkipRepetition>
1476 bool Position::is_draw() const {
1477
1478   // Draw by material?
1479   if (   !pieces(PAWN)
1480       && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1481       return true;
1482
1483   // Draw by the 50 moves rule?
1484   if (st->rule50 > 99 && (!in_check() || MoveList<LEGAL>(*this).size()))
1485       return true;
1486
1487   // Draw by repetition?
1488   if (!SkipRepetition)
1489   {
1490       int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1491
1492       if (i <= e)
1493       {
1494           StateInfo* stp = st->previous->previous;
1495
1496           do {
1497               stp = stp->previous->previous;
1498
1499               if (stp->key == st->key)
1500                   return true;
1501
1502               i +=2;
1503
1504           } while (i <= e);
1505       }
1506   }
1507
1508   return false;
1509 }
1510
1511 // Explicit template instantiations
1512 template bool Position::is_draw<false>() const;
1513 template bool Position::is_draw<true>() const;
1514
1515
1516 /// Position::flip() flips position with the white and black sides reversed. This
1517 /// is only useful for debugging especially for finding evaluation symmetry bugs.
1518
1519 void Position::flip() {
1520
1521   const Position pos(*this);
1522
1523   clear();
1524
1525   sideToMove = ~pos.side_to_move();
1526   thisThread = pos.this_thread();
1527   nodes = pos.nodes_searched();
1528   chess960 = pos.is_chess960();
1529   startPosPly = pos.startpos_ply_counter();
1530
1531   for (Square s = SQ_A1; s <= SQ_H8; s++)
1532       if (!pos.is_empty(s))
1533           put_piece(Piece(pos.piece_on(s) ^ 8), ~s);
1534
1535   if (pos.can_castle(WHITE_OO))
1536       set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, KING_SIDE));
1537   if (pos.can_castle(WHITE_OOO))
1538       set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, QUEEN_SIDE));
1539   if (pos.can_castle(BLACK_OO))
1540       set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, KING_SIDE));
1541   if (pos.can_castle(BLACK_OOO))
1542       set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, QUEEN_SIDE));
1543
1544   if (pos.st->epSquare != SQ_NONE)
1545       st->epSquare = ~pos.st->epSquare;
1546
1547   st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
1548
1549   st->key = compute_key();
1550   st->pawnKey = compute_pawn_key();
1551   st->materialKey = compute_material_key();
1552   st->psqScore = compute_psq_score();
1553   st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
1554   st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
1555
1556   assert(pos_is_ok());
1557 }
1558
1559
1560 /// Position::pos_is_ok() performs some consitency checks for the position object.
1561 /// This is meant to be helpful when debugging.
1562
1563 bool Position::pos_is_ok(int* failedStep) const {
1564
1565   int dummy, *step = failedStep ? failedStep : &dummy;
1566
1567   // What features of the position should be verified?
1568   const bool all = false;
1569
1570   const bool debugBitboards       = all || false;
1571   const bool debugKingCount       = all || false;
1572   const bool debugKingCapture     = all || false;
1573   const bool debugCheckerCount    = all || false;
1574   const bool debugKey             = all || false;
1575   const bool debugMaterialKey     = all || false;
1576   const bool debugPawnKey         = all || false;
1577   const bool debugIncrementalEval = all || false;
1578   const bool debugNonPawnMaterial = all || false;
1579   const bool debugPieceCounts     = all || false;
1580   const bool debugPieceList       = all || false;
1581   const bool debugCastleSquares   = all || false;
1582
1583   *step = 1;
1584
1585   if (sideToMove != WHITE && sideToMove != BLACK)
1586       return false;
1587
1588   if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1589       return false;
1590
1591   if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1592       return false;
1593
1594   if ((*step)++, debugKingCount)
1595   {
1596       int kingCount[2] = {};
1597
1598       for (Square s = SQ_A1; s <= SQ_H8; s++)
1599           if (type_of(piece_on(s)) == KING)
1600               kingCount[color_of(piece_on(s))]++;
1601
1602       if (kingCount[0] != 1 || kingCount[1] != 1)
1603           return false;
1604   }
1605
1606   if ((*step)++, debugKingCapture)
1607       if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1608           return false;
1609
1610   if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1611       return false;
1612
1613   if ((*step)++, debugBitboards)
1614   {
1615       // The intersection of the white and black pieces must be empty
1616       if (pieces(WHITE) & pieces(BLACK))
1617           return false;
1618
1619       // The union of the white and black pieces must be equal to all
1620       // occupied squares
1621       if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1622           return false;
1623
1624       // Separate piece type bitboards must have empty intersections
1625       for (PieceType p1 = PAWN; p1 <= KING; p1++)
1626           for (PieceType p2 = PAWN; p2 <= KING; p2++)
1627               if (p1 != p2 && (pieces(p1) & pieces(p2)))
1628                   return false;
1629   }
1630
1631   if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1632       return false;
1633
1634   if ((*step)++, debugKey && st->key != compute_key())
1635       return false;
1636
1637   if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1638       return false;
1639
1640   if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1641       return false;
1642
1643   if ((*step)++, debugIncrementalEval && st->psqScore != compute_psq_score())
1644       return false;
1645
1646   if ((*step)++, debugNonPawnMaterial)
1647   {
1648       if (   st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1649           || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1650           return false;
1651   }
1652
1653   if ((*step)++, debugPieceCounts)
1654       for (Color c = WHITE; c <= BLACK; c++)
1655           for (PieceType pt = PAWN; pt <= KING; pt++)
1656               if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1657                   return false;
1658
1659   if ((*step)++, debugPieceList)
1660       for (Color c = WHITE; c <= BLACK; c++)
1661           for (PieceType pt = PAWN; pt <= KING; pt++)
1662               for (int i = 0; i < pieceCount[c][pt]; i++)
1663               {
1664                   if (piece_on(piece_list(c, pt)[i]) != make_piece(c, pt))
1665                       return false;
1666
1667                   if (index[piece_list(c, pt)[i]] != i)
1668                       return false;
1669               }
1670
1671   if ((*step)++, debugCastleSquares)
1672       for (Color c = WHITE; c <= BLACK; c++)
1673           for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1674           {
1675               CastleRight cr = make_castle_right(c, s);
1676
1677               if (!can_castle(cr))
1678                   continue;
1679
1680               if ((castleRightsMask[king_square(c)] & cr) != cr)
1681                   return false;
1682
1683               if (   piece_on(castleRookSquare[c][s]) != make_piece(c, ROOK)
1684                   || castleRightsMask[castleRookSquare[c][s]] != cr)
1685                   return false;
1686           }
1687
1688   *step = 0;
1689   return true;
1690 }