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