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