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