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