Scid  4.6.5
engine.h
Go to the documentation of this file.
1 
2 //////////////////////////////////////////////////////////////////////
3 //
4 // FILE: engine.h
5 // Engine class
6 //
7 // Part of: Scid (Shane's Chess Information Database)
8 // Version: 3.5
9 //
10 // Notice: Copyright (c) 2002-2003 Shane Hudson. All rights reserved.
11 //
12 // Author: Shane Hudson (sgh@users.sourceforge.net)
13 //
14 //////////////////////////////////////////////////////////////////////
15 
16 // The Engine class provides a simple chess position evaluator
17 // based on negamax with quiescent search and alpha/beta pruning.
18 // It is used in Scid for doing small quick searches to determine
19 // which of the possible legal moves to or from a particular square
20 // to suggest as the best move for faster mouse input.
21 
22 #ifndef SCID_ENGINE_H
23 #define SCID_ENGINE_H
24 
25 #include <stdarg.h>
26 
27 #include "position.h"
28 #include "timer.h"
29 
30 const uint ENGINE_MAX_PLY = 40; // Maximum search ply.
31 const int ENGINE_MAX_HISTORY = 100000; // Max accumulated history value.
32 const int ENGINE_HASH_SCORE = 100000000; // To order hash moves first.
33 const uint ENGINE_HASH_KB = 32; // Default hash table size in KB.
34 const uint ENGINE_PAWN_KB = 1; // Default pawn table size in KB.
35 
36 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
37 // principalVarT
38 // Stores the principal variation at one search Ply depth.
39 //
40 struct principalVarT {
43 };
44 
45 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
46 // scoreFlagT
47 // Types of transposition table score and endgame recognition score.
48 //
49 typedef byte scoreFlagT;
50 const scoreFlagT
51  SCORE_NONE = 0, // Not a useful score.
52  SCORE_EXACT = 1, // Exact score.
53  SCORE_LOWER = 2, // Lower bound, real score could be higher.
54  SCORE_UPPER = 3; // Upper bound, real score could be lower.
55 
56 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
57 // transTableEntryT
58 // Transposition table entry.
59 // Apart from the type flag, depth and score, it also stores the
60 // hash codes and other position values for safety checks to avoid
61 // a false hit.
62 // The best move is also stored, in a compact format to save space.
63 //
65  uint hash; // Hash value.
66  uint pawnhash; // Pawn hash value, for extra safety check.
67  short score; // Evaluation score.
68  ushort bestMove; // Best move from/to/promote values.
69  byte depth; // Depth of evaluation.
70  byte flags; // Score type, side to move and castling flags.
71  byte sequence; // Sequence number, for detecting old entries.
72  squareT enpassant; // En passant target square.
73 };
74 
75 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
76 // pawnTableEntryT
77 // Pawn structure score hash table entry.
78 //
80  uint pawnhash; // Pawn hash value for this pawn structure.
81  uint sig; // Safety check value, to avoid false hits.
82  short score; // Positional score for pawn structure.
83  short wLongbShortScore; // Pawn storm score for wk on abc, bk on abc.
84  short wShortbLongScore; // Pawn storm score for wk on fgh, bk on fgh.
85  byte fyleHasPassers[2]; // One bit per file, indicating passed pawns.
86 };
87 
88 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
89 // repeatT
90 // Repetition-detection stack entry.
91 // An entry is pushed onto the stack when a move is made, and
92 // popped off when the move is unmade.
93 //
94 struct repeatT {
95  uint hash; // Position hash code.
96  uint pawnhash; // Position pawn-structure hash code.
97  uint npieces; // Total number of pieces in position.
98  colorT stm; // Side to move.
99 };
100 
101 
102 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
103 // Engine
104 // Class representing a chess engine.
105 //
106 class Engine {
107 private:
108  Position RootPos; // Position at start of search.
109  Position Pos; // Current position in search.
110  uint MaxDepth; // Search depth limit.
111  int SearchTime; // Search time limit in milliseconds.
112  int MinSearchTime; // Minimum search time in milliseconds.
113  int MaxSearchTime; // Maximum search time in milliseconds.
114  uint MinDepthCheckTime; // will not check time before this depth is reached
115  bool Debug; // If true, print debug info to stdout.
116  bool PostInfo; // If true, print post info to stdout.
117  bool XBoardMode; // If true, print info in xboard format.
118  bool Pruning; // If true, do futility pruning.
119 #ifndef WINCE
120  FILE * LogFile; // Output is to stdout and to this file.
121 #endif
122  uint QNodeCount; // Nodes examined in quiescent search.
123  uint NodeCount; // Nodes examined in total.
124  Timer Elapsed; // Timer for interrupting search.
125  bool IsOutOfTime; // Becomes true when search is out of time.
126  uint Ply; // Current ply being examined.
127  bool EasyMove; // True if the search indicates one move is
128  // far better than the others.
129  bool HardMove; // True if failed low at root on current depth.
130  uint InNullMove; // If > 0, in null move search so no PV updates.
131  uint RepStackSize; // Repetition stack size.
132  repeatT RepStack [1024]; // Repetition stack.
133  bool InCheck [ENGINE_MAX_PLY]; // In-check at each ply.
134  principalVarT PV [ENGINE_MAX_PLY]; // Principal variation at each ply.
135  simpleMoveT KillerMove [ENGINE_MAX_PLY][2]; // Two killer moves per ply.
136  int History[16][64]; // Success history of piece-to-square moves.
137  byte TranTableSequence; // Transposition table sequence number.
138  uint TranTableSize; // Number of Transposition table entries.
139  transTableEntryT * TranTable; // Transposition table.
140  uint PawnTableSize; // Number of Pawn structure table entries.
141  pawnTableEntryT * PawnTable; // Pawn structure score hash table.
142  bool (*CallbackFunction)(Engine *, void *); // Periodic callback.
143  void * CallbackData;
144  simpleMoveT * GameMoves [1024];
145  uint NumGameMoves;
146 
147 private:
148  int PieceValue (pieceT piece);
149  int SearchRoot (int depth, int alpha, int beta, MoveList * mlist);
150  int Search (int depth, int alpha, int beta, bool tryNullMove);
151  int Quiesce (int alpha, int beta);
152  int SEE (squareT from, squareT to);
153  void ScoreMoves (MoveList * mlist);
154  inline void DoMove (simpleMoveT * sm);
155  inline void UndoMove (simpleMoveT * sm);
156  inline void SetPVLength (void);
157  inline void UpdatePV (simpleMoveT * sm);
158  void Output (const char * format, ...);
159  void PrintPV (uint depth, int score) { PrintPV (depth, score, ""); }
160  void PrintPV (uint depth, int score, const char * annotation);
161  inline void PushRepeat (Position * pos);
162  inline void PopRepeat (void);
163  void StoreHash (int depth, scoreFlagT flag, int score,
164  simpleMoveT * bestmove, bool isOnlyMove);
165  scoreFlagT ProbeHash (int depth, int * score, simpleMoveT * bestMove, bool * isOnlyMove);
166 
167  inline void ClearKillerMoves (void);
168  inline void AddKillerMove (simpleMoveT * sm);
169  inline bool IsKillerMove (simpleMoveT * sm);
170 
171  inline void ClearHistoryValues (void);
172  inline void HalveHistoryValues (void);
173  inline void IncHistoryValue (simpleMoveT * sm, int increment);
174  inline int GetHistoryValue (simpleMoveT * sm);
175 
176  int Score (int alpha, int beta);
177  inline int ScoreWhiteMaterial (void);
178  inline int ScoreBlackMaterial (void);
179  void ScorePawnStructure (pawnTableEntryT * pawnEntry);
180  bool IsMatingScore (int score);
181  bool IsGettingMatedScore (int score);
182 
183  bool OutOfTime (void);
184  void AdjustTime (bool easyMove);
185 
186 public:
187  Engine() {
188  MaxDepth = ENGINE_MAX_PLY; // A large default search depth
189  SearchTime = 1000; // Default search time: 1000 ms = one second.
190  MinSearchTime = MaxSearchTime = SearchTime;
191  MinDepthCheckTime = 4; // will not check time until depth is at least of this value
192 #ifndef WINCE
193  LogFile = NULL;
194 #endif
195  Debug = false;
196  PostInfo = false;
197  XBoardMode = false;
198  Pruning = false;
199  RepStackSize = 0;
200  TranTable = NULL;
201  TranTableSize = 0;
202  TranTableSequence = 0;
203  PawnTable = NULL;
204  PawnTableSize = 0;
205  SetHashTableKilobytes (ENGINE_HASH_KB);
206  SetPawnTableKilobytes (ENGINE_PAWN_KB);
207  CallbackFunction = NULL;
208  NumGameMoves = 0;
209  RootPos.StdStart();
210  Pos.StdStart();
211  PV[0].length = 0;
212  }
213 #ifdef WINCE
214  ~Engine() { my_Tcl_Free((char*) TranTable); my_Tcl_Free((char*) PawnTable); }
215 #else
216  ~Engine() { delete[] TranTable; delete[] PawnTable; }
217 #endif
218  void SetSearchDepth (uint ply) {
219  if (ply < 1) { ply = 1; }
220  if (ply > ENGINE_MAX_PLY) { ply = ENGINE_MAX_PLY; }
221  MaxDepth = ply;
222  }
223  void SetSearchTime (uint ms) {
224  MinSearchTime = SearchTime = MaxSearchTime = ms;
225  }
226  void SetSearchTime (uint min, uint ms, uint max) {
227  MinSearchTime = min;
228  SearchTime = ms;
229  MaxSearchTime = max;
230  }
232  MinDepthCheckTime = depth;
233  }
234  void SetDebug (bool b) { Debug = b; }
235  void SetPostMode (bool b) { PostInfo = b; }
236  bool InPostMode (void) { return PostInfo; }
237  void SetXBoardMode (bool b) { XBoardMode = b; }
238  bool InXBoardMode (void) { return XBoardMode; }
239  void SetPruning (bool b) { Pruning = b; }
240 #ifndef WINCE
241  void SetLogFile (FILE * fp) { LogFile = fp; }
242 #endif
243  void SetHashTableKilobytes (uint sizeKB);
244  void SetPawnTableKilobytes (uint sizeKB);
245  uint NumHashTableEntries (void) { return TranTableSize; }
246  uint NumPawnTableEntries (void) { return PawnTableSize; }
247  void ClearHashTable (void);
248  void ClearPawnTable (void);
249  void ClearHashTables (void) {
250  ClearHashTable();
251  ClearPawnTable();
252  }
253 
254  void SetCallbackFunction (bool (*fn)(Engine *, void *), void * data) {
255  CallbackFunction = fn;
256  CallbackData = data;
257  }
258 
259  uint GetNodeCount (void) { return NodeCount; }
260 
261  bool NoMatingMaterial (void);
262  bool FiftyMoveDraw (void);
263  uint RepeatedPosition (void);
264 
265  void SetPosition (Position * pos);
266  Position * GetPosition (void) { return &RootPos; }
267  void PlayMove (simpleMoveT * move);
268  void RetractMove (void);
269  int Score (void);
270  int ScoreMaterial (void);
271  principalVarT * GetPV (void) { return &(PV[0]); }
272  uint PerfTest (uint depth);
273  uint ElapsedTime (void) { return Elapsed.MilliSecs(); }
274  int Think (MoveList * mlist);
275 };
276 
277 
278 inline void
279 Engine::SetPVLength (void)
280 {
281  if (Ply < ENGINE_MAX_PLY - 1) {PV[Ply].length = Ply; }
282 }
283 
284 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
285 // Engine::UpdatePV
286 // Updates the principal variation at the current Ply to
287 // include the specified move.
288 inline void
289 Engine::UpdatePV (simpleMoveT * sm)
290 {
291  if (Ply >= ENGINE_MAX_PLY - 1) { return; }
292  if (InNullMove > 0) { return; }
293  // if (! Pos.IsLegalMove (sm)) { return; }
294 
295  PV[Ply].move[Ply] = *sm;
296  for (uint j = Ply + 1; j < PV[Ply + 1].length; j++) {
297  PV[Ply].move[j] = PV[Ply+1].move[j];
298  }
299  PV[Ply].length = PV[Ply+1].length;
300 }
301 
302 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
303 // Killer moves:
304 // We keep track of two "killer" moves at each ply, moves which
305 // are not captures or promotions (as they get ordered first) but
306 // were good enough to cause a beta cutoff. Killer moves get
307 // ordered after good captures but before non-killer noncaptures,
308 // which are ordered using the history table (see below).
309 //
310 // Only noncaptures and non-promotion moves can be killer moves, but
311 // we make an exception for those that have a negative score (meaning
312 // they lose material according to the static exchange evaluator),
313 // since they would otherwise be searched last after all noncaptures.
314 
315 inline void
316 Engine::ClearKillerMoves (void)
317 {
318  for (uint i=0; i < ENGINE_MAX_PLY; i++) {
319  KillerMove[i][0].from = NULL_SQUARE;
320  KillerMove[i][1].from = NULL_SQUARE;
321  }
322 }
323 
324 inline void
325 Engine::AddKillerMove (simpleMoveT * sm)
326 {
327  if (sm->capturedPiece != EMPTY && sm->score >= 0) { return; }
328  if (sm->promote != EMPTY && sm->score >= 0) { return; }
329  simpleMoveT * killer0 = &(KillerMove[Ply][0]);
330  simpleMoveT * killer1 = &(KillerMove[Ply][1]);
331  if (killer0->from == sm->from && killer0->to == sm->to
332  && killer0->movingPiece == sm->movingPiece) {
333  return;
334  }
335  *killer1 = *killer0;
336  *killer0 = *sm;
337 }
338 
339 inline bool
340 Engine::IsKillerMove (simpleMoveT * sm)
341 {
342  simpleMoveT * killer0 = &(KillerMove[Ply][0]);
343  if (killer0->from == sm->from && killer0->to == sm->to
344  && killer0->movingPiece == sm->movingPiece) {
345  return true;
346  }
347  simpleMoveT * killer1 = &(KillerMove[Ply][1]);
348  if (killer1->from == sm->from && killer1->to == sm->to
349  && killer1->movingPiece == sm->movingPiece) {
350  return true;
351  }
352  return false;
353 }
354 
355 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
356 // History table:
357 // This is a table of values indexed by moving piece and
358 // target square, indicating the historical success of each move
359 // as measured by the frequency of "good" (better than alpha)
360 // scores. It is used to order non-capture moves after killers.
361 
362 inline void
363 Engine::ClearHistoryValues (void)
364 {
365  for (pieceT p = WK; p <= BP; p++) {
366  for (squareT to = A1; to <= H8; to++) {
367  History[p][to] = 0;
368  }
369  }
370 }
371 
372 inline void
373 Engine::HalveHistoryValues (void)
374 {
375  // Output("# Halving history values\n");
376  for (pieceT p = WK; p <= BP; p++) {
377  for (squareT to = A1; to <= H8; to++) {
378  History[p][to] /= 2;
379  }
380  }
381 }
382 
383 inline void
384 Engine::IncHistoryValue (simpleMoveT * sm, int increment)
385 {
386  if (sm->capturedPiece != EMPTY && sm->score >= 0) { return; }
387  if (sm->promote != EMPTY && sm->score >= 0) { return; }
388  pieceT p = sm->movingPiece;
389  squareT to = sm->to;
390  ASSERT (p <= BP && to <= H8);
391  History[p][to] += increment;
392  // Halve all history values if this one gets too large, to avoid
393  // non-capture moves getting searched before captures:
394  if (History[p][to] >= ENGINE_MAX_HISTORY) {
395  HalveHistoryValues();
396  }
397 }
398 
399 inline int
400 Engine::GetHistoryValue (simpleMoveT * sm)
401 {
402  pieceT p = sm->movingPiece;
403  squareT to = sm->to;
404  ASSERT (p <= BP && to <= H8);
405  return History[p][to];
406 }
407 
408 #endif // SCID_ENGINE_H
409 
410 //////////////////////////////////////////////////////////////////////
411 // EOF: engine.h
412 //////////////////////////////////////////////////////////////////////
const pieceT WK
Definition: common.h:236
unsigned char byte
Definition: common.h:97
piecew sq
Definition: board.tcl:1293
Definition: timer.h:51
void SetSearchDepth(uint ply)
Definition: engine.h:218
void SetPruning(bool b)
Definition: engine.h:239
const squareT NULL_SQUARE
Definition: common.h:352
uint max(int a, int b)
Definition: crosstab.cpp:237
uint sig
Definition: engine.h:81
#define ASSERT(f)
Definition: common.h:67
principalVarT * GetPV(void)
Definition: engine.h:271
squareT enpassant
Definition: engine.h:72
const pieceT BP
Definition: common.h:237
const uint ENGINE_MAX_PLY
Definition: engine.h:30
const scoreFlagT SCORE_LOWER
Definition: engine.h:53
const int ENGINE_MAX_HISTORY
Definition: engine.h:31
void SetCallbackFunction(bool(*fn)(Engine *, void *), void *data)
Definition: engine.h:254
byte depth
Definition: engine.h:69
byte flags
Definition: engine.h:70
~Engine()
Definition: engine.h:216
Position * GetPosition(void)
Definition: engine.h:266
short wShortbLongScore
Definition: engine.h:84
const squareT A1
Definition: common.h:343
const uint ENGINE_PAWN_KB
Definition: engine.h:34
simpleMoveT move[ENGINE_MAX_PLY]
Definition: engine.h:42
byte sequence
Definition: engine.h:71
int MilliSecs()
Definition: timer.h:60
const int ENGINE_HASH_SCORE
Definition: engine.h:32
const pieceT EMPTY
Definition: common.h:234
uint32_t uint
Definition: common.h:99
uint pawnhash
Definition: engine.h:80
Definition: move.tcl:20
Definition: engine.h:64
void StdStart()
Definition: position.h:145
short score
Definition: engine.h:67
const squareT H8
Definition: common.h:350
uint ElapsedTime(void)
Definition: engine.h:273
short score
Definition: engine.h:82
void SetSearchTime(uint min, uint ms, uint max)
Definition: engine.h:226
void SetXBoardMode(bool b)
Definition: engine.h:237
colorT stm
Definition: engine.h:98
void SetMinDepthCheckTime(uint depth)
Definition: engine.h:231
uint GetNodeCount(void)
Definition: engine.h:259
bool InXBoardMode(void)
Definition: engine.h:238
uint pawnhash
Definition: engine.h:66
const scoreFlagT SCORE_NONE
Definition: engine.h:51
byte scoreFlagT
Definition: engine.h:49
short wLongbShortScore
Definition: engine.h:83
squareT to
Definition: movelist.h:40
const uint ENGINE_HASH_KB
Definition: engine.h:33
uint NumHashTableEntries(void)
Definition: engine.h:245
uint16_t ushort
Definition: common.h:98
uint npieces
Definition: engine.h:97
void SetLogFile(FILE *fp)
Definition: engine.h:241
squareT from
Definition: movelist.h:39
const scoreFlagT SCORE_EXACT
Definition: engine.h:52
uint NumPawnTableEntries(void)
Definition: engine.h:246
pieceT capturedPiece
Definition: movelist.h:42
uint hash
Definition: engine.h:95
uint length
Definition: engine.h:41
bool InPostMode(void)
Definition: engine.h:236
void SetDebug(bool b)
Definition: engine.h:234
const scoreFlagT SCORE_UPPER
Definition: engine.h:54
ushort bestMove
Definition: engine.h:68
uint pawnhash
Definition: engine.h:96
byte colorT
Definition: common.h:112
void SetSearchTime(uint ms)
Definition: engine.h:223
Engine()
Definition: engine.h:187
Definition: engine.h:94
int32_t score
Definition: movelist.h:49
uint hash
Definition: engine.h:65
pieceT movingPiece
Definition: movelist.h:38
void ClearHashTables(void)
Definition: engine.h:249
Definition: engine.h:106
Definition: engine.h:79
pieceT promote
Definition: movelist.h:43
byte squareT
Definition: common.h:113
byte pieceT
Definition: common.h:111
void SetPostMode(bool b)
Definition: engine.h:235