Existing implementations with std::stack or enum state machinery have a high overhead. Here simple backing arrays with clearly defined limits are used. This performs the same as recursion - and on systems with slow function calls, it is faster.
One path of the game tree with all siblings along the path exist in memory free for query at any point in time. By storing the stack size as a pointer into the stack array a lot of pointer arithmetic can be skipped.
I needed this for profiling since recursion may throw off the profiler - or the function call overhead becomes higher than the function cost and recursive functions cannot be inlined (for non tail recursion that is).
This solves all these issues and can work with any Board structure or Movegen
This function does not need make - unmake to work - nor do you need to clean up any arrays before calling this function.
Code: Select all
constexpr int max_depth = 7;
constexpr int max_moves = 128;
static Board* movestack[max_depth];
static Board* endptr[max_depth];
uint64_t perft(const char* fen, int max_depth)
{
if (max_depth <= 0) return 1;
const int max_idx = max_depth - 1;
Board b = set_brd(fen);
endptr[0] = get_moves(b, movestack[0]); //We skip a layer where we only push in the position. -> first move is filled in
uint64_t node_count = 0;
int depth = 0;
while (depth >= 0) {
//Max depth
if (depth == max_idx) {
node_count += endptr[max_idx] - movestack[max_idx];
endptr[max_idx] = movestack[max_idx];
depth--;
}
//Enumerated all moves?
else if (endptr[depth] == movestack[depth]) {
depth--;
}
//Get moves for last board in current depth - increase depth, decrease brd ptr => "stack pop"
else {
endptr[++depth] = get_moves(*(--endptr[depth]), movestack[depth + 1]);
}
}
return node_count;
}
Board* get_moves(const Board& brd, Board* mv)
{
//write all subsequent positions following current position
*mv++ = ...
*mv++ = ...
return mv;
}
void Init() {
for (int i = 0; i < max_depth; i++) {
movestack[i] = new Board[max_moves]();
}
}