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