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