1
//////////////////////////////////////////////////////////////////////
6
// Part of: Scid (Shane's Chess Information Database)
9
// Notice: Copyright (c) 2002-2003 Shane Hudson. All rights reserved.
11
// Author: Shane Hudson (sgh@users.sourceforge.net)
13
//////////////////////////////////////////////////////////////////////
15
// The Engine class provides a simple chess position evaluator
16
// based on negamax with quiescent search and alpha/beta pruning.
17
// It is used in Scid for doing small quick searches to determine
18
// which of the possible legal moves to or from a particular square
19
// to suggest as the best move for faster mouse input.
21
#ifndef SCID_GUESSENGINE_H
22
#define SCID_GUESSENGINE_H
28
#if (QT_VERSION < QT_VERSION_CHECK(4, 7, 0))
30
typedef QTime QElapsedTimer;
32
#include <QElapsedTimer>
38
const unsigned int ENGINE_MAX_PLY = 40; // Maximum search ply.
39
const int ENGINE_MAX_HISTORY = 100000; // Max accumulated history value.
40
const int ENGINE_HASH_SCORE = 100000000; // To order hash moves first.
41
const unsigned int ENGINE_HASH_KB = 32; // Default hash table size in KB.
42
const unsigned int ENGINE_PAWN_KB = 1; // Default pawn table size in KB.
44
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~
46
// Stores the principal variation at one search Ply depth.
51
simpleMoveT move [ENGINE_MAX_PLY];
54
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~
56
// Types of transposition table score and endgame recognition score.
58
typedef unsigned char scoreFlagT;
60
SCORE_NONE = 0, // Not a useful score.
61
SCORE_EXACT = 1, // Exact score.
62
SCORE_LOWER = 2, // Lower bound, real score could be higher.
63
SCORE_UPPER = 3; // Upper bound, real score could be lower.
65
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~
67
// Transposition table entry.
68
// Apart from the type flag, depth and score, it also stores the
69
// hash codes and other position values for safety checks to avoid
71
// The best move is also stored, in a compact format to save space.
73
struct transTableEntryT
75
unsigned int hash; // Hash value.
76
unsigned int pawnhash; // Pawn hash value, for extra safety check.
77
short score; // Evaluation score.
78
unsigned short bestMove; // Best move from/to/promote values.
79
unsigned char depth; // Depth of evaulation.
80
unsigned char flags; // Score type, side to move and castling flags.
81
unsigned char sequence; // Sequence number, for detecting old entries.
82
squareT enpassant; // En passant target square.
85
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~
87
// Pawn structure score hash table entry.
89
struct pawnTableEntryT
91
unsigned int pawnhash; // Pawn hash value for this pawn structure.
92
unsigned int sig; // Safety check value, to avoid false hits.
93
short score; // Positional score for pawn structure.
94
short wLongbShortScore; // Pawn storm score for wk on abc, bk on abc.
95
short wShortbLongScore; // Pawn storm score for wk on fgh, bk on fgh.
96
unsigned char fyleHasPassers[2]; // One bit per file, indicating passed pawns.
99
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~
101
// Repetition-detection stack entry.
102
// An entry is pushed onto the stack when a move is made, and
103
// popped off when the move is unmade.
107
unsigned int hash; // Position hash code.
108
unsigned int pawnhash; // Position pawn-structure hash code.
109
unsigned int npieces; // Total number of pieces in position.
110
colorT stm; // Side to move.
114
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~
116
// Class representing a chess engine.
121
Position RootPos; // Position at start of search.
122
Position Pos; // Current position in search.
123
unsigned int MaxDepth; // Search depth limit.
124
int SearchTime; // Search time limit in milliseconds.
125
int MinSearchTime; // Minimum search time in milliseconds.
126
int MaxSearchTime; // Maximum search time in milliseconds.
127
bool Debug; // If true, print debug info to stdout.
128
bool PostInfo; // If true, print post info to stdout.
129
bool XBoardMode; // If true, print info in xboard format.
130
bool Pruning; // If true, do futility pruning.
131
FILE * LogFile; // Output is to stdout and to this file.
133
unsigned int QNodeCount; // Nodes examined in quiescent search.
134
unsigned int NodeCount; // Nodes examined in total.
135
QElapsedTimer Elapsed; // Timer for interrupting search.
136
bool IsOutOfTime; // Becomes true when search is out of time.
137
unsigned int Ply; // Current ply being examined.
138
bool EasyMove; // True if the search indicates one move is
139
// far better than the others.
140
bool HardMove; // True if failed low at root on current depth.
141
unsigned int InNullMove; // If > 0, in null move search so no PV updates.
142
unsigned int RepStackSize; // Repetition stack size.
143
repeatT RepStack [1024]; // Repetition stack.
144
bool InCheck [ENGINE_MAX_PLY]; // In-check at each ply.
145
principalVarT PV [ENGINE_MAX_PLY]; // Principal variation at each ply.
146
simpleMoveT KillerMove [ENGINE_MAX_PLY][2]; // Two killer moves per ply.
147
int History[16][64]; // Success history of piece-to-square moves.
148
unsigned char TranTableSequence; // Transposition table sequence number.
149
unsigned int TranTableSize; // Number of Transposition table entries.
150
transTableEntryT * TranTable; // Transposition table.
151
unsigned int PawnTableSize; // Number of Pawn structure table entries.
152
pawnTableEntryT * PawnTable; // Pawn structure score hash table.
153
bool (*CallbackFunction)(Engine *, void *); // Periodic callback.
155
simpleMoveT * GameMoves [1024];
156
unsigned int NumGameMoves;
159
int PieceValue(pieceT piece);
160
int SearchRoot(int depth, int alpha, int beta, MoveList * mlist);
161
int Search(int depth, int alpha, int beta, bool tryNullMove);
162
int Quiesce(int alpha, int beta);
163
int SEE(squareT from, squareT to);
164
void ScoreMoves(MoveList * mlist);
165
inline void DoMove(simpleMoveT * sm);
166
inline void UndoMove(simpleMoveT * sm);
167
inline void SetPVLength(void);
168
inline void UpdatePV(simpleMoveT * sm);
169
void Output(const char * format, ...);
170
void PrintPV(unsigned int depth, int score)
172
PrintPV(depth, score, "");
174
void PrintPV(unsigned int depth, int score, const char * annotation);
175
inline void PushRepeat(Position * pos);
176
inline void PopRepeat(void);
177
void StoreHash(int depth, scoreFlagT flag, int score,
178
simpleMoveT * bestmove, bool isOnlyMove);
179
scoreFlagT ProbeHash(int depth, int * score, simpleMoveT * bestMove, bool * isOnlyMove);
181
inline void ClearKillerMoves(void);
182
inline void AddKillerMove(simpleMoveT * sm);
183
inline bool IsKillerMove(simpleMoveT * sm);
185
inline void ClearHistoryValues(void);
186
inline void HalveHistoryValues(void);
187
inline void IncHistoryValue(simpleMoveT * sm, int increment);
188
inline int GetHistoryValue(simpleMoveT * sm);
190
int Score(int alpha, int beta);
191
inline int ScoreWhiteMaterial(void);
192
inline int ScoreBlackMaterial(void);
193
void ScorePawnStructure(pawnTableEntryT * pawnEntry);
194
bool IsMatingScore(int score);
195
bool IsGettingMatedScore(int score);
197
bool OutOfTime(void);
198
void AdjustTime(bool easyMove);
203
MaxDepth = ENGINE_MAX_PLY; // A large default search depth
204
SearchTime = 1000; // Default search time: 1000 ms = one second.
205
MinSearchTime = MaxSearchTime = SearchTime;
214
TranTableSequence = 0;
217
SetHashTableKilobytes(ENGINE_HASH_KB);
218
SetPawnTableKilobytes(ENGINE_PAWN_KB);
219
CallbackFunction = NULL;
231
void SetSearchDepth(unsigned int ply)
237
if(ply > ENGINE_MAX_PLY)
239
ply = ENGINE_MAX_PLY;
243
void SetSearchTime(unsigned int ms)
245
MinSearchTime = SearchTime = MaxSearchTime = ms;
247
void SetSearchTime(unsigned int min, unsigned int ms, unsigned int max)
253
void SetDebug(bool b)
257
void SetPostMode(bool b)
261
bool InPostMode(void)
265
void SetXBoardMode(bool b)
269
bool InXBoardMode(void)
273
void SetPruning(bool b)
277
void SetLogFile(FILE * fp)
281
void SetHashTableKilobytes(unsigned int sizeKB);
282
void SetPawnTableKilobytes(unsigned int sizeKB);
283
unsigned int NumHashTableEntries(void)
285
return TranTableSize;
287
unsigned int NumPawnTableEntries(void)
289
return PawnTableSize;
291
void ClearHashTable(void);
292
void ClearPawnTable(void);
293
void ClearHashTables(void)
299
void SetCallbackFunction(bool (*fn)(Engine *, void *), void * data)
301
CallbackFunction = fn;
305
unsigned int GetNodeCount(void)
310
bool NoMatingMaterial(void);
311
bool FiftyMoveDraw(void);
312
unsigned int RepeatedPosition(void);
314
void SetPosition(Position * pos);
315
Position * GetPosition(void)
319
void PlayMove(simpleMoveT * move);
320
void RetractMove(void);
322
int ScoreMaterial(void);
323
principalVarT * GetPV(void)
327
unsigned int PerfTest(unsigned int depth);
329
int Think(MoveList * mlist);
334
Engine::SetPVLength(void)
336
if(Ply < ENGINE_MAX_PLY - 1)
338
PV[Ply].length = Ply;
342
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~
344
// Updates the principal variation at the current Ply to
345
// include the specified move.
347
Engine::UpdatePV(simpleMoveT * sm)
349
if(Ply >= ENGINE_MAX_PLY - 1)
357
// if (! Pos.IsLegalMove (sm)) { return; }
359
PV[Ply].move[Ply] = *sm;
360
for(unsigned int j = Ply + 1; j < PV[Ply + 1].length; j++)
362
PV[Ply].move[j] = PV[Ply + 1].move[j];
364
PV[Ply].length = PV[Ply + 1].length;
367
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~
369
// We keep track of two "killer" moves at each ply, moves which
370
// are not captures or promotions (as they get ordered first) but
371
// were good enough to cause a beta cutoff. Killer moves get
372
// ordered after good captures but before non-killer noncaptures,
373
// which are ordered using the history table (see below).
375
// Only noncaptures and non-promotion moves can be killer moves, but
376
// we make an exception for those that have a negative score (meaning
377
// they lose material according to the static exchange evaluator),
378
// since they would otherwise be searched last after all noncaptures.
381
Engine::ClearKillerMoves(void)
383
for(unsigned int i = 0; i < ENGINE_MAX_PLY; i++)
385
KillerMove[i][0].from = NULL_SQUARE;
386
KillerMove[i][1].from = NULL_SQUARE;
391
Engine::AddKillerMove(simpleMoveT * sm)
393
if(sm->capturedPiece != EMPTY && sm->score >= 0)
397
if(sm->promote != EMPTY && sm->score >= 0)
401
simpleMoveT * killer0 = &(KillerMove[Ply][0]);
402
simpleMoveT * killer1 = &(KillerMove[Ply][1]);
403
if(killer0->from == sm->from && killer0->to == sm->to
404
&& killer0->movingPiece == sm->movingPiece)
413
Engine::IsKillerMove(simpleMoveT * sm)
415
simpleMoveT * killer0 = &(KillerMove[Ply][0]);
416
if(killer0->from == sm->from && killer0->to == sm->to
417
&& killer0->movingPiece == sm->movingPiece)
421
simpleMoveT * killer1 = &(KillerMove[Ply][1]);
422
if(killer1->from == sm->from && killer1->to == sm->to
423
&& killer1->movingPiece == sm->movingPiece)
430
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~
432
// This is a table of values indexed by moving piece and
433
// target square, indicating the historical success of each move
434
// as measured by the frequency of "good" (better than alpha)
435
// scores. It is used to order non-capture moves after killers.
438
Engine::ClearHistoryValues(void)
440
for(pieceT p = WK; p <= BP; p++)
442
for(squareT to = A1; to <= H8; to++)
450
Engine::HalveHistoryValues(void)
452
// Output("# Halving history values\n");
453
for(pieceT p = WK; p <= BP; p++)
455
for(squareT to = A1; to <= H8; to++)
463
Engine::IncHistoryValue(simpleMoveT * sm, int increment)
465
if(sm->capturedPiece != EMPTY && sm->score >= 0)
469
if(sm->promote != EMPTY && sm->score >= 0)
473
pieceT p = sm->movingPiece;
475
ASSERT(p <= BP && to <= H8);
476
History[p][to] += increment;
477
// Halve all history values if this one gets too large, to avoid
478
// non-capture moves getting searched before captures:
479
if(History[p][to] >= ENGINE_MAX_HISTORY)
481
HalveHistoryValues();
486
Engine::GetHistoryValue(simpleMoveT * sm)
488
pieceT p = sm->movingPiece;
490
ASSERT(p <= BP && to <= H8);
491
return History[p][to];
494
} // End namespace Guess
496
#endif // SCID_ENGINE_H
498
//////////////////////////////////////////////////////////////////////
499
// EOF: guessengine.h
500
//////////////////////////////////////////////////////////////////////
added
removed
src/guess/guessengine.h
