I recently started making a chess engine. Currently I have a basic AB engine, with piece-square tables for evaluation but I have not jet added a q-search.The only move-ordering that I have is the order in which I decided to write my movegeneration(which is somewhat ordered).
When I added a TT to my engine, I observed a significant decrease in NPS, ranging from 60-80%, depending on the FEN and table size.The engine did improve overall however is such a substantial decrease in NPS normal? (I am not sure if I count NPS correctly, when a move is made on the board I count that new board-state as a node)
I have tested running my engine with the TT implimented, but making sure that all the lookups had the wrong key. This resulted in a similar reduction in NPS. I also tried making the TT very small(16 kB) the NPS reduction mostly dissapeared. Thus I assumed that the decrease in NPS was mostly related to fetching memory.
I tried mitigating this by prefetching the ttEntry, using _mm_prefetch, but this didn't help at all. The time between having the zobrist and reading the ttEntry is quite small, so I dont imagine that prefetching can even compensate for much. I also use magic bitboards for movegeneration, those take up quite some space, but then their seems to be no problem.
Am I correct to assume that the delay is likely due to the fetching of memory? Is it normal for fetching the TTentry to take this much time?
My TT implimentation is as follows. I have a big array of entries. These entries are 16 bytes in size.
Code: Select all
struct TTentry {
uint64_t key=0;
int eval=0;
/* Exact, this is the solution, regardless of alpha and beta.
LowerBound, My eval will be greater or equal to this.
Upperbound, My eval will be smaller or equal to this.*/
enum NodeType :uint8_t {NONE, EXACT, UPPER_BOUND, LOWER_BOUND}nodeType:2 = NONE;//0-3
uint8_t inCheck : 2 = 0;//0-3//unused
uint8_t padding_1 : 4 = 0;//unused
uint8_t depth : 6;//0-63
uint8_t padding_2 : 2 = 0;//unused
CompactMove bestMove{};
};
Code: Select all
Move bestMove = Move::NULL_MOVE();
const int initialAlpha = alpha;
TTentry& ttEntry = transpositionTable[board.zobristKey.key % transpositionTableSize];
if (ttEntry.key == board.zobristKey.key && ttEntry.nodeType != TTentry::NONE) {
if (ttEntry.depth >= depth) {
if (ttEntry.nodeType == TTentry::LOWER_BOUND) {
alpha = std::max(alpha,ttEntry.eval);
}if (ttEntry.nodeType == TTentry::UPPER_BOUND) {
beta = std::min(beta, ttEntry.eval);
}
if (ttEntry.nodeType == TTentry::EXACT || alpha>=beta)return ttEntry.eval;
}
bestMove = ttEntry.bestMove.toBoardMove(board);
}
..... search and evaluation .....
if (depth >= ttEntry.depth) {
ttEntry = TTentry{
.key = board.zobristKey.key,
.eval = alpha,
.nodeType = alpha >= beta ? TTentry::LOWER_BOUND : alpha > initialAlpha ? TTentry::EXACT : TTentry::UPPER_BOUND,
.depth = uint8_t(depth),
.bestMove = CompactMove(bestMove)
};
}