fd7b1ba26a02bd2c154ae1108e711517bf977f98
[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 = make_square(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 = make_square(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 = make_square(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 = make_square(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   struct ReducedStateInfo {
704     Key pawnKey, materialKey;
705     Value npMaterial[2];
706     int castleRights, rule50, pliesFromNull;
707     Score psq_score;
708     Square epSquare;
709   };
710
711   memcpy(&newSt, st, sizeof(ReducedStateInfo));
712
713   newSt.previous = st;
714   st = &newSt;
715
716   // Update side to move
717   k ^= zobSideToMove;
718
719   // Increment the 50 moves rule draw counter. Resetting it to zero in the
720   // case of a capture or a pawn move is taken care of later.
721   st->rule50++;
722   st->pliesFromNull++;
723
724   if (is_castle(m))
725   {
726       st->key = k;
727       do_castle_move<true>(m);
728       return;
729   }
730
731   Color us = sideToMove;
732   Color them = ~us;
733   Square from = from_sq(m);
734   Square to = to_sq(m);
735   Piece piece = piece_on(from);
736   PieceType pt = type_of(piece);
737   PieceType capture = is_enpassant(m) ? PAWN : type_of(piece_on(to));
738
739   assert(color_of(piece) == us);
740   assert(color_of(piece_on(to)) != us);
741   assert(capture != KING);
742
743   if (capture)
744   {
745       Square capsq = to;
746
747       // If the captured piece is a pawn, update pawn hash key, otherwise
748       // update non-pawn material.
749       if (capture == PAWN)
750       {
751           if (is_enpassant(m))
752           {
753               capsq += pawn_push(them);
754
755               assert(pt == PAWN);
756               assert(to == st->epSquare);
757               assert(relative_rank(us, to) == RANK_6);
758               assert(piece_on(to) == NO_PIECE);
759               assert(piece_on(capsq) == make_piece(them, PAWN));
760
761               board[capsq] = NO_PIECE;
762           }
763
764           st->pawnKey ^= zobrist[them][PAWN][capsq];
765       }
766       else
767           st->npMaterial[them] -= PieceValueMidgame[capture];
768
769       // Remove the captured piece
770       byTypeBB[ALL_PIECES] ^= capsq;
771       byTypeBB[capture] ^= capsq;
772       byColorBB[them] ^= capsq;
773
774       // Update piece list, move the last piece at index[capsq] position and
775       // shrink the list.
776       //
777       // WARNING: This is a not revresible operation. When we will reinsert the
778       // captured piece in undo_move() we will put it at the end of the list and
779       // not in its original place, it means index[] and pieceList[] are not
780       // guaranteed to be invariant to a do_move() + undo_move() sequence.
781       Square lastSquare = pieceList[them][capture][--pieceCount[them][capture]];
782       index[lastSquare] = index[capsq];
783       pieceList[them][capture][index[lastSquare]] = lastSquare;
784       pieceList[them][capture][pieceCount[them][capture]] = SQ_NONE;
785
786       // Update hash keys
787       k ^= zobrist[them][capture][capsq];
788       st->materialKey ^= zobrist[them][capture][pieceCount[them][capture]];
789
790       // Update incremental scores
791       st->psqScore -= pieceSquareTable[make_piece(them, capture)][capsq];
792
793       // Reset rule 50 counter
794       st->rule50 = 0;
795   }
796
797   // Update hash key
798   k ^= zobrist[us][pt][from] ^ zobrist[us][pt][to];
799
800   // Reset en passant square
801   if (st->epSquare != SQ_NONE)
802   {
803       k ^= zobEp[file_of(st->epSquare)];
804       st->epSquare = SQ_NONE;
805   }
806
807   // Update castle rights if needed
808   if (st->castleRights && (castleRightsMask[from] | castleRightsMask[to]))
809   {
810       int cr = castleRightsMask[from] | castleRightsMask[to];
811       k ^= zobCastle[st->castleRights & cr];
812       st->castleRights &= ~cr;
813   }
814
815   // Prefetch TT access as soon as we know key is updated
816   prefetch((char*)TT.first_entry(k));
817
818   // Move the piece
819   Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
820   byTypeBB[ALL_PIECES] ^= from_to_bb;
821   byTypeBB[pt] ^= from_to_bb;
822   byColorBB[us] ^= from_to_bb;
823
824   board[to] = board[from];
825   board[from] = NO_PIECE;
826
827   // Update piece lists, index[from] is not updated and becomes stale. This
828   // works as long as index[] is accessed just by known occupied squares.
829   index[to] = index[from];
830   pieceList[us][pt][index[to]] = to;
831
832   // If the moving piece is a pawn do some special extra work
833   if (pt == PAWN)
834   {
835       // Set en-passant square, only if moved pawn can be captured
836       if (   (int(to) ^ int(from)) == 16
837           && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
838       {
839           st->epSquare = Square((from + to) / 2);
840           k ^= zobEp[file_of(st->epSquare)];
841       }
842
843       if (is_promotion(m))
844       {
845           PieceType promotion = promotion_type(m);
846
847           assert(relative_rank(us, to) == RANK_8);
848           assert(promotion >= KNIGHT && promotion <= QUEEN);
849
850           // Replace the pawn with the promoted piece
851           byTypeBB[PAWN] ^= to;
852           byTypeBB[promotion] |= to;
853           board[to] = make_piece(us, promotion);
854
855           // Update piece lists, move the last pawn at index[to] position
856           // and shrink the list. Add a new promotion piece to the list.
857           Square lastSquare = pieceList[us][PAWN][--pieceCount[us][PAWN]];
858           index[lastSquare] = index[to];
859           pieceList[us][PAWN][index[lastSquare]] = lastSquare;
860           pieceList[us][PAWN][pieceCount[us][PAWN]] = SQ_NONE;
861           index[to] = pieceCount[us][promotion];
862           pieceList[us][promotion][index[to]] = to;
863
864           // Update hash keys
865           k ^= zobrist[us][PAWN][to] ^ zobrist[us][promotion][to];
866           st->pawnKey ^= zobrist[us][PAWN][to];
867           st->materialKey ^=  zobrist[us][promotion][pieceCount[us][promotion]++]
868                             ^ zobrist[us][PAWN][pieceCount[us][PAWN]];
869
870           // Update incremental score
871           st->psqScore +=  pieceSquareTable[make_piece(us, promotion)][to]
872                          - pieceSquareTable[make_piece(us, PAWN)][to];
873
874           // Update material
875           st->npMaterial[us] += PieceValueMidgame[promotion];
876       }
877
878       // Update pawn hash key
879       st->pawnKey ^= zobrist[us][PAWN][from] ^ zobrist[us][PAWN][to];
880
881       // Reset rule 50 draw counter
882       st->rule50 = 0;
883   }
884
885   // Prefetch pawn and material hash tables
886   prefetch((char*)thisThread->pawnTable.entries[st->pawnKey]);
887   prefetch((char*)thisThread->materialTable.entries[st->materialKey]);
888
889   // Update incremental scores
890   st->psqScore += psq_delta(piece, from, to);
891
892   // Set capture piece
893   st->capturedType = capture;
894
895   // Update the key with the final value
896   st->key = k;
897
898   // Update checkers bitboard, piece must be already moved
899   st->checkersBB = 0;
900
901   if (moveIsCheck)
902   {
903       if (is_special(m))
904           st->checkersBB = attackers_to(king_square(them)) & pieces(us);
905       else
906       {
907           // Direct checks
908           if (ci.checkSq[pt] & to)
909               st->checkersBB |= to;
910
911           // Discovery checks
912           if (ci.dcCandidates && (ci.dcCandidates & from))
913           {
914               if (pt != ROOK)
915                   st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
916
917               if (pt != BISHOP)
918                   st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
919           }
920       }
921   }
922
923   sideToMove = ~sideToMove;
924
925   assert(pos_is_ok());
926 }
927
928
929 /// Position::undo_move() unmakes a move. When it returns, the position should
930 /// be restored to exactly the same state as before the move was made.
931
932 void Position::undo_move(Move m) {
933
934   assert(is_ok(m));
935
936   sideToMove = ~sideToMove;
937
938   if (is_castle(m))
939   {
940       do_castle_move<false>(m);
941       return;
942   }
943
944   Color us = sideToMove;
945   Color them = ~us;
946   Square from = from_sq(m);
947   Square to = to_sq(m);
948   Piece piece = piece_on(to);
949   PieceType pt = type_of(piece);
950   PieceType capture = st->capturedType;
951
952   assert(is_empty(from));
953   assert(color_of(piece) == us);
954   assert(capture != KING);
955
956   if (is_promotion(m))
957   {
958       PieceType promotion = promotion_type(m);
959
960       assert(promotion == pt);
961       assert(relative_rank(us, to) == RANK_8);
962       assert(promotion >= KNIGHT && promotion <= QUEEN);
963
964       // Replace the promoted piece with the pawn
965       byTypeBB[promotion] ^= to;
966       byTypeBB[PAWN] |= to;
967       board[to] = make_piece(us, PAWN);
968
969       // Update piece lists, move the last promoted piece at index[to] position
970       // and shrink the list. Add a new pawn to the list.
971       Square lastSquare = pieceList[us][promotion][--pieceCount[us][promotion]];
972       index[lastSquare] = index[to];
973       pieceList[us][promotion][index[lastSquare]] = lastSquare;
974       pieceList[us][promotion][pieceCount[us][promotion]] = SQ_NONE;
975       index[to] = pieceCount[us][PAWN]++;
976       pieceList[us][PAWN][index[to]] = to;
977
978       pt = PAWN;
979   }
980
981   // Put the piece back at the source square
982   Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
983   byTypeBB[ALL_PIECES] ^= from_to_bb;
984   byTypeBB[pt] ^= from_to_bb;
985   byColorBB[us] ^= from_to_bb;
986
987   board[from] = board[to];
988   board[to] = NO_PIECE;
989
990   // Update piece lists, index[to] is not updated and becomes stale. This
991   // works as long as index[] is accessed just by known occupied squares.
992   index[from] = index[to];
993   pieceList[us][pt][index[from]] = from;
994
995   if (capture)
996   {
997       Square capsq = to;
998
999       if (is_enpassant(m))
1000       {
1001           capsq -= pawn_push(us);
1002
1003           assert(pt == PAWN);
1004           assert(to == st->previous->epSquare);
1005           assert(relative_rank(us, to) == RANK_6);
1006           assert(piece_on(capsq) == NO_PIECE);
1007       }
1008
1009       // Restore the captured piece
1010       byTypeBB[ALL_PIECES] |= capsq;
1011       byTypeBB[capture] |= capsq;
1012       byColorBB[them] |= capsq;
1013
1014       board[capsq] = make_piece(them, capture);
1015
1016       // Update piece list, add a new captured piece in capsq square
1017       index[capsq] = pieceCount[them][capture]++;
1018       pieceList[them][capture][index[capsq]] = capsq;
1019   }
1020
1021   // Finally point our state pointer back to the previous state
1022   st = st->previous;
1023
1024   assert(pos_is_ok());
1025 }
1026
1027
1028 /// Position::do_castle_move() is a private method used to do/undo a castling
1029 /// move. Note that castling moves are encoded as "king captures friendly rook"
1030 /// moves, for instance white short castling in a non-Chess960 game is encoded
1031 /// as e1h1.
1032 template<bool Do>
1033 void Position::do_castle_move(Move m) {
1034
1035   assert(is_ok(m));
1036   assert(is_castle(m));
1037
1038   Square kto, kfrom, rfrom, rto, kAfter, rAfter;
1039
1040   Color us = sideToMove;
1041   Square kBefore = from_sq(m);
1042   Square rBefore = to_sq(m);
1043
1044   // Find after-castle squares for king and rook
1045   if (rBefore > kBefore) // O-O
1046   {
1047       kAfter = relative_square(us, SQ_G1);
1048       rAfter = relative_square(us, SQ_F1);
1049   }
1050   else // O-O-O
1051   {
1052       kAfter = relative_square(us, SQ_C1);
1053       rAfter = relative_square(us, SQ_D1);
1054   }
1055
1056   kfrom = Do ? kBefore : kAfter;
1057   rfrom = Do ? rBefore : rAfter;
1058
1059   kto = Do ? kAfter : kBefore;
1060   rto = Do ? rAfter : rBefore;
1061
1062   assert(piece_on(kfrom) == make_piece(us, KING));
1063   assert(piece_on(rfrom) == make_piece(us, ROOK));
1064
1065   // Move the pieces, with some care; in chess960 could be kto == rfrom
1066   Bitboard k_from_to_bb = SquareBB[kfrom] ^ SquareBB[kto];
1067   Bitboard r_from_to_bb = SquareBB[rfrom] ^ SquareBB[rto];
1068   byTypeBB[KING] ^= k_from_to_bb;
1069   byTypeBB[ROOK] ^= r_from_to_bb;
1070   byTypeBB[ALL_PIECES] ^= k_from_to_bb ^ r_from_to_bb;
1071   byColorBB[us] ^= k_from_to_bb ^ r_from_to_bb;
1072
1073   // Update board
1074   Piece king = make_piece(us, KING);
1075   Piece rook = make_piece(us, ROOK);
1076   board[kfrom] = board[rfrom] = NO_PIECE;
1077   board[kto] = king;
1078   board[rto] = rook;
1079
1080   // Update piece lists
1081   pieceList[us][KING][index[kfrom]] = kto;
1082   pieceList[us][ROOK][index[rfrom]] = rto;
1083   int tmp = index[rfrom]; // In Chess960 could be kto == rfrom
1084   index[kto] = index[kfrom];
1085   index[rto] = tmp;
1086
1087   if (Do)
1088   {
1089       // Reset capture field
1090       st->capturedType = NO_PIECE_TYPE;
1091
1092       // Update incremental scores
1093       st->psqScore += psq_delta(king, kfrom, kto);
1094       st->psqScore += psq_delta(rook, rfrom, rto);
1095
1096       // Update hash key
1097       st->key ^= zobrist[us][KING][kfrom] ^ zobrist[us][KING][kto];
1098       st->key ^= zobrist[us][ROOK][rfrom] ^ zobrist[us][ROOK][rto];
1099
1100       // Clear en passant square
1101       if (st->epSquare != SQ_NONE)
1102       {
1103           st->key ^= zobEp[file_of(st->epSquare)];
1104           st->epSquare = SQ_NONE;
1105       }
1106
1107       // Update castling rights
1108       st->key ^= zobCastle[st->castleRights & castleRightsMask[kfrom]];
1109       st->castleRights &= ~castleRightsMask[kfrom];
1110
1111       // Update checkers BB
1112       st->checkersBB = attackers_to(king_square(~us)) & pieces(us);
1113
1114       sideToMove = ~sideToMove;
1115   }
1116   else
1117       // Undo: point our state pointer back to the previous state
1118       st = st->previous;
1119
1120   assert(pos_is_ok());
1121 }
1122
1123
1124 /// Position::do_null_move() is used to do/undo a "null move": It flips the side
1125 /// to move and updates the hash key without executing any move on the board.
1126 template<bool Do>
1127 void Position::do_null_move(StateInfo& backupSt) {
1128
1129   assert(!in_check());
1130
1131   // Back up the information necessary to undo the null move to the supplied
1132   // StateInfo object. Note that differently from normal case here backupSt
1133   // is actually used as a backup storage not as the new state. This reduces
1134   // the number of fields to be copied.
1135   StateInfo* src = Do ? st : &backupSt;
1136   StateInfo* dst = Do ? &backupSt : st;
1137
1138   dst->key      = src->key;
1139   dst->epSquare = src->epSquare;
1140   dst->psqScore = src->psqScore;
1141   dst->rule50   = src->rule50;
1142   dst->pliesFromNull = src->pliesFromNull;
1143
1144   sideToMove = ~sideToMove;
1145
1146   if (Do)
1147   {
1148       if (st->epSquare != SQ_NONE)
1149           st->key ^= zobEp[file_of(st->epSquare)];
1150
1151       st->key ^= zobSideToMove;
1152       prefetch((char*)TT.first_entry(st->key));
1153
1154       st->epSquare = SQ_NONE;
1155       st->rule50++;
1156       st->pliesFromNull = 0;
1157   }
1158
1159   assert(pos_is_ok());
1160 }
1161
1162 // Explicit template instantiations
1163 template void Position::do_null_move<false>(StateInfo& backupSt);
1164 template void Position::do_null_move<true>(StateInfo& backupSt);
1165
1166
1167 /// Position::see() is a static exchange evaluator: It tries to estimate the
1168 /// material gain or loss resulting from a move. There are three versions of
1169 /// this function: One which takes a destination square as input, one takes a
1170 /// move, and one which takes a 'from' and a 'to' square. The function does
1171 /// not yet understand promotions captures.
1172
1173 int Position::see_sign(Move m) const {
1174
1175   assert(is_ok(m));
1176
1177   // Early return if SEE cannot be negative because captured piece value
1178   // is not less then capturing one. Note that king moves always return
1179   // here because king midgame value is set to 0.
1180   if (PieceValueMidgame[piece_on(to_sq(m))] >= PieceValueMidgame[piece_moved(m)])
1181       return 1;
1182
1183   return see(m);
1184 }
1185
1186 int Position::see(Move m) const {
1187
1188   Square from, to;
1189   Bitboard occ, attackers, stmAttackers, b;
1190   int swapList[32], slIndex = 1;
1191   PieceType capturedType, pt;
1192   Color stm;
1193
1194   assert(is_ok(m));
1195
1196   // As castle moves are implemented as capturing the rook, they have
1197   // SEE == RookValueMidgame most of the times (unless the rook is under
1198   // attack).
1199   if (is_castle(m))
1200       return 0;
1201
1202   from = from_sq(m);
1203   to = to_sq(m);
1204   capturedType = type_of(piece_on(to));
1205   occ = pieces();
1206
1207   // Handle en passant moves
1208   if (is_enpassant(m))
1209   {
1210       Square capQq = to - pawn_push(sideToMove);
1211
1212       assert(!capturedType);
1213       assert(type_of(piece_on(capQq)) == PAWN);
1214
1215       // Remove the captured pawn
1216       occ ^= capQq;
1217       capturedType = PAWN;
1218   }
1219
1220   // Find all attackers to the destination square, with the moving piece
1221   // removed, but possibly an X-ray attacker added behind it.
1222   occ ^= from;
1223   attackers = attackers_to(to, occ);
1224
1225   // If the opponent has no attackers we are finished
1226   stm = ~color_of(piece_on(from));
1227   stmAttackers = attackers & pieces(stm);
1228   if (!stmAttackers)
1229       return PieceValueMidgame[capturedType];
1230
1231   // The destination square is defended, which makes things rather more
1232   // difficult to compute. We proceed by building up a "swap list" containing
1233   // the material gain or loss at each stop in a sequence of captures to the
1234   // destination square, where the sides alternately capture, and always
1235   // capture with the least valuable piece. After each capture, we look for
1236   // new X-ray attacks from behind the capturing piece.
1237   swapList[0] = PieceValueMidgame[capturedType];
1238   capturedType = type_of(piece_on(from));
1239
1240   do {
1241       // Locate the least valuable attacker for the side to move. The loop
1242       // below looks like it is potentially infinite, but it isn't. We know
1243       // that the side to move still has at least one attacker left.
1244       for (pt = PAWN; !(stmAttackers & pieces(pt)); pt++)
1245           assert(pt < KING);
1246
1247       // Remove the attacker we just found from the 'occupied' bitboard,
1248       // and scan for new X-ray attacks behind the attacker.
1249       b = stmAttackers & pieces(pt);
1250       occ ^= (b & (~b + 1));
1251       attackers |=  (attacks_bb<ROOK>(to, occ)   & pieces(ROOK, QUEEN))
1252                   | (attacks_bb<BISHOP>(to, occ) & pieces(BISHOP, QUEEN));
1253
1254       attackers &= occ; // Cut out pieces we've already done
1255
1256       // Add the new entry to the swap list
1257       assert(slIndex < 32);
1258       swapList[slIndex] = -swapList[slIndex - 1] + PieceValueMidgame[capturedType];
1259       slIndex++;
1260
1261       // Remember the value of the capturing piece, and change the side to
1262       // move before beginning the next iteration.
1263       capturedType = pt;
1264       stm = ~stm;
1265       stmAttackers = attackers & pieces(stm);
1266
1267       // Stop before processing a king capture
1268       if (capturedType == KING && stmAttackers)
1269       {
1270           assert(slIndex < 32);
1271           swapList[slIndex++] = QueenValueMidgame*10;
1272           break;
1273       }
1274   } while (stmAttackers);
1275
1276   // Having built the swap list, we negamax through it to find the best
1277   // achievable score from the point of view of the side to move.
1278   while (--slIndex)
1279       swapList[slIndex-1] = std::min(-swapList[slIndex], swapList[slIndex-1]);
1280
1281   return swapList[0];
1282 }
1283
1284
1285 /// Position::clear() erases the position object to a pristine state, with an
1286 /// empty board, white to move, and no castling rights.
1287
1288 void Position::clear() {
1289
1290   memset(this, 0, sizeof(Position));
1291   startState.epSquare = SQ_NONE;
1292   st = &startState;
1293
1294   for (int i = 0; i < 8; i++)
1295       for (int j = 0; j < 16; j++)
1296           pieceList[0][i][j] = pieceList[1][i][j] = SQ_NONE;
1297
1298   for (Square sq = SQ_A1; sq <= SQ_H8; sq++)
1299       board[sq] = NO_PIECE;
1300 }
1301
1302
1303 /// Position::put_piece() puts a piece on the given square of the board,
1304 /// updating the board array, pieces list, bitboards, and piece counts.
1305
1306 void Position::put_piece(Piece p, Square s) {
1307
1308   Color c = color_of(p);
1309   PieceType pt = type_of(p);
1310
1311   board[s] = p;
1312   index[s] = pieceCount[c][pt]++;
1313   pieceList[c][pt][index[s]] = s;
1314
1315   byTypeBB[ALL_PIECES] |= s;
1316   byTypeBB[pt] |= s;
1317   byColorBB[c] |= s;
1318 }
1319
1320
1321 /// Position::compute_key() computes the hash key of the position. The hash
1322 /// key is usually updated incrementally as moves are made and unmade, the
1323 /// compute_key() function is only used when a new position is set up, and
1324 /// to verify the correctness of the hash key when running in debug mode.
1325
1326 Key Position::compute_key() const {
1327
1328   Key k = zobCastle[st->castleRights];
1329
1330   for (Bitboard b = pieces(); b; )
1331   {
1332       Square s = pop_1st_bit(&b);
1333       k ^= zobrist[color_of(piece_on(s))][type_of(piece_on(s))][s];
1334   }
1335
1336   if (ep_square() != SQ_NONE)
1337       k ^= zobEp[file_of(ep_square())];
1338
1339   if (sideToMove == BLACK)
1340       k ^= zobSideToMove;
1341
1342   return k;
1343 }
1344
1345
1346 /// Position::compute_pawn_key() computes the hash key of the position. The
1347 /// hash key is usually updated incrementally as moves are made and unmade,
1348 /// the compute_pawn_key() function is only used when a new position is set
1349 /// up, and to verify the correctness of the pawn hash key when running in
1350 /// debug mode.
1351
1352 Key Position::compute_pawn_key() const {
1353
1354   Key k = 0;
1355
1356   for (Bitboard b = pieces(PAWN); b; )
1357   {
1358       Square s = pop_1st_bit(&b);
1359       k ^= zobrist[color_of(piece_on(s))][PAWN][s];
1360   }
1361
1362   return k;
1363 }
1364
1365
1366 /// Position::compute_material_key() computes the hash key of the position.
1367 /// The hash key is usually updated incrementally as moves are made and unmade,
1368 /// the compute_material_key() function is only used when a new position is set
1369 /// up, and to verify the correctness of the material hash key when running in
1370 /// debug mode.
1371
1372 Key Position::compute_material_key() const {
1373
1374   Key k = 0;
1375
1376   for (Color c = WHITE; c <= BLACK; c++)
1377       for (PieceType pt = PAWN; pt <= QUEEN; pt++)
1378           for (int cnt = 0; cnt < piece_count(c, pt); cnt++)
1379               k ^= zobrist[c][pt][cnt];
1380
1381   return k;
1382 }
1383
1384
1385 /// Position::compute_psq_score() computes the incremental scores for the middle
1386 /// game and the endgame. These functions are used to initialize the incremental
1387 /// scores when a new position is set up, and to verify that the scores are correctly
1388 /// updated by do_move and undo_move when the program is running in debug mode.
1389 Score Position::compute_psq_score() const {
1390
1391   Score score = SCORE_ZERO;
1392
1393   for (Bitboard b = pieces(); b; )
1394   {
1395       Square s = pop_1st_bit(&b);
1396       score += pieceSquareTable[piece_on(s)][s];
1397   }
1398
1399   return score;
1400 }
1401
1402
1403 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1404 /// game material value for the given side. Material values are updated
1405 /// incrementally during the search, this function is only used while
1406 /// initializing a new Position object.
1407
1408 Value Position::compute_non_pawn_material(Color c) const {
1409
1410   Value value = VALUE_ZERO;
1411
1412   for (PieceType pt = KNIGHT; pt <= QUEEN; pt++)
1413       value += piece_count(c, pt) * PieceValueMidgame[pt];
1414
1415   return value;
1416 }
1417
1418
1419 /// Position::is_draw() tests whether the position is drawn by material,
1420 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1421 /// must be done by the search.
1422 template<bool SkipRepetition>
1423 bool Position::is_draw() const {
1424
1425   // Draw by material?
1426   if (   !pieces(PAWN)
1427       && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMidgame))
1428       return true;
1429
1430   // Draw by the 50 moves rule?
1431   if (st->rule50 > 99 && (!in_check() || MoveList<MV_LEGAL>(*this).size()))
1432       return true;
1433
1434   // Draw by repetition?
1435   if (!SkipRepetition)
1436   {
1437       int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1438
1439       if (i <= e)
1440       {
1441           StateInfo* stp = st->previous->previous;
1442
1443           do {
1444               stp = stp->previous->previous;
1445
1446               if (stp->key == st->key)
1447                   return true;
1448
1449               i +=2;
1450
1451           } while (i <= e);
1452       }
1453   }
1454
1455   return false;
1456 }
1457
1458 // Explicit template instantiations
1459 template bool Position::is_draw<false>() const;
1460 template bool Position::is_draw<true>() const;
1461
1462
1463 /// Position::init() is a static member function which initializes at startup
1464 /// the various arrays used to compute hash keys and the piece square tables.
1465 /// The latter is a two-step operation: First, the white halves of the tables
1466 /// are copied from PSQT[] tables. Second, the black halves of the tables are
1467 /// initialized by flipping and changing the sign of the white scores.
1468
1469 void Position::init() {
1470
1471   RKISS rk;
1472
1473   for (Color c = WHITE; c <= BLACK; c++)
1474       for (PieceType pt = PAWN; pt <= KING; pt++)
1475           for (Square s = SQ_A1; s <= SQ_H8; s++)
1476               zobrist[c][pt][s] = rk.rand<Key>();
1477
1478   for (File f = FILE_A; f <= FILE_H; f++)
1479       zobEp[f] = rk.rand<Key>();
1480
1481   for (int cr = CASTLES_NONE; cr <= ALL_CASTLES; cr++)
1482   {
1483       Bitboard b = cr;
1484       while (b)
1485       {
1486           Key k = zobCastle[1ULL << pop_1st_bit(&b)];
1487           zobCastle[cr] ^= k ? k : rk.rand<Key>();
1488       }
1489   }
1490
1491   zobSideToMove = rk.rand<Key>();
1492   zobExclusion  = rk.rand<Key>();
1493
1494   for (PieceType pt = PAWN; pt <= KING; pt++)
1495   {
1496       Score v = make_score(PieceValueMidgame[pt], PieceValueEndgame[pt]);
1497
1498       for (Square s = SQ_A1; s <= SQ_H8; s++)
1499       {
1500           pieceSquareTable[make_piece(WHITE, pt)][ s] =  (v + PSQT[pt][s]);
1501           pieceSquareTable[make_piece(BLACK, pt)][~s] = -(v + PSQT[pt][s]);
1502       }
1503   }
1504 }
1505
1506
1507 /// Position::flip() flips position with the white and black sides reversed. This
1508 /// is only useful for debugging especially for finding evaluation symmetry bugs.
1509
1510 void Position::flip() {
1511
1512   const Position pos(*this);
1513
1514   clear();
1515
1516   sideToMove = ~pos.side_to_move();
1517   thisThread = pos.this_thread();
1518   nodes = pos.nodes_searched();
1519   chess960 = pos.is_chess960();
1520   startPosPly = pos.startpos_ply_counter();
1521
1522   for (Square s = SQ_A1; s <= SQ_H8; s++)
1523       if (!pos.is_empty(s))
1524           put_piece(Piece(pos.piece_on(s) ^ 8), ~s);
1525
1526   if (pos.can_castle(WHITE_OO))
1527       set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, KING_SIDE));
1528   if (pos.can_castle(WHITE_OOO))
1529       set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, QUEEN_SIDE));
1530   if (pos.can_castle(BLACK_OO))
1531       set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, KING_SIDE));
1532   if (pos.can_castle(BLACK_OOO))
1533       set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, QUEEN_SIDE));
1534
1535   if (pos.st->epSquare != SQ_NONE)
1536       st->epSquare = ~pos.st->epSquare;
1537
1538   st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
1539
1540   st->key = compute_key();
1541   st->pawnKey = compute_pawn_key();
1542   st->materialKey = compute_material_key();
1543   st->psqScore = compute_psq_score();
1544   st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
1545   st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
1546
1547   assert(pos_is_ok());
1548 }
1549
1550
1551 /// Position::pos_is_ok() performs some consitency checks for the position object.
1552 /// This is meant to be helpful when debugging.
1553
1554 bool Position::pos_is_ok(int* failedStep) const {
1555
1556   int dummy, *step = failedStep ? failedStep : &dummy;
1557
1558   // What features of the position should be verified?
1559   const bool all = false;
1560
1561   const bool debugBitboards       = all || false;
1562   const bool debugKingCount       = all || false;
1563   const bool debugKingCapture     = all || false;
1564   const bool debugCheckerCount    = all || false;
1565   const bool debugKey             = all || false;
1566   const bool debugMaterialKey     = all || false;
1567   const bool debugPawnKey         = all || false;
1568   const bool debugIncrementalEval = all || false;
1569   const bool debugNonPawnMaterial = all || false;
1570   const bool debugPieceCounts     = all || false;
1571   const bool debugPieceList       = all || false;
1572   const bool debugCastleSquares   = all || false;
1573
1574   *step = 1;
1575
1576   if (sideToMove != WHITE && sideToMove != BLACK)
1577       return false;
1578
1579   if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1580       return false;
1581
1582   if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1583       return false;
1584
1585   if ((*step)++, debugKingCount)
1586   {
1587       int kingCount[2] = {};
1588
1589       for (Square s = SQ_A1; s <= SQ_H8; s++)
1590           if (type_of(piece_on(s)) == KING)
1591               kingCount[color_of(piece_on(s))]++;
1592
1593       if (kingCount[0] != 1 || kingCount[1] != 1)
1594           return false;
1595   }
1596
1597   if ((*step)++, debugKingCapture)
1598       if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1599           return false;
1600
1601   if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1602       return false;
1603
1604   if ((*step)++, debugBitboards)
1605   {
1606       // The intersection of the white and black pieces must be empty
1607       if (pieces(WHITE) & pieces(BLACK))
1608           return false;
1609
1610       // The union of the white and black pieces must be equal to all
1611       // occupied squares
1612       if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1613           return false;
1614
1615       // Separate piece type bitboards must have empty intersections
1616       for (PieceType p1 = PAWN; p1 <= KING; p1++)
1617           for (PieceType p2 = PAWN; p2 <= KING; p2++)
1618               if (p1 != p2 && (pieces(p1) & pieces(p2)))
1619                   return false;
1620   }
1621
1622   if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1623       return false;
1624
1625   if ((*step)++, debugKey && st->key != compute_key())
1626       return false;
1627
1628   if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1629       return false;
1630
1631   if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1632       return false;
1633
1634   if ((*step)++, debugIncrementalEval && st->psqScore != compute_psq_score())
1635       return false;
1636
1637   if ((*step)++, debugNonPawnMaterial)
1638   {
1639       if (   st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1640           || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1641           return false;
1642   }
1643
1644   if ((*step)++, debugPieceCounts)
1645       for (Color c = WHITE; c <= BLACK; c++)
1646           for (PieceType pt = PAWN; pt <= KING; pt++)
1647               if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1648                   return false;
1649
1650   if ((*step)++, debugPieceList)
1651       for (Color c = WHITE; c <= BLACK; c++)
1652           for (PieceType pt = PAWN; pt <= KING; pt++)
1653               for (int i = 0; i < pieceCount[c][pt]; i++)
1654               {
1655                   if (piece_on(piece_list(c, pt)[i]) != make_piece(c, pt))
1656                       return false;
1657
1658                   if (index[piece_list(c, pt)[i]] != i)
1659                       return false;
1660               }
1661
1662   if ((*step)++, debugCastleSquares)
1663       for (Color c = WHITE; c <= BLACK; c++)
1664           for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1665           {
1666               CastleRight cr = make_castle_right(c, s);
1667
1668               if (!can_castle(cr))
1669                   continue;
1670
1671               if ((castleRightsMask[king_square(c)] & cr) != cr)
1672                   return false;
1673
1674               if (   piece_on(castleRookSquare[c][s]) != make_piece(c, ROOK)
1675                   || castleRightsMask[castleRookSquare[c][s]] != cr)
1676                   return false;
1677           }
1678
1679   *step = 0;
1680   return true;
1681 }