I just typed a much longer explanation of this, but the site keeps logging me out and making me do Cloudflare captchas and I lost it trying to submit it. My transposition tables are slowing down the chess engine I'm working on. I've hacked them into the perft test to be sure they are the problem. Sure enough, the perft test to depth of 6 takes three times longer with the transposition tables than without them. And the result is wrong. I've tested to ensure that my board is keeping the zorbist keys accurate as it makes and unmakes moves. So I don't think that's the problem.
I've attached what I believe to be the relevant code below. If anyone sees any glaring errors that would cause slowdowns and inaccuracies, I'd love to hear about them.
Code: Select all
typedef struct {
Key key; // 64-bits
Move best_move; // 32-bits
Score score; // 16-bits
Depth depth; // 8-bits
NodeInfo node_info; // 8-bits
} TTEntry;
typedef struct {
TTEntry age_bucket;
TTEntry depth_bucket;
} TTBucket;
TTEntry *TTable::GetEntry(uint64_t hash)
{
int index = hash & hash_mask;
if (table[index].age_bucket.key == hash)
return &table[index].age_bucket;
else if (table[index].depth_bucket.key == hash)
return &table[index].depth_bucket;
else
return nullptr;
}
void TTable::StoreEntry(uint64_t hash, Move best_move, Score score, Depth depth, NodeInfo node_type)
{
int index = hash & hash_mask;
TTBucket& bucket = table[index];
if (depth >= bucket.depth_bucket.depth || generation != GetNodeGeneration(bucket.depth_bucket.node_info))
{
TTEntry *entry = &bucket.depth_bucket;
entry->key = hash;
entry->best_move = best_move;
entry->score = score;
entry->depth = depth;
entry->node_info = SetNodeType(entry->node_info, node_type);
entry->node_info = SetNodeGeneration(entry->node_info, generation);
} else {
TTEntry *entry = &bucket.age_bucket;
entry->key = hash;
entry->best_move = best_move;
entry->score = score;
entry->depth = depth;
entry->node_info = SetNodeType(entry->node_info, node_type);
entry->node_info = SetNodeGeneration(entry->node_info, generation);
}
}
uint64_t Game::Perft(int depth)
{
TTEntry* entry = t_table->GetEntry(board.key);
if (entry != nullptr && entry->depth >= depth)
{
return entry->score;
}
MoveList move_list;
uint64_t nodes = 0;
if (depth == 0)
return 1ull;
move_list = board.GeneratePseudoLegalMoves();
for (auto move_info : move_list)
{
board.MakeMove(move_info.move);
if (!board.IllegalMove())
{
nodes += Perft(depth-1);
}
board.UnmakeMove(move_info.move);
}
t_table->StoreEntry(board.key, nodes, nodes, depth, nodes);
return nodes;
}
void Game::DividedPerft(int depth)
{
MoveList move_list;
nodes_searched = 0;
move_list = board.GeneratePseudoLegalMoves();
auto start1 = std::chrono::high_resolution_clock::now();
for (auto move_info : move_list)
{
board.MakeMove(move_info.move);
if (!board.IllegalMove())
{
uint64_t move_nodes = Perft(depth-1);
nodes_searched += move_nodes;
std::cout << BuildUCIMove(move_info.move) << " " << move_nodes << "\n";
}
board.UnmakeMove(move_info.move);
}
auto finish1 = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> elapsed = finish1 - start1;
std::cout << "\nNodes searched: " << nodes_searched << " \n";
std::cout << "Time taken: " << elapsed.count() << " \n\n";
}
