Scid  4.6.5
engine.cpp
Go to the documentation of this file.
1 //////////////////////////////////////////////////////////////////////
2 //
3 // FILE: engine.cpp
4 // Engine class methods
5 //
6 // Part of: Scid (Shane's Chess Information Database)
7 // Version: 3.5
8 //
9 // Notice: Copyright (c) 2002-2003 Shane Hudson. All rights reserved.
10 //
11 // Author: Shane Hudson (sgh@users.sourceforge.net)
12 //
13 //////////////////////////////////////////////////////////////////////
14 
15 #include "attacks.h"
16 #include "engine.h"
17 #include "recog.h"
18 #include "sqmove.h"
19 #include "sqlist.h"
20 #include <algorithm>
21 
22 // The Engine class implements the Scid built-in chess engine.
23 // See engine.h for details.
24 
25 
26 // Evaluation constants:
27 
28 static const int Infinity = 32000;
29 static const int KingValue = 10000;
30 static const int QueenValue = 900;
31 static const int RookValue = 500;
32 static const int BishopValue = 300;
33 static const int KnightValue = 300;
34 static const int PawnValue = 100;
35 
36 // EndgameValue, MiddlegameValue:
37 // If the combined material score of pieces on both sides (excluding
38 // kings and pawns) is less than this value, we are in an endgame.
39 // If it is greater than MiddlegameValue, we use middlegame scoring.
40 // For anything in between, the score will be a weighted average of
41 // the middlegame and endgame scores.
42 //
43 static const int EndgameValue = 2400;
44 static const int MiddlegameValue = 4000;
45 
46 // Bonuses and penalties:
47 //
48 static const int RookHalfOpenFile = 8;
49 static const int RookOpenFile = 20;
50 static const int RookPasserFile = 25; // Rook on passed pawn file.
51 static const int RookOnSeventh = 25; // Rook on its 7th rank.
52 static const int DoubledRooks = 20; // Two rooks on same file.
53 static const int RookEyesKing = 12; // Attacks squares near enemy king.
54 static const int KingTrapsRook = 35; // E.g. King on f1, Rook on h1
55 static const int DoubledPawn = 8;
56 static const int IsolatedPawn = 16;
57 static const int BackwardPawn = 10; // Pawn at base of pawn chain.
58 // static const int DispersedPawn = 10; // Not in pawn chain/duo. (Unused)
59 static const int BlockedHomePawn = 15; // Blocked pawn on d2/e2/d7/e7.
60 static const int BishopPair = 25; // Pair of bishops.
61 static const int BishopEyesKing = 12; // Bishop targets enemy king.
62 static const int BishopTrapped = 120; // E.g. Bxa7? ...b6!
63 static const int KnightOutpost = 15; // 4th/5th/6th rank outpost.
64 static const int KnightBadEndgame = 30; // Enemy pawns on both wings.
65 static const int BadPieceTrade = 80; // Bad trade, e.g. minor for pawns.
66 static const int CanCastle = 10; // Bonus for castling rights.
67 static const int Development = 8; // Moved minor pieces in opening.
68 static const int CentralPawnPair = 15; // For d4/d5 + e4/e5 pawns.
69 static const int CoverPawn = 12; // Pawn cover for king.
70 static const int PassedPawnRank[8] = {
71 // 1 2 3 4 5 6 7 8th rank
72  0, 10, 15, 25, 50, 80, 120, 0
73 };
74 
75 // Bishops (and rooks in endings) need to be mobile to be useful:
76 static const int BishopMobility[16] = {
77  // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
78  -20, -15, -10, -6, -3, 0, 3, 6, 9, 12, 15, 15, 15, 15, 15, 15
79 };
80 static const int RookEndgameMobility[16] = {
81  // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
82  -25, -20, -15, -10, -5, 2, 0, 2, 4, 6, 8, 8, 8, 8, 8, 8
83 };
84 
85 // Piece distance to enemy king bonuses: 1 2 3 4 5 6 7
86 static const int KnightKingDist [8] = { 0, 10, 14, 10, 5, 2, 0, 0 };
87 static const int BishopKingDist [8] = { 0, 8, 6, 4, 2, 1, 0, 0 };
88 static const int RookKingDist [8] = { 0, 8, 6, 4, 2, 1, 0, 0 };
89 static const int QueenKingDist [8] = { 0, 15, 12, 9, 6, 3, 0, 0 };
90 
91 // LazyEvalMargin
92 // A score that is further than this margin outside the current
93 // alpha-beta window after material evaluation is returned as-is.
94 // A larger margin is used for endgames (especially pawn endings)
95 // since positional bonuses can be much larger for them.
96 static const int LazyEvalMargin = 250;
97 static const int LazyEvalEndingMargin = 400;
98 static const int LazyEvalPawnEndingMargin = 800;
99 
100 // NullMoveReduction:
101 // The default reduced depth for a null move search.
102 static const int NullMoveReduction = 2;
103 
104 // AspirationWindow:
105 // The window around the score of the previous depth iteration
106 // when searching at the root.
107 static const int AspirationWindow = 35;
108 
109 // PawnSquare:
110 // Gives bonuses to advanced pawns, especially in the centre.
111 static const int
112 PawnSquare [64] = {
113  0, 0, 0, 0, 0, 0, 0, 0, // A8 - H8
114  4, 8, 12, 16, 16, 12, 8, 4,
115  4, 8, 12, 16, 16, 12, 8, 4,
116  3, 6, 9, 12, 12, 9, 6, 3,
117  2, 4, 6, 8, 8, 6, 4, 2,
118  1, 2, 3, 4, 4, 3, 2, 1,
119  0, 0, 0, -4, -4, 0, 0, 0,
120  0, 0, 0, 0, 0, 0, 0, 0 // A1 - H1
121 };
122 
123 // PawnStorm:
124 // Bonus when side is castled queenside and opponent is
125 // castled kingside. Gives a bonus for own sheltering pawns
126 // and a penalty for pawns on the opposing wing to make them
127 // disposable and encourage them to move forwards.
128 static const int
129 PawnStorm [64] = {
130  0, 0, 0, 0, 0, 0, 0, 0, // A8 - H8
131  0, 0, 0, 0, 2, 2, 2, 2,
132  0, 0, 0, 0, 4, 2, 2, 2,
133  0, 0, 0, 4, 6, 0, 0, 0,
134  4, 4, 4, 4, 4, -4, -4, -4,
135  8, 8, 8, 0, 0, -8, -8, -8,
136  12, 12, 12, 0, 0, -12, -12, -12,
137  0, 0, 0, 0, 0, 0, 0, 0 // A1 - H1
138 };
139 
140 // KnightSquare:
141 // Rewards well-placed knights.
142 static const int
143 KnightSquare [64] = {
144  -24, -12, -6, -6, -6, -6, -12, -24,
145  -8, 0, 0, 0, 0, 0, 0, -8,
146  -6, 5, 10, 10, 10, 10, 5, -6,
147  -6, 0, 10, 10, 10, 10, 0, -6,
148  -6, 0, 5, 8, 8, 5, 0, -6,
149  -6, 0, 5, 5, 5, 5, 0, -6,
150  -6, 0, 0, 0, 0, 0, 0, -8,
151  -10, -8, -5, -6, -6, -6, -6, -10
152 };
153 
154 // BishopSquare:
155 // Bonus array for bishops.
156 static const int
157 BishopSquare [64] = {
158  -10, -5, 0, 0, 0, 0, -5, -10,
159  -5, 8, 0, 5, 5, 0, 8, -5,
160  0, 0, 5, 5, 5, 5, 0, 0,
161  0, 5, 10, 5, 5, 10, 5, 0,
162  0, 5, 10, 5, 5, 10, 5, 0,
163  0, 0, 5, 5, 5, 5, 0, 0,
164  -5, 8, 0, 5, 5, 0, 8, -5,
165  -10, -5, -2, -2, -2, -2, -5, -10
166 };
167 
168 // RookFile:
169 // Bonus array for Rooks, by file.
170 static const int /* a b c d e f g h */
171 RookFile [8] = { 0, 0, 4, 8, 8, 4, 0, 0 };
172 
173 // QueenSquare:
174 // Bonus array for Queens.
175 static const int
176 QueenSquare [64] = {
177  -5, 0, 0, 0, 0, 0, 0, -5, // A8 - H8
178  -5, 0, 3, 3, 3, 3, 0, -5,
179  0, 3, 6, 9, 9, 6, 3, 0,
180  0, 3, 9, 12, 12, 9, 3, 0,
181  -5, 3, 9, 12, 12, 9, 3, -5,
182  -5, 3, 6, 9, 9, 6, 3, -5,
183  -5, 0, 3, 3, 3, 3, 0, -5,
184  -10, -5, 0, 0, 0, 0, -5, -10 // A1 - H1
185 };
186 
187 // KingSquare:
188 // Bonus array for kings in the opening and middlegame.
189 static const int
190 KingSquare [64] = {
191  -50, -50, -50, -50, -50, -50, -50, -50,
192  -50, -50, -50, -50, -50, -50, -50, -50,
193  -50, -50, -50, -50, -50, -50, -50, -50,
194  -50, -50, -50, -60, -60, -50, -50, -50,
195  -40, -40, -40, -60, -60, -40, -40, -40,
196  -15, -15, -15, -20, -20, -15, -15, -15,
197  5, 5, 0, 0, 0, 0, 5, 5,
198  20, 20, 15, 5, 5, 5, 20, 20
199 };
200 
201 // EndgameKingSquare:
202 // Rewards King centralisation in endgames.
203 // TODO: Add separate king square tables for endgames where all
204 // pawns are on one side of the board.
205 static const int
206 KingEndgameSquare [64] = {
207  -10, -5, 0, 5, 5, 0, -5, -10,
208  -5, 0, 5, 10, 10, 5, 0, -5,
209  0, 5, 10, 15, 15, 10, 5, 0,
210  5, 10, 15, 20, 20, 15, 10, 5,
211  5, 10, 15, 20, 20, 15, 10, 5,
212  0, 5, 10, 15, 15, 10, 5, 0,
213  -5, 0, 5, 10, 10, 5, 0, -5,
214  -10, -5, 0, 5, 5, 0, -5, -10
215 };
216 
217 static const int
218 pieceValues [8] = {
219  0, // Invalid
220  KingValue,
221  QueenValue,
222  RookValue,
223  BishopValue,
224  KnightValue,
225  PawnValue,
226  0 // Empty
227 };
228 
229 inline int
230 Engine::PieceValue (pieceT piece)
231 {
232  return pieceValues[piece_Type(piece)];
233 }
234 
235 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
236 // isOutpost
237 // Returns true if the square is on the 4th/5th/6th rank (3rd/4th/5th
238 // for Black) and cannot be attacked by an enemy pawn.
239 static bool
240 isOutpost (const pieceT * board, squareT sq, colorT color)
241 {
242  pieceT enemyPawn = piece_Make (color_Flip(color), PAWN);
243  rankT rank = square_Rank(sq);
244  fyleT fyle = square_Fyle(sq);
245 
246  // Build the list of squares to check for enemy pawns:
247  SquareList squares;
248  if (color == WHITE) {
249  if (rank < RANK_4 || rank > RANK_6) { return false; }
250  if (fyle > A_FYLE) {
251  squares.Add(square_Make(fyle-1,RANK_7));
252  if (rank == RANK_5) { squares.Add(square_Make(fyle-1,RANK_6)); }
253  }
254  if (fyle < H_FYLE) {
255  squares.Add(square_Make(fyle+1,RANK_7));
256  if (rank == RANK_5) { squares.Add(square_Make(fyle+1,RANK_6)); }
257  }
258  } else {
259  if (rank < RANK_3 || rank > RANK_5) { return false; }
260  if (fyle > A_FYLE) {
261  squares.Add(square_Make(fyle-1,RANK_2));
262  if (rank == RANK_4) { squares.Add(square_Make(fyle-1,RANK_3)); }
263  }
264  if (fyle < H_FYLE) {
265  squares.Add(square_Make(fyle+1,RANK_2));
266  if (rank == RANK_4) { squares.Add(square_Make(fyle+1,RANK_3)); }
267  }
268  }
269 
270  // Now check each square for an enemy pawn:
271  for (uint i=0; i < squares.Size(); i++) {
272  if (board[squares.Get(i)] == enemyPawn) { return false; }
273  }
274  return true;
275 }
276 
277 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
278 // Engine::Score
279 // Returns a score in centipawns for the current engine position,
280 // from the perspective of the side to move.
281 int
283 {
284  // Look for a recognized ending with an exact score:
285  int recog = Recognizer::Recognize(&Pos);
286  if (recogFlag(recog) == SCORE_EXACT) { return recogScore(recog); }
287 
288  return Score (-Infinity, Infinity);
289 }
290 
291 static uint nScoreCalls = 0;
292 static uint nScoreFull = 0;
293 
294 inline int
295 Engine::ScoreWhiteMaterial (void)
296 {
297  byte * pieceCount = Pos.GetMaterial();
298  return pieceCount[WQ] * QueenValue + pieceCount[WR] * RookValue
299  + pieceCount[WB] * BishopValue + pieceCount[WN] * KnightValue
300  + pieceCount[WP] * PawnValue;
301 }
302 
303 inline int
304 Engine::ScoreBlackMaterial (void)
305 {
306  byte * pieceCount = Pos.GetMaterial();
307  return pieceCount[BQ] * QueenValue + pieceCount[BR] * RookValue
308  + pieceCount[BB] * BishopValue + pieceCount[BN] * KnightValue
309  + pieceCount[BP] * PawnValue;
310 }
311 
312 int
314 {
315  int score = ScoreWhiteMaterial() - ScoreBlackMaterial();
316  return (Pos.GetToMove() == WHITE) ? score : -score;
317 }
318 
319 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
320 // Engine::Score
321 // Returns a score in centipawns for the current engine position,
322 // from the perspective of the side to move.
323 // Alpha and beta cutoff scores are specified for performance. If
324 // simple material counting produces a score much lower than alpha
325 // or much greater than beta, the score is returned without
326 // slower square-based evaluation.
327 int
328 Engine::Score (int alpha, int beta)
329 {
330  colorT toMove = Pos.GetToMove();
331  const byte * pieceCount = Pos.GetMaterial();
332  const pieceT * board = Pos.GetBoard();
333  int materialScore[2] = {0, 0};
334  int allscore[2] = {0, 0}; // Scoring in all positions
335  int endscore[2] = {0, 0}; // Scoring in endgames
336  int midscore[2] = {0, 0}; // Scoring in middlegames
337  int nNonPawns[2] = {0, 0}; // Non-pawns on each side, including kings
338 
339  nScoreCalls++;
340 
341  nNonPawns[WHITE] = Pos.NumNonPawns(WHITE);
342  nNonPawns[BLACK] = Pos.NumNonPawns(BLACK);
343 
344  // First compute material scores:
345  allscore[WHITE] = materialScore[WHITE] = ScoreWhiteMaterial();
346  allscore[BLACK] = materialScore[BLACK] = ScoreBlackMaterial();
347 
348  int pieceMaterial = (materialScore[WHITE] - pieceCount[WP] * PawnValue)
349  + (materialScore[BLACK] - pieceCount[BP] * PawnValue);
350  bool inEndgame = false;
351  bool inMiddlegame = false;
352  if (pieceMaterial <= EndgameValue) { inEndgame = true; }
353  if (pieceMaterial >= MiddlegameValue) { inMiddlegame = true; }
354  bool inPawnEndgame = Pos.InPawnEnding();
355 
356  // Look for a bad trade: minor piece for pawns; Q for R+Pawns; etc.
357  // But only do this if both sides have pawns.
358  if (pieceCount[WP] > 0 && pieceCount[BP] > 0) {
359  uint wminors = pieceCount[WB] + pieceCount[WN];
360  uint bminors = pieceCount[BB] + pieceCount[BN];
361  uint wmajors = pieceCount[WR] + (2 * pieceCount[WQ]);
362  uint bmajors = pieceCount[BR] + (2 * pieceCount[BQ]);
363  if (wmajors == bmajors) {
364  if (wminors < bminors) { allscore[WHITE] -= BadPieceTrade; }
365  if (wminors > bminors) { allscore[BLACK] -= BadPieceTrade; }
366  } else if (wminors == bminors) {
367  if (wmajors < bmajors) { allscore[WHITE] -= BadPieceTrade; }
368  if (wmajors > bmajors) { allscore[BLACK] -= BadPieceTrade; }
369  }
370  }
371 
372  // Add the Bishop-pair bonus now, because it is fast and easy:
373  if (pieceCount[WB] >= 2) { allscore[WHITE] += BishopPair; }
374  if (pieceCount[BB] >= 2) { allscore[BLACK] += BishopPair; }
375 
376  // If there are no pawns, a material advantage of only one minor
377  // piece is worth very little so reduce the material score.
378  if (pieceCount[WP] + pieceCount[BP] == 0) {
379  int materialDiff = materialScore[WHITE] - materialScore[BLACK];
380  if (materialDiff < 0) { materialDiff = -materialDiff; }
381  if (materialDiff == BishopValue || materialDiff == KnightValue) {
382  allscore[WHITE] /= 4;
383  allscore[BLACK] /= 4;
384  }
385  }
386 
387  // Look for a trapped bishop on a7/h7/a2/h2:
388  if (Pos.RankCount (WB, RANK_7) > 0) {
389  if (board[A7] == WB && board[B6] == BP) { allscore[WHITE] -= BishopTrapped; }
390  if (board[H7] == WB && board[G6] == BP) { allscore[WHITE] -= BishopTrapped; }
391  }
392  if (Pos.RankCount (BB, RANK_2) > 0) {
393  if (board[A2] == BB && board[B3] == WP) { allscore[BLACK] -= BishopTrapped; }
394  if (board[H2] == BB && board[G6] == WP) { allscore[BLACK] -= BishopTrapped; }
395  }
396 
397  // Check for a score much worse than alpha or better than beta
398  // which can be returned immediately on the assumption that
399  // a full evaluation could not get inside the alpha-beta range.
400  // If we are in a pawn ending, a much larger margin is used since
401  // huge bonuses can be added for passed pawns in such endgames.
402  int lazyMargin = LazyEvalMargin;
403  if (inEndgame) { lazyMargin = LazyEvalEndingMargin; }
404  if (inPawnEndgame) { lazyMargin = LazyEvalPawnEndingMargin; }
405 
406  int fastScore = allscore[WHITE] - allscore[BLACK];
407  if (toMove == BLACK) { fastScore = -fastScore; }
408  if (fastScore - lazyMargin > beta) { return fastScore; }
409  if (fastScore + lazyMargin < alpha) { return fastScore; }
410 
411  // Get the pawn structure score next, because it is usually fast:
412  pawnTableEntryT pawnEntry;
413  ScorePawnStructure (&pawnEntry);
414 
415  // Penalise d-file and e-file pawns blocked on their home squares:
416  if (board[D2] == WP && board[D3] != EMPTY) { allscore[WHITE] -= BlockedHomePawn; }
417  if (board[E2] == WP && board[E3] != EMPTY) { allscore[WHITE] -= BlockedHomePawn; }
418  if (board[D7] == BP && board[D6] != EMPTY) { allscore[BLACK] -= BlockedHomePawn; }
419  if (board[E7] == BP && board[E6] != EMPTY) { allscore[BLACK] -= BlockedHomePawn; }
420 
421  // Incentive for side ahead in material to trade nonpawn pieces and
422  // for side behind in material to avoid trades:
423  if (materialScore[WHITE] > materialScore[BLACK]) {
424  int bonus = (5 - nNonPawns[BLACK]) * 5;
425  allscore[WHITE] += bonus;
426  } else if (materialScore[BLACK] > materialScore[WHITE]) {
427  int bonus = (5 - nNonPawns[WHITE]) * 5;
428  allscore[BLACK] += bonus;
429  }
430 
431  // Check again for a score outside the alpha-beta range, using a
432  // smaller fixed margin of error since the pawn structure score
433  // has been added:
434  fastScore = (allscore[WHITE] - allscore[BLACK]) + pawnEntry.score;
435  if (toMove == BLACK) { fastScore = -fastScore; }
436  if (fastScore > beta + 200) { return fastScore; }
437  if (fastScore < alpha - 200) { return fastScore; }
438 
439  nScoreFull++;
440 
441  // Now refine the score with piece-square bonuses:
442 
443  squareT wk = Pos.GetKingSquare(WHITE);
444  squareT bk = Pos.GetKingSquare(BLACK);
445  fyleT wkFyle = square_Fyle(wk);
446  fyleT bkFyle = square_Fyle(bk);
447 
448  // Check if each side should be storming the enemy king:
449  if (!inEndgame) {
450  if (wkFyle <= C_FYLE && bkFyle >= F_FYLE) {
451  midscore[WHITE] += pawnEntry.wLongbShortScore;
452  } else if (wkFyle >= F_FYLE && bkFyle <= C_FYLE) {
453  midscore[WHITE] += pawnEntry.wShortbLongScore;
454  }
455  }
456 
457  // Iterate over the piece for each color:
458 
459  for (colorT c = WHITE; c <= BLACK; c++) {
460  colorT enemy = color_Flip(c);
461  // squareT ownKing = Pos.GetKingSquare(c);
462  squareT enemyKing = Pos.GetKingSquare(enemy);
463  uint npieces = Pos.GetCount(c);
464  squareT * sqlist = Pos.GetList(c);
465  int mscore = 0; // Middlegame score adjustments
466  int escore = 0; // Endgame score adjustments
467  int ascore = 0; // All-position adjustments (middle and endgame)
468 
469  for (uint i = 0; i < npieces; i++) {
470  squareT sq = sqlist[i];
471  pieceT p = board[sq];
472  pieceT ptype = piece_Type(p);
473  ASSERT (p != EMPTY && piece_Color(p) == c);
474  squareT bonusSq = (c == WHITE) ? square_FlipRank(sq) : sq;
475  uint rank = RANK_1 + RANK_8 - square_Rank(bonusSq);
476 
477  // Piece-specific bonuses. The use of if-else instead of
478  // a switch statement was observed to be faster since
479  // the most common piece types are handled first.
480 
481  if (ptype == PAWN) {
482  // Most pawn-specific bonuses are in ScorePawnStructure().
483 
484  // Kings should be close to pawns in endgames:
485  // if (!inMiddlegame) {
486  // escore += 3 * square_Distance (sq, enemyKing)
487  // - 2 * square_Distance (sq, ownKing);
488  // }
489  } else if (ptype == ROOK) {
490  ascore += RookFile[square_Fyle(sq)];
491  if (rank == RANK_7) {
492  ascore += RookOnSeventh;
493  // Even bigger bonus if rook traps king on 8th rank:
494  bool kingOn8th = (p == WR) ? (bk >= A8) : (wk <= H1);
495  if (kingOn8th) { ascore += RookOnSeventh; }
496  }
497  if (!inEndgame) {
498  mscore += RookKingDist[square_Distance(sq, enemyKing)];
499  }
500  if (!inMiddlegame) {
501  uint mobility = Pos.Mobility (ROOK, c, sq);
502  escore += RookEndgameMobility [mobility];
503  }
504  } else if (ptype == KING) {
505  if (Pos.GetCount(c) == 1) {
506  // Forcing a lone king to a corner:
507  ascore += 5 * KingEndgameSquare[bonusSq] - 150;
508  } else {
509  mscore += KingSquare[bonusSq];
510  escore += KingEndgameSquare[bonusSq];
511  }
512  } else if (ptype == BISHOP) {
513  ascore += BishopSquare[bonusSq];
514  ascore += BishopMobility [Pos.Mobility (BISHOP, c, sq)];
515  // Middlegame bonus for diagonal close to enemy king:
516  if (! inEndgame) {
517  mscore += BishopKingDist[square_Distance(sq, enemyKing)];
518  // Reward a bishop attacking the enemy king vicinity:
519  int leftdiff = (int)square_LeftDiag(sq)
520  - (int)square_LeftDiag(enemyKing);
521  int rightdiff = (int)square_RightDiag(sq)
522  - (int)square_RightDiag(enemyKing);
523  if ((leftdiff >= -2 && leftdiff <= 2)
524  || (rightdiff >= -2 && rightdiff <= 2)) {
525  mscore += BishopEyesKing;
526  }
527  }
528  } else if (ptype == KNIGHT) {
529  ascore += KnightSquare[bonusSq];
530  if (!inEndgame) {
531  mscore += KnightKingDist[square_Distance(sq, enemyKing)];
532  // Bonus for a useful outpost:
533  if (rank >= RANK_4 && !square_IsEdgeSquare(sq)
534  && isOutpost(board, sq, c)) {
535  mscore += KnightOutpost;
536  }
537  }
538  if (!inMiddlegame) {
539  // Penalty for knight in an endgame with enemy
540  // pawns on both wings.
541  pieceT enemyPawn = piece_Make (enemy, PAWN);
542  uint qsidePawns = Pos.FyleCount(enemyPawn, A_FYLE)
543  + Pos.FyleCount(enemyPawn, B_FYLE)
544  + Pos.FyleCount(enemyPawn, C_FYLE);
545  uint ksidePawns = Pos.FyleCount(enemyPawn, F_FYLE)
546  + Pos.FyleCount(enemyPawn, G_FYLE)
547  + Pos.FyleCount(enemyPawn, H_FYLE);
548  if (ksidePawns > 0 && qsidePawns > 0) {
549  escore -= KnightBadEndgame;
550  }
551  }
552  } else /* (ptype == QUEEN) */ {
553  ASSERT (ptype == QUEEN);
554  ascore += QueenSquare[bonusSq];
555  ascore += QueenKingDist[square_Distance(sq, enemyKing)];
556  }
557  }
558  allscore[c] += ascore;
559  midscore[c] += mscore;
560  endscore[c] += escore;
561  }
562 
563  // Now reward rooks on open files or behind passed pawns:
564  byte passedPawnFyles =
565  pawnEntry.fyleHasPassers[WHITE] | pawnEntry.fyleHasPassers[BLACK];
566  for (colorT color = WHITE; color <= BLACK; color++) {
567  pieceT rook = piece_Make (color, ROOK);
568  if (pieceCount[rook] == 0) { continue; }
569  colorT enemy = color_Flip (color);
570  pieceT ownPawn = piece_Make (color, PAWN);
571  pieceT enemyPawn = piece_Make (enemy, PAWN);
572  fyleT enemyKingFyle = square_Fyle (Pos.GetKingSquare(enemy));
573  int bonus = 0;
574 
575  for (fyleT fyle = A_FYLE; fyle <= H_FYLE; fyle++) {
576  uint nRooks = Pos.FyleCount (rook, fyle);
577  if (nRooks == 0) { continue; }
578  if (nRooks > 1) { bonus += DoubledRooks; }
579  uint passedPawnsOnFyle = passedPawnFyles & (1 << fyle);
580  if (passedPawnsOnFyle != 0) {
581  // Rook is on same file as a passed pawn.
582  // TODO: make bonus bigger when rook is *behind* the pawn.
583  bonus += RookPasserFile;
584  } else if (Pos.FyleCount (ownPawn, fyle) == 0) {
585  // Rook on open or half-open file:
586  if (Pos.FyleCount (enemyPawn, fyle) == 0) {
587  bonus += RookOpenFile;
588  } else {
589  bonus += RookHalfOpenFile;
590  }
591  // If this open/half-open file leads to a square adjacent
592  // to the enemy king, give a further bonus:
593  int fdiff = (int)fyle - (int)enemyKingFyle;
594  if (fdiff >= -1 && fdiff < 1) { bonus += RookEyesKing; }
595  }
596  }
597  allscore[color] += bonus;
598  }
599 
600  // King safety:
601  if (! inEndgame) {
602  if (pieceCount[BQ] > 0) {
603  if (Pos.GetCastling(WHITE,KSIDE)) { midscore[WHITE] += CanCastle; }
604  if (Pos.GetCastling(WHITE,QSIDE)) { midscore[WHITE] += CanCastle; }
605  }
606  if (pieceCount[WQ] > 0) {
607  if (Pos.GetCastling(BLACK,KSIDE)) { midscore[BLACK] += CanCastle; }
608  if (Pos.GetCastling(BLACK,QSIDE)) { midscore[BLACK] += CanCastle; }
609  }
610  // Bonus for pawn cover in front of a castled king. Actually we
611  // also include bishops because they are important for defence.
612  if (square_Rank(wk) == RANK_1 && wk != D1 && wk != E1) {
613  uint nCoverPawns = 0;
614  pieceT p = board[square_Move (wk, UP_LEFT)];
615  if (p == WP || p == WB) { nCoverPawns++; }
616  p = board[square_Move (wk, UP)];
617  if (p == WP || p == WB) { nCoverPawns++; }
618  p = board[square_Move (wk, UP_RIGHT)];
619  if (p == WP || p == WB) { nCoverPawns++; }
620  midscore[WHITE] += CoverPawn * nCoverPawns;
621  if ((wk == F1 || wk == G1)
622  && (board[G1] == WR || board[H1] == WR || board[H2] == WR)) {
623  midscore[WHITE] -= KingTrapsRook;
624  }
625  if ((wk == C1 || wk == B1)
626  && (board[B1] == WR || board[A1] == WR || board[A2] == WR)) {
627  midscore[WHITE] -= KingTrapsRook;
628  }
629  }
630  if (square_Rank(bk) == RANK_8 && bk != D8 && bk != E8) {
631  uint nCoverPawns = 0;
632  pieceT p = board[square_Move (bk, DOWN_LEFT)];
633  if (p == BP || p == BB) { nCoverPawns++; }
634  p = board[square_Move (bk, DOWN)];
635  if (p == BP || p == BB) { nCoverPawns++; }
636  p = board[square_Move (bk, DOWN_RIGHT)];
637  if (p == BP || p == BB) { nCoverPawns++; }
638  midscore[BLACK] += CoverPawn * nCoverPawns;
639  if ((bk == F8 || bk == G8)
640  && (board[G8] == BR || board[H8] == BR || board[H7] == BR)) {
641  midscore[BLACK] -= KingTrapsRook;
642  }
643  if ((bk == C8 || bk == B8)
644  && (board[B8] == BR || board[A8] == BR || board[A7] == BR)) {
645  midscore[BLACK] -= KingTrapsRook;
646  }
647  }
648 
649  // Pawn centre:
650  if ((board[D4] == WP || board[D5] == WP)
651  && (board[E4] == WP || board[E5] == WP)) {
652  midscore[WHITE] += CentralPawnPair;
653  }
654  if ((board[D4] == BP || board[D5] == BP)
655  && (board[E4] == BP || board[E5] == BP)) {
656  midscore[BLACK] += CentralPawnPair;
657  }
658 
659  // Minor pieces developed:
660  if (board[B1] != WN) { midscore[WHITE] += Development; }
661  if (board[C1] != WB) { midscore[WHITE] += Development; }
662  if (board[F1] != WB) { midscore[WHITE] += Development; }
663  if (board[G1] != WN) { midscore[WHITE] += Development; }
664  if (board[B8] != BN) { midscore[BLACK] += Development; }
665  if (board[C8] != BB) { midscore[BLACK] += Development; }
666  if (board[F8] != BB) { midscore[BLACK] += Development; }
667  if (board[G8] != BN) { midscore[BLACK] += Development; }
668  }
669 
670  // Work out the middlegame and endgame scores including pawn structure
671  // evaluation, with a larger pawn structure weight in endgames:
672  int baseScore = allscore[WHITE] - allscore[BLACK];
673  int mgScore = baseScore + midscore[WHITE] - midscore[BLACK];
674  int egScore = baseScore + endscore[WHITE] - endscore[BLACK];
675  mgScore += pawnEntry.score;
676  egScore += (pawnEntry.score * 5) / 4;
677 
678  // Scale down the endgame score for bishops of opposite colors, if both
679  // sides have the same non-pawn material:
680  if (pieceCount[WB] == 1 && pieceCount[BB] == 1) {
681  if (Pos.SquareColorCount(WB,WHITE) != Pos.SquareColorCount(BB,WHITE)) {
682  if (pieceCount[WQ] == pieceCount[BQ]
683  && pieceCount[WR] == pieceCount[BR]
684  && pieceCount[WN] == pieceCount[BN]) {
685  egScore = egScore * 5 / 8;
686  }
687  }
688  }
689 
690  // Negate scores for Black to move:
691  if (toMove == BLACK) {
692  mgScore = -mgScore;
693  egScore = -egScore;
694  }
695 
696  // Determine the final score from the middlegame and endgame scores:
697  int finalScore = 0;
698  if (inMiddlegame) {
699  finalScore = mgScore; // Use the middlegame score only.
700  } else if (inEndgame) {
701  finalScore = egScore; // Use the endgame score only.
702  } else {
703  // The final score is a weighted mean of the two scores:
704  int midpart = (pieceMaterial - EndgameValue) * mgScore;
705  int endpart = (MiddlegameValue - pieceMaterial) * egScore;
706  finalScore = (endpart + midpart) / (MiddlegameValue - EndgameValue);
707  }
708  return finalScore;
709 }
710 
711 static uint nPawnHashProbes = 0;
712 static uint nPawnHashHits = 0;
713 
714 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
715 // Engine::ScorePawnStructure
716 // Fill in the provided pawnTableEntryT structure with pawn structure
717 // scoring information, using the pawn hash table wherever possible.
718 void
719 Engine::ScorePawnStructure (pawnTableEntryT * pawnEntry)
720 {
721  nPawnHashProbes++;
722  uint pawnhash = Pos.PawnHashValue();
723  // We only use 32-bit hash values, so without further safety checks
724  // the rate of false hits in the pawn hash table could be high.
725  // To reduce the chance of false hits, we compute an extra signature.
726  uint sig = (Pos.SquareColorCount(WP,WHITE) << 12)
727  | (Pos.SquareColorCount(BP,BLACK) << 8)
728  | (Pos.PieceCount(WP) << 4) | Pos.PieceCount(BP);
729  pawnEntry->pawnhash = pawnhash;
730  pawnEntry->sig = sig;
731  pawnEntry->fyleHasPassers[WHITE] = 0;
732  pawnEntry->fyleHasPassers[BLACK] = 0;
733 
734  bool inPawnEndgame = (Pos.NumNonPawns(WHITE) == 1
735  && Pos.NumNonPawns(BLACK) == 1);
736  pawnTableEntryT * hashEntry = NULL;
737 
738  // Check for a pawn hash table hit, but not in pawn endings:
739  if (!inPawnEndgame) {
740  uint hashSlot = pawnhash % PawnTableSize;
741  hashEntry = &(PawnTable[hashSlot]);
742  if (pawnhash == hashEntry->pawnhash && sig == hashEntry->sig) {
743  nPawnHashHits++;
744  *pawnEntry = *hashEntry;
745  return;
746  }
747  }
748 
749  // The pawnFiles array contains the number of pawns of each color on
750  // each file. Indexes 1-8 are used while 0 and 9 are empty dummy files
751  // added so that even the a and h files have two adjacent files, making
752  // isolated/passed pawn calculation easier.
753  uint pawnFiles[2][10] = { {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
754  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0} };
755  // firstRank stores the rank of the leading pawn on each file.
756  uint firstRank[2][10] = { {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
757  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0} };
758  // lastRank stores the rank of the rearmost pawn on each file.
759  uint lastRank[2][10] = { {7, 7, 7, 7, 7, 7, 7, 7, 7, 7},
760  {7, 7, 7, 7, 7, 7, 7, 7, 7, 7} };
761 
762  int pawnScore[2] = {0, 0};
763  int longVsShortScore[2] = {0, 0}; // Pawn storm bonuses, O-O-O vs O-O
764  int shortVsLongScore[2] = {0, 0}; // Pawn storm bonuses, O-O vs O-O-O
765  rankT bestRacingPawn[2] = {RANK_1, RANK_1};
766 
767  for (fyleT f = A_FYLE; f <= H_FYLE; f++) {
768  pawnFiles[WHITE][f+1] = Pos.FyleCount (WP, f);
769  pawnFiles[BLACK][f+1] = Pos.FyleCount (BP, f);
770  }
771 
772  for (colorT c = WHITE; c <= BLACK; c++) {
773  pieceT pawn = piece_Make (c, PAWN);
774  uint npawns = Pos.PieceCount(pawn);
775  SquareList sqlist;
776  Pos.GetSquares (pawn, &sqlist);
777  for (uint i = 0; i < npawns; i++) {
778  squareT sq = sqlist.Get(i);
779  squareT wsq = (c == WHITE) ? sq : square_FlipRank(sq);
780  squareT bonusSq = square_FlipRank(wsq);
781  pawnScore[c] += PawnSquare[bonusSq];
782  longVsShortScore[c] += PawnStorm[bonusSq];
783  shortVsLongScore[c] += PawnStorm[square_FlipFyle(bonusSq)];
784  uint fyle = square_Fyle(wsq) + 1;
785  uint rank = square_Rank(wsq);
786  if (rank > firstRank[c][fyle]) {
787  firstRank[c][fyle] = rank;
788  }
789  if (rank < lastRank[c][fyle]) {
790  lastRank[c][fyle] = rank;
791  }
792  }
793  }
794 
795  byte fyleHasPassers[2] = {0, 0};
796 
797  for (colorT color = WHITE; color <= BLACK; color++) {
798  if (Pos.PieceCount(piece_Make(color,PAWN)) == 0) { continue; }
799  colorT enemy = color_Flip(color);
800 
801  for (uint fyle=1; fyle <= 8; fyle++) {
802  uint pawnCount = pawnFiles[color][fyle];
803  if (pawnCount == 0) { continue; }
804  uint pawnRank = firstRank[color][fyle];
805 
806  // Doubled pawn penalty:
807  if (pawnCount > 1) {
808  pawnScore[color] -= DoubledPawn * pawnCount;
809  }
810 
811  // Isolated pawn penalty:
812  bool isolated = false;
813  if (pawnFiles[color][fyle-1] == 0
814  && pawnFiles[color][fyle+1] == 0) {
815  isolated = true;
816  pawnScore[color] -= IsolatedPawn * pawnCount;
817  // Extra penalty for isolated on half-open file:
818  if (pawnFiles[enemy][fyle] == 0) {
819  pawnScore[color] -= IsolatedPawn * pawnCount / 2;
820  }
821  } else if (lastRank[color][fyle-1] > lastRank[color][fyle]
822  && lastRank[color][fyle+1] > lastRank[color][fyle]) {
823  // Not isolated, but backward:
824  pawnScore[color] -= BackwardPawn;
825  // Extra penalty for backward on half-open file:
826  if (pawnFiles[enemy][fyle] == 0) {
827  pawnScore[color] -= BackwardPawn;
828  }
829  }
830 
831  // Passed pawn bonus:
832  if (pawnRank >= 7 - lastRank[enemy][fyle]
833  && pawnRank >= 7 - lastRank[enemy][fyle-1]
834  && pawnRank >= 7 - lastRank[enemy][fyle+1]) {
835  int bonus = PassedPawnRank[pawnRank];
836  // Smaller bonus for rook-file or isolated passed pawns:
837  if (fyle == 1 || fyle == 8 || isolated) {
838  bonus = bonus * 3 / 4;
839  }
840  // Bigger bonus for a passed pawn protected by another pawn:
841  if (!isolated) {
842  if (pawnRank == firstRank[color][fyle-1] + 1
843  || pawnRank == firstRank[color][fyle+1] + 1) {
844  bonus = (bonus * 3) / 2;
845  }
846  }
847  pawnScore[color] += bonus;
848  // Update the passed-pawn-files bitmap:
849  fyleHasPassers[color] |= (1 << (fyle-1));
850 
851  // Give a big bonus for a connected passed pawn on
852  // the 6th or 7th rank.
853  if (pawnRank >= RANK_6 && pawnFiles[color][fyle-1] > 0
854  && firstRank[color][fyle-1] >= RANK_6) {
855  // pawnScore[color] += some_bonus...;
856  }
857 
858  // Check for passed pawn races in pawn endgames:
859  if (inPawnEndgame) {
860  // Check if the enemy king is outside the square:
861  squareT kingSq = Pos.GetKingSquare(color_Flip(color));
862  squareT pawnSq = square_Make(fyle-1, pawnRank);
863  squareT promoSq = square_Make(fyle-1, RANK_8);
864  if (color == BLACK) {
865  pawnSq = square_FlipRank(pawnSq);
866  promoSq = square_FlipRank(promoSq);
867  }
868  uint kingDist = square_Distance(kingSq, promoSq);
869  uint pawnDist = square_Distance(pawnSq, promoSq);
870  if (color != Pos.GetToMove()) { pawnDist++; }
871  if (pawnDist < kingDist) {
872  bestRacingPawn[color] = pawnRank;
873  }
874  }
875  }
876  }
877  }
878 
879  int score = pawnScore[WHITE] - pawnScore[BLACK];
880  pawnEntry->score = score;
881  pawnEntry->fyleHasPassers[WHITE] = fyleHasPassers[WHITE];
882  pawnEntry->fyleHasPassers[BLACK] = fyleHasPassers[BLACK];
883  pawnEntry->wLongbShortScore = longVsShortScore[WHITE] - shortVsLongScore[BLACK];
884  pawnEntry->wShortbLongScore = shortVsLongScore[WHITE] - longVsShortScore[BLACK];
885 
886  // If not a pawn endgame, store the score in the pawn hash table:
887  if (!inPawnEndgame) {
888  *hashEntry = *pawnEntry;
889  return;
890  }
891 
892  // This is a pawn endgame, so we cannot store the score in the
893  // pawn hash table since we include king positions as a factor.
894  // If one side has a pawn that clearly queens before the best
895  // enemy pawn in a race (where kings cannot catch the pawns),
896  // give a huge bonus since it almost certainly wins:
897 
898  if (bestRacingPawn[WHITE] > bestRacingPawn[BLACK] + 1) {
899  pawnEntry->score += RookValue;
900  } else if (bestRacingPawn[BLACK] > bestRacingPawn[WHITE] + 1) {
901  pawnEntry->score -= RookValue;
902  }
903 }
904 
905 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
906 // Engine::IsMatingScore
907 // Returns true if the score indicates the side to move will checkmate.
908 inline bool
909 Engine::IsMatingScore (int score)
910 {
911  return (score > (Infinity - (int)ENGINE_MAX_PLY));
912 }
913 
914 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
915 // Engine::IsGettingMatedScore
916 // Returns true if the score indicates the side to move will be checkmated.
917 inline bool
918 Engine::IsGettingMatedScore (int score)
919 {
920  return (score < (-Infinity + (int)ENGINE_MAX_PLY));
921 }
922 
923 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
924 // Engine::PlayMove
925 // Play the specified move, not in a search.
926 void
928  PushRepeat(&RootPos);
929  RootPos.DoSimpleMove(sm);
930  Pos.DoSimpleMove(sm);
931 #ifdef WINCE
932  simpleMoveT * newMove = (simpleMoveT *) my_Tcl_Alloc(sizeof(simpleMoveT));
933 #else
934  simpleMoveT * newMove = new simpleMoveT;
935 #endif
936  *newMove = *sm;
937  GameMoves[NumGameMoves] = newMove;
938  NumGameMoves++;
939  // Change the transposition table sequence number:
940  TranTableSequence++;
941 }
942 
943 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
944 // Engine::RetractMove
945 // Take back a move played in the game.
946 void
948 {
949  if (NumGameMoves == 0) { return; }
950  PopRepeat();
951  NumGameMoves--;
952  RootPos.UndoSimpleMove(GameMoves[NumGameMoves]);
953  Pos.UndoSimpleMove(GameMoves[NumGameMoves]);
954 #ifdef WINCE
955  my_Tcl_Free((char *)GameMoves);
956 #else
957  delete GameMoves[NumGameMoves];
958 #endif
959  TranTableSequence--;
960 }
961 
962 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
963 // Engine::DoMove
964 // Make the specified move in a search.
965 inline void
966 Engine::DoMove (simpleMoveT * sm) {
967  PushRepeat(&Pos);
968  Pos.DoSimpleMove(sm);
969  Ply++;
970 }
971 
972 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
973 // Engine::UndoMove
974 // Take back the specified move in a search.
975 inline void
976 Engine::UndoMove (simpleMoveT * sm) {
977  PopRepeat();
978  Pos.UndoSimpleMove(sm);
979  Ply--;
980 }
981 
982 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
983 // Engine::PushRepeat
984 // Remember the current position on the repetition stack.
985 inline void
986 Engine::PushRepeat (Position * pos)
987 {
988  repeatT * rep = &(RepStack[RepStackSize]);
989  rep->hash = pos->HashValue();
990  rep->pawnhash = pos->PawnHashValue();
991  rep->npieces = pos->TotalMaterial();
992  rep->stm = pos->GetToMove();
993  RepStackSize++;
994 }
995 
996 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
997 // Engine::PopRepeat
998 // Pops the last entry off the repetition stack.
999 inline void
1000 Engine::PopRepeat (void)
1001 {
1002  ASSERT (RepStackSize > 0);
1003  RepStackSize--;
1004 }
1005 
1006 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1007 // Engine::NoMatingMaterial
1008 // Returns true if the position is a certain draw through neither
1009 // side having mating material.
1010 bool
1012 {
1013  uint npieces = Pos.TotalMaterial();
1014 
1015  // Check for K vs K, K+N vs K, and K+B vs K:
1016  if (npieces <= 2) { return true; }
1017  if (npieces == 3) {
1018  byte * material = Pos.GetMaterial();
1019  if (material[WB] == 1 || material[WN] == 1) { return true; }
1020  if (material[BB] == 1 || material[BN] == 1) { return true; }
1021  }
1022  return false;
1023 }
1024 
1025 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1026 // Engine::FiftyMoveDraw
1027 // Returns true if a draw has been reached through fifty full
1028 // moves since the last capture or pawn move.
1029 bool
1031 {
1032  if (RepStackSize < 100) { return false; }
1033 
1034  uint pawnhash = Pos.PawnHashValue();
1035  uint npieces = Pos.TotalMaterial();
1036 
1037  // Go back through the stack of hash values:
1038  uint plycount = 0;
1039  for (uint i = RepStackSize; i > 0; i--) {
1040  repeatT * rep = &(RepStack[i-1]);
1041  // Stop at an irreversible move:
1042  if (npieces != rep->npieces) { break; }
1043  if (pawnhash != rep->pawnhash) { break; }
1044  plycount++;
1045  }
1046  if (plycount >= 100) { return true; }
1047  return false;
1048 }
1049 
1050 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1051 // Engine::RepeatedPosition
1052 // Returns the number if times the current position has been reached,
1053 // with the same side to move, castling and en passant settings.
1054 // The current occurrence is included in the returned count.
1055 uint
1057 {
1058  uint hash = Pos.HashValue();
1059  uint pawnhash = Pos.PawnHashValue();
1060  uint npieces = Pos.TotalMaterial();
1061  colorT stm = Pos.GetToMove();
1062 
1063  // Go back through the stack of hash values detecting repetition:
1064  uint ntimes = 1;
1065  for (uint i = RepStackSize; i > 0; i--) {
1066  repeatT * rep = &(RepStack[i-1]);
1067  // Stop at an irreversible move:
1068  if (npieces != rep->npieces) { break; }
1069  if (pawnhash != rep->pawnhash) { break; }
1070  // Look for repetition:
1071  if (hash == rep->hash && stm == rep->stm) { ntimes++; }
1072  }
1073  return ntimes;
1074 }
1075 
1076 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1077 // Engine::SetHashTableKilobytes
1078 // Set the transposition table size in kilobytes.
1079 void
1081 {
1082  // Compute the number of entries, which must be even:
1083  uint bytes = size * 1024;
1084  if(TranTableSize != bytes / sizeof(transTableEntryT))
1085  {
1086  TranTableSize = bytes / sizeof(transTableEntryT);
1087  if ((TranTableSize % 2) == 1) { TranTableSize--; }
1088 #ifdef WINCE
1089  if (TranTable != NULL) { my_Tcl_Free((char *) TranTable); }
1090  TranTable = (transTableEntryT*)my_Tcl_Alloc(sizeof ( transTableEntryT [TranTableSize]));
1091 #else
1092  if (TranTable != NULL) { delete[] TranTable; }
1093  TranTable = new transTableEntryT [TranTableSize];
1094 #endif
1095  }
1096  ClearHashTable();
1097 }
1098 
1099 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1100 // Engine::SetPawnTableKilobytes
1101 // Set the pawn structure hash table size in kilobytes.
1102 void
1104 {
1105  // Compute the number of entries:
1106  uint bytes = size * 1024;
1107  if(PawnTableSize != bytes / sizeof(pawnTableEntryT))
1108  {
1109  PawnTableSize = bytes / sizeof(pawnTableEntryT);
1110 #ifdef WINCE
1111  if (PawnTable != NULL) { my_Tcl_Free((char *) PawnTable); }
1112  PawnTable = (pawnTableEntryT*)my_Tcl_Alloc(sizeof (pawnTableEntryT [PawnTableSize]) );
1113 #else
1114  if (PawnTable != NULL) { delete[] PawnTable; }
1115  PawnTable = new pawnTableEntryT [PawnTableSize];
1116 #endif
1117  }
1118  ClearPawnTable();
1119 }
1120 
1121 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1122 // Engine::ClearHashTable
1123 // Clear the transposition table.
1124 void
1126 {
1127  for (uint i = 0; i < TranTableSize; i++) {
1128  TranTable[i].flags = SCORE_NONE;
1129  }
1130 }
1131 
1132 
1133 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1134 // Engine::ClearPawnTable
1135 // Clear the pawn structure hash table.
1136 void
1138 {
1139  for (uint i = 0; i < PawnTableSize; i++) {
1140  PawnTable[i].pawnhash = 0;
1141  }
1142 }
1143 
1144 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1145 // tte_Get/Set functions
1146 // Helpers for packing/extracting transposition table entry fields.
1147 
1148 inline void tte_SetFlags (transTableEntryT * tte, scoreFlagT sflag,
1149  colorT stm, byte castling, bool isOnlyMove)
1150 { tte->flags = (castling << 4) | (stm << 3) | (isOnlyMove ? 4 : 0) | sflag; }
1151 
1153 { return (tte->flags & 7); }
1154 
1156 { return ((tte->flags >> 3) & 1); }
1157 
1159 { return (tte->flags >> 4); }
1160 
1162 { return (((tte->flags >> 2) & 1) == 1); }
1163 
1164 inline void tte_SetBestMove (transTableEntryT * tte, simpleMoveT * bestMove)
1165 {
1166  ASSERT (bestMove->from <= H8 && bestMove->to <= H8);
1167  ushort bm = bestMove->from;
1168  bm <<= 6; bm |= bestMove->to;
1169  bm <<= 4; bm |= bestMove->promote;
1170  tte->bestMove = bm;
1171 }
1172 
1173 inline void tte_GetBestMove (transTableEntryT * tte, simpleMoveT * bestMove)
1174 {
1175  ushort bm = tte->bestMove;
1176  bestMove->promote = bm & 15; bm >>= 4;
1177  bestMove->to = bm & 63; bm >>= 6;
1178  bestMove->from = bm & 63;
1179 }
1180 
1181 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1182 // Engine::StoreHash
1183 // Store the score for the current position in the transposition table.
1184 void
1185 Engine::StoreHash (int depth, scoreFlagT ttFlag, int score,
1186  simpleMoveT * bestMove, bool isOnlyMove)
1187 {
1188  if (TranTableSize == 0) { return; }
1189  ASSERT (ttFlag <= SCORE_UPPER);
1190 
1191  uint hash = Pos.HashValue();
1192  uint pawnhash = Pos.PawnHashValue();
1193  colorT stm = Pos.GetToMove();
1194  if (stm == BLACK) { hash = ~hash; }
1195 
1196  // Find the least useful (lowest depth) of two entries to replace
1197  // but replace the previous entry for this position if it exists
1198  // and use an empty hash table entry if possible:
1199 
1200  uint ttSlot = (hash % TranTableSize) & 0xFFFFFFFEU;
1201  ASSERT (ttSlot < TranTableSize - 1);
1202  transTableEntryT * ttEntry1 = &(TranTable[ttSlot]);
1203  transTableEntryT * ttEntry2 = &(TranTable[ttSlot + 1]);
1204  bool replacingSameEntry = false;
1205 
1206  transTableEntryT * ttEntry;
1207  if (ttEntry1->hash == hash && ttEntry1->pawnhash == pawnhash) {
1208  ttEntry = ttEntry1; // Replace this existing entry.
1209  replacingSameEntry = true;
1210  } else if (ttEntry2->hash == hash && ttEntry2->pawnhash == pawnhash) {
1211  ttEntry = ttEntry2; // Replace this existing entry.
1212  replacingSameEntry = true;
1213  } else if (tte_ScoreFlag(ttEntry1) == SCORE_NONE) {
1214  ttEntry = ttEntry1; // Use this empty entry.
1215  } else if (tte_ScoreFlag(ttEntry2) == SCORE_NONE) {
1216  ttEntry = ttEntry2; // Use this empty entry.
1217  } else {
1218  // Replace the entry with the shallower depth, unless the deeper
1219  // entry has an old sequence number:
1220  transTableEntryT * ttDeeper = ttEntry1;
1221  transTableEntryT * ttShallower = ttEntry2;
1222  if (ttEntry1->depth < ttEntry2->depth) {
1223  ttDeeper = ttEntry2;
1224  ttShallower = ttEntry1;
1225  }
1226  if (ttShallower->sequence != TranTableSequence) {
1227  ttEntry = ttShallower; // Replace this old entry
1228  } else if (ttDeeper->sequence != TranTableSequence) {
1229  ttEntry = ttDeeper; // Replace this old entry
1230  } else {
1231  ttEntry = ttShallower; // Replace this shallow entry
1232  }
1233  }
1234 
1235  if (replacingSameEntry) {
1236  if (depth < ttEntry->depth) {
1237  // Do not overwrite an existing better entry for the same
1238  // position; but if there was no move, add one:
1239  if (ttEntry->bestMove == 0 && bestMove != NULL) {
1240  tte_SetBestMove (ttEntry, bestMove);
1241  }
1242  return;
1243  }
1244  if (depth == ttEntry->depth) {
1245  // Do not replace an exact score entry of the same depth for
1246  // the same position with an inexact entry:
1247  if (tte_ScoreFlag(ttEntry) == SCORE_EXACT && ttFlag != SCORE_EXACT) {
1248  return;
1249  }
1250  }
1251  }
1252 
1253  // Convert mating scores to include the current Ply count:
1254  if (IsMatingScore(score)) { score += Ply; }
1255  if (IsGettingMatedScore(score)) { score -= Ply; }
1256 
1257  // Fill in the hash entry fields:
1258  ttEntry->hash = hash;
1259  ttEntry->pawnhash = pawnhash;
1260  ttEntry->depth = depth;
1261  ttEntry->score = score;
1262  tte_SetFlags (ttEntry, ttFlag, stm, Pos.GetCastlingFlags(), isOnlyMove);
1263  ttEntry->sequence = TranTableSequence;
1264  ttEntry->bestMove = 0;
1265  if (bestMove != NULL) {
1266  ASSERT (bestMove->movingPiece != EMPTY);
1267  ASSERT (piece_Color(bestMove->movingPiece) == stm);
1268  ASSERT (bestMove->from <= H8);
1269  tte_SetBestMove (ttEntry, bestMove);
1270  }
1271  ttEntry->enpassant = Pos.GetEPTarget();
1272 }
1273 
1274 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1275 // Engine::ProbeHash
1276 // Probe the transposition table for the current position.
1277 //
1278 scoreFlagT
1279 Engine::ProbeHash (int depth, int * score, simpleMoveT * bestMove, bool * isOnlyMove)
1280 {
1281  // Clear the best move:
1282  if (bestMove != NULL) { bestMove->from = bestMove->to = NULL_SQUARE; }
1283 
1284  if (TranTableSize == 0) { return SCORE_NONE; }
1285 
1286  uint hash = Pos.HashValue();
1287  colorT stm = Pos.GetToMove();
1288  if (stm == BLACK) { hash = ~hash; }
1289 
1290  // Examine the corresponding pair of table entries:
1291  uint ttSlot = (hash % TranTableSize) & 0xFFFFFFFEU;
1292  ASSERT (ttSlot+1 < TranTableSize);
1293  transTableEntryT * ttEntry = &(TranTable[ttSlot]);
1294  if (ttEntry->hash != hash) { ttEntry++; }
1295  if (ttEntry->hash != hash) { return SCORE_NONE; }
1296  if (tte_ScoreFlag(ttEntry) == SCORE_NONE) { return SCORE_NONE; }
1297  uint pawnhash = Pos.PawnHashValue();
1298  if (ttEntry->pawnhash != pawnhash) { return SCORE_NONE; }
1299  if (tte_SideToMove(ttEntry) != stm) { return SCORE_NONE; }
1300  if (tte_Castling(ttEntry) != Pos.GetCastlingFlags()) { return SCORE_NONE; }
1301  if (ttEntry->enpassant != Pos.GetEPTarget()) { return SCORE_NONE; }
1302 
1303  // If a hash move is stored, we return it even if the depth is not
1304  // sufficient, because it will be useful for move ordering anyway.
1305  if (bestMove != NULL && ttEntry->bestMove != 0) {
1306  tte_GetBestMove (ttEntry, bestMove);
1307  const pieceT* board = Pos.GetBoard();
1308  bestMove->movingPiece = board[bestMove->from];
1309  }
1310  if (isOnlyMove != NULL) {
1311  *isOnlyMove = tte_IsOnlyMove (ttEntry);
1312  }
1313  // Only return an exact or bounded score if the stored depth is at
1314  // least as large as the requested depth:
1315  if (ttEntry->depth < depth) { return SCORE_NONE; }
1316  if (score != NULL) {
1317  *score = ttEntry->score;
1318  // Convert mating scores to exclude the current Ply count:
1319  if (IsMatingScore(*score)) { *score -= Ply; }
1320  if (IsGettingMatedScore(*score)) { *score += Ply; }
1321  }
1322  return tte_ScoreFlag(ttEntry);
1323 }
1324 
1325 static uint nFailHigh = 0;
1326 static uint nFailHighFirstMove = 0;
1327 
1328 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1329 // Engine::SetPosition
1330 // Set the current position. If the new position parameter
1331 // is NULL, the standard starting position is used.
1332 void
1334 {
1335  // Delete old game moves:
1336  for (uint i=0; i < NumGameMoves; i++) {
1337 #ifdef WINCE
1338  my_Tcl_Free((char *) GameMoves[i]);
1339 #else
1340  delete GameMoves[i];
1341 #endif
1342  }
1343  NumGameMoves = 0;
1344 
1345  // Set the position:
1346  if (newpos == NULL) {
1347  RootPos.StdStart();
1348  Pos.StdStart();
1349  } else {
1350  RootPos.CopyFrom (newpos);
1351  Pos.CopyFrom (newpos);
1352  }
1353 
1354  // Clear the repetition stack:
1355  RepStackSize = 0;
1356 
1357  // Clear the PV:
1358  PV[0].length = 0;
1359 
1360  // Change the transposition table sequence number so existing
1361  // entries can be detected as old ones:
1362  TranTableSequence++;
1363 }
1364 
1365 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1366 // Engine::Think
1367 // Initiate a search from the current position. If the supplied
1368 // move list is NULL, generate and examine all legal moves at the
1369 // root position. However, if the move list is not NULL, it
1370 // contains a subset of the legal moves to be analyzed.
1371 //
1372 // Returns the score (in centipawns, for the side to move) and
1373 // reorders the move list (if supplied) so the best move is at
1374 // the start of the list.
1375 int
1377 {
1378  Elapsed.Reset();
1379  NodeCount = 0;
1380  QNodeCount = 0;
1381  Ply = 0;
1382  IsOutOfTime = false;
1383  EasyMove = false;
1384  HardMove = false;
1385  InNullMove = 0;
1386  SetPVLength();
1387 
1388  ClearKillerMoves();
1389  ClearHistoryValues();
1390 
1391  // If no legal move list was specified, generate and search all moves:
1392  MoveList tmpMoveList;
1393  if (mlist == NULL) {
1394  mlist = &tmpMoveList;
1395  Pos.GenerateMoves(mlist);
1396  }
1397 
1398  // No legal moves? Return 0 for stalemate, -Infinity for checkmate.
1399  if (mlist->Size() == 0) {
1400  return (Pos.IsKingInCheck() ? -Infinity : 0);
1401  }
1402 
1403  // Sort the root move list by quiescent evaluation to get a
1404  // reasonably good initial move order:
1405  for (uint i=0; i < mlist->Size(); i++) {
1406  simpleMoveT * sm = mlist->Get(i);
1407  DoMove(sm);
1408  sm->score = -Quiesce (-Infinity, Infinity);
1409  UndoMove(sm);
1410  }
1411  std::sort(mlist->begin(), mlist->end());
1412 
1413  // Check for an easy move, one that scores more than two pawns
1414  // better than any alternative:
1415  if (mlist->Size() > 1) {
1416  int margin = mlist->Get(0)->score - mlist->Get(1)->score;
1417  if (margin > (2 * PawnValue)) {
1418  // Output ("Easy move: margin = %d\n", margin);
1419  EasyMove = true;
1420  }
1421  }
1422 
1423  int bestScore = -Infinity;
1424 
1425  // Do iterative deepening starting at depth 1, until out of
1426  // time or the maximum depth is reached:
1427  for (uint depth = 1; depth <= MaxDepth; depth++) {
1428 
1429  HardMove = false;
1430 
1431  // If we have searched at least a few ply, and there is less
1432  // than 30% of the recommended search time remaining, then
1433  // continuing the search is unlikely to be useful since it
1434  // will probably spend all remaining time on the first move:
1435  if (depth > MinDepthCheckTime) { // was 4. or will think too long when trying to check if a move is obvious
1436  double used = (double)Elapsed.MilliSecs() / (double)SearchTime;
1437  if (used > 0.7) { break; }
1438  }
1439 
1440  // Set up the alpha-beta range. For all but the first depth,
1441  // use a small aspiration window around the previous score
1442  // since we do not expect the score to change much:
1443  int alpha = -Infinity - 1;
1444  int beta = Infinity + 1;
1445  if (depth > 1) {
1446  alpha = bestScore - AspirationWindow;
1447  beta = bestScore + AspirationWindow;
1448  }
1449 
1450  int score = SearchRoot (depth, alpha, beta, mlist);
1451  if (OutOfTime()) { break; }
1452  if (score >= beta) {
1453  // Aspiration window fail-high:
1454  PrintPV (depth, score, "++");
1455  alpha = score - 1;
1456  beta = Infinity + 1;
1457  score = SearchRoot (depth, alpha, beta, mlist);
1458  } else if (score <= alpha) {
1459  // Aspiration window fail-low:
1460  PrintPV (depth, score, "--");
1461  EasyMove = false;
1462  HardMove = true;
1463  alpha = -Infinity - 1;
1464  beta = score + 1;
1465  score = SearchRoot (depth, alpha, beta, mlist);
1466  }
1467  if (OutOfTime()) { break; }
1468  // If the 2nd search failed, try again with an infinite window.
1469  // This is rare, but can happen with hashing/null-move effects.
1470  if (score < alpha || score > beta) {
1471  alpha = -Infinity;
1472  beta = Infinity;
1473  EasyMove = false;
1474  HardMove = true;
1475  score = SearchRoot (depth, alpha, beta, mlist);
1476  }
1477 
1478  if (OutOfTime()) { break; }
1479  bestScore = score;
1480  PrintPV (depth, bestScore, ">>>");
1481 
1482  // Stop if Only a few moves OR checkmate has been found - but not too soon:
1483  if (mlist->Size() <= depth || (depth >= 5 && IsMatingScore(bestScore))) { break; }
1484 
1485  // Make sure the first move in the list remains there by
1486  // giving it a huge node count for its move ordering score:
1487  mlist->Get(0)->score = 1 << 30;
1488 
1489  // Sort the move list based on node counts from this iteration:
1490  std::sort(mlist->begin(), mlist->end());
1491  }
1492 
1493  return bestScore;
1494 }
1495 
1496 int
1497 Engine::SearchRoot (int depth, int alpha, int beta, MoveList * mlist)
1498 {
1499  ASSERT (depth >= 1);
1500 
1501  // If no legal move list was specified, generate and search all moves:
1502  MoveList tmpMoveList;
1503  if (mlist == NULL) {
1504  mlist = &tmpMoveList;
1505  Pos.GenerateMoves(mlist);
1506  }
1507 
1508  // No legal moves to search? Just return an equal score for
1509  // stalemate or -Infinity for checkmate.
1510  if (mlist->Size() == 0) {
1511  return (Pos.IsKingInCheck() ? -Infinity : 0);
1512  }
1513 
1514  bool isOnlyMove = (mlist->Size() == 1);
1515  int bestScore = -Infinity - 1;
1516 
1517  for (uint movenum=0; movenum < mlist->Size(); movenum++) {
1518  simpleMoveT * sm = mlist->Get(movenum);
1519  uint oldNodeCount = NodeCount;
1520  // Make this move and search it:
1521  DoMove (sm);
1522  InCheck[Ply] = Pos.IsKingInCheck (sm);
1523 #define PVS_SEARCH
1524 #ifdef PVS_SEARCH
1525  int score = alpha;
1526  if (movenum == 0) {
1527  score = -Search (depth - 1, -beta, -alpha, true);
1528  } else {
1529  // Do a minimal window search first, to try and quickly
1530  // identify the common case of a move not being good
1531  // enough to improve alpha:
1532  score = -Search (depth - 1, -alpha - 1, -alpha, true);
1533  if (score > alpha && score < beta) {
1534  // This move is good enough to search with the proper
1535  // window; use the score it returned as the lower bound:
1536  score = -Search (depth - 1, -beta, -score, true);
1537  }
1538  }
1539 #else
1540  int score = -Search (depth - 1, -beta, -alpha, true);
1541 #endif
1542  UndoMove (sm);
1543  if (OutOfTime()) { break; }
1544 
1545  // Set the move ordering score of this move to be the number of
1546  // nodes spent on it, so interesting moves of this iteration are
1547  // searched first at the next iteration depth:
1548  sm->score = NodeCount - oldNodeCount;
1549 
1550  // If this is the first move searched at this depth or
1551  // a new best move, update the best score and promote
1552  // the move to be first in the list:
1553  if (movenum == 0 || score > bestScore) {
1554  bestScore = score;
1555  alpha = score;
1556  UpdatePV (sm);
1557  PrintPV (depth, bestScore);
1558  StoreHash (depth, SCORE_EXACT, score, sm, isOnlyMove);
1559  std::rotate(mlist->begin(), mlist->begin() + movenum,
1560  mlist->begin() + movenum + 1);
1561  if (movenum > 0) { EasyMove = false; }
1562  }
1563  }
1564  return bestScore;
1565 }
1566 
1567 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1568 // Engine::Search
1569 // Internal Search routine, used at every depth except
1570 // the root position.
1571 int
1572 Engine::Search (int depth, int alpha, int beta, bool tryNullMove)
1573 {
1574  SetPVLength();
1575 
1576  // If there is no remaining depth, return a quiescent evaluation:
1577  if (depth <= 0) { return Quiesce (alpha, beta); }
1578 
1579  // Check that the absolute depth limit is not exceeded:
1580  if (Ply >= ENGINE_MAX_PLY - 1) { return alpha; }
1581 
1582  // Check for a drawn position (no mating material, repetition, etc):
1583  if (NoMatingMaterial()) { return 0; }
1584  if (FiftyMoveDraw()) { return 0; }
1585  uint repeats = RepeatedPosition();
1586  if (repeats >= 3 || (repeats == 2 && Ply > 2)) { return 0; }
1587 
1588  colorT toMove = Pos.GetToMove();
1589  NodeCount++;
1590 
1591  // Stop now if we ran out of time:
1592  if (OutOfTime()) { return alpha; }
1593 
1594  // Check for a recognized endgame score:
1595  if (Pos.TotalMaterial() <= Recognizer::MaxPieces()) {
1596  int recog = Recognizer::Recognize(&Pos);
1597  int rscore = recogScore(recog);
1598  scoreFlagT rflag = recogFlag(recog);
1599 
1600  if (rflag == SCORE_EXACT) {
1601  return rscore;
1602  } else if (rflag == SCORE_LOWER) {
1603  if (rscore >= beta) { return rscore; }
1604  if (rscore < alpha) { alpha = rscore; }
1605  } else if (rflag == SCORE_UPPER) {
1606  if (rscore <= alpha) { return rscore; }
1607  if (rscore > beta) { beta = rscore; }
1608  }
1609  }
1610 
1611  // Probe the hash table:
1612  int hashscore = alpha;
1613  simpleMoveT hashmove;
1614  bool isOnlyMove = 0;
1615  scoreFlagT hashflag = ProbeHash (depth, &hashscore, &hashmove, &isOnlyMove);
1616 
1617  switch (hashflag) {
1618  case SCORE_NONE:
1619  break;
1620  case SCORE_LOWER:
1621  if (hashscore >= beta) { return hashscore; }
1622  if (hashscore > alpha) { alpha = hashscore; }
1623  break;
1624  case SCORE_UPPER:
1625  if (hashscore <= alpha) { return hashscore; }
1626  if (hashscore < beta) { beta = hashscore; }
1627  break;
1628  case SCORE_EXACT:
1629  if (hashscore > alpha && hashscore < beta) {
1630  UpdatePV (&hashmove);
1631  }
1632  return hashscore;
1633  }
1634 
1635  int baseExtensions = 0;
1636  bool inCheck = InCheck[Ply];
1637 
1638  // Null move pruning:
1639  // If the side to move has at least a few pieces (to reduce the risk
1640  // of zugzwang) and is not in check, and a null move was not made to
1641  // reach this point in the search, try making a null move now. The
1642  // idea is to pass on our move and see (with a shallow search) if
1643  // if the enemy has any move that can score better than the beta
1644  // cutoff. If they have no such move, it means our position is good
1645  // enough to cut off the search without even considering our own
1646  // possible moves.
1647 
1648  if (inCheck || depth < 2 || Pos.NumNonPawns(toMove) < 3) {
1649  tryNullMove = false;
1650  }
1651 
1652  if (tryNullMove) {
1653  Pos.SetToMove (color_Flip(toMove));
1654  squareT oldEPTarget = Pos.GetEPTarget();
1655  Pos.SetEPTarget (NULL_SQUARE);
1656  // We keep track of whether we are in a null move search or
1657  // not, to avoid updating the PV.
1658  InNullMove++;
1659  // Do an R=2 or R=3 nullmove search, depending on remaining depth:
1660  int nulldepth = depth - NullMoveReduction;
1661  if (depth > 6) {
1662  nulldepth--; // An R=3 null move search.
1663  }
1664  int nullscore = -Search (nulldepth - 1, -beta, -beta + 1, false);
1665  InNullMove--;
1666  Pos.SetEPTarget (oldEPTarget);
1667  Pos.SetToMove (toMove);
1668 
1669  // If the null-move score is better than beta, cut the search:
1670  if (nullscore >= beta) {
1671  return beta;
1672  }
1673 
1674  // If the null-move score indicates that making a null move
1675  // would lead to us getting mated, extend the search another
1676  // ply to try and avoid the mate threats:
1677  if (IsGettingMatedScore (nullscore)) { baseExtensions++; }
1678  }
1679 
1680  // In-check extension: search one ply deeper if we are in check.
1681  if (inCheck) { baseExtensions++; }
1682 
1683  // Now we want to generate all legal moves and order them. But if
1684  // we got a move from the hash table, it is worth trying that move
1685  // first, and only generating and scoring the rest of the moves if
1686  // the hash move does not cause a beta cutoff.
1687  // Note that we already know whether the side to move is in check,
1688  // so we pass this information to GenerateMoves to speed it up.
1689 
1690  MoveList mlist;
1691  bool gotHashMove;
1692  if (Pos.IsLegalMove (&hashmove)) {
1693  gotHashMove = true;
1694  // For now, we only add the hash move to the move list.
1695  mlist.push_back(hashmove);
1696  mlist.Get(0)->score = ENGINE_HASH_SCORE;
1697  } else {
1698  // No hash table move, so generate and score all the moves now.
1699  gotHashMove = false;
1700  Pos.GenerateMoves (&mlist, EMPTY, GEN_ALL_MOVES, InCheck[Ply]);
1701  ScoreMoves (&mlist);
1702  isOnlyMove = (mlist.Size() == 1);
1703  }
1704 
1705  // If there is only one legal move, extend the search:
1706  if (isOnlyMove) { baseExtensions++; }
1707 
1708  // Remember the original alpha score:
1709  int oldAlpha = alpha;
1710  int bestMoveIndex = -1;
1711 
1712  // Search each move:
1713  for (uint movenum = 0; movenum < mlist.Size(); movenum++) {
1714  // Find the highest-scoring remaining move:
1715  MoveList::iterator sm = std::min_element(mlist.begin() + movenum, mlist.end());
1716  std::iter_swap(mlist.begin() + movenum, sm);
1717 
1718  // Move-specific extensions:
1719  int extensions = baseExtensions;
1720 
1721  // If moving a pawn to the 7th or 8th rank, extend the search:
1722  if (piece_Type(sm->movingPiece) == PAWN) {
1723  rankT rank = square_Rank(sm->to);
1724  if (rank <= RANK_2 || rank >= RANK_7) { extensions++; }
1725  }
1726 
1727  // Reduce extensions if the search is deep:
1728  if (extensions > 0 && (int)Ply >= depth + depth) { extensions /= 2; }
1729 
1730  // Limit extensions to one ply (only if deep enough?):
1731  if (extensions > 1 /*&& (int)Ply >= depth*/) { extensions = 1; }
1732 
1733  // Make this move and remember if it gives check:
1734  DoMove (sm);
1735  InCheck[Ply] = Pos.IsKingInCheck (sm);
1736 
1737  // Simple futility pruning. Note that pruning with depth of two
1738  // remaining is risky, but seems to work well enough in practise.
1739  // We only prune when:
1740  // (1) there are no extensions,
1741  // (2) we are at ply 3 or deeper,
1742  // (3) the move made does not give check,
1743  // (4) the score does not indicate mate,
1744  // (5) the move is not the only legal move, and
1745  // (6) we are not in a pawn ending.
1746 
1747  if (Pruning && extensions == 0 && Ply > 2 && depth <= 2
1748  && !InCheck[Ply] && !IsMatingScore (alpha) && !isOnlyMove
1749  && Pos.NumNonPawns(WHITE) > 1 && Pos.NumNonPawns(BLACK) > 1) {
1750  int mscore = -ScoreMaterial();
1751  bool futile = false;
1752  if (depth == 1) {
1753  // Futility pruning, when 2 pawns below alpha:
1754  futile = ((mscore + (PawnValue * 2)) < alpha);
1755  } else if (depth == 2) {
1756  // Extended futility pruning, when a rook below alpha:
1757  futile = ((mscore + RookValue) < alpha);
1758  }
1759  // Skip this move if it is futile:
1760  if (futile) {
1761  UndoMove(sm);
1762  continue;
1763  }
1764  }
1765 
1766 #define PVS_SEARCH
1767 #ifdef PVS_SEARCH
1768  // We do a normal search for the first move, but for all other
1769  // moves we try a minimal window search first to save time:
1770  int score = alpha;
1771  if (movenum == 0) {
1772  score = -Search (depth + extensions - 1, -beta, -alpha, true);
1773  } else {
1774  score = -Search (depth + extensions - 1, -alpha - 1, -alpha, true);
1775  if (score > alpha && score < beta) {
1776  // This move is good enough to search with the proper
1777  // window; use the score it returned as the lower bound:
1778  score = -Search (depth + extensions - 1, -beta, -score, true);
1779  }
1780  }
1781 #else
1782  // No PVS, just do a regular search at every move:
1783  int score = -Search (depth + extensions - 1, -beta, -alpha, true);
1784 #endif
1785  UndoMove (sm);
1786 
1787  // If this move scored at least as good as beta, we have
1788  // "failed high" so there is no need to continue searching
1789  // for an even better move:
1790  if (score >= beta) {
1791  IncHistoryValue (sm, depth * depth);
1792  AddKillerMove (sm);
1793  StoreHash (depth, SCORE_LOWER, score, sm, isOnlyMove);
1794  // Fail-high-first-move stats:
1795  nFailHigh++;
1796  if (movenum == 0) { nFailHighFirstMove++; }
1797  return beta;
1798  }
1799 
1800  // If this move is better than the alpha score, it is a new
1801  // best move at this point in the search tree. Update the PV
1802  // (and boost the history value of the move a little? - no):
1803  if (score > alpha) {
1804  alpha = score;
1805  bestMoveIndex = movenum;
1806  UpdatePV (sm);
1807  // IncHistoryValue (sm, depth);
1808  }
1809 
1810  // All done with that move. If it was the first move in the list and
1811  // it was the move from the hashtable, then the remaining moves have
1812  // not been generated and scored for move ordering. We do that now,
1813  // ensuring that the hash table move we just examined is moved to
1814  // the start of the list so it does not get searched again.
1815  if (movenum == 0 && gotHashMove && !isOnlyMove) {
1816  mlist.Clear();
1817  Pos.GenerateMoves (&mlist, EMPTY, GEN_ALL_MOVES, InCheck[Ply]);
1818  ScoreMoves (&mlist);
1819  MoveList::iterator hm = std::find(mlist.begin(), mlist.end(), cmpMove(hashmove));
1820  if (hm != mlist.end()) {
1821  std::iter_swap(mlist.begin(), hm);
1822  } else {
1823  // The hash table move was legal, but not found in the
1824  // move list -- Bizarre!
1825  Output ("# Yikes! Hash table move not in move list! Bug?\n");
1826  }
1827  }
1828  }
1829 
1830  if (mlist.Size() == 0) {
1831  // No legal moves? Must be checkmate or stalemate:
1832  return (InCheck[Ply] ? (-Infinity + Ply) : 0);
1833  }
1834 
1835  // If alpha did not get improved, we "failed low"; every move
1836  // scored worse than our lower bound.
1837  // Store alpha in the transposition table as an upper bound on
1838  // the true score of this position, with no best move.
1839  if (alpha == oldAlpha) {
1840  ASSERT (bestMoveIndex < 0);
1841  StoreHash (depth, SCORE_UPPER, alpha, NULL, isOnlyMove);
1842  } else {
1843  // Update the transposition table with the best move:
1844  ASSERT (bestMoveIndex >= 0);
1845  simpleMoveT * bestMove = mlist.Get(bestMoveIndex);
1846  IncHistoryValue (bestMove, depth * depth);
1847  // Should we also add this as a killer move? Possibly not,
1848  // since it was not good enough to cause a beta cutoff.
1849  // It seems to make little difference.
1850  AddKillerMove (bestMove);
1851  StoreHash (depth, SCORE_EXACT, alpha, bestMove, isOnlyMove);
1852  }
1853  return alpha;
1854 }
1855 
1856 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1857 // Engine::Quiesce
1858 // Search only captures until a stable position is reached
1859 // that can be evaluated.
1860 int
1861 Engine::Quiesce (int alpha, int beta)
1862 {
1863  NodeCount++;
1864  QNodeCount++;
1865 
1866  // Check that the absolute depth limit is not exceeded:
1867  if (Ply >= ENGINE_MAX_PLY - 1) { return alpha; }
1868  SetPVLength();
1869 
1870  // Stop now if we are out of time:
1871  if (OutOfTime()) { return alpha; }
1872 
1873  // Check for a recognized endgame score:
1874  if (Pos.TotalMaterial() <= Recognizer::MaxPieces()) {
1875  int recog = Recognizer::Recognize(&Pos);
1876  int rscore = recogScore(recog);
1877  scoreFlagT rflag = recogFlag(recog);
1878 
1879  if (rflag == SCORE_EXACT) {
1880  return rscore;
1881  } else if (rflag == SCORE_LOWER) {
1882  if (rscore >= beta) { return rscore; }
1883  if (rscore < alpha) { alpha = rscore; }
1884  } else if (rflag == SCORE_UPPER) {
1885  if (rscore <= alpha) { return rscore; }
1886  if (rscore > beta) { beta = rscore; }
1887  }
1888  }
1889 
1890  // Find the static evaluation of this position, to either cause
1891  // a beta cutoff or improve the alpha score:
1892  int staticScore = Score (alpha, beta);
1893  if (staticScore >= beta) { return beta; }
1894  if (staticScore > alpha) { alpha = staticScore; }
1895 
1896  // Check for a static score so far below alpha that no capture
1897  // is going to be good enough anyway:
1898  int margin = PawnValue;
1899  if (staticScore + QueenValue + margin < alpha) { return alpha; }
1900 
1901  // Generate and score the list of captures:
1902  MoveList mlist;
1903  Pos.GenerateMoves (&mlist, GEN_CAPTURES);
1904  for (uint m=0; m < mlist.Size(); m++) {
1905  simpleMoveT * sm = mlist.Get(m);
1906  sm->score = SEE (sm->from, sm->to);
1907  }
1908 
1909  // Iterate through each quiescent move to find a beta cutoff or
1910  // improve the alpha score:
1911 
1912  for (uint i = 0; i < mlist.Size(); i++) {
1913  // Find the highest-scoring remaining move, make it and search:
1914  MoveList::iterator sm = std::min_element(mlist.begin() + i, mlist.end());
1915  std::iter_swap(mlist.begin() + i, sm);
1916  pieceT promote = piece_Type(sm->promote);
1917 
1918  // Skip underpromotions:
1919  if (promote != EMPTY && promote != QUEEN) { continue; }
1920 
1921  // Stop if the capture gain is negative or is so small that it
1922  // will (very likely) not improve alpha:
1923  if (sm->score < 0) { break; }
1924  if ((sm->score + staticScore + margin) < alpha) { break; }
1925 
1926  // Make the move and evaluate it:
1927  DoMove (sm);
1928  int score = -Quiesce (-beta, -alpha);
1929  UndoMove (sm);
1930 
1931  // Check for a score so good it causes a beta cutoff:
1932  if (score >= beta) { return score; }
1933 
1934  // See if we have a new best move:
1935  if (score > alpha) {
1936  alpha = score;
1937  UpdatePV (sm);
1938  }
1939  }
1940  return alpha;
1941 }
1942 
1943 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1944 // Engine::SEE
1945 // Static Exchange Evaluator.
1946 // Evaluates the approximate material result of moving the piece
1947 // from the from square (which must not be empty) to the target
1948 // square (which may be empty or may hold an enemy piece).
1949 int
1950 Engine::SEE (squareT from, squareT target)
1951 {
1952  const pieceT * board = Pos.GetBoard();
1953  SquareList attackers[2];
1954  pieceT mover = piece_Type(board[from]);
1955  ASSERT (mover != EMPTY);
1956  colorT stm = piece_Color_NotEmpty(board[from]);
1957 
1958 #define SEE_ADD(c,sq) attackers[(c)].Add(sq)
1959 
1960  // Currently the SEE method is only called for legal moves, so if
1961  // the moving piece is a king then it clearly cannot be captured.
1962  // If potentially illegal king moves are to be passed to this
1963  // method, the following optimisation should be removed.
1964  if (mover == KING) { return PieceValue(board[target]); }
1965 
1966  // Find the estimated result assuming one recapture:
1967  int fastResult = PieceValue(board[target]) - PieceValue(mover);
1968 
1969  // We can do quick estimation for a big gain, but have to be
1970  // careful since move ordering is very sensitive to positive SEE
1971  // scores. Only return a fast estimate for PxQ, NxQ, BxQ and PxR:
1972  if (fastResult > KnightValue && mover != ROOK) { return fastResult; }
1973 
1974  // Add attacking pawns to the attackers list:
1975  squareT pawnSq = square_Move (target, DOWN_LEFT);
1976  if (board[pawnSq] == WP && pawnSq != from) { SEE_ADD (WHITE, pawnSq); }
1977  pawnSq = square_Move (target, DOWN_RIGHT);
1978  if (board[pawnSq] == WP && pawnSq != from) { SEE_ADD (WHITE, pawnSq); }
1979  pawnSq = square_Move (target, UP_LEFT);
1980  if (board[pawnSq] == BP && pawnSq != from) { SEE_ADD (BLACK, pawnSq); }
1981  pawnSq = square_Move (target, UP_RIGHT);
1982  if (board[pawnSq] == BP && pawnSq != from) { SEE_ADD (BLACK, pawnSq); }
1983 
1984  // Quick estimation for a nonpawn capturing a lesser-valued piece (or
1985  // moving to an empty square) which is defended by an enemy pawn.
1986  if (fastResult < -PawnValue && attackers[color_Flip(stm)].Size() > 0) {
1987  return fastResult;
1988  }
1989 
1990  // Add attacking knights. Only bother searching for them if there
1991  // are any knights on the appropriate square color.
1992  colorT knightSquareColor = color_Flip(square_Color(target));
1993  uint nEligibleKnights = Pos.SquareColorCount(WN, knightSquareColor)
1994  + Pos.SquareColorCount(BN, knightSquareColor);
1995  if (nEligibleKnights > 0) {
1996  const squareT * nextKnightSq = knightAttacks[target];
1997  while (true) {
1998  squareT dest = *nextKnightSq;
1999  if (dest == NULL_SQUARE) { break; }
2000  nextKnightSq++;
2001  pieceT p = board[dest];
2002  if (piece_Type(p) != KNIGHT) { continue; }
2003  if (dest == from) { continue; }
2004  // Quick estimate when this recapture ensures a negative result:
2005  colorT knightColor = piece_Color_NotEmpty(p);
2006  if (fastResult < -KnightValue && knightColor != stm) {
2007  return fastResult + KnightValue / 2;
2008  }
2009  SEE_ADD (knightColor, dest);
2010  }
2011  }
2012 
2013  // Add the first sliding attackers in each direction. Others
2014  // may appear later as appropriate, when the piece in front
2015  // of them takes part in the capture sequence.
2016 
2017  // First make an array containing all the directions that contain
2018  // potential sliding attackers, to avoid searching useless directions.
2019  rankT rank = square_Rank(target);
2020  fyleT fyle = square_Fyle(target);
2021  leftDiagT ul = square_LeftDiag(target);
2022  rightDiagT ur = square_RightDiag(target);
2023  uint rankCount = Pos.RankCount(WQ,rank) + Pos.RankCount(BQ,rank)
2024  + Pos.RankCount(WR,rank) + Pos.RankCount(BR,rank);
2025  uint fyleCount = Pos.FyleCount(WQ,fyle) + Pos.FyleCount(BQ,fyle)
2026  + Pos.FyleCount(WR,fyle) + Pos.FyleCount(BR,fyle);
2027  uint upLeftCount = Pos.LeftDiagCount(WQ,ul) + Pos.LeftDiagCount(BQ,ul)
2028  + Pos.LeftDiagCount(WB,ul) + Pos.LeftDiagCount(BB,ul);
2029  uint upRightCount = Pos.RightDiagCount(WQ,ur) + Pos.RightDiagCount(BQ,ur)
2030  + Pos.RightDiagCount(WB,ur) + Pos.RightDiagCount(BB,ur);
2031 
2032  // If the moving piece is a slider, it is worth removing it from the
2033  // rank/file/diagonal counts because we will avoid searching two
2034  // directions if it is the only slider on its rank/file/diagonal.
2035  if (piece_IsSlider(mover)) {
2036  if (square_Rank(from) == square_Rank(target)) {
2037  rankCount--;
2038  } else if (square_Fyle(from) == square_Fyle(target)) {
2039  fyleCount--;
2040  } else if (square_LeftDiag(from) == square_LeftDiag(target)) {
2041  upLeftCount--;
2042  } else {
2043  ASSERT (square_RightDiag(from) == square_RightDiag(target));
2044  upRightCount--;
2045  }
2046  }
2047 
2048  // Build the list of directions with potential sliding capturers:
2049  uint nDirs = 0;
2050  directionT sliderDir[8];
2051  if (rankCount > 0) {
2052  sliderDir[nDirs++] = LEFT;
2053  sliderDir[nDirs++] = RIGHT;
2054  }
2055  if (fyleCount > 0) {
2056  sliderDir[nDirs++] = UP;
2057  sliderDir[nDirs++] = DOWN;
2058  }
2059  if (upLeftCount > 0) {
2060  sliderDir[nDirs++] = UP_LEFT;
2061  sliderDir[nDirs++] = DOWN_RIGHT;
2062  }
2063  if (upRightCount > 0) {
2064  sliderDir[nDirs++] = UP_RIGHT;
2065  sliderDir[nDirs++] = DOWN_LEFT;
2066  }
2067 
2068  // Iterate over each direction, looking for an attacking slider:
2069 
2070  for (uint dirIndex = 0; dirIndex < nDirs; dirIndex++) {
2071  directionT dir = sliderDir[dirIndex];
2072  squareT dest = target;
2073  squareT last = square_Last (target, dir);
2074  int delta = direction_Delta (dir);
2075  uint distance = 0;
2076 
2077  while (dest != last) {
2078  dest += delta;
2079  distance++;
2080  pieceT p = board[dest];
2081  if (p == EMPTY) { continue; }
2082  if (dest == from) { continue; }
2083  pieceT ptype = piece_Type(p);
2084  if (ptype == PAWN) {
2085  // Look through this pawn if it was also a capturer.
2086  if (distance != 1) { break; }
2087  if (p == WP) {
2088  if (dir == DOWN_LEFT || dir == DOWN_RIGHT) { continue; }
2089  } else {
2090  if (dir == UP_LEFT || dir == UP_RIGHT) { continue; }
2091  }
2092  break;
2093  }
2094  if (! piece_IsSlider(ptype)) { break; }
2095  if (ptype == ROOK && direction_IsDiagonal(dir)) { break; }
2096  if (ptype == BISHOP && !direction_IsDiagonal(dir)) { break; }
2098 
2099  // Quick estimate when this recapture ensures a negative result:
2100  if (fastResult < -BishopValue && ptype == BISHOP) {
2101  if (c != stm) { return fastResult + BishopValue / 2; }
2102  } else if (fastResult < -RookValue && ptype == ROOK) {
2103  if (c != stm) { return fastResult + RookValue / 2; }
2104  }
2105 
2106  // OK, we have a sliding attacker. Add it:
2107  SEE_ADD (c, dest);
2108  break;
2109  }
2110  }
2111 
2112  // Add one capturing king if the other king cannot capture:
2113  squareT wk = Pos.GetKingSquare (WHITE);
2114  squareT bk = Pos.GetKingSquare (BLACK);
2115  if (wk != from && bk != from) {
2116  bool wkAttacks = square_Adjacent (target, wk);
2117  bool bkAttacks = square_Adjacent (target, bk);
2118  if (wkAttacks && !bkAttacks) {
2119  SEE_ADD (WHITE, wk);
2120  } else if (bkAttacks && !wkAttacks) {
2121  SEE_ADD (BLACK, bk);
2122  }
2123  }
2124 
2125  // Now go through the attack lists (which may get hidden sliders added
2126  // as sliding pieces make captures) finding the best capture sequence.
2127 
2128  bool targetIsPromoSquare = (target <= H1 || target >= A8);
2129  int swaplist[32];
2130  uint nswaps = 1;
2131  swaplist[0] = PieceValue (board[target]);
2132  int attackedVal = PieceValue (mover);
2133 
2134  // Adjust the swap value for a promotion:
2135  if (targetIsPromoSquare && attackedVal == PawnValue) {
2136  swaplist[0] += QueenValue - PawnValue;
2137  attackedVal = QueenValue;
2138  }
2139 
2140  // Add as many captures to the sequence as possible, using
2141  // lowest-valued pieces first:
2142  while (true) {
2143  // Switch to the other side:
2144  stm = color_Flip(stm);
2145  SquareList * attackList = &(attackers[stm]);
2146  uint attackCount = attackList->Size();
2147 
2148  // Has this side run out of pieces to capture with?
2149  if (attackCount == 0) { break; }
2150 
2151  // Find the best (lowest-valued) piece to capture with:
2152  uint bestIndex = 0;
2153  squareT attackSquare = attackList->Get(0);
2154  int attackValue = PieceValue(board[attackSquare]);
2155  for (uint i = 1; i < attackCount; i++) {
2156  if (attackValue == PawnValue) { break; }
2157  squareT newSquare = attackList->Get(i);
2158  int newValue = PieceValue(board[newSquare]);
2159  if (newValue < attackValue) {
2160  attackSquare = newSquare;
2161  attackValue = newValue;
2162  bestIndex = i;
2163  }
2164  }
2165  pieceT attackPiece = piece_Type(board[attackSquare]);
2166 
2167  // Update the swap list:
2168  swaplist[nswaps] = -swaplist[nswaps-1] + attackedVal;
2169  nswaps++;
2170  attackedVal = attackValue;
2171 
2172  // Fudge the value for a promotion, turning the pawn into a queen:
2173  if (targetIsPromoSquare && attackValue == PawnValue) {
2174  swaplist[nswaps-1] += QueenValue - PawnValue;
2175  attackedVal = QueenValue;
2176  }
2177 
2178  // Remove the chosen attacker from the list:
2179  attackList->Remove(bestIndex);
2180 
2181  // If the attacker is a slider, look for another slider behind it:
2182  if (piece_IsSlider (attackPiece)) {
2183  directionT dir = sqDir[target][attackSquare];
2184  ASSERT (dir != NULL_DIR);
2185  squareT dest = attackSquare;
2186  squareT last = square_Last (dest, dir);
2187  int delta = direction_Delta (dir);
2188 
2189  while (dest != last) {
2190  dest += delta;
2191  pieceT p = board[dest];
2192  if (p == EMPTY) { continue; }
2193  pieceT pt = piece_Type(p);
2194  if (! piece_IsSlider(pt)) { break; }
2195  if (pt == ROOK && direction_IsDiagonal(dir)) { break; }
2196  if (pt == BISHOP && !direction_IsDiagonal(dir)) { break; }
2197  // OK, we have another sliding attacker. Add it:
2198  SEE_ADD (piece_Color_NotEmpty(p), dest);
2199  break;
2200  }
2201  }
2202  }
2203 
2204  // Finally, go backwards through the swap list and determine when one
2205  // side would stop because further exchanges would be useless:
2206  nswaps--;
2207  while (nswaps > 0) {
2208  uint prev = nswaps - 1;
2209  if (swaplist[nswaps] > -swaplist[prev]) {
2210  swaplist[prev] = -swaplist[nswaps];
2211  }
2212  nswaps--;
2213  }
2214  return swaplist[0];
2215 }
2216 
2217 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2218 // Engine::ScoreMoves
2219 // Gives each move in the specified move list a score for move
2220 // ordering. Captures are scored using static exchange evaluation
2221 // while non-capture scores are based on killer move and history
2222 // heuristic information. Promotions are treated as captures.
2223 // The ordering has four basic categories:
2224 // (1) Non-losing captures (ordered by SEE value, score >= EMH * 2);
2225 // (2) Non-capture killer moves (EMH <= score < 2 * EMH);
2226 // (3) Other non-captures (by history heuristic, 0 <= score < EMH);
2227 // (4) Losing captures (ordered by SEE value, score < 0).
2228 // where EMH = ENGINE_MAX_HISTORY is the history value threshold.
2229 void
2230 Engine::ScoreMoves (MoveList * mlist)
2231 {
2232  for (uint i = 0; i < mlist->Size(); i++) {
2233  simpleMoveT * sm = mlist->Get(i);
2234  if (sm->capturedPiece != EMPTY || sm->promote != EMPTY) {
2235  int see = SEE (sm->from, sm->to);
2236  if (see >= 0) {
2237  sm->score = ENGINE_MAX_HISTORY * 2 + see;
2238  } else {
2239  sm->score = see;
2240  }
2241  } else {
2242  // Non-capture; just use the history/killer value for this move.
2243  sm->score = GetHistoryValue (sm);
2244  if (IsKillerMove (sm)) {
2245  sm->score += ENGINE_MAX_HISTORY;
2246  }
2247  }
2248  }
2249 }
2250 
2251 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2252 // Engine::Output
2253 // Prints a formatted string (as passed to printf) to standard output
2254 // and the the log file if one is being used.
2255 void
2256 Engine::Output (const char * format, ...)
2257 {
2258  va_list ap;
2259  va_start (ap, format);
2260  vprintf (format, ap);
2261  if (LogFile != NULL) {
2262  vfprintf (LogFile, format, ap);
2263  }
2264  va_end (ap);
2265 }
2266 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2267 // Engine::PrintPV
2268 // Print the current depth, score and principal variation.
2269 void
2270 Engine::PrintPV (uint depth, int score, const char * note)
2271 {
2272  if (! PostInfo) { return; }
2273  uint ms = Elapsed.MilliSecs();
2274  if (XBoardMode && ms < 50 && Ply < 6) { return; }
2275 
2276  if (XBoardMode) {
2277  Output (" %2u %6d %5u %9u ", depth, score, ms / 10, NodeCount);
2278  } else {
2279  Output (" %2u %-3s %+6d %5u %9u ", depth, note, score, ms, NodeCount);
2280  }
2281 
2282  principalVarT * pv = &(PV[0]);
2283  uint i;
2284 
2285  if (Pos.GetToMove() == BLACK) {
2286  Output ("%u...", Pos.GetFullMoveCount());
2287  }
2288 
2289  // Make and print each PV move:
2290  for (i = 0; i < pv->length; i++) {
2291  simpleMoveT * sm = &(pv->move[i]);
2292 
2293  // Check for legality, to protect against hash table
2294  // false hits and bugs in PV updating:
2295  if (! Pos.IsLegalMove (sm)) {
2296  Output (" <illegal>");
2297  break;
2298  }
2299  if (i > 0) { Output (" "); }
2300  if (Pos.GetToMove() == WHITE) {
2301  Output ("%u.", Pos.GetFullMoveCount());
2302  }
2303  char s[10];
2304  Pos.MakeSANString (sm, s, SAN_MATETEST);
2305  Output ("%s", s);
2306  Pos.DoSimpleMove (sm);
2307  }
2308  Output ("\n");
2309  // Undo each PV move that was made:
2310  for (; i > 0; i--) {
2311  Pos.UndoSimpleMove (&(pv->move[i-1]));
2312  }
2313 }
2314 
2315 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2316 // Engine::OutOfTime
2317 // Returns true if the search time limit has been reached.
2318 // "Out Of Time" is also the name of a great R.E.M. album. :-)
2319 bool
2320 Engine::OutOfTime ()
2321 {
2322  if (IsOutOfTime) { return true; }
2323 
2324  // Only check the time approximately every 1000 nodes for speed:
2325  if ((NodeCount & 1023) != 0) { return false; }
2326 
2327  int ms = Elapsed.MilliSecs();
2328 
2329  if (EasyMove) {
2330  IsOutOfTime = (ms > MinSearchTime);
2331  } else if (HardMove) {
2332  IsOutOfTime = (ms > MaxSearchTime);
2333  } else {
2334  IsOutOfTime = (ms > SearchTime);
2335  }
2336 
2337  if (!IsOutOfTime && CallbackFunction != NULL) {
2338  IsOutOfTime = CallbackFunction (this, CallbackData);
2339  }
2340 
2341  return IsOutOfTime;
2342 }
2343 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2344 // Engine::PerfTest
2345 // Returns the number of leaf node moves when generating, making and
2346 // unmaking every move to the specified depth from the current position.
2347 uint
2349 {
2350  if (depth <= 0) { return 1; }
2351  MoveList mlist;
2352  Pos.GenerateMoves (&mlist);
2353  uint nmoves = 0;
2354  for (uint i = 0; i < mlist.Size(); i++) {
2355  simpleMoveT * sm = mlist.Get(i);
2356  Pos.DoSimpleMove (sm);
2357  nmoves += PerfTest (depth-1);
2358  Pos.UndoSimpleMove (sm);
2359  }
2360  return nmoves;
2361 }
2362 
2363 //////////////////////////////////////////////////////////////////////
2364 // EOF: engine.cpp
2365 //////////////////////////////////////////////////////////////////////
2366 
unsigned char byte
Definition: common.h:97
squareT square_FlipRank(squareT sq)
Definition: common.h:421
void SetToMove(colorT c)
Definition: position.h:154
const pieceT BB
Definition: common.h:237
uint square_Distance(squareT from, squareT to)
Definition: common.h:449
piecew sq
Definition: board.tcl:1293
const colorT WHITE
Definition: common.h:203
pieceT piece_Type(pieceT p)
Definition: common.h:287
uint GetCount(colorT c)
Definition: position.h:163
void MakeSANString(simpleMoveT *sm, char *s, sanFlagT flag)
Definition: position.cpp:2114
const squareT C8
Definition: common.h:350
sqsqname
Definition: board.tcl:292
const pieceT BN
Definition: common.h:237
const squareT B3
Definition: common.h:345
const directionT UP
Definition: common.h:547
iterator end()
Definition: movelist.h:80
const castleDirT KSIDE
Definition: common.h:215
squareT square_Move(squareT sq, directionT dir)
Definition: sqmove.h:173
const squareT F8
Definition: common.h:350
colorT square_Color(squareT sq)
Definition: common.h:405
const squareT H1
Definition: common.h:343
const fyleT G_FYLE
Definition: common.h:361
const squareT NULL_SQUARE
Definition: common.h:352
bool IsKingInCheck()
Definition: position.h:244
byte rankT
Definition: common.h:115
byte GetCastlingFlags()
Definition: position.h:203
const squareT D2
Definition: common.h:344
const directionT LEFT
Definition: common.h:549
uint sig
Definition: engine.h:81
const squareT G6
Definition: common.h:348
const rankT RANK_2
Definition: common.h:355
#define ASSERT(f)
Definition: common.h:67
const squareT H7
Definition: common.h:349
const squareT C1
Definition: common.h:343
const rankT RANK_8
Definition: common.h:356
directionT sqDir[66][66]
Definition: misc.cpp:24
const fyleT B_FYLE
Definition: common.h:360
const directionT UP_LEFT
Definition: common.h:551
const pieceT BQ
Definition: common.h:237
const pieceT WQ
Definition: common.h:236
const pieceT KING
Definition: common.h:221
squareT enpassant
Definition: engine.h:72
const rankT RANK_3
Definition: common.h:355
uint RightDiagCount(pieceT p, rightDiagT diag)
Definition: position.h:181
void ClearHashTable(void)
Definition: engine.cpp:1125
squareT GetKingSquare(colorT c)
Definition: position.h:195
const pieceT BP
Definition: common.h:237
uint PawnHashValue(void)
Definition: position.h:211
void tte_SetBestMove(transTableEntryT *tte, simpleMoveT *bestMove)
Definition: engine.cpp:1164
const colorT BLACK
Definition: common.h:204
const uint ENGINE_MAX_PLY
Definition: engine.h:30
const scoreFlagT SCORE_LOWER
Definition: engine.h:53
int Think(MoveList *mlist)
Definition: engine.cpp:1376
bool tte_IsOnlyMove(transTableEntryT *tte)
Definition: engine.cpp:1161
static int Recognize(Position *pos)
Definition: recog.cpp:34
void DoSimpleMove(simpleMoveT *sm)
Definition: position.cpp:1789
const squareT E7
Definition: common.h:349
const int ENGINE_MAX_HISTORY
Definition: engine.h:31
uint Size()
Definition: movelist.h:81
rankT square_Rank(squareT sq)
Definition: common.h:385
byte fyleT
Definition: common.h:116
byte * GetMaterial()
Definition: position.h:151
byte depth
Definition: engine.h:69
const fyleT H_FYLE
Definition: common.h:361
byte flags
Definition: engine.h:70
void Add(squareT sq)
Definition: sqlist.h:53
bool IsLegalMove(simpleMoveT *sm)
Definition: position.cpp:877
const squareT D7
Definition: common.h:349
const fyleT C_FYLE
Definition: common.h:360
const squareT A8
Definition: common.h:350
colorT color_Flip(colorT c)
Definition: common.h:210
short wShortbLongScore
Definition: engine.h:84
const squareT E6
Definition: common.h:348
void CopyFrom(Position *src)
Definition: position.h:291
uint TotalMaterial()
Definition: position.h:164
const directionT RIGHT
Definition: common.h:550
uint NumNonPawns(colorT c)
Definition: position.h:165
scoreFlagT recogFlag(int value)
Definition: recog.h:32
iterator begin()
Definition: movelist.h:79
void SetPosition(Position *pos)
Definition: engine.cpp:1333
byte PieceCount(pieceT p)
Definition: position.h:150
const pieceT BISHOP
Definition: common.h:224
const squareT A1
Definition: common.h:343
const pieceT KNIGHT
Definition: common.h:225
squareT square_Make(fyleT f, rankT r)
Definition: common.h:372
colorpct?col?
Definition: ptracker.tcl:77
int find(const char *filename)
find() - search for a database.
Definition: dbasepool.cpp:51
const squareT A7
Definition: common.h:349
uint FyleCount(pieceT p, fyleT f)
Definition: position.h:172
void RetractMove(void)
Definition: engine.cpp:947
simpleMoveT move[ENGINE_MAX_PLY]
Definition: engine.h:42
uint Size()
Definition: sqlist.h:54
byte sequence
Definition: engine.h:71
void Reset()
Definition: timer.h:58
uint GetSquares(pieceT p, SquareList *sqlist)
Definition: position.cpp:3173
const directionT UP_RIGHT
Definition: common.h:552
int MilliSecs()
Definition: timer.h:60
const castleDirT QSIDE
Definition: common.h:215
const int ENGINE_HASH_SCORE
Definition: engine.h:32
const pieceT EMPTY
Definition: common.h:234
const pieceT WB
Definition: common.h:236
sizew
Definition: board.tcl:619
const squareT G1
Definition: common.h:343
void UndoSimpleMove(simpleMoveT *sm)
Definition: position.cpp:1940
int ScoreMaterial(void)
Definition: engine.cpp:313
#define SEE_ADD(c, sq)
sort?type?
Definition: analysis.tcl:321
const pieceT QUEEN
Definition: common.h:222
void tte_GetBestMove(transTableEntryT *tte, simpleMoveT *bestMove)
Definition: engine.cpp:1173
uint32_t uint
Definition: common.h:99
uint pawnhash
Definition: engine.h:80
Definition: board.tcl:276
void Clear()
Definition: movelist.h:82
uint RepeatedPosition(void)
Definition: engine.cpp:1056
const squareT H2
Definition: common.h:344
int direction_Delta(directionT dir)
Definition: common.h:619
uint LeftDiagCount(pieceT p, leftDiagT diag)
Definition: position.h:178
const pieceT ROOK
Definition: common.h:223
rightDiagT square_RightDiag(squareT sq)
Definition: common.h:397
Definition: engine.h:64
void StdStart()
Definition: position.h:145
short score
Definition: engine.h:67
squareT square_FlipFyle(squareT sq)
Definition: common.h:413
squareT * GetList(colorT c)
Definition: position.h:162
void tte_SetFlags(transTableEntryT *tte, scoreFlagT sflag, colorT stm, byte castling, bool isOnlyMove)
Definition: engine.cpp:1148
bool NoMatingMaterial(void)
Definition: engine.cpp:1011
const squareT H8
Definition: common.h:350
const rankT RANK_5
Definition: common.h:355
byte rightDiagT
Definition: common.h:118
const squareT B1
Definition: common.h:343
short score
Definition: engine.h:82
void PlayMove(simpleMoveT *move)
Definition: engine.cpp:927
const pieceT PAWN
Definition: common.h:226
const squareT G8
Definition: common.h:350
squareT square_Last(squareT sq, directionT dir)
Definition: sqmove.h:186
uint HashValue(void)
Definition: position.h:210
colorT stm
Definition: engine.h:98
scoreFlagT tte_ScoreFlag(transTableEntryT *tte)
Definition: engine.cpp:1152
const squareT D1
Definition: common.h:343
const squareT B8
Definition: common.h:350
void GenerateMoves(MoveList *mlist, pieceT mask, genMovesT genType, bool maybeInCheck)
Definition: position.cpp:787
uint Mobility(pieceT p, colorT color, squareT from)
Definition: position.cpp:1688
void SetEPTarget(squareT s)
Definition: position.h:152
const directionT NULL_DIR
Definition: common.h:546
colorT tte_SideToMove(transTableEntryT *tte)
Definition: engine.cpp:1155
bool square_IsEdgeSquare(squareT sq)
Definition: common.h:476
leftDiagT square_LeftDiag(squareT sq)
Definition: common.h:391
uint pawnhash
Definition: engine.h:66
const scoreFlagT SCORE_NONE
Definition: engine.h:51
const squareT E5
Definition: common.h:347
const genMovesT GEN_CAPTURES
Definition: position.h:57
const squareT D6
Definition: common.h:348
int Score(void)
Definition: engine.cpp:282
uint RankCount(pieceT p, rankT r)
Definition: position.h:175
byte scoreFlagT
Definition: engine.h:49
short wLongbShortScore
Definition: engine.h:83
squareT to
Definition: movelist.h:40
const genMovesT GEN_ALL_MOVES
Definition: position.h:59
uint16_t ushort
Definition: common.h:98
uint npieces
Definition: engine.h:97
squareT from
Definition: movelist.h:39
colorT piece_Color(pieceT p)
Definition: common.h:280
const scoreFlagT SCORE_EXACT
Definition: engine.h:52
const squareT knightAttacks[66][9]
Definition: attacks.h:43
const pieceT WP
Definition: common.h:236
const squareT E2
Definition: common.h:344
simpleMoveT * Get(uint index)
Definition: movelist.h:101
uint SquareColorCount(pieceT p, colorT sqColor)
Definition: position.h:184
void Remove(uint index)
Definition: sqlist.h:77
const pieceT * GetBoard() const
Definition: position.h:189
pieceT capturedPiece
Definition: movelist.h:42
uint hash
Definition: engine.h:95
uint length
Definition: engine.h:41
const directionT DOWN
Definition: common.h:548
materialw
Definition: board.tcl:1551
const scoreFlagT SCORE_UPPER
Definition: engine.h:54
const squareT A2
Definition: common.h:344
const squareT E8
Definition: common.h:350
ushort bestMove
Definition: engine.h:68
const squareT D3
Definition: common.h:345
const squareT D4
Definition: common.h:346
const rankT RANK_6
Definition: common.h:355
bool FiftyMoveDraw(void)
Definition: engine.cpp:1030
uint pawnhash
Definition: engine.h:96
colorT piece_Color_NotEmpty(pieceT p)
Definition: common.h:284
bool direction_IsDiagonal(directionT dir)
Definition: common.h:595
const squareT E3
Definition: common.h:345
byte colorT
Definition: common.h:112
byte tte_Castling(transTableEntryT *tte)
Definition: engine.cpp:1158
const squareT B6
Definition: common.h:348
const pieceT BR
Definition: common.h:237
colorT GetToMove()
Definition: position.h:155
bool InPawnEnding()
Definition: position.h:168
const pieceT WN
Definition: common.h:236
Definition: engine.h:94
byte directionT
Definition: common.h:114
const squareT E1
Definition: common.h:343
const squareT D5
Definition: common.h:347
static uint MaxPieces(void)
Definition: recog.h:71
int recogScore(int value)
Definition: recog.h:31
bool square_Adjacent(squareT from, squareT to)
Definition: common.h:677
int32_t score
Definition: movelist.h:49
byte leftDiagT
Definition: common.h:117
const directionT DOWN_RIGHT
Definition: common.h:554
const rankT RANK_1
Definition: common.h:355
ushort GetFullMoveCount()
Definition: position.h:158
squareT GetEPTarget()
Definition: position.h:153
uint hash
Definition: engine.h:65
const squareT E4
Definition: common.h:346
const fyleT A_FYLE
Definition: common.h:360
const rankT RANK_4
Definition: common.h:355
pieceT movingPiece
Definition: movelist.h:38
void SetHashTableKilobytes(uint sizeKB)
Definition: engine.cpp:1080
void SetPawnTableKilobytes(uint sizeKB)
Definition: engine.cpp:1103
const rankT RANK_7
Definition: common.h:356
uint PerfTest(uint depth)
Definition: engine.cpp:2348
void push_back(const simpleMoveT &sm)
Definition: movelist.h:97
const squareT F1
Definition: common.h:343
bool GetCastling(colorT c, castleDirT dir)
Definition: position.h:322
pieceT piece_Make(colorT c, pieceT p)
Definition: common.h:290
const directionT DOWN_LEFT
Definition: common.h:553
const fyleT F_FYLE
Definition: common.h:360
Definition: engine.h:79
byte fyleHasPassers[2]
Definition: engine.h:85
pieceT promote
Definition: movelist.h:43
byte squareT
Definition: common.h:113
const squareT D8
Definition: common.h:350
const sanFlagT SAN_MATETEST
Definition: position.h:41
byte pieceT
Definition: common.h:111
void ClearPawnTable(void)
Definition: engine.cpp:1137
fyleT square_Fyle(squareT sq)
Definition: common.h:379
squareT Get(uint index)
Definition: sqlist.h:61
const pieceT WR
Definition: common.h:236
bool piece_IsSlider(pieceT p)
Definition: common.h:317