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