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