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